# A Countermeasure to Side Channel Message Recovery Attacks Using Chosen Ciphertexts Against ML-KEM

Pierre-Augustin Berthet

► To cite this version:

Pierre-Augustin Berthet. A Countermeasure to Side Channel Message Recovery Attacks Using Chosen Ciphertexts Against ML-KEM. Central European Conference on Cryptology, NASK- National Research Institute, Warsaw, Poland; Military University of Technology, Warsaw, Poland, Jun 2024, Warsaw, Poland. hal-05040679

HAL Id: hal-05040679

https://hal.science/hal-05040679v1

Submitted on 19 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Countermeasure to Side Channel Message Recovery Attacks Using Chosen Ciphertexts Against ML-KEM<sup>a</sup>

Pierre-Augustin Berthet<sup>1,2</sup>

Hensoldt SAS France, Plaisir, France, pierre-augustin.berthet@hensoldt.net
Télécom Paris, Palaiseau, France, berthet@telecom-paris.fr

**Keywords:** CECC 2024 · Post-Quantum Cryptography · ML-KEM FIPS 203 · Side-Channel Analysis · Countermeasure · Abstract

## Introduction

With the emergence of quantum computing, new asymmetric cryptography primitives are studied. Amongst the ones selected by the National Institute of Standards and Technology (NIST) [1] to be a future standard is Module-Lattice based Key Encapsulation Module (ML-KEM) or FIPS 203 [5]. This KEM is based on the CRYSTALS-Kyber candidate [2] and is the algorithm studied in this work.

A recent concern for new cryptographic primitives is their resilience to physical attacks. First introduced by Kocher [4], Side-Channel Analysis (SCA) is a kind of cryptanalysis which targets the physical environment of a cryptosystem and analyze potential leakages (execution timing, heat, power consumption, electromagnetic emissions...) to try and discover correlations between sensitive data and the physical data the attacker observes.

The resilience of ML-KEM and more specifically CRYSTALS-Kyber to those attacks has already been studied. Several papers sum up the existing attacks and countermeasures against microcontroller implementations, like Ravi et al. [7].

In this work we propose a countermeasure to a specific attack designed by Ravi et al. [6]. This countermeasure has the advantage of reusing existing parts of ML-KEM. This allows our work to be mostly compatible with more generic countermeasures like masking or shuffling.

## 1 ML-KEM

ML-KEM [5] is a lattice-based KEM relying on the Learning-With-Errors (LWE) as well as on the Learning-With-Rounding (LWR) mathematical problems. It manipulates polynomials as well as vectors and matrices of polynomials over $F_{3329}/X^{256} + 1$. It uses a Public-Key Encryption (PKE) core. To avoid chosen-ciphertexts attacks (CCA), the core is used within an adaptation of the Fujisaki-Okamoto Transform (FOT) [3].

However, a side-channel opponent can circumvent the FOT by observing leakages emanating from the use of the PKE core. Thus, it can re-enact a chosen-ciphertext attack and recover the message or the secret by observing the leakage from the deciphered message at the end of the call of the PKE Decrypt core within the Decapsulation procedure.

<footnote><sup>a</sup>Supported by Agence Innovation Défense, Ministère des Armées</footnote>
## 2 The Attack from Ravi et al.

Such an attack using chosen-ciphertexts was proposed by Ravi et al. [6]. The PKE Decrypt function outputs the following:

$$m = \text{Compress}_q(v - \vec{u} \cdot \vec{s}, 1) \qquad (1)$$

$m$ is the message<fnref n="1" />, $c = (\vec{u}, v)$ the ciphertext and $\vec{s}$ the secret. $v - \vec{u} \cdot \vec{s}$ is a polynomial. The $\text{Compress}_q$ function does the following on each coefficient $\alpha$ of a polynomial:

$$\text{Compress}_q(\alpha, d) = \lceil 2^d/q * \alpha \rceil \text{ mod } 2^d \qquad (2)$$

When $d = 1$, this function simply outputs 0 if the value $\alpha$ is closer from 0 than $q/2 = 1665$ and 1 if $\alpha$ is closer to $q/2$. However, it also means that adding $q/2$ to $\alpha$ inverts the output of $\text{Compress}_q$. Ravi et al. [6] exploit this weakness:

$$\text{Compress}_q((v + 1665 * X^i) - \vec{u} \cdot \vec{s}, 1) = m \oplus (1 \ll i) \qquad (3)$$

