Cryptography Reference
In-Depth Information
m
and
a
(
j,l
)
i
k
. Substitute
x
=
x
(
i
)
and
y
(
l
)
j
=
δ
(
i
)
j
where 1
≤
l
≤
n
,1
≤
j
≤
∈
into
(18). Then
N
linear equations of
n
+1 variables(
a
(
j,l
)
1
, a
(
j,l
n
, b
(
j,l
)
)appear.
According to (17), we see that, if such equations have no common solutions for
any
l
,then
S
is not faulty.
,
···
3.3
Fault Attacks on
r
In the signature schemes, ephemeral random values
r
1
,
k
are used for
the signature generation in equation (5). In our fault attack on
r
, we assume
that the attacker can fix a part of such
r
1
,
···
,r
u
∈
···
,r
u
∈
k
by a fault. Without the
loss of generality, suppose that (
r
u−u
1
+1
,
···
,r
u
)isfixedfor
u
1
≤
u
. The basic
approach of the fault attack is as follows.
——————————————————————————————————-
Step 1.
Cause a fault in which (
r
u−u
1
+1
,
···
,r
u
) is fixed in every signature
generation process. Suppose that (
r
u−u
1
+1
,
···
,r
u
)=(
r
u−u
1
+1
,
···
, r
u
)where
r
u−u
1
+1
,
k
are fixed (unknown) values.
Step 2.
For given messages
y
(1)
,
···
, r
u
∈
,y
(
N
)
, generate the corresponding signature
···
x
(1)
,
,x
(
N
)
with
r
=(
r
1
,
···
···
,r
u−u
1
, r
u−u
1
+1
,
···
, r
u
).
(
x
(
l
)
,y
(
l
)
)
Step 3.
Recover (parts of)
S
and
T
by using
}
1
≤l≤N
.
——————————————————————————————————-
Next, we will describe precisely how to recover the
S
and
T
details.
{
3.3.1 Fault Attack on
r
for (“Minus” of) BF Type
In the basic BF type,
e.g.
MI and HFE, random parameters are not used. In
the “minus” and the “vinegar” variation, however, ephemeral random values are
used for the signature generation. Since the fault attack on
r
for the vinegar is
similar to that on the STS type given later, we now explain the fault attack on
r
for the minus of the BF type.
Assume that
r
u−u
1
+1
,
···
,r
u
are fixed to be (
r
u−u
1
+1
,
···
, r
u
)(1
≤
u
1
≤
u
).
The signatures
x
(1)
,
,x
(
N
)
are then the solutions of
···
g
m−u
1
+1
(
S
(
x
)) =
r
u−u
1
+1
,
···
,
g
m
(
S
(
x
)) =
r
u
,
(19)
where
g
l
is the hidden polynomial. Taking differences of (19), we have
g
l
(
S
(
x
(
l
)
))
g
l
(
S
(
x
(1)
)) = 0
,
−
(
m
−
u
1
+1
≤
l
≤
m
)
.
(20)
Similar to the case of the fault attack on
G
fortheBFtype,weseethat,if
N>
(
n
+1)(
n
+2)
/
2, we can recover the central polynomials
g
m−u
1
+1
(
S
(
x
))
,
···
,
g
m
(
S
(
x
)).
Recall that the “minus” hides the central polynomials
g
m−u
+1
(
x
)
,
,g
m
(
x
)
of the original scheme and, if the number
u
of the hidden polynomials is small,
the hidden polynomials can be discovered. Our fault attack finds several hidden
polynomials, namely the number of hidden polynomials is reduced. Our fault
attack therefore reduces the security of the “minus” variations. In particular, if
u
1
=
u
, all of the hidden central polynomials are recovered. In this case, the
···
