[BitTorrent] SHA-0 Broken, MD5 Rumored Broken

Marcel Popescu mdpopescu at yahoo.com
Sat Aug 28 07:31:24 EDT 2004


From: "Elliott Mitchell" <ehem at m5p.com>

> >From: Marcel Popescu <mdpopescu at yahoo.com>

> > The only problem with SHA-1 is theoretical so far: you can generate 2^80
> > collisions with "only" 80 * 2^80 work, instead of the theoretical 2^80 *
> > 2^80. That's bad (and it will, according to the guys on the cypherpunks
>
> You're missing something here, your numbers don't make sense. 2^80 * 2^80
> is the amount of work required to break it by pure brute force.

Yes, which was why I said "the theoretical...". In theory, you can break any
160-bit hash with 2^160 work. These guys discovered an attack that works
with only an 80 * 2^80 effort. I wrote 2^160 as 2^80 * 2^80 to compare these
numbers - in other words, they "shrunk" a 2^80 down to an 80.

> > groups, lead to new research in the field), but only bad in the sense of
> > "the Sun might burn out in only 4 billion years, instead of 5". No need
to
> > worry about it.
>
> At least as far as BitTorrent is concerned, yes. For digital signatures
> this is a severe problem.

No, it's not. It's a severe problem with MD5 and SHA-0, which have been
broken far worse. For SHA-1, the required 80 * 2^80 work for a collision is
still far too great to be of any practical use - even for digital
signatures. With 10^6 attempts / second, 10^5 seconds / day, and 10^3 days /
year, you still need 800 billion years for a collision. (2^80 = 10^24; 10^24
/ (10^6 * 10^5 * 10^3) = 10^10; the required work is not just 2^80, but 80 *
2^80 - ok, the next collisions are cheaper than that, but let's worry about
the Sun first, ok?)

Marcel




------------------------ Yahoo! Groups Sponsor --------------------~--> 
$9.95 domain names from Yahoo!. Register anything.
http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 



More information about the BitTorrent mailing list