In the old days, valuable data was kept secret
within safes, and protected with locks.
Computational security was obtained thanks
to a number of combinations that grows exponentially
in the number of locks.
Yet, clever adversaries found a way to get
around this number of combinations, by listening
to lock clicks.
Taking advantage of this information, the
security of the safes is only linear in the
number of locks.
Similarly, in modern information systems,
valuable data is protected by encryption algorithms,
parametrized by secret keys.
Modern cryptography guarantees that the computational security of the data grows exponentially
in the key size.
Yet, clever adversaries also found ways to
get around such a guarantee, by exploiting
physical information such as the power consumption
of an implementation.
Those pretty much look like the electroencephalogram
of a chip.
In a side-channel attack, an adversary takes
advantage of these unintended leakages in
order to reduce the computational security
of the data from exponential to linear.
Side-channel attacks are not only an important
concern for the secure deployment of embedded
devices, like your smart card, mobile phone,
or for the Internet-of-Things.
They also raise fascinating questions regarding
the formal security guarantees that can be
expected from physical objects.
In the CRASH project, funded by the European
Research Council, we developed new solutions
for this purpose.
For example, evaluating a leaking device requires
estimating an unknown physical distribution.
If the evaluator’s model is perfect, we
can extract all the available information.
If not, the attack is suboptimal and the evaluation
may suffer from a false sense of security.
That is, a weak device looking secure because
of a weak evaluation.
Interestingly, and despite the perfect model
is always unknown to the evaluator, we developed
tools in order to guarantee a model is at
least good enough.
Those work by testing whether assumption errors
in the model are small enough in front of
the estimation errors.
Given some physical information, the next
evaluation step is to recover a key, by testing
the most likely candidates.
Enumeration can be viewed as digging into
a high-dimensional space.
If the correct key is within reach of the
adversary, the device is considered insecure.
If not, we need to determine its computational
security, a problem that is exponentially
hard if an exact solution has to be found.
Hence, here as well we developed tools in
order to approximate the answer.
Namely, rank estimation allows ensuring that
the computational security of a key is between
2 to 90 and 2 to 91 within seconds of computations,
while enumeration of up to 2 to 90 keys would
require billions of years on the same computer.
Thanks to these evaluation tools, we are equipped
to understand and develop new design methods
for secure implementations.
For example masking, where we split every
piece of secret into several shares, so that
the adversary has to target the shares jointly
in order to extract information.
Or re-keying, where every leaking device only
contains ephemeral secrets.
For this part of the project, I let you look
at the following website.
