RE: Security team successfully cracks SSL using 200 PS3's and MD5 flaw.
That md5 has now been deprecated for awhile is certainly also true; and people should have definitely moved on by now. Then again, I just got yet another Debian DSA mail which has plaintext download links for new binaries. The integrity verification mechanism for said binaries is, you guessed it: PGP-signed md5sums. We still have a long way to go. :) – S -----Original Message----- From: Steven M. Bellovin <smb@cs.columbia.edu> Sent: Friday, January 02, 2009 15:07 To: Skywing <Skywing@valhallalegends.com> Cc: Deepak Jain <deepak@ai.net>; NANOG <nanog@nanog.org> Subject: Re: Security team successfully cracks SSL using 200 PS3's and MD5 flaw. On Fri, 2 Jan 2009 16:51:53 -0600 Skywing <Skywing@valhallalegends.com> wrote:
Of course, md5 *used* to be good crypto.
See http://www.cs.columbia.edu/~smb/blog/2008-12/2008-12-30.html for the links, but MD5 has been suspect for a very long time. Dobbertin found problems with it in 1996. The need for caution with it was not just knowable but known, and stated publicly. I'm sure others did so as well; I can only easily quote my own works. From the second edition of my Firewalls book, in 2003: Additionally, \i{SHA} has replaced \i{MD5}, as the latter appears to be weaker than previously believed. and Hints of weakness have shown up in MD5 and RIPEMD-160; cautious people will eschew them, though none of the attacks are of use against either function when used with HMAC\@. As of this writing, the \i{NIST} algorithm appears to be the best choice. For many purposes, the newer versions of SHA are better; these have block sizes ranging from 256 to 512 bits. Even if that were not enough, Wang et al presented the actual collisions in 2004. There have been many updates and patches to more or less everything since then... Yes -- if you pick something that's very weak, you can get caught by surprise. But modern algorithms don't fall all at once. I should add, of course, that if you use bad algorithms or bad protocols, it doesn't matter where you store the public key. When I said that the update problem was easier, what I was saying is that you're not relying on outside parties for verification of identity, etc., it's all your own data. --Steve Bellovin, http://www.cs.columbia.edu/~smb
Then again, I just got yet another Debian DSA mail which has plaintext download links for new binaries. The integrity verification mechanism for said binaries is, you guessed it: PGP-signed md5sums.
I can assure you that you will continue to receive these messages for a while (unless you unsubscribe from the relevant mailing lists). Our rationale is that in order to carry out currently known attacks on MD5, you need to create a twin of documents, one evil and one harmless. In Debian's case, we prepare the data we sign on our trusted infrastructure. If someone can sneak in an evil twin due to a breach, more direct means of attack are available. In practice, the download links themselves are the larger problem because users might use them without checking anything. Eventually, they will go away, together with the MD5 hashes. Newer versions of APT also use the SHA-256 checksums embedded in the Release and Packages files.
For me the MD5 hashes on file downloads are more valuable to ensure the package is accurate to a byte rather than to verify its authenticity or integrity. Wouldn't listing both SHA-1 and MD5 hashes for a file download assure almost complete confidence that the file is the original one? I don't think anyone has been able to create a duplicate file that generates the same SHA-1 *and* MD5 hashes as the original file. Frank -----Original Message----- From: Florian Weimer [mailto:fw@deneb.enyo.de] Sent: Saturday, January 03, 2009 10:23 AM To: Skywing Cc: NANOG Subject: Re: Security team successfully cracks SSL using 200 PS3's and MD5 flaw.
Then again, I just got yet another Debian DSA mail which has plaintext download links for new binaries. The integrity verification mechanism for said binaries is, you guessed it: PGP-signed md5sums.
I can assure you that you will continue to receive these messages for a while (unless you unsubscribe from the relevant mailing lists). Our rationale is that in order to carry out currently known attacks on MD5, you need to create a twin of documents, one evil and one harmless. In Debian's case, we prepare the data we sign on our trusted infrastructure. If someone can sneak in an evil twin due to a breach, more direct means of attack are available. In practice, the download links themselves are the larger problem because users might use them without checking anything. Eventually, they will go away, together with the MD5 hashes. Newer versions of APT also use the SHA-256 checksums embedded in the Release and Packages files.
On Jan 3, 2009, at 12:46 PM, Frank Bulk wrote:
For me the MD5 hashes on file downloads are more valuable to ensure the package is accurate to a byte rather than to verify its authenticity or integrity.
Wouldn't listing both SHA-1 and MD5 hashes for a file download assure almost complete confidence that the file is the original one? I don't think anyone has been able to create a duplicate file that generates the same SHA-1 *and* MD5 hashes as the original file.
I would not be too sure. MD5 only makes one pass over the data. Suppose that I find two messages, M1 and M2, that have the same MD5 hash - there are methods out there to do that. M1 is the good message, M2 is the bad message. Let "||" be the concatenation operator. So, for any string S M1||S and M2||S have the same MD5 hash. So, if I can find an S such that the SHA-1 hash for M1||S and M2||S are the same, the MD5 hashes for these messages will still be the same, and you have your feared condition. My understanding is that one type of collision search involves using an S and trying to find collisions of M1 and M2||S by varying S. Modifying this to a common S does not seem that different, and I would not want to bet a lot on it being fundamentally much more difficult. (It might be, it might not be, I have no idea, the question is, how much are you willing to bet on it ?) Regards Marshall Regards Marshall
Frank
-----Original Message----- From: Florian Weimer [mailto:fw@deneb.enyo.de] Sent: Saturday, January 03, 2009 10:23 AM To: Skywing Cc: NANOG Subject: Re: Security team successfully cracks SSL using 200 PS3's and MD5 flaw.
Then again, I just got yet another Debian DSA mail which has plaintext download links for new binaries. The integrity verification mechanism for said binaries is, you guessed it: PGP-signed md5sums.
I can assure you that you will continue to receive these messages for a while (unless you unsubscribe from the relevant mailing lists).
Our rationale is that in order to carry out currently known attacks on MD5, you need to create a twin of documents, one evil and one harmless. In Debian's case, we prepare the data we sign on our trusted infrastructure. If someone can sneak in an evil twin due to a breach, more direct means of attack are available.
In practice, the download links themselves are the larger problem because users might use them without checking anything. Eventually, they will go away, together with the MD5 hashes. Newer versions of APT also use the SHA-256 checksums embedded in the Release and Packages files.
* Frank Bulk:
For me the MD5 hashes on file downloads are more valuable to ensure the package is accurate to a byte rather than to verify its authenticity or integrity.
Indeed. I've experienced that first-hand: the hashes helped to isolate a case of faulty router memory at the ISP I used at home. (The TCP checksum is very weak and does not detect bit errors which occur at multiples of 16 bits. If the probability of such errors is so high that two of them occur in a single segment, they very likely cancel out, which was exactly what I observed in the issue mentioned above.)
Wouldn't listing both SHA-1 and MD5 hashes for a file download assure almost complete confidence that the file is the original one? I don't think anyone has been able to create a duplicate file that generates the same SHA-1 *and* MD5 hashes as the original file.
For most applications, it's better to include a totally random string at the beginning of the message, before signing it, and strip it upon signature verification (or encode it in a way so that it is simply ignored by the application). The convergent property of hash functions (if, by chance, two people come up independently with the same document, it hashes to the same value) is rarely needed. A random string near the beginning means that the attacker doesn't know the initial internal state of the hash function when the collision is constructed, which should make attacks involving evil twins much, much harder. I expect that at a not too distant point in the future (say, within the next ten years), strong hashes keyed in a such a way offer very significant performance gains over non-keyed, but still strong hashes, so that most protocols which do not rely on the convergence property will switch to them. Convergence might even turn out to be too costly, not just in terms of performance, but in security. (And I write this as a frequent Git user. 8-/)
On Sat, 03 Jan 2009 17:23:06 +0100, Florian Weimer said:
Our rationale is that in order to carry out currently known attacks on MD5, you need to create a twin of documents, one evil and one harmless. In Debian's case, we prepare the data we sign on our trusted infrastructure. If someone can sneak in an evil twin due to a breach, more direct means of attack are available.
More to the point - there are known easy ways for an attacker to generate *two* documents that have the same MD5 hash (the basis of this attack). However, the attacker has no control over what the actual value of that MD5 hash is. What's *not* still feasible is for an attacker to take Debian's data and the already-generated MD5 hash, and create a second file that hashes to that same already-known hash. At that point, it's probably easier to just attack the trusted infrastructure in an attempt to recover the GnuPG private key, and then just sign your evil replacement package. There's 2 advantages to this attack: 1) It doesn't *matter* if they PGP-sign the file with the MD5 hashes or if the file has SHA1 or SHA512 - the signature will look fine. 2) It's been proven doable to at least one major distro in the past few months.
participants (5)
-
Florian Weimer -
Frank Bulk -
Marshall Eubanks -
Skywing -
Valdis.Kletnieks＠vt.edu