Bitslicing is a technique commonly used in cryptography to implement high-throughput parallel and constant-time symmetric primitives. However, writing, optimizing and protecting bitsliced implementations by hand are tedious tasks, requiring knowledge of cryptography, CPU microarchitectures and side-channel attacks. The resulting programs tend to be hard to maintain due to their high complexity. To overcome those issues, we propose Usuba, a high-level domain-specific language to write symmetric cryptographic primitives. Usuba allows developers to write high-level specifications of ciphers without worrying about the actual parallelization: an Usuba program is a scalar description of a cipher, from which the Usuba compiler (Usubac) automatically produce vectorized bitsliced code.
When targeting high-end Intel CPUs, the Usubac applies several domain-specific optimizations, such as interleaving and custom instruction-scheduling algorithms. We are thus able to match the throughput of hand-tuned assembly and C implementations of several widely used ciphers.
Furthermore, in order to protect cryptographic implementations on embedded devices against side-channel attacks, we extend our compiler in two ways. First, we integrate into Usubac state-of-the-art techniques in higher order masking to generate implementations that are provably secure against power-analysis attacks. Second, we implement a backend for SKIVA, a custom 32-bit CPU enabling the combination of countermeasures against power-based and timing-based leakage, as well as fault injection.
Defence : 11/20/2020 - 15h - https://youtu.be/GSE1PdDo4nU
Jury members :
BHARGAVAN Karthik (Directeur de recherche, Inria) [Rapporteur]
BLAZY Sandrine (Professeur des Universités, IRISA) [Rapporteur]
COLLANGE Caroline (Chargé de recherche, Inria)
LEROY Xavier (Professeur, Collège de France)
PORNIN Thomas (Directeur technique, NCC Group)
VERGNAUD Damien (Professeur des Universités, Sorbonne Université)
MULLER Gilles (Directeur de recherche, Inria)
DAGAND Pierre-Évariste (Chargé de recherche, Sorbonne Université)
- D. Mercadier : “Usuba, Optimizing Bitslicing Compiler”, thesis, defence 11/20/2020, supervision Muller, Gilles, rapporteurs : DAGAND Pierre-Évariste (2020)
- P. Kiaei, D. Mercadier, P.‑E. Dagand, K. Heydemann, P. Schaumont : “Custom Instruction Support for Modular Defense against Side-channel and Fault Attacks”, International Workshop on Constructive Side-Channel Analysis and Secure Design, COSADE 2020, Lecture Notes in Computer Science, Lugano, Switzerland (2020)
- S. Belaid, P.‑E. Dagand, D. Mercadier, M. Rivain, R. Wintersdorff : “Tornado: Automatic Generation of Probing-Secure Masked Bitsliced Implementations”, EUROCRYPT, vol. 12107, Lecture Notes in Computer Science, Zagreb / Virtual, Croatia, pp. 311-341, (Springer) (2020)
- D. Mercadier, P.‑E. Dagand : “Usuba: high-throughput and constant-time ciphers, by construction”, PLDI 2019 - 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, Phoenix, United States, pp. 157-173, (ACM Press) (2019)
- D. Mercadier, P.‑E. Dagand, L. Lacassagne, G. Muller : “Usuba, Optimizing & Trustworthy Bitslicing Compiler”, WPMVP’18 - Workshop on Programming Models for SIMD/Vector Processing, Vienna, Austria, (ACM Press) (2018)