Cryptography Reference
In-Depth Information
which allows the attacker to factor
N
by computing
gcd
(σ
)
N
=
e
−
μ(
m
)
mod
N
,
p
.
Clearly, Boneh et al.'s fault attack applies to any deterministic RSA encoding
μ
,
such as the Full Domain Hash [29], where
is a full-length hash function. The attack
is also applicable to probabilistic signature schemes where the random nonce used
to generate the signature is sent along with the signature.
However, if the nonce is only recovered when verifying the signature, or if some
part of the message is unknown, the attack does not apply directly. For example, with
a probabilistic encoding of the form
μ
r
, where a random nonce
r
is simply
concatenated with the message
m
, the nonce
r
is only recovered when verifying a
correct signature. Given a faulty signature
μ(
m
)
=
m
σ
, the attacker cannot retrieve
r
nor infer
which would be necessary to compute gcd
(σ
)
N
=
e
(
p
.It
is not advisable to use this particular toy encoding (for example, one can clearly forge
signatures if
r
is allowed to be as large as
N
1
−
1
/
e
), but more serious probabilistic
encodings in which the randomness is recovered as part of signature verification
(such as PSS [31]) are similarly immune to the Bellcore attack.
Coron et al. [104] have shown how, for certain padding schemes, the case of
unknown nonces or partially unknown messages can be tackled nonetheless if
the unknown part is not too large. The attack uses a technique by Herrmann and
May [179] for finding small roots of linear equations modulo an unknown factor
p
of a public modulus
N
. This technique is in turned based on Coppersmith's lattice-
based method for finding small roots of polynomials [101].
The main application considered by Coron et al. was RSA signatures using the
ISO/IEC 9797-2 standard padding scheme [191], where the message is partially
unknown, a common situation in smart card applications, especially EMV smart
cards [132]. The ISO/IEC 9797-2 encoding function is of the form
m
r
)
−
μ(
m
)
mod
N
,
μ(
m
)
=
6A
16
m
[
1
]
H
(
m
)
BC
16
where
m
=
m
[
1
]
m
[
2
]
is split in two parts, and
H
is a hash function, typically
d
mod
N
.
To recover the whole message and verify the signature, the recipient first computes
μ(
SHA-1. Only
m
[
2
]
is transmitted together with the signature
σ
=
μ(
m
)
e
m
)
=
σ
mod
N
, from which he deduces
m
[
1
]
, and then checks that the hash
value
H
is correct.
In the cases considered in [104], the message prefix
m
(
m
)
is partially known to
a fault attacker (because messages are formatted in a particular way, as is common
in applications) but some variable part is unknown, and the hash value
H
[
1
]
(
m
)
is
[
]
unknown, as well as is a result. Yet, if the unknown part of
m
1
is not too large (up
,
to about 160 bits for a 2
048-bit modulus), then, in Boneh et al.'s attack, the private
key can be recovered with a single fault.
In addition, the same paper presents an extension of this attack to the case when
multiple faults are available, which makes it theoretically possible to deal with
larger unknown message parts. However, this variant involves lattice reduction in
