SHA-1 broken

[Marcel Popescu]

http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

As the guy on cypherpunks said, "damn chinese" <g>

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





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/

[Justin Cormack]

Post by Marcel Popescu
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
As the guy on cypherpunks said, "damn chinese" <g>
Marcel

hmm. I was always slightly suspicious of SHA1 due to the last minute change
that was added to it. SOmeone knew something then.

Performance starts to become a major issue with some of these other hash
functions. Anyone one of any pages with up to date performance figures?

Might be worth offernig a choice of hash function in the protocol, for the
paranoid....



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/

[Bill Cox]

Post by Marcel Popescu
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
As the guy on cypherpunks said, "damn chinese" <g>
Marcel

Ouch. 2^69 seems like a lot of searching to find a collision, but it's
a whole lot smaller than our hash key length of 20 bytes, and not all
that much larger than the 56 bits of DES, which has been hacked to
death. 69 bits is probably ok for credit card transactions, but I
wouldn't want to use it to sign Fedora Core releases.

What other choices are there out there that are still considered strong?

I know this is a field with well-paid professionals from several
countries, so my relative ignorance will show, but what the heck.
Digital signatures are fun, too!

How about using multiple signatures? If I find a way to modify data so
that I can spoof the first Merkle hash root, it's unlikely that the same
modification would result in the correct signature of the other. So for
example, I could do some simple transformation on the torrent data, like
xor-ing it with a pseudo random string, and then compute the SHA1 Merkle
hash tree again.

So, we could extend the Merkle hash tree concept to include multiple
root values, perhaps 3 if we're really paranoid? Three times 69 (207)
seems like a reasonable space to have to search for collisions. A
simple use of multiple root hashes would be a double-check after
download was complete. A more complex scheme could require REQUEST and
PIECE messages to include the hash tree number.

Bill





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/

[Olaf van der Spek]

Post by Bill Cox

Post by Marcel Popescu
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
As the guy on cypherpunks said, "damn chinese" <g>
Marcel

Ouch. 2^69 seems like a lot of searching to find a collision, but it's
a whole lot smaller than our hash key length of 20 bytes, and not all

Eh, 20 bytes is 160 bits is 2^160.



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/

[Olaf van der Spek]

Post by Olaf van der Spek

Post by Bill Cox

Post by Marcel Popescu
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
As the guy on cypherpunks said, "damn chinese" <g>
Marcel

Ouch. 2^69 seems like a lot of searching to find a collision, but it's
a whole lot smaller than our hash key length of 20 bytes, and not all

Eh, 20 bytes is 160 bits is 2^160.

Oops, nevermind, I read that the wrong way.



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/

[Marcel Popescu]

Post by Bill Cox
What other choices are there out there that are still considered strong?

SHA-256, SHA-512.

Post by Bill Cox
So, we could extend the Merkle hash tree concept to include multiple
root values, perhaps 3 if we're really paranoid?

Nah. MD5 and SHA-1 should be enough, even if both are broken, and they're
both reasonably fast. (The chance of finding two block with the same hash
for both algorithms is very likely zero.) That is, if there's some reason
not to use SHA-256.

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





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/

[Justin Cormack]

Post by Bill Cox

Post by Marcel Popescu
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
As the guy on cypherpunks said, "damn chinese" <g>
Marcel

Ouch. 2^69 seems like a lot of searching to find a collision, but it's
a whole lot smaller than our hash key length of 20 bytes, and not all
that much larger than the 56 bits of DES, which has been hacked to
death. 69 bits is probably ok for credit card transactions, but I
wouldn't want to use it to sign Fedora Core releases.
What other choices are there out there that are still considered strong?

The SHA2 series (SHA256, 384 and 512) are probably not affected.

SHA256 is about half the speed to calculate as SHA1, and the hash is 32 bytes.
384 and 512 use 64 bit values not 32 in the calculation, and the figures
I have found suggest they are much slower but none of these use MMX or
64 bit machines, which probably make a huge difference. Hash lengths
are rather long. Whirlpool is also 64 bit based, but again has a 64 byte
hash length.

I see Bram submitted a Rijndael based hash to NIST
http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/ (at the bottom)
but they wont consider it as it uses Rijndael with block size 256 which
hasnt been vetted.

Post by Bill Cox
I know this is a field with well-paid professionals from several
countries, so my relative ignorance will show, but what the heck.
Digital signatures are fun, too!
How about using multiple signatures? If I find a way to modify data so
that I can spoof the first Merkle hash root, it's unlikely that the same
modification would result in the correct signature of the other. So for
example, I could do some simple transformation on the torrent data, like
xor-ing it with a pseudo random string, and then compute the SHA1 Merkle
hash tree again.
So, we could extend the Merkle hash tree concept to include multiple
root values, perhaps 3 if we're really paranoid? Three times 69 (207)
seems like a reasonable space to have to search for collisions. A
simple use of multiple root hashes would be a double-check after
download was complete. A more complex scheme could require REQUEST and
PIECE messages to include the hash tree number.

Cryptography. Dont try it at home. Lots of reasons why not.

Post by Bill Cox
Bill
Yahoo! Groups Links

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/

[Harold Feit - Depthstrike.com Administrator]

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

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.

The hash blocks are always fixed within a torrent (except for the
final block) at a specified value within the .torrent metadata. When
a hash algorithm finds collisions on two different-sized pieces of
data, it is not as much of a concern for users using those algorithms
for file hashing since a same-sized collision is required.

