Re: [IP] SHA-1 cracked?
Steve Bellovin writes: Note that finding a hash function collision by brute force is inherently harder, because it requires some communication: two widely-separated machines may have produced matching outputs, but they need to know about the other one. That's not necessarily true, although we don't know the details yet about the new attacks so we can't say for sure. (The new cert collision paper suggests that the details will be presented at Eurocrypt.) Some of the work in this area finds the collisions in a different way than might be expected. They start with a linear or nearly linear approximation to the hash function. On this basis they find an XOR or additive difference that will produce a collision. Then they look for an input for which this pre-chosen difference will produce a collision in the actual hash. That amounts to finding a text for which the nonlinearities cancel out in the proper way, so that the chosen difference works to produce a collision. In the case of MD5, the differential was only 6 (carefuly chosen!) bits. The hard part was to find a plaintext where the nonlinearities associated with those bits did not prevent the collision from occuring. http://eprint.iacr.org/2004/264.pdf presents some musings on the Wang attack and estimates that they could find a suitable text for this differential in 2^42.2 work, which is a couple of orders of magnitude more than what Wang apparently needs, indicating that she has more tricks up her sleeve. This method does not require comparing hashes from different plaintexts. Rather, each independent search engine is given the pre-chosen differential and tries to find a plaintext which satisfies the conditions that will allow a collision to occur. A machine to do this would be highly parallelizable and would not require any special communication capabilities. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [IP] SHA-1 cracked?
On Wed, 16 Feb 2005, Ben Laurie wrote: A work factor of 2^69 is still a serious amount of work. Yep. Does anyone recall DeepCrack's specs? -- Yours, J.A. Terranson [EMAIL PROTECTED] 0xBD4A95BF Quadriplegics think before they write stupid pointless shit...because they have to type everything with their noses. http://www.tshirthell.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
Ian G wrote: Stefan Brands just posted on my blog (and I saw reference to this in other blogs, posted anon) saying that it seems that Schneier forgot to mention that the paper has a footnote which says that the attack on full SHA-1 only works if some padding (which SHA-1 requires) is not done. I posted the note on yousendit, http://s17.yousendit.com/d.aspx?id=0MZULY5IBDAU130DK0RKV3GTIB Mads - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
From: Joseph Ashwood [EMAIL PROTECTED] Sent: Feb 17, 2005 12:15 AM To: cryptography@metzdowd.com Subject: Re: SHA-1 cracked This attack means that we need to begin the process for a quick and painless retirement of SHA-1 in favor of SHA-256/384/512 in the immediate future and begin further preparations to move to Whirlpool and other hashes in the near future. I say this because with MD5 completely broken, SHA-0 effectively completely broken, and SHA-1 showing big cracks, the entire SHA series is in doubt, and needs to be heavily reconsidered, otherwise we're looking at a continuing failure of hash functions apparently in a yearly fashion until we run out of the SHA series. Yep. The thing that's interesting here is that the more-or-less obvious fallbacks for SHA1 are RIPE-MD160 and SHA256/512. But given the pile of bodies in front of Wang's door already (MD4,MD5, Haval, RIPE-MD, SHA0, SHA1), it's hard to have any confidence at all that RIPE-MD160 will survive long. All the remaining SHA functions are the same, modulo some constants and the wordsize used--SHA512 is just SHA256 using 64-bit words, different constants, and a few more rounds. So there's really only one SHA function left. It's different enough from SHA1 that it's plausible Wang's attacks won't work, but I can't see any really strong reason to trust in that. Whirlpool looks like the best bet for a fallback right now, but it really hasn't seen anything like the amount of analysis I'd like. This is what it looks like when someone develops a new class of attack that breaks a whole bunch of your available cryptographic primitives in a big hurry. Joe --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
John Kelsey wrote: Anyone know where we could find the paper? It'd be kind-of convenient when trying to assess the impact of the attack if we knew at least a few details The *words* part I typed in here: http://www.financialcryptography.com/mt/archives/000357.html I skipped the examples. It is very brief. If it's really the case that the attack requires colliding messages of different sizes (that's what this comment implies), then maybe the attack won't be applicable in the real world, but it's hard to be sure of that. Suppose I can find collisions of the form (X,X*) where X is three blocks long, and X* is four blocks long. Now, that won't work as a full collision, because the length padding at the end will change for X and X*. But I can find two such collisions, and still get a working attack by concatenating them. This is the relevant para: Table 2: A collision of SHA1 reduced to 58 steps. The two messages that collide are M0 and M'0. Note that padding rules were not applied to the messages. iang -- News and views on what matters in finance+crypto: http://financialcryptography.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
Ian Grigg writes: Stefan Brands just posted on my blog (and I saw reference to this in other blogs, posted anon) saying that it seems that Schneier forgot to mention that the paper has a footnote which says that the attack on full SHA-1 only works if some padding (which SHA-1 requires) is not done. http://www.financialcryptography.com/mt/archives/000355.html First, that's not quite what it says. According to what I have seen the language is, in reference to a pair of collisions exhibited for a weakened SHA, Note that padding rules were not applied to the messages. But that is irrelevant. The padding for SHA, aka Merkle Damgard strengthening, involves padding it up a a multiple of 512 bits, while appending a 1 bit and a 64 bit length field. If you have two messages M and M' which collide without this padding, they must by definition be a multiple of the block length. So you add one extra block which is a 1 bit, all zeros, and then the length of M. Now you have a legally padded pair of SHA messages which collide. In fact, you can add anything at all after the blocks which collide (the same thing to both messages). Once you have a collision it stays collided as long as the suffix is identical. None of the hashes exhibited by Wang et al at http://eprint.iacr.org/2004/199.pdf have the padding! That doesn't matter. They are still valid collisions and can be extended or padded any way we want while retaining the colliding property. Presumably the text in the footnote was a reference to this fact. Don't try to interpret it as meaning that the attack won't work against SHA. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
On Feb 16, 2005, at 9:15 PM, Joseph Ashwood wrote: - Original Message - From: Steven M. Bellovin [EMAIL PROTECTED] Subject: SHA-1 cracked It's probably not a practical threat today, since it takes 2^69 operations to do it I will argue that the threat is realizable today, and highly practical. I would have to reply that you would be wrong. It is well documented that in 1998 RSA Security's DES Challenge II was broken in 72 hours by $250,000 worth of custom machine. The DES challenge had an upper limit of 2^56, so attacking a 2^69 space would take you 16 years instead of 3 days (the three day break was not an exhaustive search either, but I will give you the benefit of the doubt and say that you will get as lucky as the people going after the DES Challenge were...) This also assumes that a hardware attack on SHA1 is equivalent to an exhaustive keysearch of DES. This is not the case. SHA1 is fast in hardware, but not as fast as DES. While you can speed things up for a FPGA attack using various tricks to make internal steps run in parallel, the numerous multiply operations in SHA1 are painful for a FPGA implementation, unlike the shifts and additions that are more common in DES. This also assumes that the known hardware speed-ups for SHA1 will also apply to the attack vector recently revealed, which I am unable to make a guess at. While I think that the recent results do not bode well for the future of the SHA line of hashes, your claims that the sky is falling (e.g. you are looking at minutes if not seconds before break) are simply not supported by known facts. Jim - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
At 22:33 2005-02-16 +, Ian G wrote: Steven M. Bellovin wrote: According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. Stefan Brands just posted on my blog (and I saw reference to this in other blogs, posted anon) saying that it seems that Schneier forgot to mention that the paper has a footnote which says that the attack on full SHA-1 only works if some padding (which SHA-1 requires) is not done. http://www.financialcryptography.com/mt/archives/000355.html No, that's not what it says. It says that Note that padding rules were not applied to the message. This is exactly the same as the previous breaks; it just means that the collision appears in the chaining output... if you just append anything at all to the end of the texts, and pad it correctly, you will have valid SHA-1 hashes. Nothing different here than from the MD4/MD5/SHA-0 breaks. Since I'm typing anyway, I'll also reply to Joseph Ashwood's earlier mail, in which he said: [...] SHA-1 showing big cracks, the entire SHA series is in doubt, and needs to be heavily reconsidered, [...] If you look at Phil Hawkes' paper http://eprint.iacr.org/2004/207.pdf, you will see that the SHA-2s are very different algorithms, and my own opinion is that the data-expansion part of the algorithm is *seriously* beefed up. My guess is that the NSA were already worried about this kind of attack (whether they'd found it or not). We don't have a good analysis of the data-expansion part, but I'm pretty sure that it'll defeat the Wang attacks. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drivehttp://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
On Feb 15, 2005, at 11:29 PM, Steven M. Bellovin wrote: nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb Should anything be read into the timing of the NIST announcement and the release of this paper a week later? --dfc Douglas F. Calvert http://anize.org/dfc/ .::. GPG Key: 0xC9541FB2 A mystic in the sense that I am still mystified by things... - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
On Tue, 15 Feb 2005, Steven M. Bellovin wrote: According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. and what about HMAC-SHA1 ? Is it reducing the operation required by the same factor or as the structure of HMAC is so different that the attack is very unlikely to be practical ? -- -- Alexandre Dulaunoy (adulau) -- http://www.foo.be/ -- http://pgp.ael.be:11371/pks/lookup?op=getsearch=0x44E6CBCD -- Knowledge can create problems, it is not through ignorance --that we can solve them Isaac Asimov - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
In message [EMAIL PROTECTED], Alexandre Dulaunoy writes: On Tue, 15 Feb 2005, Steven M. Bellovin wrote: According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. and what about HMAC-SHA1 ? Is it reducing the operation required by the same factor or as the structure of HMAC is so different that the attack is very unlikely to be practical ? As the blog entry mentions, it's it's unlikely that SHA-1 is affected. That said, the attack merits close attention; as Schneier has noted in other contexts, attacks always get better, never worse. --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
From: Steven M. Bellovin [EMAIL PROTECTED] Sent: Feb 15, 2005 11:29 PM To: cryptography@metzdowd.com Subject: SHA-1 cracked According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. Well, there *weren't* any a week ago --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [IP] SHA-1 cracked?
David Farber wrote: -- Forwarded Message From: Rodney Joffe [EMAIL PROTECTED] Date: Wed, 16 Feb 2005 07:36:36 -0700 To: Dave Farber [EMAIL PROTECTED] Subject: SHA-1 cracked? For IP Hi Dave, Bruce Schneier is reporting in his blog that SHA-1 appears to have been broken by a Chinese group, and that is has collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length.. This could have non-trivial implications for many current commercial operations. http://www.schneier.com/blog/archives/2005/02/sha1_broken.html A work factor of 2^69 is still a serious amount of work. At a thousand million trials a second, that's still well over 17 years. I doubt you can get anything like that speed without _serious_ expenditure. For reference, a middling PC can do around 200k single block SHA-1's a second. So, multiply that by 5 million to get it down to 17 years, assuming all you have to do is hash. Of course, we don't have the details yet, but this is not the sky falling on our heads (yet). Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
It is worth emphasizing that, as a 2^69 attack, we're not going to be getting test vectors out of Wang. After all, if she had 2^69 computation available, she wouldn't have needed to attack MD5; she could have just brute forced it in 2^64. This means the various attacks in the MD5 Someday paper aren't going to cross over to SHA-1, i.e. don't expect these anytime soon for SHA-1. http://www.doxpara.com/t1.html http://www.doxpara.com/t2.html --Dan Steven M. Bellovin wrote: According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
- Original Message - From: Steven M. Bellovin [EMAIL PROTECTED] Subject: SHA-1 cracked It's probably not a practical threat today, since it takes 2^69 operations to do it I will argue that the threat is realizable today, and highly practical. It is well documented that in 1998 RSA Security's DES Challenge II was broken in 72 hours by $250,000 worth of custom machine. Scale this forward to today, and $500,000 worth of custom equipment and 2^69 is not out of reach for 3 days worth of work. So assuming that your attackers are smallish businesses, you have 3 days of security, and large businesses with a vested interest in breaking your security you are looking at minutes if not seconds before break. While most uses of SHA-1 actually end up searching for collisions against fixed outputs (e.g. given A find B such that AB and SHA1(A) == SHA1(B)), this attack does not immediately cause the collapse of all e-commerce This attack means that we need to begin the process for a quick and painless retirement of SHA-1 in favor of SHA-256/384/512 in the immediate future and begin further preparations to move to Whirlpool and other hashes in the near future. I say this because with MD5 completely broken, SHA-0 effectively completely broken, and SHA-1 showing big cracks, the entire SHA series is in doubt, and needs to be heavily reconsidered, otherwise we're looking at a continuing failure of hash functions apparently in a yearly fashion until we run out of the SHA series. Joe Trust Laboratories Changing Software Development http://www.trustlaboratories.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
Steven M. Bellovin wrote: According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. Stefan Brands just posted on my blog (and I saw reference to this in other blogs, posted anon) saying that it seems that Schneier forgot to mention that the paper has a footnote which says that the attack on full SHA-1 only works if some padding (which SHA-1 requires) is not done. http://www.financialcryptography.com/mt/archives/000355.html I think this might be an opportune time to introduce a new way of looking at algorithms. I've written it up in draft (excuse the postit notes) : http://iang.org/papers/pareto_secure.html In short, what I do is apply the concepts of the econ theory of Pareto efficiency to the metric of security. This allows a definition of what we mean by secure which is quite close to colloquial usage; in the language so introduced, I'd suggest that SHA-1 used to be Pareto-complete, and is now Pareto-secure for certain applications. I have a little table down the end that now needs to be updated! Comments welcome, it is not a long nor mathematical paper! Some small consolation for those not at the RSA conference. iang -- News and views on what matters in finance+crypto: http://financialcryptography.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
SHA-1 cracked
According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
