This is how it works. Here the attack they want to mount is the following: find another string, ANY string, that will hash to the same output, but only 32 bits of the output.
Since it is any string, it can also be a SHA1 itself. So what you do is to start with an "X" that can be ANY ANY value, even "foo". And you start doing:
x = SHA1(x)
x = SHA1(x)
... again and again ...
right? Well in the average case after 2^31 iterations you find a collision, right?
But the output 65536 iterations ago was it! The string that will output that specific 32 bit output after SHA1() nested 65536 times. So you want to go backward but it is not possible, SHA1 can't be inverted.
So what you do? You start again from "X" and stop exactly 65536 iterations before you found the wanted value.
Obviously doing 65536 more SHA1s of that string you get the previous output. So you found your string.
Why the original poster says that the attack takes 2x time but can even optimized? Since you can store the value of SHA1 at 10000 iterations, at 20000 and so forth. Then instead of re-running the iteration again you start from the nearest cached value.
Is it clear now? Otherwise please ask me and I'll be willing to help.
Edit: do you see that chat? This is the dogmatic approach we don't need. gcp found a random message on sci.crypt, and it used it as an universal proof that nested SHA1 is wrong (well he said "likely" actually). It may be wrong for other reasons perhaps, but not for this. First of all: try to understand what you read.
I think there's a fairly huge difference between pointing out an exact attack on the primitive you propose versus dogmatically rejecting it because it's not commonly used. For one, it's possible to have this discussion and arrive at an obvious conclusion (attack does not apply).
First of all: try to understand what you read
I didn't read your blog post, as I clearly stated at the beginning :-)
Comments
I guess the difference is that you're not actually interested in slowing down the generation of a collision, just that of a dictionary attack.
This is how it works. Here the attack they want to mount is the following: find another string, ANY string, that will hash to the same output, but only 32 bits of the output.
Since it is any string, it can also be a SHA1 itself. So what you do is to start with an "X" that can be ANY ANY value, even "foo". And you start doing:
right? Well in the average case after 2^31 iterations you find a collision, right?But the output 65536 iterations ago was it! The string that will output that specific 32 bit output after SHA1() nested 65536 times. So you want to go backward but it is not possible, SHA1 can't be inverted.
So what you do? You start again from "X" and stop exactly 65536 iterations before you found the wanted value.
Obviously doing 65536 more SHA1s of that string you get the previous output. So you found your string.
Why the original poster says that the attack takes 2x time but can even optimized? Since you can store the value of SHA1 at 10000 iterations, at 20000 and so forth. Then instead of re-running the iteration again you start from the nearest cached value.
Is it clear now? Otherwise please ask me and I'll be willing to help.
Edit: do you see that chat? This is the dogmatic approach we don't need. gcp found a random message on sci.crypt, and it used it as an universal proof that nested SHA1 is wrong (well he said "likely" actually). It may be wrong for other reasons perhaps, but not for this. First of all: try to understand what you read.
I think there's a fairly huge difference between pointing out an exact attack on the primitive you propose versus dogmatically rejecting it because it's not commonly used. For one, it's possible to have this discussion and arrive at an obvious conclusion (attack does not apply).
First of all: try to understand what you read
I didn't read your blog post, as I clearly stated at the beginning :-)