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$
3
  • $\begingroup$ What do you mean with "power of ripemd-160"? $\endgroup$
    – SEJPM
    Commented May 16, 2017 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
    Commented May 16, 2017 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
    Commented May 16, 2017 at 12:41

1 Answer 1

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.

$\endgroup$
3
  • 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
    Commented May 16, 2017 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
    Commented May 17, 2017 at 22:41
  • 3
    $\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
    Commented May 18, 2017 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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