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

2. Compute R ( p j ,w j )for j =0 , 1 ,..., 97 and confirm whether or not the
resulting p 98 matches the form of
C ≪ 2
100

(( D ≪ 2 ( D ≪ 2 E 100 E 100 ∗

100 ) [31 − 10] ∗ [9 − 4] 100 ) [3 − 0] )

.

If there is no match, go back to the first step. The match will occur with
probability 2 − 122 .
3. Compute E [7 − 0] ← H D [7 − 0] − D 0[7 − 0] − D 100[7 − 0] (mod 2 8 ), and reassign

E 100[7 − 0] ← E [7 − 0] − E 0[7 − 0] .
4. Compute R ( p j ,w j )for j =0 , 1 ,..., 96 and confirm whether or not the
resulting p 97 matches the form of D ≪ 2 E ≪ 2

100

C ≪ 2
100

C ≪ 2
100

.Ifthere
is no match, go back to the first step. The match will occur with probability
2 − 128 .

∗

100

As a result, we will find a preimage in 2 250 .

Note for Weak Hash Values. After setting up the intermediate variables in
Table 10, ( C ≪ 2

100 ) [ k ] =( D ≪ 2

1

100 ) [ k ] for k =0 , 1 holds with probability

2 .Thus,

1
4

of the hash value in 2 248 ,

1
2

we can compute a preimage for of the hash value

in 2 249 ,and 4 of the hash value in 2 250 . On average, the attack complexity is

2 249 . 2 .

An Attack against HAS-V-288. We can attack HAS-V-288 in a similar
manner. On the right line, we can cancel the effect of B 98[7 − 2] .Ontheleft
line, unfortunately we cannot satisfy Eq. (10) anymore because E is directly
used to compute a part of the hash value. However, the condition is sometimes
automatically satisfied for a given hash value. For l =0 , 1 ,..., 6, we can compute
a preimage of HAS-V-288 in 2 256 −l for

( l )
2 6

of the hash values. On average, the

attack complexity is 2 253 . 5 .