Cryptography Reference
In-Depth Information
changes depending on
y
. The variables in Table 8 guarantee that two unfixed
words (registers
B
and
E
of
p
98
) never impact
p
2
regardless of their values.
We explain this computation step by step.
•
f
4
(
B, C, D, E
)fortheleftlineis
BD
⊕
(
B
⊕
1
)
C
⊕
DE
⊕
CE
.
For
R
(
p
98
,w
98
)
:
f
r
(
y, c
0
,c
0
,x
)=(
y
∧
c
0
)
⊕
((
y
⊕
1
)
∧
c
0
)
⊕
(
c
0
∧
x
)
⊕
(
c
0
∧
x
)=
0=
c
0
.
For
R
(
p
99
,w
99
)
:
f
r
(
c
0
⊕
c
0
⊕
1
,y
≫
2
,c
0
,c
0
)=((
c
0
⊕
1
)
∧
c
0
)
⊕
(
c
0
∧
y
≫
2
)
⊕
(
c
0
∧
(
y
≫
2
c
0
)
⊕
∧
c
0
)=
c
0
.
Assume that
p
0
in Table 8 can be achieved from
p
98
in Table 8. We later
show that this assumption is reasonable. The Boolean function of the right
line for the first round,
f
r
,isthesameas
f
4
for the left line, which is
BD
•
⊕
(
B
⊕
1
)
C
⊕
DE
⊕
CE
.
For
R
(
p
0
,w
0
)
:
f
r
(
c
1
,c
≫
2
c
≫
2
1
,y
,c
1
)=(
c
1
∧
y
)
(
y
∧
⊕
((
c
1
⊕
1
)
∧
)
⊕
c
1
)
⊕
1
(
c
≫
2
1
c
1
)=
c
≫
2
∧
.
1
For
R
(
p
1
,w
1
)
:
f
r
(
,c
≫
2
1
,c
≫
2
1
,y
)=(
c
≫
2
1
c
≫
2
1
(
c
≫
2
1
∗
∗∧
)
⊕
((
∗⊕
1
)
∧
)
⊕
∧
y
)
(
c
≫
2
1
y
)=
c
≫
2
1
⊕
∧
.
Finally, we can conclude that the two unfixed words of
p
98
are always ignored
in the
f
r
function in each step, and thus do not impact
p
2
.
The remaining problem is how to satisfy the above assumption, namely, how
we choose variables
c
0
and
c
1
so that they are consistent with the transformation
from
p
100
to
p
0
. Specifically, we need to make sure that
C
100
+
C
0
,which
is (
c
0
⊕
1
)
≫
2
+
c
≫
1
, is equal to the third word of
g
i
+1
and, at the same time,
E
100
+
E
0
,whichis
c
0
+
c
1
is equal to the fifth word of
g
i
+1
(We do not have
to consider register
D
because
y
is a variable that can change depending on the
value of
y
). This is usually impossible if
g
i
+1
is a given and a fixed target value.
Therefore, this attack is impossible for HAS-V-320. However, for the shorter
outputs, there exist multiple candidates of
g
i
+1
that can produce the given short
hash values. This redundancy introduced by the output tailoring function enables
us to satisfy the constraints on registers
C
and
E
simultaneously.
p
100
and
p
0
.
Let us denote five words of
Satisfying Constraints Between
h
i
+1
and
g
i
+1
by
A
E
, respectively. The
output tailoring function is shown in Table 9. The goal here is to find a tuple of
values (
c
0
,c
1
,C
,E
) that can produce the given target hash value of a reduced
size and satisfy equations (
c
0
⊕
B
C
D
E
and
A
B
C
D
1
)
≫
2
+
c
≫
1
=
C
and
c
0
+
c
1
=
E
.
Westartwithanobservation:
C
may not have freedom depending on the
output size.
For example, in a 256-bit case, 8 LSBs of
C
can take any value
by choosing
E
[15
−
8]
so that
C
[7
−
0]
+
E
[15
−
8]
can be equal to the 8 LSBs
of the 6th word of the given target value. However, the other 24 bits of
C
must be fixed uniquely. Therefore, in this attack procedure, we regard that
C
is fixed by the given target hash value (Even if
C
has the freedom, we fix
C
to one of the possible values and do not use the freedom). Hence, if we
determine the value of
c
0
(resp.
c
1
), the value of
c
1
(resp.
c
0
) will be fixed by
(
c
0
⊕
1
)
≫
2
+
c
≫
1
=
C
. This also fixes the value of
E
by
c
0
+
c
1
=
E
. Then,
we have another observation:
For a given hash value,
E
cantakeanyvaluefor
Search WWH ::
Custom Search