What is to be said about pre-image resistance?

[Dan Kaminsky]

Ian,

    The Wang attack does nothing (yet) for second preimages.

    The best attack I know of against them refers is in Kelsey and
Schneier's "*Second Preimages on n-bit Hash Functions for Much Less than
2^n Work".*  It's at:  http://eprint.iacr.org/2004/304

    Once you cut through the verbiage, it's really pretty simple:  The
bigger a file, the more intermediate hashes there are inside of it.  The
more intermediate hashes, the more points there are to collide against. 
So, a 700MB CD image vs. a hash with a 512 bit blocksize will have
734,003,200 bytes / 64 bytes = 11,468,800 intermediate hashes that may
be collided against.  That's a little more than 2^23.  Against MD5,
you're looking at 2^105 for a CD; against SHA-1, you're looking at
2^137.  This is of course work that's far outside the range of
feasibility (and, in a small ahem to the paper, 2^60 byte messages are
equally ridiculous).

    You may say this isn't a true second preimage attack, because you
only acquire an intermediate collision.  But all intermediate collisions
can be appended to with legitimate data until they return to the correct
final hash state.  So you generate your malicious data, search for
random garbage that, when appended, equals one of the 11M potential
states, and then append the rest of the legitimate file from that point.

    MD Hardening, i.e. the conclusion of a data stream with its own
length, *does* create a problem though.  We cannot alter the final
length of the file, or the hash will fail.  So if we find an
intermediate collision at an earlier point in the file than our
malicious payload requires, we must discard it.  For large malicious
payloads (say, replacing one CD entirely with another), this eliminates
our attack window entirely.

    Of course, again, 2^105 work is ridiculous.

--Dan


Ian G wrote:

>
> Collision resistance of message digests is effected by the birthday
> paradox, but that does not effect pre-image resistance.  (correct?)
>
> So can we suggest that for pre-image resistance, the strength of
> the SHA-1 algorithm may have been reduced from 160 to 149?  Or can
> we make some statement like "reduced by some number of bits that may
> be related to 11?"
>
> Or is there no statement we can make?
>
> iang
>
> PS: There is a nice description (with a bad title) here for the
> amateurs like myself:
>
> http://www.k2crypt.com/sha1.html
>


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