# Computing the powers of hash (ripemd-160) function

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?

• What do you mean with "power of ripemd-160"? May 16, 2017 at 11:46
• @SEJPM I mean its iterated application, I think of ripemd(ripemd(ripemd(x))) as of a 3d power of ripemd for example May 16, 2017 at 12:25
• 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). May 16, 2017 at 12:41

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.
• 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... May 16, 2017 at 14:44
• 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$.
• 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. May 18, 2017 at 2:28