CRYSTALS-Kyber is a post-quantum secure key encapsulation mechanism which is currently being standardized by the NIST. This makes it important to assess the resistance of CRYSTALS-Kyber implementations to physical attacks. In this paper, we present an attack on a masked and shuffled implementation of CRYSTALS-Kyber in ARM Cortex-M4 that combines side-channel analysis (SCA) with fault injection. First, voltage glitching is performed to bypass the shuffling. We found settings that consistently skip the desired instructions without crashing the device. After the successful fault injection, a deep learning-assisted profiled power analysis based on the Hamming weight leakage model is applied to recover the message (shared key). We use a partial key enumeration method that significantly increases the success rate of message recovery. We also propose countermeasures against the presented attack.

Most of the previous attacks on Dilithium exploit side-channel information which is leaked during the computation of the polynomial multiplication cs1, where s1 is a small-norm secret and c is a verifier's challenge. In this paper, we present a new attack utilizing leakage during secret key unpacking in the signing algorithm. The unpacking is also used in other post-quantum cryptographic algorithms, including Kyber, because inputs and outputs of their API functions are byte arrays. Exploiting leakage during unpacking is more challenging than exploiting leakage during the computation of cs1 since c varies for each signing, while the unpacked secret key remains constant. Therefore, post-processing is required in the latter case to recover a full secret key. We present two variants of post-processing. In the first one, a half of the coefficients of the secret s1 and the error s2 is recovered by profiled deep learning-assisted power analysis and the rest is derived by solving linear equations based on t = As1 + s2, where A and t are parts of the public key. This case assumes knowledge of the least significant bits of t, t0. The second variant uses lattice reduction to derive s1 without the knowledge of t0. However, it needs a larger portion of s1 to be recovered by power analysis. We evaluate both variants on an ARM Cortex-M4 implementation of Dilithium-2. The experiments show that the attack assuming the knowledge of t0 can recover s1 from a single trace captured from a different from profiling device with a non-negligible probability.

Creating a good deep learning model is an art which requires expertise in deep learning and a large set of labeled data for training neural networks. Neither is readily available. In this paper, we introduce a method that enables us to recover messages of LWE/LWR-based PKE/KEMs using simple multilayer perceptron (MLP) models trained on a small dataset. The core idea is to extend the attack dataset so that at least one of its traces has the ground truth label to which the models are biased towards. We demonstrate the effectiveness of the presented method on the examples of CRYSTALS-Kyber and Saber algorithms implemented in ARM Cortex-M4 CPU on nRF52832 system-on-chip supporting Bluetooth 5.2.We use amplitude-modulated EM emanations which are typically weaker and noisier than power or near-field EM side channels, and thus more difficult to exploit.

CRYSTALS-Kyber has been recently selected by the NIST as a new public-key encryption and key-establishment algorithm to be standardized. This makes it important to assess how well CRYSTALS-Kyber implementations withstand side-channel attacks. Software implementations of CRYSTALS-Kyber have already been analyzed and the discovered vulnerabilities were patched in the subsequently released versions. In this paper, we present a profiling side-channel attack on a hardware implementation of CRYSTALS-Kyber. Since hardware implementations carry out computations in parallel, they are typically more difficult to break than their software counterparts. We demonstrate a successful message (session key) recovery attack on a Xilinx Artix-7 FPGA implementation of CRYSTALS-Kyber  by deep learning-based power analysis. Our results indicate that currently available hardware implementations of CRYSTALS-Kyber need better protection against side-channel attacks.

In this paper, we show that a software implementation of IND-CCA-secure Saber key encapsulation mechanism protected by first-order masking and shuffling can be broken by deep learning-based power analysis. Using an ensemble of deep neural networks trained at the profiling stage, we can recover the session key and the secret key from 257 × N and 24 × 257 × N traces, respectively, where N is the number of repetitions of the same measurement. The value of N depends on the implementation of the algorithm, the type of device under attack, environmental factors, acquisition noise, etc.; in our experiments N= 10 is sufficient for a successful attack. The neural networks are trained on a combination of 80% of traces from the profiling device with a known shuffling order and 20% of traces from the device under attack captured for all-0 and all-1 messages. “Spicing” the training set with traces from the device under attack helps us minimize the negative effect of inter-device variability.

CRYSTALS-Kyber has been selected by the NIST as a public-key encryption and key encapsulation mechanism to be standardized. It is also included in the NSA's suite of cryptographic algorithms recommended for national security systems. This makes it important to evaluate the resistance of CRYSTALS-Kyber's implementations to side-channel attacks. The unprotected and first-order masked software implementations have been already analysed. In this paper, we present deep learning-based message recovery attacks on the omega-order masked implementations of CRYSTALS-Kyber in ARM Cortex-M4 CPU for omega <= 5. The main contribution is a new neural network training method called recursive learning. In the attack on an omega-order masked implementation, we start training from an artificially constructed neural network M-omega whose weights are partly copied from a model M omega-1 trained on the (omega - 1)-order masked implementation, and then extended to one more share. Such a method allows us to train neural networks that can recover a message bit with the probability above 99% from high-order masked implementations.

Public-key cryptographic schemes currently in use depend on the intractability of certain mathematical problems such as integer factorization or the discrete logarithm. However, Shor's algorithm can solve these problems in polynomial time if large-scale quantum computers become available. This will compromise the security of today's public-key cryptosystems. To address this issue, new public-key cryptographic primitives are being developed. One of them is Saber whose security relies on the Learning With Rounding (LWR) problem that is believed to be hard for quantum computers. The resistance of unprotected and first-order masked implementations of Saber to side-channel attacks has been already investigated. In this paper, we demonstrate the first successful message and secret key recovery attacks on the second- and third-order masked implementations of Saber in ARM Cortex-M4 CPU by deep learning-based power analysis. Our experimental results show that currently available software implementations of Saber need better protection.

Shuffling is a well-known countermeasure against side-channel attacks. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel attacks more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the long-term secret key was reported. In this paper, we present an attack that can recover the long-term secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack. We capture a power trace during the execution of the decryption algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted. By recovering messages contained in k∗ l chosen ciphertexts constructed using a new method based on error-correcting codes of length l, where k is the module rank, we recover the long-term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.

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.

In the ongoing last round of NIST’s post-quantum cryptography standardization competition, side-channel analysis of finalists is a main focus of attention. While their resistance to timing, power and near field electromagnetic (EM) side-channels has been thoroughly investigated, amplitude-modulated EM emanations has not been considered so far.The attacks based on amplitude-modulated EM emanations are more stealthy because they exploit side-channels intertwined into the signal transmitted by the on-board antenna. Thus, they can be mounted on a distance from the device under attack.In this paper, we present the first results of an amplitude-modulated EM side-channel analysis of one of the NIST PQ finalists, Saber key encapsulation mechanism (KEM), implemented on the nRF52832 (ARM Cortex-M4) system-on-chip supporting Bluetooth 5.By capturing amplitude-modulated EM emanations during decapsulation, we can recover each bit of the session key with 0.91 probability on average.