Re: [p2p-hackers] SHA1 broken? (fwd from [EMAIL PROTECTED])
- Forwarded message from "\"Hal Finney\"" <[EMAIL PROTECTED]> -
From: [EMAIL PROTECTED] ("Hal Finney")
Date: Thu, 17 Feb 2005 14:25:36 -0800 (PST)
To: [EMAIL PROTECTED]
Subject: Re: [p2p-hackers] SHA1 broken?
Reply-To: "Peer-to-peer development." <[EMAIL PROTECTED]>
The problem with the attack scenario where two versions of a program are
created with the same hash, is that from what little we know of the new
attacks, they aren't powerful enough to do this.
All of the collisions they have shown have the property where the two
alternatives start with the same initial value for the hash; they then
have one or two blocks which are very carefully selected, with a few
bits differing between the two blocks; and at the end, they are back
to a common value for the hash.
It is known that their techniques are not sensitive to this initial value.
They actually made a mistake when they published their MD5 collision,
because they had the wrong initial values due to a typo in Schneier's
book. When people gave them the correct initial values, they were able
to come up with new collisions within a matter of hours.
If you look at their MD5 collision in detail, it was two blocks long.
Each block was almost the same as the other, with just a few bits
different. They start with the common initial value. Then they run
the first blocks through. Amazingly, this has only a small impact on
the intermediate value after this first block. Only a relatively few
bits are different.
If you or I tried to take two blocks with a few bits different and feed
them to MD5, we would get totally different outputs. Changing even
one bit will normally change half the output bits. The fact that they
are able to change several bits and get only a small difference in the
output is the first miracle.
But then they do an even better trick. They now go on and do the
second pair of blocks. The initial values for these blocks (which are
the outputs from the previous stage) are close but not quite the same.
And amazingly, these second blocks not only keep things from getting
worse, they manage to heal the differences. They precisely compensate
for the changes and bring the values back together. This is the second
miracle and it is even greater.
Now, it would be a big leap from this to being able to take two arbitrary
different initial values and bring them together to a common output.
That is what would be necessary to mount the code fraud attack. But as
we can see by inspection of the collisions produced by the researchers
(who are keeping their methodology secret for now), they don't seem to
have that power. Instead, they are able to introduce a very carefully
controlled difference between the two blocks, and then cancel it.
Being able to cancel a huge difference between blocks would be a problem
of an entirely different magnitude.
Now, there is this other idea which Zooko alludes to, from Dan Kaminsky,
www.doxpara.com, which could exploit the power of the new attacks to
do something malicious. Let us grant that the only ability we have is
that we can create slightly different pairs of blocks that collide.
We can't meaningfully control the contents of these blocks, and they
will differ in only a few bits. And these blocks have to be inserted
into a program being distributed, which will have two versions that
are *exactly the same* except for the few bits of difference between
the blocks. This way the two versions will have the same hash, and this
is the power which the current attacks seem to have.
Kaminsky shows that you could still have "good" and "bad" versions of
such a program. You'd have to write a program which tested a bit in
the colliding blocks, and behaved "good" if the bit was set, and "bad"
if the bit was clear. When someone reviewed this program, they'd see
the potential bad behavior, but they'd also see that the behavior was
not enabled because the bit that enabled it was not set. Maybe the
bad behavior could be a back door used during debugging, and there is
some flag bit that turns off the debugging mode. So the reviewer might
assume that the program was OK despite this somewhat questionable code,
because he builds it and makes sure to sign or validate the hash when
built in the mode when the bad features are turned off.
But what he doesn't know is, Kaminsky has another block of data prepared
which has that flag bit in the opposite state, and which he can substitute
without changing the hash. That will cause the program to behave in its
"bad" mode, even though the only change was a few bits in this block
of random data. So this way he can distribute a malicious build and it
has the hash which was approved by the reviewer.
And as Zooko points out, this doesn't have to be the main developer
who is doing this, anyone who is doing some work on creat
Re: [p2p-hackers] SHA1 broken?
--- begin forwarded text
Delivered-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: [p2p-hackers] SHA1 broken?
Date: Thu, 17 Feb 2005 14:25:36 -0800 (PST)
From: [EMAIL PROTECTED] ("Hal Finney")
Reply-To: "Peer-to-peer development." <[EMAIL PROTECTED]>
Sender: [EMAIL PROTECTED]
The problem with the attack scenario where two versions of a program are
created with the same hash, is that from what little we know of the new
attacks, they aren't powerful enough to do this.
All of the collisions they have shown have the property where the two
alternatives start with the same initial value for the hash; they then
have one or two blocks which are very carefully selected, with a few
bits differing between the two blocks; and at the end, they are back
to a common value for the hash.
It is known that their techniques are not sensitive to this initial value.
They actually made a mistake when they published their MD5 collision,
because they had the wrong initial values due to a typo in Schneier's
book. When people gave them the correct initial values, they were able
to come up with new collisions within a matter of hours.
If you look at their MD5 collision in detail, it was two blocks long.
Each block was almost the same as the other, with just a few bits
different. They start with the common initial value. Then they run
the first blocks through. Amazingly, this has only a small impact on
the intermediate value after this first block. Only a relatively few
bits are different.
If you or I tried to take two blocks with a few bits different and feed
them to MD5, we would get totally different outputs. Changing even
one bit will normally change half the output bits. The fact that they
are able to change several bits and get only a small difference in the
output is the first miracle.
But then they do an even better trick. They now go on and do the
second pair of blocks. The initial values for these blocks (which are
the outputs from the previous stage) are close but not quite the same.
And amazingly, these second blocks not only keep things from getting
worse, they manage to heal the differences. They precisely compensate
for the changes and bring the values back together. This is the second
miracle and it is even greater.
Now, it would be a big leap from this to being able to take two arbitrary
different initial values and bring them together to a common output.
That is what would be necessary to mount the code fraud attack. But as
we can see by inspection of the collisions produced by the researchers
(who are keeping their methodology secret for now), they don't seem to
have that power. Instead, they are able to introduce a very carefully
controlled difference between the two blocks, and then cancel it.
Being able to cancel a huge difference between blocks would be a problem
of an entirely different magnitude.
Now, there is this other idea which Zooko alludes to, from Dan Kaminsky,
www.doxpara.com, which could exploit the power of the new attacks to
do something malicious. Let us grant that the only ability we have is
that we can create slightly different pairs of blocks that collide.
We can't meaningfully control the contents of these blocks, and they
will differ in only a few bits. And these blocks have to be inserted
into a program being distributed, which will have two versions that
are *exactly the same* except for the few bits of difference between
the blocks. This way the two versions will have the same hash, and this
is the power which the current attacks seem to have.
Kaminsky shows that you could still have "good" and "bad" versions of
such a program. You'd have to write a program which tested a bit in
the colliding blocks, and behaved "good" if the bit was set, and "bad"
if the bit was clear. When someone reviewed this program, they'd see
the potential bad behavior, but they'd also see that the behavior was
not enabled because the bit that enabled it was not set. Maybe the
bad behavior could be a back door used during debugging, and there is
some flag bit that turns off the debugging mode. So the reviewer might
assume that the program was OK despite this somewhat questionable code,
because he builds it and makes sure to sign or validate the hash when
built in the mode when the bad features are turned off.
But what he doesn't know is, Kaminsky has another block of data prepared
which has that flag bit in the opposite state, and which he can substitute
without changing the hash. That will cause the program to behave in its
"bad" mode, even though the only change was a few bits in this block
of random data. So this way he can distribute a malicious build and it
has the hash which was approved by the reviewer.
And as Zooko points out, this doesn't have to be the main developer
who is doing this, anyone who is doing some work on creating the final
packa
Re: [p2p-hackers] SHA1 broken?
On Wed, Feb 16, 2005 at 07:55:15AM -0500, R.A. Hettinga wrote: > From: "Serguei Osokine" <[EMAIL PROTECTED]> > To: "Peer-to-peer development." <[EMAIL PROTECTED]> > Subject: RE: [p2p-hackers] SHA1 broken? > Date: Wed, 16 Feb 2005 00:11:07 -0800 > > Okay, so the effective SHA-1 length is 138 bits instead of full > 160 - so what's the big deal? It is still way more than, say, MD5 In applications where collisions are important, SHA1 is now effectively 69 bits as opposed to 80. That's not very much, and odds are there will be an improvement on this attack in the near future. Eric
RE: [p2p-hackers] SHA1 broken?
--- begin forwarded text Delivered-To: [EMAIL PROTECTED] From: "Serguei Osokine" <[EMAIL PROTECTED]> To: "Peer-to-peer development." <[EMAIL PROTECTED]> Subject: RE: [p2p-hackers] SHA1 broken? Date: Wed, 16 Feb 2005 00:11:07 -0800 Reply-To: [EMAIL PROTECTED], "Peer-to-peer development." <[EMAIL PROTECTED]> Sender: [EMAIL PROTECTED] > # * collisions in the the full SHA-1 in 2**69 hash operations, > # much less than the brute-force attack of 2**80 operations... Okay, so the effective SHA-1 length is 138 bits instead of full 160 - so what's the big deal? It is still way more than, say, MD5 length. And MD5 is still widely used for stuff like content id'ing in various systems, because even 128 bits is quite a lot, never mind 138 bits. Best wishes - S.Osokine. 16 Feb 2005. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Gordon Mohr (@ Bitzi) Sent: Tuesday, February 15, 2005 9:41 PM To: p2p-hackers Subject: [p2p-hackers] SHA1 broken? Via Slashdot, as reported by Bruce Schneier: http://www.schneier.com/blog/archives/2005/02/sha1_broken.html Schneier writes: # SHA-1 Broken # # SHA-1 has been broken. Not a reduced-round version. Not a # simplified version. The real thing. # # The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu # (mostly from Shandong University in China) have been quietly # circulating a paper announcing their results: # # * collisions in the the full SHA-1 in 2**69 hash operations, # much less than the brute-force attack of 2**80 operations # based on the hash length. # # * collisions in SHA-0 in 2**39 operations. # # * collisions in 58-round SHA-1 in 2**33 operations. # # This attack builds on previous attacks on SHA-0 and SHA-1, and # is a major, major cryptanalytic result. It pretty much puts a # bullet into SHA-1 as a hash function for digital signatures # (although it doesn't affect applications such as HMAC where # collisions aren't important). # # The paper isn't generally available yet. At this point I can't # tell if the attack is real, but the paper looks good and this # is a reputable research team. # # More details when I have them. - Gordon @ Bitzi ___ p2p-hackers mailing list [EMAIL PROTECTED] http://zgp.org/mailman/listinfo/p2p-hackers ___ Here is a web page listing P2P Conferences: http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences ___ p2p-hackers mailing list [EMAIL PROTECTED] http://zgp.org/mailman/listinfo/p2p-hackers ___ Here is a web page listing P2P Conferences: http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences --- end forwarded text -- - R. A. Hettinga The Internet Bearer Underwriting Corporation <http://www.ibuc.com/> 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
Re: [p2p-hackers] SHA1 broken?
--- begin forwarded text Delivered-To: [EMAIL PROTECTED] Date: Wed, 16 Feb 2005 01:10:13 -0800 From: "Gordon Mohr (@ Bitzi)" <[EMAIL PROTECTED]> User-Agent: Mozilla Thunderbird 1.0 (X11/20041206) To: "Peer-to-peer development." <[EMAIL PROTECTED]> Subject: Re: [p2p-hackers] SHA1 broken? Reply-To: "Peer-to-peer development." <[EMAIL PROTECTED]> Sender: [EMAIL PROTECTED] Serguei Osokine wrote: >># * collisions in the the full SHA-1 in 2**69 hash operations, >># much less than the brute-force attack of 2**80 operations... > > > Okay, so the effective SHA-1 length is 138 bits instead of full > 160 - so what's the big deal? If the results hold up: SHA1 is not as strong as it was designed to be, and its effective strength is being sent in the wrong direction, rather than being confirmed, by new research. Even while maintaining that SHA1 was unbroken and likely to remain so just last week, NIST was still recommending that SHA1 be phased out of government use by 2010: http://www.fcw.com/fcw/articles/2005/0207/web-hash-02-07-05.asp One more paper from a group of precocious researchers anywhere in the world, or unpublished result exploited in secret, could topple SHA1 from practical use entirely. Of course, that's remotely possible with any hash, but the pattern of recent results suggest that a further break is now more likely with SHA1 (and related hashes) than others. So the big deal would be: don't rely on SHA1 in any applications you intend to have a long effective life. > It is still way more than, say, MD5 > length. And MD5 is still widely used for stuff like content id'ing > in various systems, because even 128 bits is quite a lot, never > mind 138 bits. Just because it's widely used doesn't mean it's a good idea. MD5 should not be used for content identification, given the ability to create content pairs with the same MD5, with one version being (and appearing and acquiring a reputation for being) innocuous, and the other version malicious. - Gordon @ Bitzi ___ p2p-hackers mailing list [EMAIL PROTECTED] http://zgp.org/mailman/listinfo/p2p-hackers ___ Here is a web page listing P2P Conferences: http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences --- end forwarded text -- - R. A. Hettinga The Internet Bearer Underwriting Corporation <http://www.ibuc.com/> 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
