Security team successfully cracks SSL using 200 PS3's and MD5
Steven M. Bellovin
smb at cs.columbia.edu
Sat Jan 3 18:03:48 UTC 2009
On Sat, 3 Jan 2009 12:31:53 -0500
"Christopher Morrow" <morrowc.lists at gmail.com> wrote:
> On Sat, Jan 3, 2009 at 10:49 AM, Steven M. Bellovin
> <smb at cs.columbia.edu> wrote:
> > On Sat, 03 Jan 2009 09:35:06 -0500
> > William Warren <hescominsoon at 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
More information about the NANOG
mailing list