4 ms·

This is a very old writeup (2007, revised 2009) and one of the things that it misses is the difference between pre-image resistance, second pre-image resistance

by tytso 13y ago

This is a very old writeup (2007, revised 2009) and one of the things that it misses is the difference between pre-image resistance, second pre-image resistance, and collision resistance. Yes, if you are using a 64-bit hash, it only takes 2^32 tries to find a collsion via the birthday paradox. This is a problem if you want to protect against random corruption. But an attacker who is trying to subvert a system generally wants to replace a specific node in a content-based addressing scheme. For example, they might want to replace a commit in a git tree. In order to do this, you need to be able to carry out a 2nd pre-image attack. That is, given a message m which hashes to h, you need to find another message m' which hashes to the same value. In this case, the birthday attack doesn't apply, because you can't just find any collsion --- you need to find a collision given a specific hash value. This is the difference between trying to find two people in a crowd that have the same birthday, and trying to find a single person in a crowd that has the same birthday as another, specific person in that crowd (say, May 14th). The latter is far more difficult than the former. So for example, even if git used MD5, for which a collision was demonstrated in 2005, a theoretical pre-image attack was only demonstrated in 2009, and even then it had a complexity of 2^123. So you could replace a file in a git tree with another, but it would require trying 2^123 different messages --- only slightly better than a brute force search. And even then, there is no guarantee that the replacement file would make any sense as a valid C file. And of course, git is not using MD5; it's using SHA-1. It's really unfortunate that Val's compare-by-hash paper doesn't go into this rather subtle point, because it causes people to get more excited than what the facts really warrant.

lambda 13y ago
Birthday attacks can work against content-based addressing schemes too. Sure, they may be a little bit harder (you need to convince someone to merge something that is able to carry a large random payload), but given that, say, the Linux kernel has a bunch of binary blob firmwares, it wouldn't be too hard for a hardware manufacturer to submit a driver for new hardware with one firmware, and then replace it with another later on. For a similar example, you may think that generating a CA signing certificate would involve a second preimage attack, as you would need to generate a certificate that had a hash that matched one of an existing CA. But it turns out that you only need a birthday attack, because you just need to submit a certificate for signing that is one of two that collide, where the second one is marked as being a CA cert. This has actually been done a with certificate authority that used MD5 for signing certificates.[1] There are lots of file formats that allow you to fairly easily create MD5 collisions, by virtue of being able to stick a random string that won't be interpreted somewhere in them.[2] If it were feasible to produce such a collision using SHA-1, anyone who got such a file merged in Git could then substitute it for an evil file and no one would be the wiser. That said, this attack does require the ability to generate a collision on SHA-1 (which has not yet been done), the ability to convince Linus (or a subsystem maintainer) to pull your tree containing a big binary blob, and that binary blob being able to do something harmful when substituted that it couldn't do just by virtue of being a difficult to audit binary blob (otherwise, why bother with the birthday attack when you could just subvert the blob anyhow). It's true that the writeup should distinguish between these cases, and contrast their difficulty, but you shouldn't be quite so quick to handwave away the possibility of collision attacks rather than second-preimage attacks. If I were to build a content-addressed storage system or design Git today, I'd probably use a SHA-2 or SHA-3 hash to be on the safe side. While no one has yet demonstrated a SHA-1 collision publicly, it's been substantially weakened; it just doesn't give a good enough security margin. Current estimate are that finding a collisions would cost about $2.7M in cloud computing time[3], and there are lots of adversaries who have well more than those kinds of resources. 1: http://www.win.tue.nl/hashclash/rogue-ca/ http://www.win.tue.nl/hashclash/rogue-ca/ 2: http://www.mscs.dal.ca/~selinger/md5collision/ http://www.mscs.dal.ca/~selinger/md5collision/ 3: https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html https://www.schneier.com/blog/archives/2012/10/when_will_we_...
- tytso 13y ago
  Fair point. Although it's important to note that not any collision attack would work. The collision attack still had to meet certain properties before it could be used to successfully attack x509 certificates. So the ability to use this to succesfully attack a git tree from a cryptographic perspective falls somewhere between a collision attack and a pre-image attack. Making the binary blob do something useful also assumes that you know enough about the firmware that you could figure out how to create a valid blob as well as a malicious blob. Very often with these binary blobs the low-level detail of the hardware is not generally available except to the manufacturer --- and if the manufacturer were malicious, they could insert the malware into the official firmware image (or to an update of the official firmware image) in the first place. Finally, the cost estimates in [3] are for a brute force birthday attack, which is definitely not going to be enough for the sort of replacement attack which you are describing. That being said, certainly if we were starting from scratch today, using a newer hash would probably be a good idea. But it's still true that there's a goodly distance from "we can generate a collision" to we can use that to attack a CBA system in real life.

