MD5 collision confirmed
Well, I guess that's confirmed. Someone just sent me the messages in question, and yep, those are very definitely two different files that hash to the same thing. Still got no idea of course how they did it. But I guess they've proved they have.
Anyone out there looking for a good crypto guy to replace a lotta MD5 stuff, you know where to find me.
Hex dumps of the messages in question, in case you're curious:
MSG1:
D1 31 DD 02 C5 E6 EE C4 69 3D 9A 06 98 AF F9 5C
2F CA B5 87 12 46 7E AB 40 04 58 3E B8 FB 7F 89
55 AD 34 06 09 F4 B3 02 83 E4 88 83 25 71 41 5A
08 51 25 E8 F7 CD C9 9F D9 1D BD F2 80 37 3C 5B
96 0B 1D D1 DC 41 7B 9C E4 D8 97 F4 5A 65 55 D5
35 73 9A C7 F0 EB FD 0C 30 29 F1 66 D1 09 B1 8F
75 27 7F 79 30 D5 5C EB 22 E8 AD BA 79 CC 15 5C
ED 74 CB DD 5F C5 D3 6D B1 9B 0A D8 35 CC A7 E3
MSG2:
D1 31 DD 02 C5 E6 EE C4 69 3D 9A 06 98 AF F9 5C
2F CA B5 07 12 46 7E AB 40 04 58 3E B8 FB 7F 89
55 AD 34 06 09 F4 B3 02 83 E4 88 83 25 F1 41 5A
08 51 25 E8 F7 CD C9 9F D9 1D BD 72 80 37 3C 5B
96 0B 1D D1 DC 41 7B 9C E4 D8 97 F4 5A 65 55 D5
35 73 9A 47 F0 EB FD 0C 30 29 F1 66 D1 09 B1 8F
75 27 7F 79 30 D5 5C EB 22 E8 AD BA 79 4C 15 5C
ED 74 CB DD 5F C5 D3 6D B1 9B 0A 58 35 CC A7 E3
... both hash to: a4c0d35c95a63a805915367dcfe6b751
For you non-crypto folk out there, what this essentially means is that you can modify messages other folk have signed as legitimately having come from them, make it look like they've said something other than they did--in the cases in which the message is hashed with MD5, and the hash is then signed using some asymmetric signature scheme--which is a fairly common thing to do when generating digital signatures. You can't make it look like they've said whatever you please, but you can mess with the message in certain finite ways. You can also alter files authenticated using a published MD5 hash, which could also lead to some mischief--though in practical terms doing anything so complicated as inserting trojans is unlikely to be particularly workable (breaking things by flipping bits here and there, on the other hand, may prove quite easy). The ramifications will probaby be that MD5 isn't going to be in use much as a hash any more, and a number of protocol specifications are probably going to have to be updated to eliminate its use. Since MD5 is an extremely common hash function--one of the top two in use--this will definitely affect a large amount of code.
Anyone out there looking for a good crypto guy to replace a lotta MD5 stuff, you know where to find me.
Hex dumps of the messages in question, in case you're curious:
MSG1:
D1 31 DD 02 C5 E6 EE C4 69 3D 9A 06 98 AF F9 5C
2F CA B5 87 12 46 7E AB 40 04 58 3E B8 FB 7F 89
55 AD 34 06 09 F4 B3 02 83 E4 88 83 25 71 41 5A
08 51 25 E8 F7 CD C9 9F D9 1D BD F2 80 37 3C 5B
96 0B 1D D1 DC 41 7B 9C E4 D8 97 F4 5A 65 55 D5
35 73 9A C7 F0 EB FD 0C 30 29 F1 66 D1 09 B1 8F
75 27 7F 79 30 D5 5C EB 22 E8 AD BA 79 CC 15 5C
ED 74 CB DD 5F C5 D3 6D B1 9B 0A D8 35 CC A7 E3
MSG2:
D1 31 DD 02 C5 E6 EE C4 69 3D 9A 06 98 AF F9 5C
2F CA B5 07 12 46 7E AB 40 04 58 3E B8 FB 7F 89
55 AD 34 06 09 F4 B3 02 83 E4 88 83 25 F1 41 5A
08 51 25 E8 F7 CD C9 9F D9 1D BD 72 80 37 3C 5B
96 0B 1D D1 DC 41 7B 9C E4 D8 97 F4 5A 65 55 D5
35 73 9A 47 F0 EB FD 0C 30 29 F1 66 D1 09 B1 8F
75 27 7F 79 30 D5 5C EB 22 E8 AD BA 79 4C 15 5C
ED 74 CB DD 5F C5 D3 6D B1 9B 0A 58 35 CC A7 E3
... both hash to: a4c0d35c95a63a805915367dcfe6b751
For you non-crypto folk out there, what this essentially means is that you can modify messages other folk have signed as legitimately having come from them, make it look like they've said something other than they did--in the cases in which the message is hashed with MD5, and the hash is then signed using some asymmetric signature scheme--which is a fairly common thing to do when generating digital signatures. You can't make it look like they've said whatever you please, but you can mess with the message in certain finite ways. You can also alter files authenticated using a published MD5 hash, which could also lead to some mischief--though in practical terms doing anything so complicated as inserting trojans is unlikely to be particularly workable (breaking things by flipping bits here and there, on the other hand, may prove quite easy). The ramifications will probaby be that MD5 isn't going to be in use much as a hash any more, and a number of protocol specifications are probably going to have to be updated to eliminate its use. Since MD5 is an extremely common hash function--one of the top two in use--this will definitely affect a large amount of code.
posted by AJM at 11:50 a.m. (Permanent Link)
