Leakage-Resilient Symmetric Encryption via Re-keying

Michel Abdalla (1) , Sonia Belaïd (1) , Pierre-Alain Fouque (2, 3)

1 LIENS - Laboratoire d'informatique de l'école normale supérieure
2 UR - Université de Rennes
3 IUF - Institut universitaire de France

In the paper, we study whether it is possible to construct an efficient leakage-resilient symmetric scheme using the AES block cipher. We aim at bridging the gap between the theoretical leakage-resilient symmetric primitives used to build encryption schemes and the prac-tical schemes that do not have any security proof against side-channel adversaries. Our goal is to construct an as efficient as possible leakage-resilient encryption scheme, but we do not want to change the crypto-graphic schemes already implemented. The basic idea consists in adding a leakage-resilient re-keying scheme on top of the encryption scheme and has been already suggested by Kocher to thwart differential power analy-sis techniques. Indeed, in such analysis, the adversary queries the encryp-tion box and from the knowledge of the plaintext/ciphertext, she can per-form a divide-and-conquer key recovery attack. The method consisting in changing the key for each or after a small number of encryption with the same key is known as re-keying. It prevents DPA adversaries but not SPA attacks which uses one single leakage trace. Here, we prove that using a leakage-resilient re-keying scheme on top of a secure encryption scheme in the standard model, leads to a leakage-resilient encryption scheme. The main advantage of the AES block cipher is that its implementations are generally heuristically-secure against SPA adversaries. This assump-tion is used in many concrete instantiations of leakage-resilient symmet-ric primitives. Consequently, if we use it and change the key for each new message block, the adversary will not be able to recover any key if the re-keying scheme is leakage-resilient. There is mainly two different techniques for re-keying scheme, either parallel or sequential, but if we want to avoid the adversary having access to many inputs/outputs, only the sequential method is possible. However, the main drawback of the latter technique is that in case of de-synchronization, many useless com-putations are required. In our re-keying scheme, we use ideas from the skip-list data structure to efficiently recover a specific key. Full version of the paper published in the proceedings of CHES 2013.

Mots clés: leakage-resilience; symmetric encryption; re-keying; synchro-nization

Domaines: Cryptographie et sécurité [cs.CR]

Michel Abdalla, Sonia Belaïd, Pierre-Alain Fouque. Leakage-Resilient Symmetric Encryption via Re-keying. Cryptographic Hardware and Embedded Systems - {CHES} 2013, Aug 2013, Santa Barbara, United States. pp.18, ⟨10.1007/978-3-642-40349-1_27⟩. ⟨hal-01094306⟩