[BitTorrent] SHA-0 Broken, MD5 Rumored Broken

Elliott Mitchell ehem at m5p.com
Fri Aug 27 17:43:02 EDT 2004

>From: Martin Nilsson <yahoo at mani.user.lysator.liu.se>
> Also note that the hashes are not only dependent of hash algorithm, but 
> also of the chosen block size. If the clients are allowed to select the 
> piece length (think multiple TTH strings in a torrent, for different 
> piece lengths) I would be very impressed to see someone creating a 
> trashing seed.

Dead wrong. You simply attack pieces one at a time. In the case of
including multiple Merkel hashes, once you've attacked a number of blocks
of the smallest size to equal the next size up, you work harder and
produce a dual match (harder, but depending on the severity of the break
maybe not much).

If only the hashes remain weakly collision free, this attack can only be
carried out by the original source of the torrent (because only they can
adjust the original to find these matches). Given that you're pretty much
at the mercy of the torrent originator anyway, this isn't a huge deal,
but it is still a very real attack.

>From: Marcel Popescu <mdpopescu at yahoo.com>
> From: "Elliott Mitchell" <ehem at m5p.com>
> > Interestingly if there is a break and it only affects the strongly
> > collision free property of SHA-1, then you could make breakable files.
> > Use slack (comments fields, any chunks that will be thrown out) in your
> > file(s) to make a file with matching hashes. Once past a certain date
> > you can thoroughly kill the file.
> 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.

> 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.

> What HAS been broken are MD5 (completely) and SHA-0 (apparently here only a
> collision was found, but the consensus is that the algorithm is doomed
> anyway). However, since it's been obsolete for a lot of years, that doesn't
> really matter.

I've seen mentions suggesting they've broken MD5's strongly collision
free property, but this isn't a complete break. Digital signatures
require strongly collision free hashes, BitTorrent only requires a weakly
collision free hash (unless you need to stop the originator from
producing a torrent killer too).

Still, only a cause for concern with respect to BitTorrent at the moment
(a concern because there could be a bigger break on the horizon).

(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/

------------------------ Yahoo! Groups Sponsor --------------------~--> 
$9.95 domain names from Yahoo!. Register anything.

Yahoo! Groups Links

<*> To visit your group on the web, go to:

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

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list