Cryptography Reference
In-Depth Information
“minus” is completely reduced to the original scheme (
e.g.
MI
−→
MI, HFE
−
→
HFE) and the attacks on the original scheme are then used directly.
3.3.2 Fault Attack on
r
for STS Type (and the “Vinegar”)
In most STS type signature schemes and “vinegar variations, the signature
x
∈
k
n
k
m
,r
u
)
t
k
u
for a message
y
∈
and ephemeral random values
r
=(
r
1
,
···
∈
in (5) are given by
x
=
S
−
1
(
G
−
1
(
T
−
1
(
y, r
))) =
S
−
1
z
r
,
k
n−u
,namelythelower
u
entries of
S
(
x
) coincide with
r
. In fact, the
signatures of UOV, Rainbow, TTS and HFEv are all given in this way. We now
propose the fault attack on
r
by using this property.
Assume that (
r
u−u
1
+1
,
where
z
∈
···
,r
u
)isfixedtobe(
r
u−u
1
+1
,
···
, r
u
)(
u
≤
u
1
). Let
=(
r
(
l
1
,
,r
(
l
)
u−u
1
r
(
l
)
, r
u
)
t
=(
η
(
l
)
t
, r
t
)
t
where
η
(
l
)
k
u−u
1
are
···
, r
u−u
1
+1
,
···
∈
the ephemeral random values corresponding to the signature
x
(
l
)
given in Step
2. Then we have
⎛
⎞
z
(
l
)
η
(
l
)
r
⎝
⎠
,
S
1
x
(
l
)
+
s
2
=
(21)
where
S
1
,s
2
are given in (2). Divide
x
(
l
)
,S
1
and
s
2
by
x
(
l
)
=
x
(
l,
1)
x
(
l,
2)
,
S
1
=
AB
CD
,
2
=
s
21
s
22
with
x
(
l,
1)
,s
21
∈
k
n−u
1
,
x
(
l,
2)
,s
22
∈
k
u
1
,
A
∈
k
(
n−u
1
)
×
(
n−u
1
)
,
B
∈
k
(
n−u
1
)
×u
1
,
C ∈ k
u
1
×
(
n−u
1
)
k
u
1
×u
1
, and assume that
D
is invertible. Then the
lower
u
1
entries in (21) are
Cx
(
l,
1)
+
Dx
(
l,
2)
+
s
22
=
r.
Since
s
22
and
r
are fixed
values, we can take
and
D
∈
C x
(
l,
1)
+
Dx
(
l,
2)
=0
,
where
x
(
l,
1)
:=
x
(
l,
1)
x
(1
,
1)
and
x
(
l,
2)
:=
x
(
l,
2)
x
(1
,
2)
−
−
for 2
≤
l
≤
N
.Wecan
thus recover
D
−
1
C
by
D
−
1
C
=
X
2
X
−
1
,
−
(22)
where
X
1
:= (
x
(1
,
1)
,
, x
(
n−u
1
,
1)
),
X
2
:= (
x
(1
,
2)
,
, x
(
n−u
1
,
2)
). Since
···
···
S
I
n−u
1
=
∗
n−u
1
∗
0
,
0
D
−
1
CI
u
1
−
∗
u
1
we see that our fault attack reduces the complexity
O
(
q
n−
2
o
o
4
) of Kipnis-
Shamir's attack on UOV [33,31] to
O
(
q
n−
2
o−u
1
o
4
). The fault attack on
r
then
weakens the security of UOV like schemes (UOV, Rainbow and TTS) on Kipnis-
Shamir's attack to find (a part of)
S
.
