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

Table 1. Summary of Current Results Compared to Previous Best Results

Complexity Preimage

No. Attack Memory length

Reference Target steps Type Time (words) (blocks)

2 144

[4] PKC98-Hash 80 PPI Negligible —

2 152 7 × 2 16 PI 2

Ful l PPI 2 128 Negligible Sect. 3.1 PKC98-Hash —

2 96 † Negligible Sect. 3.2 PKC98-Hash Ful l PI 1

2 128 Negligible

Sect. B.1 PKC98-Hash Ful l PI 34

2 160 [14] HAS-V-(128 + 32 k )( k ≥ 2) Full PPI Negligible —

2 162 20 × 2 160

PI 161

2 256 Negligible Sect. 4.1 HAS-V-320 Full PI 1

2 249 . 2 Negligible Sect. B.3 HAS-V-256 Full PI 1

2 253 . 5 Negligible HAS-V-288 Full PI 1

Full PPI 2 128 Negligible

Sect. 4.2 HAS-V-320 —

Full PPI 2 96 Negligible Sect. 4.3 HAS-V- 128 + 32 k ( k< 6 ) —

PPI: Pseudo-preimage attack, PI: Preimage attack
Bold-face fonts indicate the best results.
† : Success probability of this attack is 1 − e − 1 .

In this paper, we show how to exploit the non-injective property of the step
function of PKC98-Hash, and propose the first preimage attack against the full
specification. Moreover, this attack can work for any number of steps. The best
proposed attack generates 1-block preimages with a complexity of 2 96 . However,
for a randomly given target hash value, the attack can generate preimages with a
probability of 1 −e − 1 ≈ 0 . 63 at most due to the effect of the message-dependent

rotation. Note that, as a second-preimage attack, this attack succeeds with high
probability if the given first-preimage is two blocks or more. We also show that by
combining the non-injective property with a multi-collision technique [16], we can
eciently convert from pseudo-preimages to a preimage. This guarantees that
for any given target hash value, preimages can be computed with a complexity
of 2 128 . Second, we apply the techniques to HAS-V. As a result, we can find
preimages of one block long with only a negligible sized memory. Moreover, we
can find pseudo-preimages of HAS-V-160 and HAS-V-128 while the previous
work could not obtain any results on these output sizes. Again, this attack can
work for any number of steps.
The analytic approach is totally different from the previous meet-in-the-
middle preimage attack [4]. Table 1 summarizes the current results compared
to the previous best results. These results show the weakness of non-injective
step functions. Note that the attack in Section B.2 shows that the choice of the
feed-forward operation sometimes makes the difference in security. It may be
useful for hash function designers to take this result into account.