Cryptography Reference
In-Depth Information
dimensions exponential in the number of faults (using heuristic, multivariate ver-
sions of Coppersmith's method), and becomes quickly impractical.
Later, Coron et al. presented another multiple fault attack in the same setting [108]
eschewing Coppersmith-like techniques entirely. It is based on orthogonal lattices, as
used in earlier cryptanalytic results such as [307, 308]. The lattice sizes involved are
moderate and make the attack quite practical for relatively large unknown message
parts. For a particular EMV use case highlighted in [108], and well beyond the reach
of the attack in [104], ten faulty signatures are sufficient to recover the private key
almost instantaneously.
12.4.1 The ISO/IEC 9797-2 Signature Scheme
ISO/IEC 9797-2 is an encoding standard allowing partial message recovery [190,
191], and is used in many embedded applications, including EMV smart cards [132].
The encoding can be used with hash functions H of various digest sizes k h . When
k h , the message size and the size of N (denoted k ) are all multiples of 8, the
ISO/IEC 9797-2 encoding of a message m
=
[
]
[
]
m
1
m
2
is
μ(
m
) = 6A 16
m
[
1
]
H
(
m
) BC 16
where m
[
1
]
consists of the k
k h
16 leftmost bits of m and m
[
2
]
represents the
remaining bits of m . In [191] it is required that k h
160.
The ISO/IEC 9797-2 encoding itself is deterministic, but it is often used with
messages containing parts which are either secret or picked at random upon signature
generation. This is particularly the case in EMV smart cards. The message to be
signed can be put in the following general form: m
=
m
[
1
]
m
[
2
]
with
α
m
[
1
]= α
r
and
m
[
2
]= data
α are bit strings known
to the attacker, and data is a possibly unknown bit string. Thus, the ISO/IEC 9797-
2-encoded message is
where r is an unknown bit string (e.g. a random nonce),
α
and
α
α data ) BC 16
μ(
m
) = 6A 16 α
r
H
r
where both r and the hash value are unknown. In typical use cases, the hash value
is a 160-bit long SHA-1 digest, and N is an RSA modulus of around 1
024 bits.
The unknown string r can be of various sizes depending on the nature of the signed
message; the shorter r is, the easier the attack becomes.
More generally, we will consider encoded messages of the form
,
μ(
m
) =
A
+
B
·
x 0 +
C
·
y 0
Search WWH ::




Custom Search