Public key cryptographic schemes used today rely on the intractability of certain mathematical problems that are known to be efficiently solvable with a large-scale quantum computer. To address the need for long-term security, in 2016 NIST started a project for standardizing post-quantum cryptography (PQC) primitives that rely on problems not known to be targets for a quantum computer, such as lattice problems. However, algorithms that are secure from the point of view of traditional cryptanalysis can be susceptible to side-channel attacks. Therefore, NIST put a major emphasis on evaluating the resistance of candidate algorithms to side-channel attacks.

This thesis focuses on investigating the susceptibility of two NIST PQC candidates, Saber and CRYSTALS-Kyber Key Encapsulation Mechanisms (KEMs), to side-channel attacks. We present a collection of nine papers, of which eight focus on side-channel analysis of Saber and CRYSTALS-Kyber, and one demonstrates a passive side-channel attack on a hardware random number generator (RNG) integrated in STM32 MCUs.

In the first three papers, we demonstrate attacks on higher-order masked software implementations of Saber and CRYSTALS-Kyber. One of the main contributions is a single-step deep learning message recovery method capable of recovering secrets from a masked implementation directly, without explicitly extracting the random masks. Another main contribution is a new neural network training method called recursive learning, which enables the training of neural networks capable of recovering a message bit with a probability higher than 99% from higher-order masked implementations.

In the next two papers, we show that even software implementations of Saber and CRYSTALS-Kyber protected by both first-order masking and shuffling can be compromised. We present two methods for message recovery: Hamming weight-based and Fisher-Yates (FY) index-based. Both approaches are successful in recovering secret keys, with the latter using considerably fewer traces. In addition, we extend the ECC-based secret key recovery method presented in the prior chapter to ECCs with larger code distances.

In the last two papers, we consider a different type of side channel amplitude-modulated electromagnetic (EM) emanations. We show that information leaked from implementations of Saber and CRYSTALS-Kyber through amplitude-modulated EM side channels can be used to recover the session and secret keys. The main contribution is a multi-bit error-injection method that allows us to exploit byte-level leakage. We demonstrate the success of our method on an nRF52832 system-on-chip supporting Bluetooth 5 and a hardware implementation of CRYSTALS-Kyber in a Xilinx Artix-7 FPGA.

Finally, we present a passive side-channel attack on a hardware TRNG in a commercial integrated circuit in our last paper. We demonstrate that it is possible to train a neural network capable of recovering the Hamming weight of random numbers generated by the RNG from power traces with a higher than 60% probability. We also present a new method for mitigating device inter-variability based on iterative re-training.

Overall, our research highlights the importance of evaluating the resistance of candidate PQC algorithm implementations to side-channel attacks and demonstrates the susceptibility of current implementations to various types of side channel analysis. Our findings are expected to provide valuable insights into the design of future PQC algorithms that are resistant to side-channel analysis.

Kryptografiska system för offentlig nyckel som används idag är beroende av omöjligheten i vissa matematiska problem som är kända för att vara effektivt lösbara med en storskalig kvantdator. För att möta behovet av långsiktig säkerhet startade NIST 2016 ett projekt för standardisering av post-kvantkryptografi (PQC) primitiver som förlitar sig på problem som inte är kända för att vara mål för en kvantdator, såsom gitterproblem. Algoritmer som är säkra ur traditionell kryptoanalyss synvinkel kan dock vara svaga mot sidokanalsattacker. Därför lägger NIST stor vikt vid att utvärdera härdigheten hos kandidatalgoritmer mot sidokanalsattacker.

Denna avhandling fokuserar på att undersöka känsligheten av två NIST PQC-kandidater, Saber och CRYSTALS-Kyber Key Encapsulation Mechanisms (KEMs), mot sidokanalsattacker. Vi presenterar en samling av nio artiklar, varav åtta fokuserar på sidokanalanalys av Saber och CRYSTALS-Kyber, och en visar en passiv sidokanalattack på en hårdvarugenerator för slumptal (RNG) integrerad i STM32 MCU:er.

