On the Physical Security of Cryptographic Implementations
Thesis defended on September 22nd 2009 at University of Luxembourg.
PhD advisor: Jean-Sébastien Coron
PhD committee: Alex Biryukov, Jean-Sébastien Coron, Louis Goubin, Marc Joye, Franck Leprévost, François-Xavier Standaert
Abstract:
In modern cryptography, an encryption system is usually studied in the so-called
black-box model. In this model, the cryptosystem is seen as an oracle replying
to message encryption (and/or decryption) queries according to a secret value:
the key. The security of the cryptosystem is then defined following a simple
game. An adversary questions the oracle about the encryption (and/or decryption)
of messages of its choice and, depending on the answers, attempts to recover the
value of the secret key (or to encrypt/decrypt a message for which he did not
query the oracle). If by following an optimal strategy the adversary only has a
negligible chance of winning, the system is considered as secure. Several
cryptosystems have been proved secure in the black-box model. However, this
model is not always sufficient to ensure the security of a cryptosystem in
practice. Let us consider the example of smart cards which are used as platforms
for cryptosystems in various applications such as banking, access control,
mobile telephony, pay TV, or electronic passport. By the very nature of these
applications, a cryptosystem embedded on a smart card is physically accessible
to potential attackers. This physical access invalidates the modeling of the
cryptosystem as a simple encryption oracle since it allows the adversary to
observe and disrupt its physical behavior. New attacks then become possible
which are known as physical cryptanalysis.
Physical cryptanalysis includes two main families of attacks: side channel
attacks and fault attacks. The purpose of side channel attacks is to analyze the
different physical leakages of a cryptographic implementation during its
computation. Chief among these rank timing, power consumption, and
electromagnetic radiation. Observing these so-called side channels provides
sensitive information about the cryptographic computation. The secret key value
can then be easily recovered by statistical treatment although the cryptosystem
is secure in the black-box model. The access to a cryptographic implementation
enables more than a simple observation of its physical behavior; it is also
possible to disrupt its computation. Working on this assumption, fault attacks
consist in corrupting cryptographic computations so that they produce erroneous
results. Surprisingly, these results can be used in order to recover information
about the secret key.
This thesis focuses on physical cryptanalysis as well as on the secure
implementation of cryptographic primitives. We examine in the first part side
channel attacks from a theoretical viewpoint. Various techniques of attack based
on different statistical tools are addressed. We analyze their success rate, we
compare their efficiency and we propose some improvements. Our analyses are
illustrated by results of simulated attacks as well as practical attacks on
smart cards. The second part of this thesis is devoted to one of the most widely
used countermeasures to side channel attacks: data masking. Our investigations
concentrate on generic masking schemes for block ciphers such as the encryption
standards DES and AES. We analyze existing schemes, exhibiting some attacks
against certain of them and we propose new designs. The third and last part of
this thesis deals with fault attacks. First, we describe a new attack on the DES
cipher which exhibits some requirements to its secure implementation. We then
provide a case study based on the RSA cryptosystem where we propose a new
countermeasure which can also be applied to secure any exponentiation algorithm.
We finally address an important issue for practical security: the implementation
of coherence checks.
pdf file
