Fwd: 80-bit security? (Was: Re: SHA-1 collisions now at 2^{52}?)
On Fri, May 8, 2009 at 10:28 AM, Brandon Enright bmenr...@ucsd.edu wrote: Steven M. Bellovin s...@cs.columbia.edu wrote: On Thu, 30 Apr 2009 17:44:53 -0700 Jon Callas j...@callas.org wrote: The accepted wisdom on 80-bit security (which includes SHA-1, 1024-bit RSA and DSA keys, and other things) is that it is to be retired by the end of 2010. That's an interesting statement from a historical perspective -- is it true? And what does that say about our ability to predict the future, and hence to make reasonable decisions on key length? See, for example, the 1996 report on key lengths, by Blaze, Diffie, Rivest, Schneier, Shimomura, Thompson, and Wiener, available at http://www.schneier.com/paper-keylength.html -- was it right? It was a best guess by a group of clever and well-informed people. There's no way to tell if it was precisely right, but there's no way to get a better estimate either, short of getting a similar group to re-do the work today. A back-of-the envelope approximation to today's requirements can be had by saying Moore's Law gives twice the computer speed every 18 months, so ciphers needs one more key bit every 18months to keep up. They said minimum 75 bits to keep an existing cipher in service, minimum 90 for any new ones, as of 1996. Add 10 bits to each for a rough estimate as of 2011. Now, even assuming 64 bits is within reach of modern computing power, ... I'd have thought that was obvious, and had been for a decade or so. EFF broke DES in a few days for $200,000 ten years ago. A 64-bit cipher is only 256 times harder, easily within reach on an intelligence agency budget. Copacobana break DES in a week for 9,000 euro. 256 of them would break a 64-bit cipher in a week. This is within reach for a high-stakes industrial espionage situation, say Boeing and Airbus competing for big orders. -- Sandy Harris, Quanzhou, Fujian, China - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 80-bit security? (Was: Re: SHA-1 collisions now at 2^{52}?)
On Wed, 6 May 2009 20:54:34 -0400 Steven M. Bellovin s...@cs.columbia.edu wrote: On Thu, 30 Apr 2009 17:44:53 -0700 Jon Callas j...@callas.org wrote: The accepted wisdom on 80-bit security (which includes SHA-1, 1024-bit RSA and DSA keys, and other things) is that it is to be retired by the end of 2010. That's an interesting statement from a historical perspective -- is it true? And what does that say about our ability to predict the future, and hence to make reasonable decisions on key length? See, for example, the 1996 report on key lengths, by Blaze, Diffie, Rivest, Schneier, Shimomura, Thompson, and Wiener, available at http://www.schneier.com/paper-keylength.html -- was it right? On breaking DES the paper says: As explained above, 40-bit encryption provides inadequate protection against even the most casual of intruders, content to scavenge time on idle machines or to spend a few hundred dollars. Against such opponents, using DES with a 56-bit key will provide a substantial measure of security. At present, it would take a year and a half for someone using $10,000 worth of FPGA technology to search out a DES key. In ten years time an investment of this size would allow one to a DES key in less than a week. This is surprising accurate. As Sandy Harris pointed out, http://www.copacobana.org/ is selling about $10k worth of FPGA technology to crack DES in about 6.4 days: With further optimization of our implementation, we could achieve a clock frequency of 136MHz for the brute fore attack with COPACOBANA. Now, the average search time for a single DES key is less than a week, precisely 6.4 days. The worst case for the search has been reduced to 12.8 days now. Now, even assuming 64 bits is within reach of modern computing power, I still think it is naive to assume that computing power will continue to grow to 80 or more bits any time soon. The energy requirements for cycling a 80 bit counter are significant. We are likely to get to a point where the question is not how parallel a machine can you afford to build? but rather how much heat can you afford to dissipate?. Brandon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 80-bit security? (Was: Re: SHA-1 collisions now at 2^{52}?)
At 8:54 PM -0400 5/6/09, Steven M. Bellovin wrote: On Thu, 30 Apr 2009 17:44:53 -0700 Jon Callas j...@callas.org wrote: The accepted wisdom on 80-bit security (which includes SHA-1, 1024-bit RSA and DSA keys, and other things) is that it is to be retired by the end of 2010. That's an interesting statement from a historical perspective -- is it true? That's an oddly-worded question. It is true that NIST has specified that algorithms with 80 bits of effective strength should stop being used in US government systems after the end of 2010. It is not true that the accepted wisdom is 80-bit crypto is to be retired by the end of 2010. It is true that some uses of SHA-1 have 80 (now many fewer) bits of effective strength. It is not true that SHA-1 gives 80-bit security; many uses of a hash rely on the preimage resistance, not the collision resistance. It may be true that 1024-bit RSA and DSA gives 80 bits of effective strength, and it is true that this is the accepted wisdom. This is based on some wild hand-waving and scaling assumptions with very few data points, and particularly few in the past five years since that number became oft-repeated accepted wisdom. And what does that say about our ability to predict the future, and hence to make reasonable decisions on key length? Bupkis. The best asymmetric attack published so far is about 700 bits. No one has produced a SHA-1 collision at 62 bits of effort (the previous estimated work). Our ability to extrapolate work effort to 80 bits is questionable indeed. See, for example, the 1996 report on key lengths, by Blaze, Diffie, Rivest, Schneier, Shimomura, Thompson, and Wiener, available at http://www.schneier.com/paper-keylength.html -- was it right? How could we tell? The whole point of the paper was estimating the strength needed to keep a secret *for a long time*. We are only 13 years into the 20 years that they used as a basis for the estimate of 90 bits. In 1993, Brickell, Denning, Kent, Maher, and Tuchman's interim report on Skipjack (I don't believe there was ever a final report) stated that Skipjack (an 80-bit cipher) was likely to be secure for 30-40 years. Was it right? Asking that question six years into the 30 years (if those were the numbers they used) is begging to make approximations on insufficient data. The problem with SHA-1 is not its 80-bit security, but rather that it's not that strong. That's one problem. Another is that because it can also be used in environments where 160ish bits of security are needed and it's still believed to be fine there, people on this list and in the press are sloppy when they speak about its use. Another is that people on this list and in the press are sloppy about security decisions that involve periods of time longer than about a year. --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
80-bit security? (Was: Re: SHA-1 collisions now at 2^{52}?)
On Thu, 30 Apr 2009 17:44:53 -0700 Jon Callas j...@callas.org wrote: The accepted wisdom on 80-bit security (which includes SHA-1, 1024-bit RSA and DSA keys, and other things) is that it is to be retired by the end of 2010. That's an interesting statement from a historical perspective -- is it true? And what does that say about our ability to predict the future, and hence to make reasonable decisions on key length? See, for example, the 1996 report on key lengths, by Blaze, Diffie, Rivest, Schneier, Shimomura, Thompson, and Wiener, available at http://www.schneier.com/paper-keylength.html -- was it right? In 1993, Brickell, Denning, Kent, Maher, and Tuchman's interim report on Skipjack (I don't believe there was ever a final report) stated that Skipjack (an 80-bit cipher) was likely to be secure for 30-40 years. Was it right? The problem with SHA-1 is not its 80-bit security, but rather that it's not that strong. --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
Perry E. Metzger pe...@piermont.com writes: Home routers and other equipment last for years. If we slowly roll out various protocol and system updates now, then in a number of years, when we find ourselves with real trouble, a lot of them will already be updated because new ones won't have issues. I'm not really sure if it works that way. From my experience with SSH in routers [0] I'd say it's more like: Binary images in routers last years. If we deploy first-cut, buggy implementations of new protocols now, we'll have to support the bugs in a backwards-compatible manner for the rest of eternity. That is, in the absence of widely-deployed, mature implementations to test against, router vendors will (if they were to ship with this right now) deploy pre-alpha quality code that would then be frozen for the rest of eternity. I have to maintain support for ten-year-old SSH bugs in my code because of ports to... well, unnamed vendors' systems done a decade or so back that never get touched again once the initial version got to the point where it would respond to a packet. So if vendors are going to bake things into firmware (which includes firmware images that never get updated, more or less the same thing) then I'd prefer they hold on a bit until it's certain they've got somewhat more mature code. Peter. [0] Implementations of this are easier to date than SSL, and also a lot buggier so there's more to watch out for. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
Perry E. Metzger pe...@piermont.com writes: Greg Rose g...@qualcomm.com writes: It already wasn't theoretical... if you know what I mean. The writing has been on the wall since Wang's attacks four years ago. Sure, but this should light a fire under people for things like TLS 1.2. Why? Seriously, what threat does this pose to TLS 1.1 (which uses HMAC-SHA1 and SHA-1/MD5 dual hashes)? Do you think the phishers will even notice this as they sort their multi-gigabyte databases of stolen credentials? The problem with TLS 1.2 is that it completely breaks backwards compatibility with existing versions, it's an even bigger break than the SSL - TLS changeover was. If you want something to incentivise vendors to break compatibility with the entire deployed infrastructure of TLS devices, the attack had better be something pretty close to O( 1 ), preferably with deployed malware already exploiting it. Ten years ago you may have been able to do this sort of thing because it was cool and the geeks were in charge, but today with a deployed base of several billion devices (computers, cellphones, routers, printers, you name it) the economists are in charge, not the cryptographers, and if you do the sums TLS 1.2 doesn't make business sense. It may be geeky-cool to make the change, but geeky-cool isn't going to persuade (say) Linksys to implement TLS 1.2 on their home routers. (I can't believe I just said that :-). Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
Peter Gutmann pgut...@cs.auckland.ac.nz writes: Perry E. Metzger pe...@piermont.com writes: Greg Rose g...@qualcomm.com writes: It already wasn't theoretical... if you know what I mean. The writing has been on the wall since Wang's attacks four years ago. Sure, but this should light a fire under people for things like TLS 1.2. Why? Seriously, what threat does this pose to TLS 1.1 (which uses HMAC-SHA1 and SHA-1/MD5 dual hashes)? No immediate threat. The issue is that attacks only get better with time. Now that we've seen this set of attacks, we can't be entirely sure what will happen next. In three or five years, we may find that HMAC-SHA1 is more easily attacked than it is now. On the 1.2 issue, the real point of 1.2 is not to replace SHA-1 per se but to permit us to deal with the situation where *any* algorithm proves to be dangerously weak. We've learned this lesson several times now -- it is best to have protocols that can move to new crypto algorithms as old ones need to be abandoned. Note that I said things like TLS -- TLS is not the only issue. There are many out there. There is no need to panic over any one of them, but it would be good to get things replaced. Right now, without much of a rush or any real anxiety about it we can take the several years needed to move new mechanisms out. If we dither, then in a few years we may find ourselves having a much less pleasant transition where suddenly the problem isn't long term but immediate. Do you think the phishers will even notice this as they sort their multi-gigabyte databases of stolen credentials? No, they clearly won't notice at all. However, lets broaden this and consider not only phishermen but all attackers. Remember, attackers go for the lowest hanging fruit, not for any particular technique. They pick the weakest links available. The reason bad crypto has not been an attack point is because other things have been much easier to attack than the crypto. I would prefer to keep it that way. My worry isn't about the phishermen per se. My worry is about things we haven't thought about -- tricks like the CA forgery trick lying in wait for us. There are more and more things out there that depend on the crypto being right -- things like signed software updates, people who actually *need* authentication for life critical systems, etc. If we clean things up now, in three or five or seven years we won't have to rush. There is no need to panic, but clearly the handwriting is on the wall. The time to act is early when it is inexpensive to do so. It may be geeky-cool to make the change, but geeky-cool isn't going to persuade (say) Linksys to implement TLS 1.2 on their home routers. (I can't believe I just said that :-). Home routers and other equipment last for years. If we slowly roll out various protocol and system updates now, then in a number of years, when we find ourselves with real trouble, a lot of them will already be updated because new ones won't have issues. If we wait until things get bad, then instead of being a natural part of the upgrade cycle things get to be expensive and painful. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
At Sat, 02 May 2009 21:53:40 +1200, Peter Gutmann wrote: Perry E. Metzger pe...@piermont.com writes: Greg Rose g...@qualcomm.com writes: It already wasn't theoretical... if you know what I mean. The writing has been on the wall since Wang's attacks four years ago. Sure, but this should light a fire under people for things like TLS 1.2. Why? Seriously, what threat does this pose to TLS 1.1 (which uses HMAC-SHA1 and SHA-1/MD5 dual hashes)? Do you think the phishers will even notice this as they sort their multi-gigabyte databases of stolen credentials? Again, I don't want to get into a long argument with peter about TLS 1.1 vs. TLS 1.2, but TLS 1.2 also defines an extension that lets the client tell the server that it would take a SHA-256 certificate. Absent that, it's not clear how the server would know. Of course, you could use that extension with 1.1 and maybe that's what the market will decide... -Ekr - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
On May 2, 2009, at 5:53, Peter Gutmann wrote: Perry E. Metzger pe...@piermont.com writes: Greg Rose g...@qualcomm.com writes: It already wasn't theoretical... if you know what I mean. The writing has been on the wall since Wang's attacks four years ago. Sure, but this should light a fire under people for things like TLS 1.2. Why? Seriously, what threat does this pose to TLS 1.1 (which uses HMAC- SHA1 and SHA-1/MD5 dual hashes)? Do you think the phishers will even notice this as they sort their multi-gigabyte databases of stolen credentials? [snip] I must admit I don't understand this line of reasoning (not to pick on Perry, Greg, or Peter, all of whom have a high level of crypto-clue and who certainly understand protocol design). The serious concern here seems to me not to be that this particular weakness is a last straw wedge that enables some practical attack against some particular protocol -- maybe it is and maybe it isn't. What worries me is that SHA-1 has been demonstrated to not have a property -- infeasible to find collisions -- that protocol designers might have relied on it for. Security proofs become invalid when an underlying assumption is shown to be invalid, which is what has happened here to many fielded protocols that use SHA-1. Some of these protocols may well still be secure in practice even under degraded assumptions, but to find out, we'd have to analyze them again. And that's a non-trivial task that as far as I know has not been done yet (perhaps I'm wrong and it has). They'll never figure out how to exploit it is not, sadly, a security proof. Any attack that violates basic properties of a crypto primitive is a serious problem for anyone relying on it, pretty much by definition. -matt - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
At Sat, 2 May 2009 15:00:36 -0400, Matt Blaze wrote: The serious concern here seems to me not to be that this particular weakness is a last straw wedge that enables some practical attack against some particular protocol -- maybe it is and maybe it isn't. What worries me is that SHA-1 has been demonstrated to not have a property -- infeasible to find collisions -- that protocol designers might have relied on it for. Security proofs become invalid when an underlying assumption is shown to be invalid, which is what has happened here to many fielded protocols that use SHA-1. Some of these protocols may well still be secure in practice even under degraded assumptions, but to find out, we'd have to analyze them again. And that's a non-trivial task that as far as I know has not been done yet (perhaps I'm wrong and it has). They'll never figure out how to exploit it is not, sadly, a security proof. Without suggesting that collision-resistance isn't an important property, I'd observe that we don't have anything like a reduction proof of full TLS, or, AFAIK, any of the major security protocols in production use. Really, we don't even have a good analysis of the implications of relaxing any of the (soft) assumptions people have made about the security of various primitives (though see [1] and [2] for some handwaving analysis). It's not clear this should make you feel any better when a primitive is weakened, but then you probably shouldn't have felt that great to start with. -Ekr [1] http://www.rtfm.com/dimacs.pdf [2] http://www.cs.columbia.edu/~smb/papers/new-hash.pdf - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
On Thu, Apr 30, 2009 at 11:07:31PM -0400, Perry E. Metzger wrote: Greg Rose g...@qualcomm.com writes: This is a very important result. The need to transition from SHA-1 is no longer theoretical. It already wasn't theoretical... if you know what I mean. The writing has been on the wall since Wang's attacks four years ago. Sure, but this should light a fire under people for things like TLS 1.2. Perhaps, though the MAC in TLS cipher-suites needs just 2nd pre-image resistance, not collision resistance. The collision resistance is more relevant to X.509 authentication, and even there only when CA practices are sub-optimal. Yes, by all means, new hash functions, but lets not over-emphasize the magnitude of the problem. This is not a SHA-1 pandemic... -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
SHA-1 collisions now at 2^{52}?
McDonald, Hawkes and Pieprzyk claim that they have reduced the collision
strength of SHA-1 to 2^{52}.
Slides here:
http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf
Thanks to Paul Hoffman for pointing me to this.
-Ekr
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
Eric Rescorla e...@networkresonance.com writes:
McDonald, Hawkes and Pieprzyk claim that they have reduced the collision
strength of SHA-1 to 2^{52}.
Slides here:
http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf
Thanks to Paul Hoffman for pointing me to this.
This is a very important result. The need to transition from SHA-1 is no
longer theoretical.
Perry
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
On 2009 Apr 30, at 4:31 , Perry E. Metzger wrote:
Eric Rescorla e...@networkresonance.com writes:
McDonald, Hawkes and Pieprzyk claim that they have reduced the
collision
strength of SHA-1 to 2^{52}.
Slides here:
http://eurocrypt2009rump.cr.yp.to/
837a0a8086fa6ca714249409ddfae43d.pdf
Thanks to Paul Hoffman for pointing me to this.
This is a very important result. The need to transition from SHA-1
is no
longer theoretical.
It already wasn't theoretical... if you know what I mean. The writing
has been on the wall since Wang's attacks four years ago.
BTW, it is my (our) opinion that the current attacks can't be extended
to the SHA-2 family, due to the avalanche effect in the data
expansion, which is significantly different to the designs of its
ancestors. SHA-2 would need a new breakthrough.
Greg.
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
On Apr 30, 2009, at 4:31 PM, Perry E. Metzger wrote:
Eric Rescorla e...@networkresonance.com writes:
McDonald, Hawkes and Pieprzyk claim that they have reduced the
collision
strength of SHA-1 to 2^{52}.
Slides here:
http://eurocrypt2009rump.cr.yp.to/
837a0a8086fa6ca714249409ddfae43d.pdf
Thanks to Paul Hoffman for pointing me to this.
This is a very important result. The need to transition from SHA-1
is no
longer theoretical.
Let me make a couple of comments, one from each side of my mouth.
* I would like to see an implementation of this result, producing a
collision. 2^52 is a nice number, but it needs a scale. I'm not
worried about 2^52 years. Or even seconds. I say this solely because I
expected a practical 2^63 collision by now, and have been wondering
about what the scale of that 2^63. I would like to see an
implementation.
* What do you mean by no longer theoretical? The accepted wisdom on
80-bit security (which includes SHA-1, 1024-bit RSA and DSA keys, and
other things) is that it is to be retired by the end of 2010. The end
of 2010 fast approacheth. If you include into development time some
reasonable level of market adoption, one might convincingly argue that
the end of SHA-1 ought to be shipping this summer, or certainly in the
fall, and no later than the *start* of 2010. The need to transition
from SHA-1 is apparent and manifest. New results merely confirm
conventional wisdom.
Jon
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
Greg Rose g...@qualcomm.com writes: This is a very important result. The need to transition from SHA-1 is no longer theoretical. It already wasn't theoretical... if you know what I mean. The writing has been on the wall since Wang's attacks four years ago. Sure, but this should light a fire under people for things like TLS 1.2. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
