-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathwangs-attack.html
213 lines (197 loc) · 12.9 KB
/
wangs-attack.html
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
<html>
<head>
<link rel="stylesheet" type="text/css" href="style/main.css"></link>
</head>
<header>
<h1>
<a href="index.html"> Sukun </a>
</h1>
</header>
<h1 id="wangs-attack-for-generating-md4-collisions">Wang’s Attack for
generating MD4 collisions</h1>
<p>Cryptopals Set7 Problem 53 is about finding collisions in MD4 using
wangs attack. In “Cryptanalysis of the Hash Functions MD4 and RIPEMD”
Wang et al describe a method to find collisions in MD4. If you are
interested in implementing this attack and are stuck I suggest looking
for the paper “Improved Collision Attack on MD4 with Probability Almost
1” by Naito et al which describes the attack in more detail than the
original paper. Here I summarise the attack and its implementation</p>
<h3 id="md4">MD4</h3>
<p>MD4 is a hashing algorithm that hashes the input message by first
padding it, dividing the input into blocks of size 64 bytes and then
applying three rounds of transformation to each block.</p>
<p>The pseudocode for md4 copied from <a
href="https://www.ietf.org/rfc/rfc1320.html#section-3.4">RFC
1320</a></p>
<pre><code>First break down the padded message m of size N bytes
into a uint32 array of words M
for i, j := 0, 0; i < N; i, j = i + 4, j+1
M[j] = uint32(m[i: i+4]) // In little endian format
We first define three auxiliary functions that each take as input
three 32-bit words and produce as output one 32-bit word.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XY v XZ v YZ
H(X,Y,Z) = X xor Y xor Z
Do the following:
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */
/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B
CC = C
DD = D
/* Round 1. */
/* Let [abcd k s] denote the operation
a = (a + F(b,c,d) + X[k]) <<< s. */
/* Do the following 16 operations. */
[ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19]
[ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19]
[ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19]
[ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19
/* Round 2. */
/* Let [abcd k s] denote the operation
a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. *
/* Do the following 16 operations. */
[ABCD 0 3] [DABC 4 5] [CDAB 8 9] [BCDA 12 13]
[ABCD 1 3] [DABC 5 5] [CDAB 9 9] [BCDA 13 13]
[ABCD 2 3] [DABC 6 5] [CDAB 10 9] [BCDA 14 13]
[ABCD 3 3] [DABC 7 5] [CDAB 11 9] [BCDA 15 13
/* Round 3. */
/* Let [abcd k s] denote the operation
a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */
/* Do the following 16 operations. */
[ABCD 0 3] [DABC 8 9] [CDAB 4 11] [BCDA 12 15]
[ABCD 2 3] [DABC 10 9] [CDAB 6 11] [BCDA 14 15]
[ABCD 1 3] [DABC 9 9] [CDAB 5 11] [BCDA 13 15]
[ABCD 3 3] [DABC 11 9] [CDAB 7 11] [BCDA 15 15]
/* Then perform the following additions. (That is, increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end /* of loop on i */</code></pre>
<h3 id="wangs-attack">Wang’s attack</h3>
<p>Consider two blocks</p>
<pre><code>M = (m0, m1, ..., m15)
M' = (m'0, m'1, ..., m'15)
such that
ΔM = M' - M = (Δm0, Δm1, Δm2, ... Δm15)
Where
Δm0 = 2^31
Δm1 = 2^31 - 2^28
Δm12 = -2^16
Δmi = 0 for all other is</code></pre>
<p>If the conditions on table 6 in paper are satisfied for block M, M
and M’ will have the same hash. Table 6 in the paper provides a
sufficient set of conditions for M and M’ to have a collision. It was
later found that this set was not sufficient and Naito et al added two
more conditions to the set.</p>
<p>Our aim is to find an M such that it satisfies all these conditions.
Just trying random Ms is infeasible. But as we will see a lot of these
conditions can be fixed by taking a random M and applying simple
transformations to M.</p>
<p>The algorithm for finding a collision is</p>
<pre><code> M = random bytes
for i from 1..18
if M does not satisfy the conditions of step i in table 6
transform M to satisfy condition</code></pre>
<p>There are two kinds of transforms that you can do on M to satisfy the
conditions. The first 16 steps all operate on different blocks. As we
will see this makes these steps easily invertible. The next two steps
are more complicated. Changing <code>m[0]</code> for step 17 will change
<code>a[1]</code> which will change <code>m[2]</code> which will change
<code>d[1]</code> and so on</p>
<h3 id="first-16-rounds-single-step-transformations">First 16 rounds,
Single Step Transformations</h3>
<p>The first 16 conditions apply to outputs of the 16 steps of the first
round. Consider the state variable a</p>
<p>let a0 be the initial value of a a1 be the output of applying the
transformation to a for the first time a2 be the output of applying the
transformation to a for the second time a3 … a4 …</p>
<p>Similarly define b0, b1 … b4, c0, c1 … c4, d0, d1 … d4</p>
<p>The first round of transformation for a is</p>
<pre><code> a = (a + F(b,c,d) + X[k]) <<< s</code></pre>
<p>here each step depends on a different word in the original block
which allows us to find the message word given the output. Given a
required a1 we can find <code>X[0]</code></p>
<pre><code>a1 = (a0 + F(b0, c0, d0) + X[0]) <<< 3
a1 >>> 3 = a0 + F(b0, c0, d0) + X[0]
X[0] = (a1 >>> 3) - a0 - F(b0, c0, d0)</code></pre>
<p>From table 6 first row we want a1 to satisfy the following
condition</p>
<pre><code>a1,7 = b0,7 // the 7th bit of a1 = 7th bit of b0</code></pre>
<p>To satisfy this condition first find the a1 for original X[0]</p>
<pre><code>a1 = (a0 + F(b0, c0, d0) + X[0]) <<< 3</code></pre>
<p>This is a1 from our original message Now fix this a1 to satisfy the
condition</p>
<pre><code>a1 = a1 ^ (a1,7 ^ b1,7) // this ensures that we flip bit 7 if a1,7 != b1,7</code></pre>
<p>Now we back calculate X[0]</p>
<pre><code>X[0] = (a1 >>> 3) - a0 - F(b0, c0, d0)</code></pre>
<p>If we implement just the first round transforms this gets the
probability of collision down to 1 in a million.</p>
<h3 id="second-round-multistep-transformation">Second Round, Multistep
transformation</h3>
<p>From second round onwards we cannot simply invert the operation to
satisfy our condition because the new message word might not satisfy the
conditions of the first 16 steps. These steps are complicated and I only
implemented the first two to fix <code>a5</code> and <code>d5</code></p>
<h3 id="implementation">Implementation</h3>
<p>To implement the attack, I structured the code such that I could
generate operations of table 6 using a parser. The code can be found
here
https://github.com/sukunrt/cryptopals/blob/main/crypto/wangmd/wangmd.go</p>
<p>The state is tracked using this struct</p>
<div class="sourceCode" id="cb10"><pre
class="sourceCode go"><code class="sourceCode go"><span id="cb10-1"><a href="#cb10-1" aria-hidden="true" tabindex="-1"></a><span class="kw">type</span> WangMD4 <span class="kw">struct</span> <span class="op">{</span></span>
<span id="cb10-2"><a href="#cb10-2" aria-hidden="true" tabindex="-1"></a> m <span class="op">[</span><span class="dv">16</span><span class="op">]</span><span class="dt">uint32</span></span>
<span id="cb10-3"><a href="#cb10-3" aria-hidden="true" tabindex="-1"></a> a<span class="op">,</span> b<span class="op">,</span> c<span class="op">,</span> d <span class="op">[</span><span class="dv">16</span><span class="op">]</span><span class="dt">uint32</span></span>
<span id="cb10-4"><a href="#cb10-4" aria-hidden="true" tabindex="-1"></a> st <span class="dt">int</span></span>
<span id="cb10-5"><a href="#cb10-5" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
<p>here m is the message broken into words. a, b, c, d are the md4 state
variables and st is the step num currently being computed.</p>
<p>Single step transformations are implemented as</p>
<div class="sourceCode" id="cb11"><pre
class="sourceCode go"><code class="sourceCode go"><span id="cb11-1"><a href="#cb11-1" aria-hidden="true" tabindex="-1"></a> <span class="cf">switch</span> wmd<span class="op">.</span>st <span class="op">{</span></span>
<span id="cb11-2"><a href="#cb11-2" aria-hidden="true" tabindex="-1"></a> <span class="cf">case</span> <span class="dv">1</span><span class="op">:</span></span>
<span id="cb11-3"><a href="#cb11-3" aria-hidden="true" tabindex="-1"></a> wmd<span class="op">.</span>a<span class="op">[</span><span class="dv">1</span><span class="op">]</span> <span class="op">=</span> wmd<span class="op">.</span>a<span class="op">[</span><span class="dv">1</span><span class="op">]</span> <span class="op">^</span> pb<span class="op">(</span>wmd<span class="op">.</span>a<span class="op">[</span><span class="dv">1</span><span class="op">],</span> <span class="dv">7</span><span class="op">)</span> <span class="op">^</span> pb<span class="op">(</span>wmd<span class="op">.</span>b<span class="op">[</span><span class="dv">0</span><span class="op">],</span> <span class="dv">7</span><span class="op">)</span></span>
<span id="cb11-4"><a href="#cb11-4" aria-hidden="true" tabindex="-1"></a> <span class="cf">case</span> <span class="dv">2</span><span class="op">:</span></span>
<span id="cb11-5"><a href="#cb11-5" aria-hidden="true" tabindex="-1"></a> wmd<span class="op">.</span>d<span class="op">[</span><span class="dv">1</span><span class="op">]</span> <span class="op">=</span> wmd<span class="op">.</span>d<span class="op">[</span><span class="dv">1</span><span class="op">]</span> <span class="op">^</span> pb<span class="op">(</span>wmd<span class="op">.</span>d<span class="op">[</span><span class="dv">1</span><span class="op">],</span> <span class="dv">7</span><span class="op">)</span> <span class="op">^</span> pb<span class="op">(</span>wmd<span class="op">.</span>d<span class="op">[</span><span class="dv">1</span><span class="op">],</span> <span class="dv">8</span><span class="op">)</span> <span class="op">^</span> pb<span class="op">(</span>wmd<span class="op">.</span>a<span class="op">[</span><span class="dv">1</span><span class="op">],</span> <span class="dv">8</span><span class="op">)</span> <span class="op">^</span> pb<span class="op">(</span>wmd<span class="op">.</span>d<span class="op">[</span><span class="dv">1</span><span class="op">],</span> <span class="dv">11</span><span class="op">)</span> <span class="op">^</span> pb<span class="op">(</span>wmd<span class="op">.</span>a<span class="op">[</span><span class="dv">1</span><span class="op">],</span> <span class="dv">11</span><span class="op">)</span></span>
<span id="cb11-6"><a href="#cb11-6" aria-hidden="true" tabindex="-1"></a> <span class="op">...</span></span>
<span id="cb11-7"><a href="#cb11-7" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span></code></pre></div>
<p>The entire function is here
https://github.com/sukunrt/cryptopals/blob/main/crypto/wangmd/wangmd.go#L120 <br />
These cases are generated using a parser, that takes in lines from the
table in the form</p>
<pre><code>d1 d1,7 = 0, d1,8 = a1,8, d1,11 = a1,11</code></pre>
<p>and generates</p>
<pre><code> case 2:
wmd.d[1] = wmd.d[1] ^ pb(wmd.d[1], 7) ^ pb(wmd.d[1], 8) ^ pb(wmd.a[1], 8) ^ pb(wmd.d[1], 11) ^ pb(wmd.a[1], 11)</code></pre>
<p>The parser parses the rule, one condition at a time.<br />
<code>d1,7 = 0</code> becomes <code>pb(wmd.d[1], 7)</code> where pb(x,
n) picks the nth byte of x setting everything else to 0.<br />
<code>d1,8 = a1,8</code> becomes
<code>pb(wmd.d[1], 8) ^ pb(wmd.a[1].8)</code>.<br />
Finally, all the conditions are stitched together with the xor
operator.</p>
<p>The parser is available at
https://github.com/sukunrt/cryptopals/blob/main/crypto/wangmd/codegen/main.go</p>
<h3 id="testing">Testing</h3>
<p>The test is available at
https://github.com/sukunrt/cryptopals/blob/main/crypto/wangmd/wangmd_test.go<br />
It takes a couple of seconds to find a collision. It rougly takes 200k
iterations per collision. I got</p>
<pre><code>c2d093b8db8b6524118c66189dea3cfa8fb8477348b94285bd02785147f3b46a529f92de61dcc0812b594e7f753e9ff54c7b023a11865262d44939cb83c09e4e
c2d093b8db8b65a4118c66889dea3cfa8fb8477348b94285bd02785147f3b46a529f92de61dcc0812b594e7f753e9ff54c7b013a11865262d44939cb83c09e4e</code></pre>
<p>The strings look very similar because their only difference is delta
m0 = 2^31 delta m1 = 2^31 - 2^28 delta m12 = -2^16</p>
<p>To highlight the first difference take this prefix. The last hex
digit is different</p>
<pre><code>c2d093b8db8b652
c2d093b8db8b65a</code></pre>
</html>