Research Area: CyberSecurity
Frodo is post-quantum cryptographic scheme, submitted to the NIST post-quantum standardisation effort. In this context, my contribution is twofold. First of all, I apply several side-channel techniques to attack Frodo on a (emulated) ARM Cortex-M0. By using a single power consumption trace of a matrix multiplication involving secret material, I show how a divide-and-conquer technique can be used to mount an efficient key recovery attack, which however does not fully exploit the available leakage.
Divide-and-conquer indeed assumes that leakage is independent across different subkeys, which is a limitation I overcome by mounting an extend-and-prune attack that exploits previously recovered subkeys to formulate an educated guess on intermediate variables. My study proceeds with the analysis of countermeasures: I show a deterministic countermeasure aimed at thwarting the extend-and-prune attack, I present a countermeasure that masks the Hamming weight thanks to the fact that secret elements are much smaller than the size of the space they live in, and finally I show how well-known countermeasures, such as blinding and masking, can be integrated into Frodo and assess the corresponding overhead.
My second contribution is a detailed analysis of the performances of Frodo on another embedded device, the ARM Cortex-M4. Although more powerful than the M0, this is still a very constrained environment where not all the matrices needed in the computations can be fully stored in memory, as they are too large. On-the-fly generation of such matrices is therefore required. I take the optimisations a step further by utilising ARM assembly instructions to multiply and accumulate 16-bit values as half words of 32-bit registers. Finally, I challenge the need for cryptographically secure PRNGs for the generation of public matrices in favor of faster non-cryptographic PRNGs. The result is a dramatic improvement in performance accompanied by an educated discussion about whether doing so affects security.
Name of the Researcher: Marco Martinoli
Name of the Supervisor(s): M E Oswald, Martijn Stam
Year of Completion: 2020
University: The University of Bristol
Thesis Link: Home Page Url