by tytso 13y ago

lambda 13y ago

Birthday attacks can work against content-based addressing schemes too. Sure, they may be a little bit harder (you need to convince someone to merge something that is able to carry a large random payload), but given that, say, the Linux kernel has a bunch of binary blob firmwares, it wouldn't be too hard for a hardware manufacturer to submit a driver for new hardware with one firmware, and then replace it with another later on. For a similar example, you may think that generating a CA signing certificate would involve a second preimage attack, as you would need to generate a certificate that had a hash that matched one of an existing CA. But it turns out that you only need a birthday attack, because you just need to submit a certificate for signing that is one of two that collide, where the second one is marked as being a CA cert. This has actually been done a with certificate authority that used MD5 for signing certificates.[1] There are lots of file formats that allow you to fairly easily create MD5 collisions, by virtue of being able to stick a random string that won't be interpreted somewhere in them.[2] If it were feasible to produce such a collision using SHA-1, anyone who got such a file merged in Git could then substitute it for an evil file and no one would be the wiser. That said, this attack does require the ability to generate a collision on SHA-1 (which has not yet been done), the ability to convince Linus (or a subsystem maintainer) to pull your tree containing a big binary blob, and that binary blob being able to do something harmful when substituted that it couldn't do just by virtue of being a difficult to audit binary blob (otherwise, why bother with the birthday attack when you could just subvert the blob anyhow). It's true that the writeup should distinguish between these cases, and contrast their difficulty, but you shouldn't be quite so quick to handwave away the possibility of collision attacks rather than second-preimage attacks. If I were to build a content-addressed storage system or design Git today, I'd probably use a SHA-2 or SHA-3 hash to be on the safe side. While no one has yet demonstrated a SHA-1 collision publicly, it's been substantially weakened; it just doesn't give a good enough security margin. Current estimate are that finding a collisions would cost about $2.7M in cloud computing time[3], and there are lots of adversaries who have well more than those kinds of resources. 1: http://www.win.tue.nl/hashclash/rogue-ca/ http://www.win.tue.nl/hashclash/rogue-ca/ 2: http://www.mscs.dal.ca/~selinger/md5collision/ http://www.mscs.dal.ca/~selinger/md5collision/ 3: https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html https://www.schneier.com/blog/archives/2012/10/when_will_we_...

tytso 13y ago
Fair point. Although it's important to note that not any collision attack would work. The collision attack still had to meet certain properties before it could be used to successfully attack x509 certificates. So the ability to use this to succesfully attack a git tree from a cryptographic perspective falls somewhere between a collision attack and a pre-image attack. Making the binary blob do something useful also assumes that you know enough about the firmware that you could figure out how to create a valid blob as well as a malicious blob. Very often with these binary blobs the low-level detail of the hardware is not generally available except to the manufacturer --- and if the manufacturer were malicious, they could insert the malware into the official firmware image (or to an update of the official firmware image) in the first place. Finally, the cost estimates in [3] are for a brute force birthday attack, which is definitely not going to be enough for the sort of replacement attack which you are describing. That being said, certainly if we were starting from scratch today, using a newer hash would probably be a good idea. But it's still true that there's a goodly distance from "we can generate a collision" to we can use that to attack a CBA system in real life.