Setting aside that this is a brute force attack on the hash rather than the key, only made possible because of dropped bits, the method here doesn't apply. It depends on there being no initial salt. All further iterations of sha1 can be salt free and still safe from this attack since you are not able to feed an arbitrary string into the key function.
Edit: Thinking about it I should be more specific, especially since I got confused myself for a moment. The key is that you don't salt the same way at each step. So a unique salt per iteration is great, salting the first iteration is fine, salting zero or all iterations with a particular salt ruins you.
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 couldn't be bothered to read the article entirely, but what he proposes at the end (iterating SHA) is likely broken:
https://groups.google.com/group/sci.crypt/msg/92fe3e4e1edf0d...
Setting aside that this is a brute force attack on the hash rather than the key, only made possible because of dropped bits, the method here doesn't apply. It depends on there being no initial salt. All further iterations of sha1 can be salt free and still safe from this attack since you are not able to feed an arbitrary string into the key function.
Edit: Thinking about it I should be more specific, especially since I got confused myself for a moment. The key is that you don't salt the same way at each step. So a unique salt per iteration is great, salting the first iteration is fine, salting zero or all iterations with a particular salt ruins you.
I think this is a different context where it does not make the attack harder. Our context is different AFAIK and the approach works.
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 :-)