2
$\begingroup$

Is there a way I can compute $2^{100}$th power of ripemd-160 of my string, just like I can do with square matrix powers? I.e. can I easily compute ripemd-160 large amount of times?

$\endgroup$
  • $\begingroup$ What do you mean with "power of ripemd-160"? $\endgroup$ – SEJPM May 16 '17 at 11:46
  • $\begingroup$ @SEJPM I mean its iterated application, I think of ripemd(ripemd(ripemd(x))) as of a 3d power of ripemd for example $\endgroup$ – A. Can May 16 '17 at 12:25
  • $\begingroup$ There's no (known) way to do this, because then you would be able to completely undermine the security of common iterated password hashes (if they use RIPMD). $\endgroup$ – SEJPM May 16 '17 at 12:41
0
$\begingroup$

The only way to do so with cryptographically secure hashes is to perform the actual computations... (i.e. this is not a feature any hash propose to the extent of my knowledge, nor will likely propose in the future.)

But this is not practically possible since if you were to perform such a feat, then you'd be able to perform a brute force collision search attack on a 200-bit hash... Since Ripemd-160 is only 160 bits, the complexity of such a brute force attack is only $2^{80}$ (without any optimization). This means that you would exceed the computing power needed for it.

For reference, SHA-1 was broken after a whooping $2^{63}$ operations, and it took the equivalent of 6,500 years of single-CPU computations or 110 years of single-GPU computations.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Actually, you could compute $\text{RipeMD-160}^{2^{100}}(X)$ in $O(2^{80})$ time; you'd run Pollard Rho to find $a, b$ with $\text{RipeMD-160}^a(X) = \text{RipeMD-160}^b(X)$; then simple math and some more hashes gives you the value $\text{RipeMD-160}^{2^{100}}(X)$. Doesn't change the point you're making... $\endgroup$ – poncho May 16 '17 at 14:44
  • $\begingroup$ Mhhh, I haven't considered this and I must confess I'm not entirely sure it would work for all $X$. You want to find a collision between two different powers and then decompose $2^{100}$ as a multiple of $a$ and $b$ plus a few hashes, right? So that you may get really close to $2^{100}$ at the cost of only a brute-force attack. Interesting. That being said, I wouldn't like to have to study the repartition of the different powers for all $X$. $\endgroup$ – Lery May 17 '17 at 22:41
  • 2
    $\begingroup$ Actually, it's a bit simpler than that; once you determine $a > b$ with $\text{R}^a(X) = \text{R}^b(X)$ (where $\text{R}$ is RipeMD, then you know $\text{R}^{b + k(a-b)}(X) = \text{R}^b(X)$ for all integers $k$. So, you pick the largest $k$ with $b + k(a - b) \le 2^{100}$, and then hash up from there. $\endgroup$ – poncho May 18 '17 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.