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 [EMAIL PROTECTED]