Joseph Ashwood
2005-02-16 08:29:08 UTC
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-***@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
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-***@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/