Cryptography Reference
In-Depth Information
H
i
H
i
h
i
(=
p
0
)
g
i
(=
p
0
)
h
i
(=
p
0
)
g
i
(=
p
0
)
↓
↓
↓
↓
Round 1
Round 1
Round 1
Round 1
←
Interchange
→
Round 2
Round 2
Round 2
Round 2
←
Interchange
→
Round 3
Round 3
Round 3
Round 3
←
Interchange
→
Round 4
Round 4
Round 4
Round 4
←
Interchange
→
Round 5
Round 5
Round 5
Round 5
←
Interchange
→
↓
↓
↓
↓
↓
↓
h
i
+1
g
i
+1
h
i
+1
g
i
+1
H
i
+1
H
i
+1
Fig. 2.
Original Description of HAS-V
Compression Function
Fig. 3.
Alternative
Description
of
HAS-V Compression Function
3 Preimage Attacks against PKC98-Hash
This section describes the vulnerability of non-injective step functions. In all
proposed attacks, we exploit the following property:
The value of one input chaining variable can be ignored for the remaining
computations.
In Section 3.1, we show that this property leads to a simple pseudo-preimage
attack with 2
128
computations. Then, in Section 3.2, we apply this idea to gener-
ate preimages of 1-block long with 2
96
computations. However, due to the effect
of the message-dependent rotation, this attack only works with the probability
of 1
− e
−
1
for a randomly given target.
We also show that non-injective step functions enable attackers to convert
pseudo-preimages to a preimage by performing a pre-computation with a lower
complexity level. Because the best proposed attack in Section 3.2 directly gener-
ates preimages, the impact of this attack is limited, and thus we explain it only
in the appendix. However, explaining this conversion will be useful to learn bad
behaviors of non-injective step functions. In addition, by combining this conver-
sion with the results of Section 3.1, we can generate preimages for any given
target value with 2
128
computations. In Appendix B.1, we explain this conver-
sion that combines the ideas of the weak property of non-injective step functions
with the multi-collision technique [16]. Then, in Appendix B.2, we show another
ecient conversion that works well only if the feed-forward operation is modular
addition, not XOR.
Search WWH ::
Custom Search