Re: SHA-1 broken

>From: Bill Cox <[email protected]>
> Modify the target file, introducing your hack.  Then run this simple
> loop:
> 
> while(SHA1(piece) != publishedValue) {
> 	unusedData ^= randomString();
> }
> 
> This should produce a valid signature in about 2^69 itterations.
> Obviously, hardware acceleration is required to make this practical.
> However, I don't see how fixed piece size helps the security.

Incorrect. In order to make this attack work, you need to break the
hash's weakly collision-free property. The attack being mentioned is
against the strongly collision-free property.

The above will still take 2^159 operations on average. Nick Johnson's
explanation gets it right. Someone creating a torrent can make a torrent
with a pair of blocks that both verify with 2^69 work (and note that
neither of the pair can be chosen, you generate 2^69 of them and two of
them match). Someone who isn't the creator still has to attack the weakly
collision-free property and do 2^159 operations.

The strongly collision-free property is important for digital signatures,
where the original content may not of been created by the signer. This
isn't yet a problem for BT, just cause for concern.


>From: Harold Feit - Depthstrike.com Administrator <[email protected]>
> For situations where multiple different hashes are available, such as
> BT's segmented SHA1, a standard file-wide SHA1, MD5, CRC32 and
> Edonkey's segmented MD4, if 2 or more are available to verify a file,
> the amount of CPU time required to find a collision increases. With
> each additional algorithm added, the amount of CPU time grows
> MASSIVELY.
> 
> Perhaps the current solution is to adopt more hash algorithm
> extensions (md5sum, sha1 <this one is file-wide instead of BT's
> segmented>, ed2k) for the torrent metadata as standard rather than
> try to re-work the existing code to a different hash algorithm, since
> finding a size-matched collision that is common to two different hash
> algorithms is far more difficult than finding a collision in just
> one.

Wrong! Getting collisions with multiple hash functions is only _slightly_
harder than finding one pair with the most complex of the hash functions.
You'd need more than 2^69 work, but not a lot more. This is a known fact,
though I don't have a reference handy.

Oh, while I'm on it, matching size doesn't make things harder. *All*
secure hash functions in use include the amount of data run through them
during the hash operation. Most of the attacks found already require the
colliding pair to be the same size, so adding the requirement that both
blocks be the same size doesn't effect things in the slightest. In fact
specifying that the colliding pair be of different size would make thing
more difficult.


I think I'll have to add what Justin Cormack said to my collection of
quotes "Cryptography. Dont try it at home. Lots of reasons why not."

So in summary, this is cause for _concern_, but not yet a problem for
BitTorrent.


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         [email protected] 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 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:
    [email protected]

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