Abstract
The appearance of Shor’s Algorithm in 1994 provided a polynomial-time algorithm to solve assumed hard problems for classical computers such as large integer factorization or discrete logarithm, given a powerful enough quantum computer. The targeted problems are the base of widely used public key cryptosystems such as RSA or ECC. To answer the future treat of quantum computers, the United States’ National Institute of Standards and Technology (NIST) launched the Post-Quantum Cryptography Standardization Process to analyze new propositions of cryptosystems that are assumed to not be targeted by quantum computers. One particular construction stood out for its balance of performance and security: lattice-based cryptography. Among the standards chosen by NIST, three lattice-based proposals can be found, including CRYSTALS-KYBER in the key-encapsulation mechanism category. However, the algorithms are usually built for mathematical hardness that does not guarantee their resistance to side-channel attacks (SCA) on the implementation side. The goal of this work is to analyze such resistance of lattice-based cryptography to SCA, with a focus on CRYSTALS-KYBER and its hardware implementations, in terms of vulnerability to attacks, and trade-off between area, security and performance of SCA countermeasures.First, we describe the background of lattice-based cryptography, CRYSTALS-KYBER and SCAs, to then delve into the specific attacks targeted towards CRYSTALS-KYBER’s routines, including their countermeasures and attacks targeting hardware implementations.Secondly, we describe a Correlation Power Analysis (CPA) on an FPGA implementation of CRYSTALS-KYBER, which was at its time, the first attack reported in the literature for such algorithm in hardware. This unprofiled attack requires around 160000 traces to recover the full key. Additionally, we propose a low-cost countermeasure to counteract the used attack model.Subsequently, we undertake the analysis of local masking, a countermeasure against Soft-Analytical Side-Channel Attacks (SASCAs) for the Number-Theoretic Transform (NTT), operation used to accelerate the polynomial multiplication in CRYSTALS-KYBER. By randomizing constants called twiddle factors, it effectively masks the real intermediate values in the NTT. We first propose a hardware implementation capable of executing different variants of this countermeasure. Then, we identify possible vulnerabilities of this countermeasure, inherent to its nature. Lastly, we perform a leakage assessment on an FPGA with our implementation, confirming the existence of leakage.Finally, we examine an adaptation of SASCA for an NTT that employs local masking. Since the twiddle factors have become sensitive, we assume an attacker could exploit this leakage to adjust a factor graph. We simulate the attack, varying the number of masks u used to randomize the twiddle factors at each layer, demonstrating that the attack remains feasible. Specially, if u is low (u = {1, 2, 4}), the attack performs similarly or better than the unprotected case. From u = 8, increasing u gradually decreases the permissible noise level required for an acceptable success rate. When using u=n masks, the most secure scenario, the maximum standard deviation of noise for which the attack maintains a success rate above 70% is σ = 0.3. This case could be achievable in scenarios with very low noise in reality.In summary, this thesis explores some challenges of securing an implementation of CRYSTALS-KYBER, against multi-trace attacks like the CPA or potentially single-trace attacks such as SASCA. We analyze countermeasures in terms of their security offered and their trade-off with area and performance, highlighting in general that confident security is only achieved by a combination of countermeasures.