Leakage- and Fault-Resilient Cryptography

Abstract

One of the goals of modern cryptography is to prevent an adversary from making forgeries. That is, sending a message which the receiver believes valid while not sent by a genuine sender. For "black box" adversaries, that is, adversaries that can access the inputs and outputs of a cryptographic algorithm, many efficient solutions exist and provide strong mathematical security guarantees.

Over the last decade, various research advances have shown that preventing black box attacks is not sufficient. For example, so-called side-channel adversaries can also access physical quantities produced during the cryptographic computations in a passive or active (i.e., injecting faults) way.

Thanks to these physical leakages, very efficient forgery attacks can be performed, for example by extracting the long-term cryptographic keys.

In this talk, we propose a formal solution to the problem of authenticity in the presence of physical attacks. For this purpose, we introduce a new theoretical framework that allows capturing security against such attacks, explain what security we aim for and how we model physical leakages, and then build constructions for which the physical security can be reduced to clear assumptions thanks to rigorous proofs.

In particular, our proofs have a very relevant practical meaning, because they point which part of an implementation must be strongly protected against side-channel (or faults) attacks and which part can leak (sometimes in full) with limited consequences (or can be left unprotected against fault attacks). Given the cost of protections against physical attacks, reducing significantly their use makes schemes significantly more efficient.

For example, we show that it is possible to reduce the security of full fledged authentication schemes to standard black box security properties and only requiring strong protections against side-channel (and faults) attacks for one execution of its underlying cryptographic primitive.

Finally, we show how our model can be used the study a mode-level study of cryptographic primitives that ensure security in the presence of leakage and faults.