Cryptography Reference
In-Depth Information
h
i
g
i
p
0
p
2
Independent of
unfixed words
Table 8.
Two Neutral Words Allocation
2
-96
match?
A
j
B
j
C
j
D
j
E
j
w
j
j
p
98
A
C
D
98
c
0
⊕
1
y
c
0
c
0
x
X
4
unfixed
p
100
y
≫2
99
c
0
⊕
1
c
0
c
0
X
0
(
c
0
⊕
1
)
≫2
y
≫2
100
c
0
A
j
B
j
C
j
D
j
E
j
w
j
h
i
+1
g
i
+1
c
≫2
1
y
0
c
1
c
1
Y
0
Output Tailoring
Tailored hash value
c
≫2
1
c
≫2
1
y
1
Y
1
Fig. 4.
Pseudo-Preimages on Tai-
lored HAS-V
5. If the newly computed
p
98
matches the form of
C
≪
2
100
D
≪
2
100
E
100
E
100
∗
, we obtain a pseudo-preimage. Otherwise, go back to Step 4.
The success probability of Step 5 is 2
−
128
, and we expect to find a pseudo-
preimage in 2
128
.
Since we can easily invert the output tailoring function, we expect to find
pseudo-preimages faster than with a brute-force search for all output lengths of
HAS-V except for the 128-bit output.
4.3
Pseudo-preimage Attacks with Output Tailoring
Regarding HAS-V with shorter hash lengths, we can further reduce the com-
plexity of the pseudo-preimage attack in Section 4.2 by using the redundancy
introduced in the output tailoring function.
Overall Strategy.
Similar to Section 4.2, we make unfixed words in the last
several steps of the left line (
p
98
). However, different from Section 4.2, we make
two unfixed words. The overall strategy is as follows, which is also illustrated in
Fig. 4.
-
Set two unfixed words on registers
B
and
E
of
p
98
.
-
Set intermediate variables in
p
98
,
p
99
,
p
100
,
p
0
,and
p
1
so that
p
2
and
the following computations can be carried out independently of the values
of unfixed words.
-
For a randomly chosen message, compute
p
2
→
p
98
. Finally
check that the registers of
A
,
C
,and
D
of the computed
p
98
match the values
of
p
98
set in advance.
p
100
→
p
0
→
p
98
p
2
Computations from
and Use of Output Tailoring Function.
Table 8 describes the intermediate variables at the last 3 steps of the left line
and the first 2 steps of the right line.
c
0
and
c
1
are constants to be determined
by the method below and
x
and
y
are unfixed variables.
y
is a variable that
to
Search WWH ::
Custom Search