Cryptography Reference
In-Depth Information
Table 3.
The number of messages to recover the central map or secret key in our fault
attacks on
r
Big Field (
§
3.3.1)
STS (
§
3.3.2)
1
2
#(
x, y
)
(
n
+1)(
n
+2)
n − u
1
+1
Recovering
hidden
g
m
−
u
1
+1
, ··· ,g
m
apartof
S
Even if the scheme is not UOV like, the information
D
−
1
C
is necessary to
prevent the rank attacks. In fact, when the rank for the rank attack is
R
,our
fault attack on
r
reduces the rank for the rank attack to
R
−
u
1
. This weakens
the security against the rank attacks.
In “vinegar”, the information
D
−
1
C
is enough to discover the original scheme.
Thus, the fault attack reduces the “vinegar” with
u
random values to the “vine-
gar” with
u
u
1
random values. In particular, if
u
=
u
1
, the polynomials in the
original scheme are recovered and then the attacks against the original scheme
can be used directly.
Table 3 shows a comparison of the fault attack results on
r
against (”minus”
of) the Big Field type in section 3.3.1 and the STS type (and ”vinegar”) in
section 3.3.2. #(
x, y
) is the number of pairs given in Step 2. The proposed fault
attack can recover central polynomials
g
m−u
1
+1
(
x
)
,
−
,g
m
(
x
)in
G
hidden to
generate the “minus” for the Big Field type and the secret key
T
in equation
(2) for the STS type.
···
3.4
Countermeasures
In this section, we explain naive countermeasures against our fault attacks.
Fault attacks on
G
.
Recall that our fault attack on
G
requires several signa-
tures
x
derived from randomly chosen messages
y
and the faulty central map
G
. The basic strategy to prevent the fault attack is to check whether
G
is faulty
and, if so, to not generate the signature. For example, prepare
c
G
the sum of
the coecients of the polynomials in
G
and check whether
c
G
coincides with
the sum of the coecients in the central map before the signature generation
process. If it does not, reject the given message for the signature generation. Our
fault attack will not work, because the signatures cannot be generated by the
faulty central map
G
.
Fault attack on
r
.
Recall that the fault attack on
r
require the signature
x
derived from several randomly chosen messages
y
and (partially) fixed random
ephemeral values
r
. The basic strategy to prevent this attack is to recall the
random ephemeral values
r
chosen in the past several signature generations and
if there are (partial) coincidences of
r
, to stop the next signature generation
process. Our fault attack will not work because a su
cient number of signatures
with a fixed
r
cannot be given.
