[BitTorrent] SHA1 (Bram should also take notice)

Joseph Ashwood ashwood at msn.com
Wed Feb 16 03:29:08 EST 2005


I apologize for not replying in some time but I decided to quickly post a 
new message on something that substantially changes the Merkle question.

SHA-1 is broken. 
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

This casts doubt on the entire SHA line, simply because the SHA-256/384/512 
designs are simple scalings of the SHA-1 design.

The breaking of SHA-1 has definite ramifications for the hash tree of any 
form, and has the possibility of slanting the entire computation structure 
(the SHA-2 series is much slower, crypto++ shows speeds of SHA-1 68 MB/sec, 
SHA-256 44.5 MB/sec, and SHA-512 11.4 MB/sec). This imposes a larger penalty 
for stopping and restarting the hashing (e.g. with binary Merkle trees, or 
small leaf nodes).

Now on to the more immediate issues. The break of SHA-1 is of the free 
collision type, that is:
Find A and B such that
A <> B
SHA-1(A) == SHA-1(B)

The attack takes 2^69 operations. The cost of this attack is currently 
substantial*, and is no need to immediately revoke all SHA-1 uses, but it is 
necessary to immediately begin the plans to decommision SHA-1 in favor of a 
hash function that has not been broken. Additionally, while this retooling 
is happening it is probably worth the small extra effort to allow the hash 
function to be replaced arbitrarily, for example by including a "hash" 
identifier in the torrent file.

                Joe



* To give a more solid grounding in the estimated cost of attack, in 1998 
2^56 work was performed in 72 hours by a $250,000 semi-custom DSP rig. 
Scaling this to today, and assuming a $500,000 investment, this can be moved 
to a full custom design, and should scale to the necessary 2^69 work in 36 
hours, with an error factor of +- a couple orders of magnitude due to the 
complicated nature of moving from DSP to custom. This attack is realizable, 
but costly. It is unlikely that any torrents will be attacked using it in 
the foreseeable future, but it is necesary to begin decommisioning SHA-1 in 
every use including BitTorrent. 



 
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