Cryptography Reference
In-Depth Information
MPKC is its eciency. Chen
et al.
[10] presented several MPKC implementations
that are more ecient than RSA and ECC on modern x86 CPUs. Before MPKCs
can be implemented for practical use, it is necessary to check their security
against physical attacks. However, at this time, there have been few such works,
aside from the one on a side channel attack against Sflash by Okeya
et al.
[37].
On the other hand, there have been many quite recent studies [36,2,9] on physical
attacks against lattice- and code-based cryptosystems.
In this paper, we propose general fault attacks on MPKCs, and discuss the
security of MPKCs against the proposed fault attacks comprehensively. A fault
attack is a physical attack, first introduced by Boneh
et al.
[7], that causes faults
on the parameters in a target device. This type of attacks has been studied with
regard to its influence on RSA [30], ECC [6,12] and Pairing [38], but to the best
of our knowledge this is the first work that deals with fault attacks on MPKC.
1.1
The Proposed Fault Attacks
Two different fault attacks on MPKCs are discussed in this paper. The first is
an attack in which the attacker causes a fault to change coecients of unknown
terms in the central quadratic map
G
.FortheBigFieldtypescheme(
e.g.
MI
[34],HFE[40],Sflash[1]and
l
lIC [21]), the attacker can simplify the target
problem to an easier one (
e.g.
HFE to MI) and can recover the secret ane
transforms
S, T
by only single fault and suciently many pairs of messages and
signatures given by the faulty central map. For the Stepwise Triangular System
(STS)typescheme(
e.g.
Tsujii's scheme [44], Shamir's scheme [42], UOV [31],
Rainbow [20] and TTM/TTS [35,46]), the attacker can recover a part of the
secret ane transform
T
on the quadratic forms directly from a pair of message
and signature given by the faulty central map. On our attacks in practice, the
fault can not always change the coecients in
G
, since there are three possible
system parameters (
G
,
S
,or
T
). However, the success probability of changing
the central map
G
by one fault attack is high enough for attackers (see Table 2),
and we are able to distinguish whether the location of the fault is in
G
or not.
The other fault attack is an attack in which the attacker causes faults such
that the parameters
r
chosen randomly in the process of signature generation are
(partially) fixed to the same values. For the “minus” variation of the Big Field
type signature scheme, the attacker can simplify the “minus” to the original
scheme. For the STS type signature schemes, the attacker can recover a part of
the secret ane transform
S
on the variables.
In the side-channel attack on Sflash by Okeya
et al.
[37], the attacker reduces
Sflash to MI by finding the secret key
Δ
using the side channel attack, and gener-
ates a dummy signature of MI by Patarin's attack [39]. On the other hand in our
fault attacks, we do not use the secret information discovered by the side-channel
attacks but use pairs of messages and signatures given by the faulty secret in-
formation to recover the secret ane maps
S, T
. Though these fault attacks do
not necessarily break the schemes directly, partial information of secret keys re-
covered by the fault attacks is usually critical in terms of preserving the security
against known attacks. In other words, the fault attacks weaken the security of
