> From: owner-openssl-us...@openssl.org On Behalf Of Steffen DETTMER > Sent: Wednesday, 20 April, 2011 12:25
> * Luc Perthuis: > > Is there any theoretical proof for a "good" selection of 2 > > HASH (computing the results of two different algorithms on > > the same data) that would annihilate the collision risk ? > > If the hash is shorter than possible arbitrary input message, > there will be a collision risk, because you cannot resolve > 2^n possible hashes back to more than 2^n possible messages > (even theoretically by using "brute force", this is impossible), Right. > so among 2^n+1 different messages, at least two of them must > have the same 2^n bit hash (actually half because of > birthday "attack"). > To be exact: for an n-bit or 2^n-value hash, with 2^n + 1 messages you are certain to have a collision. Because of the birthday paradox, with about 2^(n/2) random messages you are *likely* to have a collision. This is just a fact of nature; "attack" is used for actions by an intelligent adversary. > > NB: I've mentioned MD5 and SHA-1 in the subject, as they are > > the most used nowadays, but if this association doesn't fit > > the need whereas another does, that would be interesting anyway ;-) > > SHA-1 collision attack need 2^63. > Similar to MD5 (I guess ~ 2^64?). > There are *attacks* -- by an adversary who can control what you hash (particularly, for certificates, what a CA signs) -- on MD5 collisions that are small enough to be practical, and on SHA-1 that are close enough to worry about. *Accidental* (birthday) collision is about 2^64 for MD5 and about 2^80 for SHA-1. > SHA-256 should be much stronger, would this be sufficient > for your needs? Or SHA-512? > That's simpler and probably at least as good as a hybrid. It's still not an absolute guarantee, though. ______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List openssl-users@openssl.org Automated List Manager majord...@openssl.org
