SHA-1 cracked

[Hal Finney]

Ian Grigg writes:
> Stefan Brands just posted on my blog (and I saw
> reference to this in other blogs, posted anon)
> saying that "it seems that Schneier forgot to
> mention that the paper has a footnote which
> says that the attack on full SHA-1 only works
> if some padding (which SHA-1 requires) is not
> done."
>
> http://www.financialcryptography.com/mt/archives/000355.html

First, that's not quite what it says.  According to what I have seen
the language is, in reference to a pair of collisions exhibited for a
weakened SHA, "Note that padding rules were not applied to the messages."

But that is irrelevant.  The padding for SHA, aka Merkle Damgard
strengthening, involves padding it up a a multiple of 512 bits, while
appending a 1 bit and a 64 bit length field.  If you have two messages
M and M' which collide without this padding, they must by definition be
a multiple of the block length.  So you add one extra block which is a 1
bit, all zeros, and then the length of M.  Now you have a legally padded
pair of SHA messages which collide.  In fact, you can add anything at
all after the blocks which collide (the same thing to both messages).
Once you have a collision it "stays collided" as long as the suffix
is identical.

None of the hashes exhibited by Wang et al at
http://eprint.iacr.org/2004/199.pdf have the padding!  That doesn't
matter.  They are still valid collisions and can be extended or padded
any way we want while retaining the colliding property.

Presumably the text in the footnote was a reference to this fact.
Don't try to interpret it as meaning that the attack won't work against SHA.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com