By recovering the Hamming Weight of $m$ before and after their bit-flipping attack through side-channel leakages, they can recover the exact value of the i-th bit of the message.

## 3 Our Countermeasure

### 3.1 Countering Ravi et al.

To counter Ravi et al. [6], we use their attack as a defense mechanism. By adding to the ciphertext $v$ a random polynomial where the coefficients can uniformly be 0 or 1665, we perform a random bit-flipping of the 256 bits of the message. As we know which bits were flipped, we are able to undo the flipping later in the algorithm to ensure correctness.

The effectiveness of our countermeasure against Ravi et al. [6] is immediate: indeed, a side-channel opponent performing the attack will first recover the Hamming Weight not of $m$ but of $m \oplus \text{mask}_1$. After performing a bit-flipping error $e$ it will recover the Hamming Weight of $m \oplus e \oplus \text{mask}_2$. An attacker can't conclude without knowing both $\text{mask}_1$ and $\text{mask}_2$, as they are random and independent.

This method re-uses elements existing within ML-KEM. Generating a 256 bit-long message is done within the Encapsulation function. Converting this bit-string $\text{mask}$ into a polynomial such as its coefficients are given by $1665 * \text{mask}_i$ (with $\text{mask}_i$ the i-th bit of $\text{mask}$) is also performed within the Encapsulation, more specifically by the $\text{Decompress}_q$ function<fnref n="2" />. We have the following PKE Decrypt with the countermeasure:

**Algorithm 1 PKE Decrypt with countermeasure**

1: **Input:** Ciphertext $c = (v, \vec{u})$

2: **Input:** Secret key $\vec{s}$

3: **Output:** Message $mm = m \oplus \text{mask}$, Mask $\text{mask}$

4: $\text{mask}$ (256 random bits from system forming a degree 255 polynomial)

5: $mm = \text{Compress}_q(v + \text{Decompress}_q(\text{mask}, 1) - t\vec{s} \cdot \vec{u}, 1)$

6: **return** $mm, \text{mask}$

### 3.2 Extending The Countermeasure To The Decapsulation

PKE Decrypt is the first step of the ML-KEM Decapsulation. The message is used afterwards in a hash function to generate a seed for randomness. The seed has to be correct, thus limiting the options to the use of a masked<fnref n="3" /> boolean hash function or some clever trick to remove the

<footnote n="1">¹Converted directly from a degree 255 polynomial to a 256 bit message</footnote>

<footnote n="2">²This function simply multiplies each coefficient of a polynomial by 1665 mod 3329 when $d=1$</footnote>

<footnote n="3">³Masking divides the secret into shares processed separately</footnote>
mask from the message within the function call without leakage. This is one drawback of our countermeasure which thus require a different hash function from the one of the implementation it protects. With this seed, the message is also used in a re-encryption involving PKE Encrypt. We have several options.

As the output of our PKE Decrypt is identical to a first-order boolean masking of the message, one could use for the remainder of the algorithm a first-order masked implementation. However, this impacts the performances of the implementation negatively as masked implementations are costly. Thus, we propose another approach.

We propose to perform the re-encryption not with the correct message but with the masked one. The message intervenes in the generation of the ciphertext $v$ as follows:

$$v = \vec{t} \cdot \vec{r} + e_2 + Decompress_q(m, 1) \quad (4)$$

$\vec{t}$ is part of the public key, $\vec{r}$ and $e_2$ are ephemeral secret and error generated for the message. Thus, by proposing to encapsulate the message $m$ in its masked form $mm = m \oplus mask$, we have the following:

$$vm = \vec{t} \cdot \vec{r} + e_2 + Decompress_q(mm, 1) \quad (5)$$

Naturally, this differ from the correct $v$. To compensate, we add to $vm$ the decompression of the mask:

$$v' = vm + Decompress_q-Year, 1) \quad (6)$$

However, we noticed that $v'$ is not always equal to $v$ as shown in the following table:

<table><caption>Table 1: Decompress_q-Year, 1) + Decompress_q(mm, 1)</caption><thead><tr><th></th><th>mm<sub>i</sub> = 0</th><th>mm<sub>i</sub> = 1</th></tr></thead><tbody><tr><td>mask<sub>i</sub> = 0</td><td>0</td><td>1665</td></tr><tr><td>mask<sub>i</sub> = 1</td><td>1665</td><td>3330≠0</td></tr></tbody></table>

