Re: [Python-Dev] SHA-256 module
[Michael Hudson, on 30 June 2004]
Nevertheless, am I right to still believe that there are no known distinct strings which even MD5 to the same hash?
[Andrew Kuchling]
Correct.
And two months later, the world is all different again: """ import md5 S = ('\xd11\xdd\x02\xc5\xe6\xee\xc4i=\x9a\x06\x98\xaf\xf9\\' '/\xca\xb5\x87\x12F~\xab@\x04X>\xb8\xfb\x7f\x89U\xad4' '\x06\t\xf4\xb3\x02\x83\xe4\x88\x83%qAZ\x08Q%\xe8\xf7' '\xcd\xc9\x9f\xd9\x1d\xbd\xf2\x807<[\x96\x0b\x1d\xd1' '\xdcA{\x9c\xe4\xd8\x97\xf4ZeU\xd55s\x9a\xc7\xf0\xeb' '\xfd\x0c0)\xf1f\xd1\t\xb1\x8fu\'\x7fy0\xd5\\\xeb"' '\xe8\xad\xbay\xcc\x15\\\xedt\xcb\xdd_\xc5\xd3m\xb1' '\x9b\n\xd85\xcc\xa7\xe3') T = ('\xd11\xdd\x02\xc5\xe6\xee\xc4i=\x9a\x06\x98\xaf\xf9\\' '/\xca\xb5\x07\x12F~\xab@\x04X>\xb8\xfb\x7f\x89U\xad4' '\x06\t\xf4\xb3\x02\x83\xe4\x88\x83%\xf1AZ\x08Q%\xe8\xf7' '\xcd\xc9\x9f\xd9\x1d\xbdr\x807<[\x96\x0b\x1d\xd1\xdcA{' '\x9c\xe4\xd8\x97\xf4ZeU\xd55s\x9aG\xf0\xeb\xfd\x0c0)' '\xf1f\xd1\t\xb1\x8fu\'\x7fy0\xd5\\\xeb"\xe8\xad\xbayL' '\x15\\\xedt\xcb\xdd_\xc5\xd3m\xb1\x9b\nX5\xcc\xa7\xe3') assert S != T print md5.new(S).hexdigest() print md5.new(T).hexdigest() print "oops" """ A number of hash functions got cracked since this thread started, by some researchers in China: http://eprint.iacr.org/2004/199.pdf MD5 is truly dead now for "secure" applications. Maybe someone who gives a rip <wink> could update the docs. Best I understand it, SHA-1 still stands, although a variant with half the rounds has been cracked. It does increase the desirability (IMO) of adding SHA-256, lest SHA-1 get cracked too while Python 2.4.j is still current.
Tim Peters <tim.peters@gmail.com> writes:
[Michael Hudson, on 30 June 2004]
Nevertheless, am I right to still believe that there are no known distinct strings which even MD5 to the same hash?
[Andrew Kuchling]
Correct.
And two months later, the world is all different again:
Heh, I'd already blogged about that: http://starship.python.net/crew/mwh/blog/nb.cgi/view/weblog/2004/08/18/0
""" import md5
S = ('\xd11\xdd\x02\xc5\xe6\xee\xc4i=\x9a\x06\x98\xaf\xf9\\' '/\xca\xb5\x87\x12F~\xab@\x04X>\xb8\xfb\x7f\x89U\xad4' '\x06\t\xf4\xb3\x02\x83\xe4\x88\x83%qAZ\x08Q%\xe8\xf7' '\xcd\xc9\x9f\xd9\x1d\xbd\xf2\x807<[\x96\x0b\x1d\xd1' '\xdcA{\x9c\xe4\xd8\x97\xf4ZeU\xd55s\x9a\xc7\xf0\xeb' '\xfd\x0c0)\xf1f\xd1\t\xb1\x8fu\'\x7fy0\xd5\\\xeb"' '\xe8\xad\xbay\xcc\x15\\\xedt\xcb\xdd_\xc5\xd3m\xb1' '\x9b\n\xd85\xcc\xa7\xe3')
T = ('\xd11\xdd\x02\xc5\xe6\xee\xc4i=\x9a\x06\x98\xaf\xf9\\' '/\xca\xb5\x07\x12F~\xab@\x04X>\xb8\xfb\x7f\x89U\xad4' '\x06\t\xf4\xb3\x02\x83\xe4\x88\x83%\xf1AZ\x08Q%\xe8\xf7' '\xcd\xc9\x9f\xd9\x1d\xbdr\x807<[\x96\x0b\x1d\xd1\xdcA{' '\x9c\xe4\xd8\x97\xf4ZeU\xd55s\x9aG\xf0\xeb\xfd\x0c0)' '\xf1f\xd1\t\xb1\x8fu\'\x7fy0\xd5\\\xeb"\xe8\xad\xbayL' '\x15\\\xedt\xcb\xdd_\xc5\xd3m\xb1\x9b\nX5\xcc\xa7\xe3')
assert S != T print md5.new(S).hexdigest() print md5.new(T).hexdigest() print "oops" """
A number of hash functions got cracked since this thread started, by some researchers in China:
Is there any resource that explains these guys results any more fully? The only examples I've seen only differ in a very few bits.
MD5 is truly dead now for "secure" applications.
I'd say it's resting :)
Maybe someone who gives a rip <wink> could update the docs.
Best I understand it, SHA-1 still stands, although a variant with half the rounds has been cracked. It does increase the desirability (IMO) of adding SHA-256, lest SHA-1 get cracked too while Python 2.4.j is still current.
I'm hardly an expert, but I'd still like to know more about this attack. If it's as limited as it could possibly be (i.e. it can only make very specific strings differing by a handful of bits hash the same) then it's only an issue for the paranoid. If it's as wide as it could possibly be it seems that all hash functions we currently know could be doomed. Cheers, mwh -- Q: Isn't it okay to just read Slashdot for the links? A: No. Reading Slashdot for the links is like having "just one hit" off the crack pipe. -- http://www.cs.washington.edu/homes/klee/misc/slashdot.html#faq
[Tim Peters] ...
A number of hash functions got cracked since this thread started, by some researchers in China:
[Michael Hudson]
Is there any resource that explains these guys results any more fully?
Not that I know of. I've read that they're writing a paper on *how* their approach works, but it will take time to finish it. There's no doubt that they're on to something. Apparently the first version of the paper provided collisions for a hash that wasn't actually MD5, due (at least) to confusing endianness in places. This was pointed out at the conference, and by the next morning they produced two collisions for "the real" MD5.
The only examples I've seen only differ in a very few bits.
Probably due to the method, which apparently makes a sequence of small, controlled changes, based more on analysis than on brute force. Given the uses of MD5 for verifying downloads, it doesn't take much of a change to open "a security hole" in C code, so even if they can't extend the method beyond a few bits' difference, that would be cold comfort. I note that they got to pick both msgs here, and haven't claimed to be able to derive a collision for a given msg. When more about their method is known, it may or may not prove feasible to extend.
MD5 is truly dead now for "secure" applications.
I'd say it's resting :)
I based "truly dead" on press reaction. MD5 had been falling out of favor for years anyway (due to earlier cracks of various weakened versions); this is just nail-in-the-coffin news.
... I'm hardly an expert, but I'd still like to know more about this attack. If it's as limited as it could possibly be (i.e. it can only make very specific strings differing by a handful of bits hash the same) then it's only an issue for the paranoid. If it's as wide as it could possibly be it seems that all hash functions we currently know could be doomed.
Security weenies are paranoid by necessity -- paranoia is part of their field. I'm not sure there's ever been a real-world attack based on a "double free" bug, for example, but finding such a bug is sufficient to kill a product release anyway. They don't claim to have an attack against SHA-1, BTW. Someone else reported collisions using a grossly weakened SHA-1, with 42 rounds instead of 80.
Michael Hudson wrote:
I'm hardly an expert, but I'd still like to know more about this attack. If it's as limited as it could possibly be (i.e. it can only make very specific strings differing by a handful of bits hash the same) then it's only an issue for the paranoid. If it's as wide as it could possibly be it seems that all hash functions we currently know could be doomed.
The nicest summary I have seen on this so far was Tim Churches' message <mailman.3198.1094942493.5135.python-list@python.org>. In his terminology, "collision resistance" has been attacked (i.e. it is now possible to create pairs of plaintext that hash same). "Preimage resistance" and "2nd preimage resistance" remain unattacked, atleast wrt. to this paper. IOW, it is still not possible to easily reconstruct some plaintext given the hash (good for password hashing), and it is still not possible to modify a given plaintext so that it still hashes same (good for signing). However, the trust into "pseudo-randomness" of the hash is gone now - for a cryptographically "secure" hash, it should not be possible to create a collision until the sun collapses. Regards, Martin
participants (3)
-
"Martin v. Löwis" -
Michael Hudson -
Tim Peters