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

f r ( B, C, D, E )isdefinedasfollows.
⎧
⎨

f 0 = BC ⊕ ( B ⊕ 1 ) D ⊕ CE ⊕ DE

f 1 = BD ⊕ C ⊕ E , (4)

⎩

f 2 = BC ⊕ ( B ⊕ 1 ) E ⊕ D

where 1 represents bit-string, 1 32 .Moreover, f 3 ( B, C, D, E )= f 1 ( C, B, D, E )
and f 4 ( B, C, D, E )= f 0 ( B, D, C, E ).
Finally, feed-forward is computed; The initial values and the output of the
last step are added by wordwise modular addition in both lines as an output of
the compression function.
When the digest is shorter than 320 bits, output tailoring is applied after the
last iteration of the compression function. Table 9 in Appendix A shows the
details of the output tailoring of HAS-V.
Alternative Description. For the following analysis, we use the alternative
description shown in [14, Section 3]. Let h i

H i and h ( h i ,M i )and g ( g i ,M i )
denote the state update function in the left and right stream. CF can be written
as

g i ←

h i +1 ←

h i + g ( g i ,M i )

g i + h ( h i ,M i )
Notations p j , p j , w j ,and w j correspond to the variables indicated with
prime notation but the swapping procedure is omitted. That is, p 0

g i +1 ←

p 0 = h 0 g 0 ,

p 1 = p 1 ,and p 22 = p 22 , for example. Figures 2 and 3 show the graphical
explanation of this correspondence.

2.3 Conversion from Pseudo-preimage Attack to Preimage Attack

[5, Fact 9.99] describes a generic conversion from a pseudo-preimage attack to
a preimage attack. When the complexity of a pseudo-preimage attack is 2 t ,a
preimage attack can be constructed in 2 ( n + t ) / 2+1 where n is the number of bits
in the internal state length, that is, 160 for PKC98-Hash and 320 for HAS-V.
The memory complexity of the converted attack requires the order of 2 ( n−t ) / 2 .
When the pseudo-preimage attack satisfies several conditions, more effective
conversion can be used such as a tree structure [17], P 3

graph [14,18], and

GMTPP [19].

2.4 Pseudo-preimage Attack against HAS-V

Mendel and Rijmen [14, Algorithm 1] proposed an algorithm to invert the com-
pression function of HAS-V as given below.
Input: The final hash value h i +1 g i +1 and an arbitrary intermediate hash value

h i .
Output: Intermediate hash value g i and message M i such that CF( h i

g i ,M i )

= h i +1

g i +1 .
1. Guess M i and calculate: g i ← h ( h i ,M i ).

2. Check if the following equation holds: h i +1 = h i + g ( g i ,M i ).
The time complexity of the attack is expected to be 2 160 .

g i +1 −