There is a bias of 3330 = 1 mod 3329 when both the mask and the masked message are equal to 1 (implying the message is 0). Thus, we propose 2 strategies to counter this bias:

* We retrieve $mask \land mm$ from $v'$ as follow: $v' = vm + Decompress_q-Year, 1) - \sum_{i=0}^{255} (mask_i \land mm_i) * X^i$

* We modify the ciphertext comparison which concludes the FOT and requires the correct ciphertext by including the bias within it.

The first option can create a leakage point if not done properly. The second one is inspired by most of the masked implementations of ML-KEM. Existing masked implementations do not compare $c_v$ and $c_{v'} = Decompress_q(v', d_v)$ but $v = Decompress_q(c_v, d_v)$ and $v'$. Due to the lossy nature of the compression, they do not check $c_v = c_{v'}$ but $||v - v'|| \in [0, 104]$. Thus, we propose to check $||v - v'|| \in [0, 105]$.

## 3.3 Comparison With Existing Countermeasures And Compatibility

According to Ravi et al. [7], generic countermeasures like shuffling<fnref n="4" /> or masking do not seem to be efficient at countering the attack from Ravi et al. [6]. Thus they recommend hardware-based countermeasures, like shielding or adding jitter to decrease the Signal-to-Noise Ratio (SNR).

However, as our countermeasure involves re-using existing part of a ML-KEM implementation, it also applies to masked ones and shuffled ones. The only caveat for masking is regarding formal proofs of security as the composition of masked gadgets is not always secured and can require a refresh of the shares used within the mask. Note however that those refresh are common within masked implementations.

<footnote n="4">⁴Randomly changing the order of execution the instructions while ensuring correctness</footnote>
## 3.4 Effect Of Our Countermeasure On Other CCA Side Channel Attacks And Applications

Our countermeasure deprives an opponent of the control of the impact of the ciphertext $v$. Thus, any attack requiring control over $v$ is affected by our countermeasure. Attacks that benefits from the control of $v$ are also affected albeit only slow down. This includes a majority of existing side-channel attacks against ML-KEM on FPGA and also current Artificial Intelligence based attacks.

While our countermeasure can't be used as a standalone countermeasure to fully protect ML-KEM from a side-channel opponent, it is useful for constrained devices which can't use generic countermeasures like masking but can benefit from a bit of SCA security to protect the message. Thanks to its compatibility with masking, our countermeasure help in increasing the resilience of masked implementations against AI-assisted opponents.

## 4 Conclusion

In this work we propose a countermeasure to a specific side channel attack using chosen ciphertexts against ML-KEM. We have demonstrated its theoretical effectiveness against the specified attack and also discussed its compatibility with more generic and larger countermeasures, as well as discussed the impact of our countermeasure on some other attacks involving chosen ciphertexts.

**Acknowledgments** This work was realized thanks to the grant 2022156 from the Appel à projets 2022 thèses AID Cifre-Défense by the Agence de l'Innovation de Défense (AID), Ministère des Armées (French Ministry of Defense).

## References

[1] Gorjan Alagic, Daniel Apon, David Cooper, Quynh Dang, Thinh Dang, John Kelsey, Jacob Lichtinger, Carl Miller, Dustin Moody, Rene Peralta, et al. Status report on the third round of the nist post-quantum cryptography standardization process. *US Department of Commerce, NIST*, 2022.

[2] Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. Crystals-kyber algorithm specifications and supporting documentation. *pq-crystals*, 2021.

[3] Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption schemes. In *Annual international cryptology conference*, pages 537–554. Springer, 1999.

[4] Paul C Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In *Advances in Cryptology—CRYPTO’96: 16th Annual International Cryptology Conference Santa Barbara, California, USA August 18–22, 1996 Proceedings 16*, pages 104–113. Springer, 1996.

[5] NIST. Module-lattice-based key-encapsulation mechanism standard. *NIST FIPS*, 2023.

[6] Prasanna Ravi, Shivam Bhasin, Sujoy Sinha Roy, and Anupam Chattopadhyay. On exploiting message leakage in (few) nist pqc candidates for practical message recovery attacks. *IEEE Transactions on Information Forensics and Security*, 17:684–699, 2021.

[7] Prasanna Ravi, Anupam Chattopadhyay, Jan Pieter D’Anvers, and Anubhab Baksi. Side-channel and fault-injection attacks over lattice-based post-quantum schemes (kyber, dilithium): Survey and new results. *ACM Transactions on Embedded Computing Systems*, 23(2):1–54, 2024.