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

Table 10. Intermediate Variables to Compute 1-Block Preimage of HAS-V-256

j A j B j C j D j E j A j B j C j D j E j w j w j

D ≪2 100 E ≪2 100 C ≪2 100 C ≪2

97 100 x X 10

C ≪2 100 D ≪2 100 E 100 C ≪2 100 C ≪2 100 C ≪2 100 D ≪2 100 E 100 E 100 y 98 X 4 Y 4

B 100 C ≪2 100 D 100 E 100 C ≪2 100 B 100 C ≪2 100 D 100 E 100 E 100 99 X 0 Y 0

A 100 B 100 C 100 D 100 E 100 A 100 B 100 C 100 D 100 E 100 100

A 0 B 0 C 0 D 0 E 0 A 0 B 0 C 0 D 0 E 0

0 Fixed

A B C D E A B C D E

Adjust-
able

E [31 − 24] E [23 − 16] E [15 − 8] E [7 − 0] E [31 − 24] E [23 − 16] E [15 − 8] E [7 − 0]

H A H B H C H D H A H B H C H D Given

1. Setup the intermediate variables similar to Section 4.1. Moreover, the least
significant few bits of register B will not influence the following computation
for updating register A .
2. Compute the right line, and check the match. The least significant few bits
of register B will influence a register that inputs to the output tailoring
function.
3. Fortunately, the influenced bits cannot influence the intermediate values for
the left line. We can finally absorb the influenced bits by matching in the
left line.
Table 10 shows the initial setup for the attack. Let A , B , ... , E be the
input of the output tailoring function and H A H B H C H D H A H B H C

H D be the given hash value for the preimage to be computed. How to construct
Table 10 is as follows. Note that we have full redundancy in register E ,since
E 0 + E 100 = E and E 0 + E 100 = E hold. First, we construct the equations
using the variables with E 99 and E 100 , then we compute these variables from
the fixed and the given values.
- Focus on the right line. For Step 98, we want to ignore E 98 and B 98 .We
can ignore the variables under the condition D 98 = C 98 (= E 100 ), since
the Boolean function of the step is f 0 .
- For Step 99, we want to ignore C 99 . It can be achieved with B 99 = E 99
(= D 98 ). Using the condition in Step 98, we have
C ≪ 2

100 = E 100

(6)

- For the output of Step 99, namely j = 100, D 100 should be consistent with
the output tailoring function and feed-forward operation,

D 100 = H D − D 0 − E [7 − 0] . (7)

- Now focus on the left line. For Step 97, we want to ignore E 97 and B 97
(= E 100 ). This can be achieved by D 97 = C 97 (= E 99 ), since the Boolean
function of the step is f 4 .