RE: Combining MD5 and SHA-1 to reduce collision probability
Hi, thank you for clarification, Dave! * Dave Thompson Friday, April 22, 2011 12:34 AM: 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. Just for sake of completeness I think it could be added (for the assumed intention of the OP's question) that there is no guarantee that two different messages have two different hashes, because the first two tested messages could have the same hash (of course with very very low probability). Could it even be possible that two messages shorter than n bit accidently have the same (strong n-bit) hash? 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 Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: Combining MD5 and SHA-1 to reduce collision probability
Thank you all for your valuable answers. On 22/04/2011 00:33, Dave Thompson wrote: *Accidental* (birthday) collision is about 264 for MD5 and about 280 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. To be honest, I've no particular need, I was just auditing someone else realization... -- Luc Perthuis, Team Leader, Backup and Restore Technologies luc.perth...@atempo.com T +33 (0)2 97 68 40 26 | M +33 (0)6 89 16 96 37 http://www.atempo.com Atempo | Data Management, Simplified. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
RE: Combining MD5 and SHA-1 to reduce collision probability
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 Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: Combining MD5 and SHA-1 to reduce collision probability
On 4/20/2011 1:18 AM, Luc Perthuis wrote: 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 ? Simply use a hash for which the probability of a collision (either accidental or malicious) is at least one order of magnitude lower than the probability of your most probable failure mode. IMO, SHA-512 has this characteristic, unless you plan on shielding your hardware from cosmic rays. There is no advantage to using two different algorithms and two huge disadvantages. First, the computation time will be greater. Second, the vulnerability risk is likely greater. It is expected, for example, to be harder to break a single 512-bit hash than to break two 256-bit hashes concurrently. The probability of an accidental collision should be the same -- so why do more work? 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 ;-) If you're willing to go to 288-bits, why not just use 512-bit SHA and truncate to 288 bits? That way, you don't have the known weaknesses of MD5 dragging you down and each bit 'pays its way'. DS __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
RE: Combining MD5 and SHA-1 to reduce collision probability
* 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 Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
