Analysis of Implementations and Side-Channel Security of Frodo on Embedded Devices

  • Marco Martinoli

Student thesis: Doctoral ThesisDoctor of Philosophy (PhD)


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 halfwords of 32-bit registers. Finally, I challenge the need for cryptographically secure PRNGs for the generation of public matrices in favour of faster non-cryptographic PRNGs. The result is a dramatic improvement in performance accompanied by an educated discussion about whether doing so affects security.
Date of Award29 Sept 2020
Original languageEnglish
Awarding Institution
  • The University of Bristol
SupervisorM E Oswald (Supervisor) & Martijn Stam (Supervisor)

Cite this