RE: SHA-1 broken

 
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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.

We can agree however that the difference between a same-sized piece
collision and a different-sized piece collision is significant in the
realm of BT file verification.

- -----Original Message-----
From: Bill Cox [mailto:[email protected]] 
Sent: Wednesday, February 16, 2005 10:50 AM
To: [email protected]
Subject: RE: [BitTorrent] SHA-1 broken


> BitTorrent is a bit more secure about its overall use of SHA1 than
> just a basic hash since the hashed data has a known size. With that
> known size, the scope of data that can cause a colission is a LOT
> smaller.

Well... here's a dumb simple algorithm to hack a fedora core release
BitTorrent file, which uses the fixed size.

Find the file you wish to corrupt (there are VERY many that will do
if
all you want is a back-door).

Find a file no one uses in the piece containing the file you want to
corrupt.  This should be easy, as pieces are 1M byte.

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.

Bill




 
Yahoo! Groups Links



 




- -- 
No virus found in this incoming message.
Checked by AVG Anti-Virus.
Version: 7.0.300 / Virus Database: 265.8.8 - Release Date: 2/14/2005
 

- -- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.300 / Virus Database: 265.8.8 - Release Date: 2/14/2005
 

-----BEGIN PGP SIGNATURE-----
Version: PGP 8.0.3

iQEVAwUBQhN9M18nceBm0DUaAQI88Qf6A11MMQqv05rC6e4Vk9QTTs/3UqMRcrGD
iBvsN86GeGT1hqnCE8AyuN/mAE8SP5yIbmsTd+5uLHRH1eGK9V4Uk0WIISHAOXlE
m21sZqKcrxNqBCVAslbABEEjwSu4HUruOwmQRpgqwXsjfXc0sn6Crw2+9AHyYd3Y
dyb5tHNG3LYkhml6gzUAv1FIO5Tv3YyrilqhB9kR8vFOJEvI2l6JO7E4xgMypD1C
ZNaEUFs2VVpvId/3pS2eyF9Q4PakYlIcoUPaJcQophzd5TweTtFw3/BSFMrMkCbw
qq88zgxaDa4zFXtlnZvyKv/ftBoHb+xIC0XN0t5+T8n6lQBKQivDOg==
=CBoS
-----END PGP SIGNATURE-----




 
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/