Cryptography Reference
In-Depth Information
2
86
2
32
2
128
H
0
−→ Z
−→ ∗
0
∗∗∗
−→ H
Fig. 6.
Intermediate Values
E
cient Pseudo-preimage Conversion Applicable for Addition
Feed-Forward
B.2
In this section, we describe another ecient conversion from pseudo-preimages
to a preimage. This conversion is worse than the one in Section B.1 with respect
to two points: 1) pre-computation requires higher level of complexity, and 2) the
generated preimages are longer (2
33
blocks). However, this attack has a unique
characteristic where the attack works well for modular-addition feed-forward but
does not work for XOR feed-forward. As far as we know, this is the first case
where the attack eciency is significantly different between these two operations,
and thus, we explain the attack.
Note that this attack uses an expandable message. (
a, b
)-expandable message
is a set of messages, where each message outputs the same hash value and the
block length of each message covers all values between
a
and
b
for a given in-
put
H
.(
k, k
+2
k
2
n/
2+1
[22].
Followed by Section 3.1, we can find (
A
,M
∗
)in2
128
that satisfies
1)-expandable messages can be computed in 2
k
+
k
−
×
E
=CF(
A
A
0
C
D
0
C
D
E, M
∗
)
with given
A
,
C
,
D
,and
E
.Let
X
be
−
A
96
,thenwehave
A
=
A
+
X.
Because
X
is the constant only depending on
C
,
D
,
E
,and
M
∗
,
CDE
=CF
i
((
A
+
iX
)
A
0
0
CDE, M
∗
)
holds. Utilizing the property, we compute a preimage of
H
A
H
B
H
C
H
D
H
E
.
Figure 6 shows a graphical explanation of this attack.
1. Construct a (33
,
33 + 2
33
−
1)-expandable message whose input is
H
0
,and
let
Z
be its output.
2. Find (
A
,C,D,E,M
Z
) such that
A
0
C
D
E
=CF(
Z, M
Z
), by randomly
choosing
M
Z
.
3. Find (
A, M
LAST
) such that
H
A
E, M
LAST
)
using Section 3.1.
M
LAST
should follow the padding rule for a message whose
length is 512
H
B
H
C
H
D
H
E
=CF(
A
0
C
D
2
33
+ 447 bits.
4. Find (
A
,M
∗
) such that
A
×
E
=CF(
A
0
C
D
0
C
D
E, M
∗
) using Sec-
tion 3.1.
Search WWH ::
Custom Search