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

5. Compute i such that A ≡ A + i ( A − A )(mod2 32 ). If there is no solution,

go back to Step 4.
6. With the preceding and appropriate expandable part depending on i to sat-
isfy the padding rule, M Z

( M ∗ ) i

M LAST is a preimage for the given hash

value.

The complexity of the attack is as follows.

1. 2 33 +33 2 86 .

2. 2 32 because we need to specify the second word as 0.
3. 2 128 followed by Section 3.1.
4. 2 128 followed by Section 3.1.
5. Negligible but the success probability is about 3 , where the success probabil-
ity is estimated as follows. Let X = A −

2 81

× ≈

A and Y = A − A . Assume X and Y

are uniformly distributed. When X is odd, there is a solution. This happens
with probability 2 .When X is even and Y is odd, there is no solution. When
X is even, Y is even, and X/ 2 is odd, there is a solution. This happens with
probability

1

2 3 . We can continue to confirm the parity of each bit to the most
significant bit, thus the success probability is

1
2

1
2 +

1
2 3 +

1
2 5 +

2
3 .

···≈ =

− 2 2 1

6. The time to output a message whose length is about 2 33 blocks, and we

regard this step as negligible.

In total, the complexity is about
2 86 +2 32 +2 128 + 2
3

− 1

2 128 2 129 . 3 . ≈

The length of the preimage is about 2 33 blocks, but the memory requirement of
the attack is negligible since most of the message block is a repetition of M ∗ and
thus all we have to remember is a counter which tells the number of repetitions
of M ∗ . Moreover, we can compute the expandable message with a memoryless
collision search.
In Step 5, we need to solve modular equation mod2 32 . If the feed-forward
operation in Davies-Meyer is

, the equation hardly has a solution, and the
attack described above does not work well. When designing a hash function,
the difference in security between modular addition and XOR of feed-forward
operation in Davies-Meyer as well as the difference in performance may need to
be considered.

⊕

B.3 One-Block Attack on PKC98-Hash with Output Tailoring

We can compute 1-block preimages of HAS-V-256 faster than the brute-force
search using the redundancy in the output tailoring function, and we can also
reduce the complexity of the attack against HAS-V-288 using the same idea.
The outline of the attack is as follows.