Invalidating hash algorithms for file verification operations is a
lot harder than just invalidating them for general use because of the
fixed-size restriction placed.

The amount of CPU time required to break SHA1's use in BT is far more
than the amount of CPU time used to break SHA1's use in
variable-sized messages.

SHA1 is still more secure in BT's use than general use because of the
amount of information already known about the pieces.

The Edonkey implementation of MD4 is still more secure than the base
MD4 implementation for similar reasons.

We don't need to worry at all unless a same-sized collision has been
found.

- -----Original Message-----
From: Marcel Popescu [mailto:***@yahoo.com]
Sent: Wednesday, February 16, 2005 8:08 AM
To: ***@yahoogroups.com
Subject: [BitTorrent] SHA-1 broken


http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

As the guy on cypherpunks said, "damn chinese" <g>

Marcel


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

iQEVAwUBQhNRRl8nceBm0DUaAQLR3ggAk2TNFIA28jrB9aZA3It4B2zUzrEj3xAB
7kQI2ignrQRT91gwxqpclvcA7gn03OSUBIRtPuKqHRAw5AUYkTRX65IDvgX3PBgn
julYJVjNPay6OTTIkl02jDjjk7Y2XF+4QcF8VZAp04xEU/Uw+PTDo+gi4/0s+Xfv
vUEcJqRfOBb5IVdpQoEey7sNpEMCd65Jfv2geHTG8VKn3kQiUCW0gAWAi/M+CCz3
iFv0ylky94xMW5XW38mlCSm89gV+TGGA/4kWrmQtm3QKw11wZMESICgEiPCbj1en
Piqj1Yvwzg5/lMXVctdcVIBtwXJdHilkEvauaAkyHPFgqWjlsaXgvQ==
=qIi4
-----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:
BitTorrent-***@yahoogroups.com

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

[Justin Cormack]

Post by Harold Feit - Depthstrike.com Administrator
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
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.
The hash blocks are always fixed within a torrent (except for the
final block) at a specified value within the .torrent metadata. When
a hash algorithm finds collisions on two different-sized pieces of
data, it is not as much of a concern for users using those algorithms
for file hashing since a same-sized collision is required.
Invalidating hash algorithms for file verification operations is a
lot harder than just invalidating them for general use because of the
fixed-size restriction placed.
The amount of CPU time required to break SHA1's use in BT is far more
than the amount of CPU time used to break SHA1's use in
variable-sized messages.
SHA1 is still more secure in BT's use than general use because of the
amount of information already known about the pieces.
The Edonkey implementation of MD4 is still more secure than the base
MD4 implementation for similar reasons.
We don't need to worry at all unless a same-sized collision has been
found.

The collisions found for md5 were same size. Because SHA1 has the size
hashed (at the end) it is quite likely they would be same size, though
not necessarily the case.

Some Merkle tree based BT versions might not have all messages of a known
size.

j





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/

[Bill Cox]

Post by Harold Feit - Depthstrike.com Administrator
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

<*> 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/

[Harold Feit - Depthstrike.com Administrator]

-----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:***@viasic.com]
Sent: Wednesday, February 16, 2005 10:50 AM
To: ***@yahoogroups.com
Subject: RE: [BitTorrent] SHA-1 broken

Post by Harold Feit - Depthstrike.com Administrator
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:
BitTorrent-***@yahoogroups.com

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

[Elliott Mitchell]

Post by Bill Cox
Modify the target file, introducing your hack. Then run this simple
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.

Post by Bill Cox
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 <=-- ______/)___/)___/)
\ ( | ***@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 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/

[Bill Cox]

Post by Elliott Mitchell
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.

I think I get it. The Chinese are just saying that in 2^69 random
blocks, typically there will be two that collide, and not that I can
find a random block that matches a specific signature.

Thanks for the clarification.

Bill





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/

[Nick Johnson]

Post by Bill Cox
I think I get it. The Chinese are just saying that in 2^69 random
blocks, typically there will be two that collide, and not that I can
find a random block that matches a specific signature.
Thanks for the clarification.

Slightly more than that: If you picked the blocks randomly, it'd take
2^80 blocks to find a collision. They're claiming a method of choosing
blocks that reduces it to 2^69. If it's anything like the MD5 break, it
seems likely we'll see an improvement that lets you choose all but a
few bytes of the messages yourself. In this case, someone could, for
example, generate two distinct torrents with identical info_hash
values. (Granted 2^69 operations is still high enough it'd take a major
distributed project to do so!)

-Nick Johnson




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/

[Nick Johnson]

Post by Marcel Popescu
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
As the guy on cypherpunks said, "damn chinese" <g>
Marcel

There's a few things worth noting here:
1) The 'break' is a collision attack. This means it's easier than
brute-force (which would be 2^80) to find two blocks that collide. It's
not a preimage attack, though, so you can't take an existing block and
make another one with the same hash. In the case of BT, this would mean
someone could publish a torrent with a chunk (containing garbage
somewhere unimportant) and be able to send another chunk in its place
if they wanted. Not really very useful, that I can see.
2) It's _still_ 2^69 operations. This is a lot of work.
3) It's not published yet. Until qualified cryptographers review the
work, we can't be sure if it's authentic or a mistake.

All that said, it's still the first major crack in SHA-1's security,
and an indication it's time to start considering other hashes. What it
isn't is a disaster.

-Nick Johnson




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/