Re: [tahoe-dev] SHA-1 broken!
lance james lan...@securescience.net writes: stupid question - does this effect IPSec realistically as well? IPSec and IPSec related protocols like IKE use SHA-1 in various places. Whether those actually could be attacked using the known weaknesses in SHA-1 would require detailed examination of the individual protocols. In general, uses that require only preimage resistance are not yet at risk, those that require collision resistance are. However, as has been seen in the MD5-based fake CA attack, sufficiently clever people can sometimes come up with ways to turn something that appears to depend on preimage resistance into something that really only depends on collision resistance. This is all another way of saying no reason to panic, but moving to things that use SHA-2 instead of SHA-1 would be a good idea. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken!
Quoting Perry E. Metzger pe...@piermont.com: Ray Dillinger b...@sonic.net writes: I cannot derive a realistic threat model from the very general statements in the slides. (BTW, you mean threat, not threat *model*, in this instance.) As just one obvious example of a realistic threat, consider that there are CAs that will happily sell you certificates that use SHA-1. Various clever forgery attacks have been used against certs that use MD5, see: http://www.win.tue.nl/hashclash/rogue-ca/ Those attacks can now be extended to SHA-1 pretty easily. It might It is in my opinion way to early to jump to this kind of conclusions: Even if the new attack works are promised (and I have the feeling that people are too optimistic here), there is the following issue: * these advanced attacks against CAs do require a special type of collision attack (the name chosen-prefix attack was coined), not a normal collision attack we are talking about here for the case of SHA-1. A chosen-prefix attack can be expected to be significantly harder to perform than a normal attack. The link you provided should contain a more in-depth discussion on this for the case of MD5. Nevertheless, I agree that moving away from SHA-1 should be encouraged (since 2005). Best, Christian -- Christian Rechberger, Graz University of Technology, Austria. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken!
On Sat, May 2, 2009 at 12:33 PM, Perry E. Metzger pe...@piermont.com wrote: As just one obvious example of a realistic threat, consider that there are CAs that will happily sell you certificates that use SHA-1. Various clever forgery attacks have been used against certs that use MD5, see: http://www.win.tue.nl/hashclash/rogue-ca/ Those attacks can now be extended to SHA-1 pretty easily. It might require a bit of compute infrastructure -- say a lot of FPGAs and a bunch of cleverness -- to turn out certs quickly, but it can be done. Given that there are lots of high value certs out there of this form, this is rather dangerous. Off-the-shelf FPGA-based device that breaks DES by brute force in about a week, costs 9,000 euros: http://www.copacobana.org/ These are commercially available and programmable. Setting a few of them up to break SHA-1 certainly would not be trivial, but it looks feasible. The design of DES facilitates this kind of throughput/cost gains on FPGAs. Remember that the MD4 family (incl. SHA-1) was designed to be efficient on 32-bit CPUs. For these hash functions, it is much harder to get a throughput/cost gain on FPGAs compared to off-the-shelf CPUs. At least, this was my conclusion when I quickly looked into this a few years ago. Best, Christian -- Christian Rechberger, Graz University of Technology, Austria - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken!
On Sun, May 3, 2009 at 4:35 PM, Christian Rechberger christian.rechber...@tugraz.at wrote: The design of DES facilitates this kind of throughput/cost gains on FPGAs. Remember that the MD4 family (incl. SHA-1) was designed to be efficient on 32-bit CPUs. For these hash functions, it is much harder to get a throughput/cost gain on FPGAs compared to off-the-shelf CPUs. At least, this was my conclusion when I quickly looked into this a few years ago. The n...@home project(http://nsa.unaligned.org/) seems to do it pretty well. He even provides the optimized SHA-1 and MD5 Verilog code used. This only works because straight-up bruteforce requires little memory, though. If the new SHA-1 break requires significant memory usage I don't think something like the COPACOBANA can help. Regards, -- Thomas Coppi - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken!
On Sat, May 2, 2009 at 12:33 PM, Perry E. Metzger pe...@piermont.com wrote: As just one obvious example of a realistic threat, consider that there are CAs that will happily sell you certificates that use SHA-1. Various clever forgery attacks have been used against certs that use MD5, see: http://www.win.tue.nl/hashclash/rogue-ca/ Those attacks can now be extended to SHA-1 pretty easily. It might require a bit of compute infrastructure -- say a lot of FPGAs and a bunch of cleverness -- to turn out certs quickly, but it can be done. Given that there are lots of high value certs out there of this form, this is rather dangerous. Off-the-shelf FPGA-based device that breaks DES by brute force in about a week, costs 9,000 euros: http://www.copacobana.org/ These are commercially available and programmable. Setting a few of them up to break SHA-1 certainly would not be trivial, but it looks feasible. -- Sandy Harris, Quanzhou, Fujian, China - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken!
It also is not going to be trivial to do this -- but it is now in the realm of possibility. I'm not being entirely a smartass when I say that it's always in the realm of possibility. The nominal probability for SHA-1 -- either 2^80 or 2^160 depending on context -- is a positive number. It's small, but it's always possible. The recent case of cert collisions happened because of two errors, hash problems and sequential serial numbers. If either had been corrected, the problem wouldn't have happened. I liken in in analogy to a fender-bender that happened because the person responsible had both worn-out brakes (an easily-fixable technological problem) and was tailgating (an easily-fixable suboptimal operational policy). It's a mistake to blame the wreck on either. It's enlightening to point out that either a good policy or a more timely upgrade schedule would have made the problem not occur. The problem right now is not that MD5, SHA1, etc. are broken. It is that they are broken in ways that you have to be an expert to understand and even the experts get into entertaining debates about. Any operational expert worth their salt should run screaming from a technology that the boffins have debates about flaws over dinner. Jon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken! (was: Request for hash-dependency in Tahoe security.)
On Thu, 2009-04-30 at 13:56 +0200, Eugen Leitl wrote: http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf Wow! These slides say that they discovered a way to find collisions in SHA-1 at a cost of only 2^52 computations. If this turns out to be right (and the authors are respected cryptographers -- the kind of people who really hate to be wrong about something like this) then it is very exciting! I cannot derive a realistic threat model from the very general statements in the slides. In the case of, for example, the Debian organization, which uses SHA-1 keys to check in code so that it's always clear with a distributed network of developers who made what changes, What threats must they now guard against and what corrective measures ought they take? Can a third-party attacker now forge someone's signature and check in code containing a backdoor under someone else's key? Such code could be loaded on a poisoned server, downloaded, and executed on millions of target machines with devastating effect and no way to catch the attacker. Can a rogue developer now construct a valid code vector B, having the same signature as some of his own (other) code A, thus bypassing the signature check and inserting a backdoor? The scenario is the same with a poisoned server but, once detected, the attacker would be identifiable. Is it the case that a constructed hash collision between A and B can be done by a third party but would be highly unlikely to contain any executable or sensible code at all? In this case the threat is serious, but mainly limited to vandalism rather than exploits. Is it the case that a constructed hash collision between A and B can only be done by the developer of both A and B, but would be highly unlikely to contain any executable or sensible code at all? In this case the threat is very minor, because the identity of the vandal would be instantly apparent. Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken!
Ray Dillinger b...@sonic.net writes: I cannot derive a realistic threat model from the very general statements in the slides. (BTW, you mean threat, not threat *model*, in this instance.) As just one obvious example of a realistic threat, consider that there are CAs that will happily sell you certificates that use SHA-1. Various clever forgery attacks have been used against certs that use MD5, see: http://www.win.tue.nl/hashclash/rogue-ca/ Those attacks can now be extended to SHA-1 pretty easily. It might require a bit of compute infrastructure -- say a lot of FPGAs and a bunch of cleverness -- to turn out certs quickly, but it can be done. Given that there are lots of high value certs out there of this form, this is rather dangerous. For example, Verisign has lots of cert infrastructure right now that uses SHA-1. Imagine if I now use the above described attack and start forging certs that look to all the world like they're from Verisign and claim that I'm a major bank, or to forge a CA that then forges certs that claim I'm a major bank. Ooops! In the case of, for example, the Debian organization, which uses SHA-1 keys to check in code so that it's always clear with a distributed network of developers who made what changes, What threats must they now guard against and what corrective measures ought they take? One can easily imagine a forgery attack right now where someone presented you with one piece of code which you sign and then made use of a different piece of code with the exact same SHA-1 which you didn't intend to sign. I don't know if Debian's specific processes are vulnerable or not to various clever attacks -- it would require a lot of thinking even if I was familiar enough with them, and I'm not. So, use something other than SHA-1 -- SHA-256 at least. Don't panic, don't flail around like a headless chicken, but do move away with all deliberate speed. Can a third-party attacker now forge someone's signature and check in code containing a backdoor under someone else's key? Perhaps, if they're clever enough. The most obvious attacks require preimage weaknesses, and those aren't known yet. However clever people can find ways to get around this -- see the Rogue CA attack -- and cause havoc. Is it the case that a constructed hash collision between A and B can be done by a third party but would be highly unlikely to contain any executable or sensible code at all? See the Rogue CA attack -- by being clever enough, one can almost certainly produce two executables with the same SHA-1 hash. They would need some sort of area that varied, but that's not too hard -- ELF note sections, data segments regions that contain some blob of data you don't care about, etc., are all fine possibilities. So, don't use SHA-1 if you can help it. This is not to say that all uses are unsafe. There is also no need to panic. However, it is clearly not a good idea to continue using it. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] SHA-1 broken!
Perry E. Metzger pe...@piermont.com writes: For example, Verisign has lots of cert infrastructure right now that uses SHA-1. Imagine if I now use the above described attack and start forging certs that look to all the world like they're from Verisign and claim that I'm a major bank, or to forge a CA that then forges certs that claim I'm a major bank. Ooops! Eric Rescorla correctly points out to me that Verisign randomizes SNs so it would be hard to attack them that way, but I'm sure not everyone who is in the root cert list in IE or Firefox does. It also is not going to be trivial to do this -- but it is now in the realm of possibility. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
[tahoe-dev] SHA-1 broken! (was: Request for hash-dependency in Tahoe security.)
From: Zooko O'Whielacronx zo...@zooko.com Subject: [tahoe-dev] SHA-1 broken! (was: Request for hash-dependency in Tahoe security.) To: nejuc...@gmail.com, tahoe-...@allmydata.org Date: Wed, 29 Apr 2009 15:59:05 -0600 Reply-To: tahoe-...@allmydata.org On Apr 29, 2009, at 11:51 AM, Nathan wrote: http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf Wow! These slides say that they discovered a way to find collisions in SHA-1 at a cost of only 2^52 computations. If this turns out to be right (and the authors are respected cryptographers -- the kind of people who really hate to be wrong about something like this) then it is very exciting! SHA-1 was already known to be vulnerable to attack by a moderately well-funded organization such as a national security agency, national military, corporation, or organized criminal group. Now it turns out that finding SHA-1 collisions is in the reach of a dedicated hobbyist or an eccentric genius [1]. Let's put a rough number on it. I might be a little bit off, but you can build a COPACOBANA machine for about $10,000 [2], and it can brute-force a 56- bit DES key in about six and a half days. 2^52 SHA-1 operations should take roughly the same amount of time and money. As another example I guess that distributed computation engines [3] and botnets [4] might be able to generate a SHA-1 collision in seconds. Plus of course the amplifying effects of birthday attacks and rainbow tables and so on mean that the longer you keep your COPACOBANA or your botnet generating SHA-1 collisions, the more SHA-1 users around the world become vulnerable to you. So basically, if these slides are right then relying on SHA-1 collision-resistance has been revealed as a major vulnerability! Almost all hash functions in civilian, open use are either MD5 or SHA-1. For example, decentralized revision control tools such as monotone, git, and hg rely on SHA-1. Interesting times! As Shawn already correctly pointed out (and as Nathan probably already knew), Tahoe doesn't use SHA-1, so we're not affected by this new discovery. Tahoe-LAFS uses SHA-256 (in the double-hashing mode suggested by Ferguson and Schneier and named SHA-256d). We also add our own tagging and salting prefix to avoid certain problems. We aren't currently vulnerable to hash collision attacks, and we plan never to get into that position (about which more below). Nonetheless, it would be a very good exercise to spell out what sorts of problems could result if attackers could violate what sorts of properties of the hash function(s) used in Tahoe. The basic uses of secure hashes in Tahoe are for integrity-checking of immutable files and for digital signatures on mutable files and directories. If an attacker could generate two different inputs which yielded the same hash output (that is, to find a hash collision), then they could give you a single immutable file cap that produced two (or more) different files when you used it to download the file. We believe that nobody is currently able to do that, so currently if someone gives you an immutable file cap, you can rely on there being at most one file which can be downloaded using that cap. For mutable files it is even safer. If an attacker could find an input which yielded the same output as someone *else*'s input (that is, to find a second pre-image), then that attacker could write changes to a mutable file or directory that they were not authorized to write to. Finding a second pre-image is probably much harder than finding a collision -- for example nobody has yet figured out how to find a second pre-image in SHA-1. That's why I say it is even safer. You already assume that the person who can write to a mutable file can make it so that two or more different file contents would be downloaded from using the same mutable-file read cap, but for immutable files we hold them to a higher standard and prevent even the original uploader of the immutable file from being able to make more than one file that matches the immutable-file read cap. There are a lot more details of how Tahoe uses hash functions that I would be happy to work out when I have time, but those are the most important ones, and the immutable file caps are the most likely to turn out to be vulnerable. (Although, as I've said, even the immutable file caps are extremely unlikely to be vulnerable.) (Hm, this puts an interesting twist on Vincent and Nathan's idea of layering Mercurial-or-Bazaar on top of Tahoe. Tahoe uses stronger cryptography (and also more flexible cryptography, by the way), so if you have uploaded your Mercurial repository to Tahoe then even when SHA-1 turns out to be weak (as it has), you can still rely on the integrity of your repository.) ps: For the case of Merkel Trees, are any security guarantees preserved in the face of hash collision
