Re: Security team successfully cracks SSL using 200 PS3's and MD5

["Steven M. Bellovin" <smb () cs columbia edu>]

On Sat, 3 Jan 2009 12:31:53 -0500
"Christopher Morrow" <morrowc.lists () gmail com> wrote:

> On Sat, Jan 3, 2009 at 10:49 AM, Steven M. Bellovin
> <smb () cs columbia edu> wrote:
> > On Sat, 03 Jan 2009 09:35:06 -0500
> > William Warren <hescominsoon () 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