I de första tre artiklarna demonstrerar vi attacker på maskerade programvaruimplementationer av hög ordning av Saber och CRYSTALS-Kyber. Vårt huvudsakliga bidrag är en ny träningsmetod för neuronnätverk som kallas rekursiv inlärning, som möjliggör träning av neuronnätverk som kan återställa en meddelandebit med en sannolikhet som är högre än 99% från maskerade implementationer av hög ordning.

I de följande två artiklarna visar vi att även mjukvaruimplementationer av Saber och CRYSTALS-Kyber skyddade av både första ordningens maskering och blandning kan äventyras. Vi presenterar två metoder för meddelandeåterställning: Hamming-viktbaserad och Fisher-Yates (FY) indexbaserad. Båda tillvägagångssätten är framgångsrika för att återställa hemliga nycklar, där den senare använder betydligt färre mätningar. Dessutom utökar vi den ECC-baserade metoden för hemlig nyckelåterställning som presenterades i det föregående kapitlet till ECC:er med större kodavstånd.

I de två sista artiklarna betraktar vi en annan typ av sidokanalamplitudmodulerade elektromagnetiska (EM) emanationer. Vi visar att information som läckt från implementeringar av Saber och CRYSTALS-Kyber genom amplitudmodulerade EM-sidokanaler kan användas för att återställa sessionen och hemliga nycklar. Det huvudsakliga bidraget är en flerbitars felinjiceringsmetod som gör att vi kan utnyttja läckage på bytenivå. Vi visar framgången av vår attack mot ett nRF52832 system-på-chip som stöder Bluetooth 5 och en hårdvaruimplementering av CRYSTALS-Kyber i Xilinx Artix-7 FPGA.

Slutligen presenterar vi en passiv sidokanalattack på en hårdvaru-TRNG i en kommersiell integrerad krets i vårt senaste dokument. Vi visar att det är möjligt att träna ett neuronnätverk som kan återvinna Hamming-vikten för slumptal som genereras av RNG från kraftmätningar med en sannolikhet som är högre än 60%. Vi presenterar också en ny metod för att mildra enhets intervariabilitet baserad på iterativ omträning.

Sammantaget belyser vår forskning vikten av att utvärdera motståndet hos  av kandidat-PQC-algoritmer mot sidokanalsattacker och visar känsligh-eten hos nuvarande PQC- för olika typer av sidokanalanalys. Våra resultat förväntas ge värdefulla insikter i utformningen av framtida PQC-algoritmer som är resistenta mot sidokanalanalys.

Traditional public key cryptosystems rely on the hardness of specific mathematical problems, such as integer factorization and discrete logarithm problem. However, these problems can be solved efficiently by Shor's algorithm on a large-scale quantum computer. Although the development of quantum computers has progressed slowly over the past 40 years, it is estimated that a cryptographically relevant quantum computer is likely to be available in 2040, which intensifies the need for quantum-resistant cryptographic algorithms. In response to the quantum threat, in 2016, NIST launched a competition for standardizing post-quantum cryptographic primitives. In August 2024, NIST selected CRYSTALS-Kyber as the public key encryption and key encapsulation standard, and CRYSTALS-Dilithium as the digital signature standard.

However, algorithms which are secure from the perspective of conventional cryptanalysis may still be vulnerable to physical attacks, such as side-channel attacks. This thesis evaluates the resilience of software implementations of three lattice-based post-quantum cryptographic algorithms: Saber, CRYSTALS-Kyber, and CRYSTALS-Dilithium to side-channel attacks.

The presented results are based on seven appended papers. Two of them focus on side-channel attacks on Saber, four target CRYSTALS-Kyber, and one considers CRYSTALS-Dilithium. The main contributions of the thesis are:

