We all know about MD5 hash collisions but I have never imagined that so much progress has been made. Meaningful hash collisions can now be computed on desktop grade hardware. The below collision was computed using unicoll on an i3 desktop in under 30 minutes. Position of byte differences have been marked using ". Thanks to SANS Holiday Hack 2020 for introducing this subject at an approachable level.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | $ strings collision1.bin | head -n 1
I, Benjamin Lim, in my lifetime, confess to the murder of a total no. of 0 people/person.
$ strings collision2.bin | head -n 1
I, Benjamin Lim, in my lifetime, confess to the murder of a total no. of 1 people/person.
$ md5sum collision*
f3f2f56ac8fbf44e1c326c19a93fe61c collision1.bin
f3f2f56ac8fbf44e1c326c19a93fe61c collision2.bin
$ # MD5 is truly dead!
$ xxd collision1.bin
00000000: 492c 2042 656e 6a61 6d69 6e20 4c69 6d2c I, Benjamin Lim,
00000010: 2069 6e20 6d79 206c 6966 6574 696d 652c in my lifetime,
00000020: 2063 6f6e 6665 7373 2074 6f20 7468 6520 confess to the
00000030: 6d75 7264 6572 206f 6620 6120 746f 7461 murder of a tota
00000040: 6c20 6e6f 2e20 6f66"2030"2070 656f 706c l no. of 0 peopl
00000050: 652f 7065 7273 6f6e 2e00 0000 6bdd 3173 e/person....k.1s
00000060: deb5 ffc3 9acc f17c 2ce2 2479 cdca af68 .......|,.$y...h
00000070: 14a7 ec3f 4c02 e12b 1431 426d 262d 6bf8 ...?L..+.1Bm&-k.
00000080: c065 0ec7 c95d 6242"0f03"d406 aa38 d395 .e...]bB.....8..
00000090: 51ea fedf a78c b650 7a48 da5e 3f3e c2b5 Q......PzH.^?>..
000000a0: 7db7 8087 6312 a0f8 036f e1d6 f50e 6e99 }...c....o....n.
000000b0: f315 2240 c9a2 0d77 4943 558b 15c7 6440 .."@...wICU...d@
$ xxd collision2.bin
00000000: 492c 2042 656e 6a61 6d69 6e20 4c69 6d2c I, Benjamin Lim,
00000010: 2069 6e20 6d79 206c 6966 6574 696d 652c in my lifetime,
00000020: 2063 6f6e 6665 7373 2074 6f20 7468 6520 confess to the
00000030: 6d75 7264 6572 206f 6620 6120 746f 7461 murder of a tota
00000040: 6c20 6e6f 2e20 6f66"2031"2070 656f 706c l no. of 1 peopl
00000050: 652f 7065 7273 6f6e 2e00 0000 6bdd 3173 e/person....k.1s
00000060: deb5 ffc3 9acc f17c 2ce2 2479 cdca af68 .......|,.$y...h
00000070: 14a7 ec3f 4c02 e12b 1431 426d 262d 6bf8 ...?L..+.1Bm&-k.
00000080: c065 0ec7 c95d 6242"0f02"d406 aa38 d395 .e...]bB.....8..
00000090: 51ea fedf a78c b650 7a48 da5e 3f3e c2b5 Q......PzH.^?>..
000000a0: 7db7 8087 6312 a0f8 036f e1d6 f50e 6e99 }...c....o....n.
000000b0: f315 2240 c9a2 0d77 4943 558b 15c7 6440 .."@...wICU...d@
|
The generation process is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 | $ xxd message.bin
00000000: 492c 2042 656e 6a61 6d69 6e20 4c69 6d2c I, Benjamin Lim,
00000010: 2069 6e20 6d79 206c 6966 6574 696d 652c in my lifetime,
00000020: 2063 6f6e 6665 7373 2074 6f20 7468 6520 confess to the
00000030: 6d75 7264 6572 206f 6620 6120 746f 7461 murder of a tota
00000040: 6c20 6e6f 2e20 6f66 2030 2070 656f 706c l no. of 0 peopl
00000050: 652f 7065 7273 6f6e 2e00 0000 e/person....
/hashclash/scripts/poc_no.sh message.bin
MD5 differential path toolbox
Copyright (C) 2009 Marc Stevens
http://homepages.cwi.nl/~stevens/
delta_m[2] = [!8!]
In-block prefix words: 7
Parsed path:
Q-3: |00010100 10010010 01110101 01110000|
Q-2: |00011010 10110110 00011101 10001110|
Q-1: |10110111 00001111 01000010 11111100|
Q0: |11001010 11000000 10000111 11010111| ok p=1
Q1: |10011011 01101011 00100000 01001101| ok p=1
Q2: |10101110 11101011 10010001 11010000| ok p=1
Q3: |10000+-1 01100111 10111101 01000101| ok p=1
Q4: |011000+0 0000110+ 10010011 11011010| ok p=1
Q5: |-------1 1000010+ 11100100 10011-++| ok p=1
Q6: |101001+1 110110+- +-0+00++ --1-++++| ok p=1
Q7: |+-+10-00 +0011+01 011+00-1 0+1010+-| ok p=0.0253906
Q8: |+.+...-. +......+ ...+.-.+ .+.-.+.+|
Saving data/path_prefix.bin...done.
Continuing in 3 seconds...
Extend MD5 differential paths forward
Copyright (C) 2009 Marc Stevens
http://homepages.cwi.nl/~stevens/
delta_m[2] = [!8!]
...
8192 0
16384 0
32768 0
65536 0
115866 1
121381 2
131072 2
179993 4
262144 6
311107 8
Block 1: ./data/coll1_66747968
c0 65 0e c7 c9 5d 62 42 0f 02 d4 06 aa 38 d3 95
51 ea fe df a7 8c b6 50 7a 48 da 5e 3f 3e c2 b5
7d b7 80 87 63 12 a0 f8 03 6f e1 d6 f5 0e 6e 99
f3 15 22 40 c9 a2 0d 77 49 43 55 8b 15 c7 64 40
Block 2: ./data/coll2_66747968
c0 65 0e c7 c9 5d 62 42 0f 03 d4 06 aa 38 d3 95
51 ea fe df a7 8c b6 50 7a 48 da 5e 3f 3e c2 b5
7d b7 80 87 63 12 a0 f8 03 6f e1 d6 f5 0e 6e 99
f3 15 22 40 c9 a2 0d 77 49 43 55 8b 15 c7 64 40
Found collision!
f3f2f56ac8fbf44e1c326c19a93fe61c collision1.bin
f3f2f56ac8fbf44e1c326c19a93fe61c collision2.bin
9d532ab75da9aaaaf7210748f3c4678a0ffb2b25 collision1.bin
2d7ff13b9c83243e722fc51b67128f49e5ec6d0f collision2.bin
4 -rw-r--r-- 1 root root 192 Dec 31 08:21 collision1.bin
4 -rw-r--r-- 1 root root 192 Dec 31 08:21 collision2.bin
|