On Sat, 3 Jan 2009 12:31:53 -0500 "Christopher Morrow" <morrowc.li...@gmail.com> wrote:
> On Sat, Jan 3, 2009 at 10:49 AM, Steven M. Bellovin > <s...@cs.columbia.edu> wrote: > > On Sat, 03 Jan 2009 09:35:06 -0500 > > William Warren <hescomins...@emmanuelcomputerconsulting.com> wrote: > > > >> Everyone seems to be stampeding to SHA-1..yet it was broken in > >> 2005. So we trade MD5 for SHA-1? This makes no sense. > >> > > (a) SHA-1 was not broken as badly. The best attack is, as I recall, > > 2^63, which is computationally infeasible without special-purpose > > hardware. > > > > special purpose? or lots of commodity? like the Amazon-EC2 example > used in the cert issue? (or PS3s or...) No -- special-purpose chips, along the lines of Deep Crack (http://en.wikipedia.org/wiki/EFF_DES_cracker). Let's do the arithmetic. 'openssl speed sha1' on my desktop -- a 3.4 Ghz Dell -- manages 1583237 16-byte blocks in 2.92 seconds, or ~542204/second. Let's assume that for an attack to be economical, the calculations have to be completed within 30 days. My machine could do 1405B hashes in that time frame. But I need 2^63 of them, which means I need 6.5 million machines cooperating. Not impossible for BOINC, but I don't think that EC2 could handle it. > > > (b) Per a paper Eric Rescorla and I wrote, there's no usable > > alternative, since too many protocols (including TLS) don't > > negotiate hash functions before presenting certificates. In > > particular, this means that a web site can't use SHA-256 because > > (1) most clients won't support it; and (2) it can't tell which ones > > do. (Note that this argument applies just as much to combinations > > of hash functions -- anything that *the large majority of today's* > > browsers don't implement isn't usable.) > > This is a function of an upgrade (firefox3.5 coming 'soon!') for > browsers, and for OS's as well, yes? So, given a future flag-day (18 > months from today no more MD5, only SHA-232323 will be used!!) > browsers for the majority of the market could be upgraded. Certainly > there are non-browsers out there (eudora, openssl, wget, > curl..bittorrent-clients, embedded things) which either will lag more > or break all together. > Have you looked at the statistics on upgrades lately? Not a pretty picture... See, among others, http://www.ews.uiuc.edu/bstats/latest.html http://www.upsdell.com/BrowserNews/stat_trends.htm http://marketshare.hitslink.com/browser-market-share.aspx?qprid=2 http://www.techzoom.net/publications/insecurity-iceberg/index.en > > > > These two points lead us to (c): security is a matter of economics, > > not algorithms. Switching now to something else loses more in > > connectivity or customers than you would lose from such an > > expensive attack. > > > > only if not staged out with enough time to roll updates in first, > right? > From all the data I've seen, very many machines are *never* upgraded, so the proper metric for "enough time" is "computer lifetime". Firefox 3 does handle SHA-256/384/512; I don't think IE7 does. --Steve Bellovin, http://www.cs.columbia.edu/~smb
