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?
3
-
$\begingroup$ What do you mean with "power of ripemd-160"? $\endgroup$– SEJPMMay 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. CanMay 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$– SEJPMMay 16, 2017 at 12:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
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$– ponchoMay 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$– LeryMay 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$– ponchoMay 18, 2017 at 2:28