Cryptography Reference
In-Depth Information
E
(
i
+1)
.Store
A
(
i
)
96
and
A
(
i
)
C
(
i
+1)
D
(
i
+1)
96
,which
will be used later. Note that we can compute registers
B
,
C
,
D
,and
E
of
H
i
+1
without knowing the value of
A
(
i
)
or
A
(
i
)
.
3. Find a pseudo-preimage for the last block by using the attack in Section 3.1.
First, fix registers
B
,
C
,
D
,and
E
of the input chaining variable to 0,
C
(33)
,
D
(33)
,and
E
(33)
, and fix the target hash value to
H
34
. Then, find
A
(33)
and
M
33
where
H
34
=CF(
H
33
,M
33
)and
M
33
satisfy the padding for a 34-block
message.
4. Determine which of
M
i
and
M
i
(
i
=1
,
2
,...,
32) should be used for a preim-
age. This is done by the exhaustive search, namely, for all message combi-
nations, check
A
(33)
fixed in Step 3 is achieved or not. This can work with
high probability, because the following equation holds.
colliding values be
∗
0
A
(
i
)
96
31
if
M
i
is used.
A
(33)
=
A
(1)
+
A
(
i
)
96
if
M
i
is used.
i
=0
This can be done with the previous technique such as one described in [20].
Note that we write the case that the feed-forward operation is modular
addition. Replace the modular operation with XOR if the feed-operation is
XOR.
The complexity of the attack is as follows.
1. 2
32
because we need to specify that register
B
is 0.
2. For each
i
, collision without register
A
can be found in 2
64
,andregister
B
of
such a collision is 0 with a probability of approximately 2
−
32
. In total, 2
101
(= 32
2
32
). The computation can be done with negligible memory,
while we can compute this in 2
85
with 2
48
blocks of memory.
3. 2
128
followed by Section 3.1.
4. Less than 2
32
2
64
×
·
because 32 additions are expected in less than one CF com-
putation.
In total, 2
32
+2
101
+2
128
+2
32
≈
2
128
computations are required to obtain a
preimage. Note that Steps 1 and 2 can be pre-computed before the target hash
value is given. Also note that if 2
32
words of memory is allowed, Step 4 can also
be precomputed.
The above attack uses 2 collisions. We can shorten the length of the preimage
with a slightly higher level of complexity and much more memory. When we use
k
-collisions, the length of the multi-collision part is
log
k
(2
32
)
blocks, and the
complexity for pre-computation is
log
k
(2
32
)
×
2
32
2
96
×
(
k−
1)
/k
)
×
(
k
!
×
and the memory requirement for the attack is approximately 2
96
×
(
k−
1)
/k
blocks.
Thanks to the Joux and Lucks attack [21], we can reduce the memory complexity
to 2
32
for the case of
k
=3.When
k
≤
6, the increase of the time complexity is
negligible with the use of
k
-collisions.
Search WWH ::
Custom Search