Cryptography Reference
In-Depth Information
Table 6.
Intermediate Variables in the Last 5 Steps
j
A
j
B
j
C
j
D
j
E
j
w
j
s
j
91
x
000
y
X
19
X
19
yA
≫10
96
92
000
X
8
X
20
E
≫10
96
93
0
A
96
00
X
9
X
21
D
≫10
96
E
96
A
96
X
11
X
22
94
0
0
C
≫10
96
95
0
D
96
E
96
A
96
X
1
X
23
96
A
96
B
96
C
96
D
96
E
96
where
c
B
is a fixed constant.
f
1
(
y, c
B
,
0
,
0
,
0) returns
c
B
regardless of
y
.Fi-
nally, the attack complexity can be improved to that achieving (
x,
0
,
0
,
0
,y
)
at an intermediate step, which is 2
96
.
By considering the above two improvements, we set the value of (
A
91
,B
91
,C
91
,
D
91
,E
91
)to(
x,
0
,
0
,
0
,y
) and adjust each variable for a fixed target during the
last five steps. Table 6 shows how to control the last five steps, and Eq. (5) shows
the message schedule for the last five steps.
⎧
⎨
X
15
)
≪
1
X
19
=(
X
3
⊕
X
5
⊕
X
10
⊕
X
12
)
≪
1
)
≪
1
X
20
=(
X
4
⊕
X
6
⊕
X
11
⊕
(
X
0
⊕
X
2
⊕
X
7
⊕
X
13
)
≪
1
)
≪
1
X
21
=(
X
5
⊕
X
7
⊕
X
12
⊕
(
X
1
⊕
X
3
⊕
X
8
⊕
(5)
⎩
X
14
)
≪
1
)
≪
1
X
22
=(
X
6
⊕
X
8
⊕
X
13
⊕
(
X
2
⊕
X
4
⊕
X
9
⊕
X
15
)
≪
1
)
≪
1
X
23
=(
X
7
⊕
X
9
⊕
X
14
⊕
(
X
3
⊕
X
5
⊕
X
10
⊕
Based on Table 6, we develop the following procedure for given hash value
H
A
H
E
.
1. Set
A
96
← H
A
− A
0
,
B
96
← H
B
− B
0
,
C
96
← H
C
− C
0
,
D
96
← H
D
− D
0
,
and
E
96
← H
E
− E
0
,where
A
0
B
0
C
0
D
0
E
0
(=
H
0
) is the initial value.
2. Set
A
j
,
B
j
,
C
j
,
D
j
,and
E
j
as specified in Table 6 for
j
=95
,
94
,...,
91,
where
x
and
y
are unfixed values. Compute
w
j
←
H
B
H
C
H
D
B
≫
s
j
j
+1
f
1
(
A
j
,
B
j
,C
j
,D
j
,E
j
)for
j
=95
,
94
,
93
,
92 to achieve these values. Remember that
f
1
(
x,
0
,
0
,
0
,y
)and
f
1
(
y, A
≫
10
−
K
3
−
96
,
0
,
0
,
0) are fixed constants regardless of the
values of
x
and
y
.On
s
92
,s
93
,s
94
,
and
s
95
, we set arbitrary values.
3. For Step 91, by exhaustively trying the least significant 5 bits of
w
91
(=
s
91
=
X
19
), check if there exists
X
19
satisfying the following with respect to the
least significant 5 bits. Fix the least significant 5 bits and compute
X
19
=
(
A
≫
10
96
)
≫
X
19
mod2
5
K
3
. If the least significant 5
bits of the newly computed
X
19
matches the fixed value, the solution exists.
Otherwise, the attack fails.
4. Set
X
13
,
X
14
,and
X
15
astheappropriatepaddingrulefora1blockmessage.
Now, we determine the full bits of
X
1
,
X
8
,
X
9
,
X
11
,
X
13
,
X
14
,
X
15
,and
X
19
.
5. We have not yet determined
X
0
,
X
2
,
X
3
,
X
4
,
X
5
,
X
6
,
X
7
,
X
10
,and
X
12
,
but we have the constraint for
X
19
. So, we still have 32
−
f
1
(
A
j
,B
j
,C
j
,D
j
,E
j
)
−
×
8 = 256 free bits.
Equation (5) specifies 5
×
4bitsfor
s
j
for
j
=95
,
94
,
93
,
92. In total, we have
256
−
5
×
4 = 236 free bits by solving the linear system in GF(2) of Eq. (5).
Search WWH ::
Custom Search