* Luc Perthuis: > Hi all, > > I'm specially interested on finding a way to uniquely > identify rather small data chunks (less than or equal to > 128*1024 bytes in size) without using a byte per byte compare. > > 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), 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"). BTW, what is the use case? Calculating a hash takes much more computing power than a byte-to-byte compare, so I think any hash algorithm is worser than comparing (but of course using hashes can have advantages if the data is on different places or secret). And comparing 128*1024 bytes byte-per-byte is collision free :) > Unfortunately, I'd guess that the answer could be "no", but > among the experts on this list, I hope to catch a solid > proof, not only a guess. I think since any n-bit hash guarantees a collision after at least each (!) 2^n different input messages, using a n-bit and a m-bit hash guarantees a collision after at least each 2^(n+m) different input messages. > 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?). SHA-256 should be much stronger, would this be sufficient for your needs? Or SHA-512? oki, Steffen About Ingenico: Ingenico is a leading provider of payment, transaction and business solutions, with over 15 million terminals deployed in more than 125 countries. Over 3,000 employees worldwide support merchants, banks and service providers to optimize and secure their electronic payments solutions, develop their offer of services and increase their point of sales revenue. http://www.ingenico.com/. This message may contain confidential and/or privileged information. If you are not the addressee or authorized to receive this for the addressee, you must not use, copy, disclose or take any action based on this message or any information herein. If you have received this message in error, please advise the sender immediately by reply e-mail and delete this message. Thank you for your cooperation. P Please consider the environment before printing this e-mail ______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List [email protected] Automated List Manager [email protected]
