Preimage Attacks against PKC98-Hash and HAS-V - Information Security and Cryptology-ICISC 2010 - page 69

characteristic is that a step function is not injective. This design is very different
from many other hash functions adopting a Davies-Meyer mode [5, Algorithm
9.42], which is a block-cipher based construction. Let us compare the behaviors
of these two designs when a message input is fixed. When two different chain-
ing variables are input to the standard Davies-Meyer mode, they never collide
except for the last feed-forward computation. On the other hand, PKC98-Hash
compresses the data in every step. From this observation, the following are in-
teresting objectives on PKC98-Hash from the view of hash function design.

1. Obtaining collisions seem easier than in the standard Davies-Meyer construc-
tion.
2. Is it possible to use this property to mount a preimage attack?
3. Is there any advantage to this structure compared to the standard Davies-
Meyer mode?

History of the cryptanalysis against PKC98-Hash shows that the first perception
is correct. Han et al. [6] showed that Boolean functions used in PKC98-Hash do
not satisfy the Strict Avalanche Criterion (SAC) which is intended to be satis-
fied by the designers, and a collision can be found in 2 30 compression function
computations (hereafter, if the unit of computational complexity is expressed in
terms of compression function computations, we omit it for the sake of simplic-
ity. Otherwise, we explicitly write the unit) if these functions are replaced with
any function satisfying the SAC. Chang et al. [7]extendthisattackandshow
that a collision can be found in 2 37 . 13 by making a good differential path for the
non-SAC functions. They also showed an example of a pair of colliding messages.
Moreover, Mendel et al. [8] reduces the complexity to 2 20 . 5 using the collision

finding techniques described in [1].
While several collision attacks have been proposed, only one preimage attack
has been proposed so far [4]. It applies a recently developed framework of the
meet-in-the-middle preimage attack [9,10,11] to PKC98-Hash, and finds an at-
tack against 80 steps out of 96 steps. However, note that this attack includes a
technically vague point 1 .
To obtain deep knowledge of a hash construction such as PKC98-Hash, more
hash functions with a similar structure should be analyzed. HAS-V [12] is a
hash function for this case. HAS-V was proposed as a candidate to meet the
requirement of KCDSA [13], which is one of the ISO standard digital signature
algorithms. It can output 128 + 32 k ( k =0 , 1 ,..., 6) bits of hash values, and
its compression function consists of two copies of the Davies-Meyer compression
function. For HAS-V-320, Mendel et al. [14] showed that pseudo-near-collisions
can be found with a complexity of 1, and preimages can be found with a com-
plexity of 2 162 . Mouha et al. [15] showed some results on finding collisions for
simplified variants of HAS-V.

1 The paper simply indicates “step − 1 ” in Section 5.3, and how to compute the inverse
of the step function is not mentioned. Because the step function is not injective, we
doubt that the step function can easily be inverted consistently with the message
schedule.