Side-channel analysis of isogeny-based key encapsulation mechanisms and hash-based digital signatures

Current cryptographic solutions will become obsolete with the arrival of large-scale universal quantum computers. As a result, the National Institute of Standards and Technology supervises a post-quantum standardization process which involves evaluating candidates in a round-based competition-like format. Among these candidates, two notable schemes were submitted: the isogeny-based key encapsulation mechanism SIKE, and the hash-based digital signature scheme SPHINCS+. While considerable theoretical cryptanalysis has been dedicated to these candidates, relatively little attention has been given to the potential risks associated with their implementation. This thesis aims to address this gap by investigating the vulnerabilities of SIKE and SPHINCS+ to side-channel analysis. The first part of the thesis focuses on SIKE in relation to power analysis, where we describe three side-channel attacks. The first attack involves a horizontal differential power analysis of the three-point ladder used in the scheme, which recovers the secret scalar used to generate the secret isogeny within a single trace of power consumption through an extend-and-prune method. The second attack applies clustering power analysis to identify all the bits of the secret scalar from a single trace of the three-point ladder by exploiting the leakages of a procedure that swaps two elliptic curve points depending on the difference between two bits of the secret scalar. Lastly, the final attack details a zero-value point attack on the secret isogeny computation, which works by providing a malicious ciphertext that causes many operations, including the j-invariant calculation, to have a zero result based on the value of a single bit of the secret scalar. All attacks were experimentally verified with power traces collected from an STM32F3 running the recommended Cortex-M4 implementation of SIKE. Note that while the work in this thesis was being conducted, an independent attack on SIKE resulted in the total security break of the scheme. Our work remains of value despite this attack. The second part of the thesis focuses on the side-channel analysis of the SPHINCS family. First, we target the seminal SPHINCS-256 scheme through a differential power analysis of its pseudorandom number generator based on BLAKE-256, and describe an attack that recovers at least one 32-bit chunk of the signing key. We successfully conducted an experimental verification of this attack using 10,000 electromagnetic traces collected from a SAM3X8E running a custom Cortex-M3 SPHINCS-256 implementation. Secondly, we adapt an original fault attack on the SPHINCS-256 scheme to SPHINCS+ and analyze its impact on the security of the scheme. This analysis demonstrates that, with high probability, the security of SPHINCS+ significantly drops when a single random bit flip occurs anywhere in the signing process, and that the countermeasures based on caching the intermediate W-OTS+s offer a marginally greater protection against unintentional faults. Experimental validation of these results was conducted on an STM32F4 running the reference implementation of SPHINCS+ adapted to the Cortex-M4 architecture. The thesis concludes that the current state of SIKE and SPHINCS+ are vulnerable to side-channel analysis and proposes directions to develop effective countermeasures.