3 ms·

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 t

by 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 lambda 13y ago

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.