1. We evaluate and compare power side-channel and EM side-channel attacks, pointing that amplitude-modulated EM emissions are typically weaker and require a higher sampling rate for secret recovery. We also investigate the difficulty of performing attacks on protected and unprotected implementations.
2. We propose several methods to improve the attack efficiency. For example, a novel neural network model aggregation technique called threshold voting is introduced for deep learning-based attacks. A higher-order attack on CRYSTALS-Kyber is presented by combining the leakages from Barrett reduction and message decoding. Furthermore, an optimal chosen-ciphertext construction strategy is developed to maximize the probability of secret key recovery given a fixed probability of message bit recovery. 
3. We provide a thorough discussion of various attack scenarios, including attacks on encapsulation, decapsulation, and signing procedures. For each scenario, we outline the assumptions and requirements for a successful attack.
4. We present countermeasures to mitigate side-channel attacks at both the algorithmic and hardware levels. We also discuss the limitations of these countermeasures, as well as the challenges associated with deep learning-based attacks.

Most of the methods presented in this thesis are not limited to the specific algorithms described in the papers, and can be extended to other algorithms that are similar to Saber, CRYSTALS-Kyber, and CRYSTALS-Dilithium.

Traditionella kryptosystem med offentlig nyckel bygger på svårigheten i specifika matematiska problem, såsom faktorisering av heltal och problemet med diskreta logaritmer. Dessa problem kan dock lösas effektivt med Shors algoritm på en storskalig kvantdator. Även om utvecklingen av kvantdatorer har gått långsamt under de senaste 40 åren, beräknas det att en kryptografiskt relevant kvantdator sannolikt kommer att finnas tillgänglig år 2040, vilket ökar behovet av kvantresistenta kryptografiska algoritmer. Som svar på hotet från kvantdatorer lanserade NIST 2016 en tävling för standardisering av kvantdatorsäkra primitiver. I augusti 2024 valde NIST CRYSTALS-Kyber som standard för asymmetrisk kryptering och nyckelinkapsling, och CRYSTALS-Dilithium som standard för digitala signaturer.

Algoritmer som är säkra ur konventionell kryptanalytisk synvinkel kan dock fortfarande vara sårbara för fysiska attacker, såsom sidokanalsattacker. Denna avhandling utvärderar motståndskraften hos mjukvaruimplementationer av tre gitterbaserade kvantdatorsäkra algoritmer: Saber, CRYSTALS-Kyber och CRYSTALS-Dilithium mot sidokanalsattacker.

De presenterade resultaten baseras på sju bifogade artiklar. Två av dem fokuserar på sidokanalsattacker mot Saber, fyra riktar sig mot CRYSTALS-Kyber, och en behandlar CRYSTALS-Dilithium. Avhandlingens huvudsakliga bidrag är:

1. Vi utvärderar och jämför effektbaserade och EM-baserade sidokanalsattacker, och påpekar att amplitudmodulerade EM-emissioner typiskt är svagare och kräver högre samplingsfrekvens för att återskapa hemligheter. Vi undersöker även svårigheten med att utföra attacker på skyddade och oskyddade implementationer.
2. Vi föreslår flera metoder för att förbättra attackeffektiviteten. Till exempel introduceras en ny teknik för aggregering av neurala nätverksmodeller, kallad “threshold voting”, för attacker baserade på djupinlärning. En högre ordningens attack mot CRYSTALS-Kyber presenteras genom att kombinera läckage från Barrett-reduktion och meddelandede-kodning. Dessutom utvecklas en optimal strategi för valda chiffertextattacker för att maximera sannolikheten för att återskapa en hemlig nyckel givet en fast sannolikhet att återskapa av meddelandebitar.
3. Vi ger en grundlig diskussion av olika attackscenarier, inklusive attacker mot inkapsling, avkapsling och signering. För varje scenario redogör vi för antaganden och krav för en framgångsrik attack.
4. Vi presenterar motåtgärder för att försvåra sidokanalsattacker både på algoritm- och hårdvarunivå. Vi diskuterar också begränsningarna hos dessa motåtgärder samt utmaningarna med attacker baserade på djupinlärning.

De flesta metoder som presenteras i denna avhandling är inte begränsade till de specifika algoritmer som beskrivs i artiklarna, utan kan även tillämpas på andra algoritmer som liknar Saber, CRYSTALS-Kyber och CRYSTALS-Dilithium.