Tonight is the “rump session” at the Crypto conference, where researchers can give informal short presentations on up-to-the-minute results.
Biham and Chen have a presentation scheduled, entitled “New Results on SHA-0 and SHA-1”. If there’s an SHA-1 collision announced, they’ll probably be the ones to do it.
Antoine Joux will present his SHA-0 collision. Also the authors of the slightly flawed paper claiming an MD5 collision have a presentation; it seems likely they’ll announce that they’ve fixed their bug and have a collision in MD5.
Each group has been given fifteen minutes, which is a significant departure from the normal five minutes allocated for rump session talks.
The session is tonight; I’ll give you an update as soon as I hear what happened. It will be webcast at 7PM Pacific time, tonight.
I wish I could be there, but I’m on the wrong coast. Anybody who is at Crypto is invited to post updates in the comments section of this post.
Electronic Forgery
What triggered this? A collision in MD5. I am not an expert in cryptography, but I do find this subject fascinating. Here is what I have pieced together so far: What does a collision mean? One thing it does not mean is that somebody can reverse en
So who get’s the award?
http://www.certainkey.com/md5challenge/
comparing these two numbers digs out interestng tidbits:
Here’s the output of a small stringcompare I threw together:
d38: Difference in char 38
b5 8 71
b5 0 71
d52: Difference in char 90
25 7 14
25 f 14
d28: Difference in char 118
bd f 28
bd 7 28
d48: Difference in char 166
9a c 7f
9a 4 7f
d52: Difference in char 218
79 c c1
79 4 c1
d28: Difference in char 246
0a d 83
0a 5 83
I find it interesting that the differing numbers are alle 8 apart and even the positions where they are found hint on a repetitive pattern.
If my program outputs something like this I’d rather check my implementation, but I dont know nothing about cryptography, so I just hope you enjoyed my amateur numerology 😉
For those who want to test using Python:
a = “xd1x31xddx02xc5xe6xeexc4x69x3dx9ax06x98xafxf9x5cx2fxcaxb5x87x12x46x7exabx40x04x58x3exb8xfbx7fx89x55xadx34x06x09xf4xb3x02x83xe4x88x83x25x71x41x5ax08x51x25xe8xf7xcdxc9x9fxd9x1dxbdxf2x80x37x3cx5bxd8x82x3ex31x56x34x8fx5bxaex6dxacxd4x36xc9x19xc6xddx53xe2xb4x87xdax03xfdx02x39x63x06xd2x48xcdxa0xe9x9fx33x42x0fx57x7exe8xcex54xb6x70x80xa8x0dx1exc6x98x21xbcxb6xa8x83x93x96xf9x65x2bx6fxf7x2ax70″b = “xd1x31xddx02xc5xe6xeexc4x69x3dx9ax06x98xafxf9x5cx2fxcaxb5x07x12x46x7exabx40x04x58x3exb8xfbx7fx89x55xadx34x06x09xf4xb3x02x83xe4x88x83x25xf1x41x5ax08x51x25xe8xf7xcdxc9x9fxd9x1dxbdx72x80x37x3cx5bxd8x82x3ex31x56x34x8fx5bxaex6dxacxd4x36xc9x19xc6xddx53xe2x34x87xdax03xfdx02x39x63x06xd2x48xcdxa0xe9x9fx33x42x0fx57x7exe8xcex54xb6x70x80x28x0dx1exc6x98x21xbcxb6xa8x83x93x96xf9x65xabx6fxf7x2ax70″a != bmd5.md5(a).hexdigest() == md5.md5(b).hexdigest()
Note that that 2^40 number is the number of SHA-0 computations. I think Joux’s number is “operations”, so they’re not that far apart.
Eli Biham did not present an attack on full SHA-1 as expected.
The chinese women who presented the md5 attack has a really thick accent and I could not understand much of what she was saying. From what I could read from her slides, it looks like her technique was the differential one that everyone uses, but they looked for the best differential and then determined all the conditions that caused it to occur. With this information, they derived a collison. In fact, it’s general and applies to all the hash functions stated.
Also, her SHA-0 attack appears to have much better complexity bounds (2^40) than either Joux’s (2^51) or Biham’s.
You’re right that the authors of the MD5 collision paper have corrected their bug, and have an actual MD5 collision now. This was posted to sci.crypt, but I’ll repeat here. The following two 1024-bit values (given in hex) produce a collision. I’ve verified this with “md5sum”:
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
960b1dd1dc417b9ce4d897f45a6555d535739ac7f0ebfd0c3029f166d109b18f
75277f7930d55ceb22e8adba79cc155ced74cbdd5fc5d36db19b0ad835cca7e3
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
960b1dd1dc417b9ce4d897f45a6555d535739a47f0ebfd0c3029f166d109b18f
75277f7930d55ceb22e8adba794c155ced74cbdd5fc5d36db19b0a5835cca7e3
(These two 1024-bit values only differ in 6 bit positions)
From their paper, it does not seem likely that Biham and Chen will announce a SHA-1 collision.
http://eprint.iacr.org/2004/146/
The newest version of their SHA-0 collisions paper has a breaking news section where it appears they improve their results by using their SHA-0 near collisions to find collisions. Furthermore, they use their new techniques to find collisions in reduced round SHA-1 (not the full SHA-1).
Lastly, the section concludes with the statement that their attack is unlikely to break the full SHA-1. So if the SHA-1 collision has been found, it’s looks probable that they are not the ones that found it.
CRYPTO 2004 rumblings
Wow, I wish I were in Santa Barbara right now, and not just because it’s beastly humid here in Ithaca. There’s a prominent cryptography conference going on, and there are rumors flying about a paper to be presented that may…
According to http://www.mail-archive.com/cryptography%40metzdowd.com/msg02585.html the rump session will be webcast. The 3 new hash results are the first thing scheduled, from 7:00 to 7:45 PDT.
The rump session is being webcast. See
http://www.rtfm.com/movabletype/archives/2004_08.html#001054
[Thanks. I updated the main posting to reflect this information. — Ed F.]