# Cracking the mask: SASCA against local-masked NTT for CRYSTALS-Kyber

Rafael Carrera Rodriguez, Florent Bruguier, Emanuele Valea, Pascal Benoit

► To cite this version:

Rafael Carrera Rodriguez, Florent Bruguier, Emanuele Valea, Pascal Benoit. Cracking the mask: SASCA against local-masked NTT for CRYSTALS-Kyber. IACR Communications in Cryptology, 2025, 2 (2), 10.62056/aesgbnja5. hal-05384787

HAL Id: hal-05384787

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

Submitted on 27 Nov 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
# Cracking the Mask: SASCA Against Local-Masked NTT for CRYSTALS-Kyber

Rafael Carrera Rodriguez<fnref n="1" />,<fnref n="2" /> ID, Florent Bruguier<fnref n="1" /> ID, Emanuele Valea<fnref n="2" /> ID
and Pascal Benoit<fnref n="1" /> ID

**Abstract.** Soft-Analytical Side-Channel Attacks (SASCAs) on lattice-based cryptography implementations have become a prominent vector of attack in the recent years, specially against the Number-Theoretic Transform (NTT). To address this issue, local masking with twiddle factors has been proposed as a countermeasure to protect the NTT against such attacks. In this paper we propose an adaptation of SASCA to local-masked NTT implementations, by modifying the factor graph representation to include the masking nodes. We evaluate the success rate of the attack with respect to the level of noise of simulated traces and the number of masks *u* per layer. We show that the attack proves very successful in the lower values of *u*, by even outperforming the attack on the unmasked case. When *u* is increased there is a gradual augmentation of security, which comes with an important overhead on performance. Thus, we question the practicality of this countermeasure when compared to other analyzed countermeasures in the state of the art, such as shuffling.

# 1 Introduction

Lattice based cryptography represents one of the most important categories of post-quantum cryptography. Its balance between security and efficiency has made it a popular alternative to classical public-key cryptosystems. As a matter of fact, the United States' National Institute of Standards and Technology (NIST) selected three lattice-based schemes as standards in its Post-Quantum Standardization process [Nat]: CRYSTALS-KYBER as a key encapsulation mechanism, and CRYSTALS-DILITHIUM and FALCON as digital signature schemes. An operation present in the aforementioned schemes is the Number-Theoretic Transform (NTT), an analog of the Fast Fourier Transform (FFT) over the ring of integers modulo *q*, used to accelerate polynomial multiplication, by bringing its complexity to $O(n \log n)$, where *n* is the degree of the polynomials. Polynomials are converted into the NTT domain, multiplied pointwise with linear complexity, and then converted back to normal domain.

However, the NTT and its pointwise multiplication have been targets of side-channel attacks, where an attacker exploits the leakage of intermediate values through physical measurements, such as power consumption or electromagnetic radiation. These attacks can be broadly divided into *vertical attacks*, where multiple traces are used to recover the secret key on few points of interest, and *horizontal attacks*, where a single trace (or few traces) is used to recover the secret key on multiple points of interest.

Examples of vertical attacks in the literature include the study on attacking the polynomial multiplication for multiple Key Encapsulation Mechanism (KEM) candidates

E-mail: rafael.carrera-rodriguez@lirmm.fr (Rafael Carrera Rodriguez), florent.bruguier@lirmm.fr (Florent Bruguier), emanuele.valea@cea.fr (Emanuele Valea), pascal.benoit@lirmm.fr (Pascal Benoit)

<footnote n="1">¹ LIRMM, University of Montpellier, CNRS, Montpellier, France</footnote>

<footnote n="2">² Univ. Grenoble Alpes, CEA, List, Grenoble, France</footnote>
on software by Mujdei et al. [MWK+22] and the attacks on hardware implementations of CRYSTALS-KYBER by Carrera Rodriguez et al. [CBVB23] and Zhao et al. [ZPM+23]. This type of attack is prevented by using masking countermeasures, where intermediate variables and functions are split into shares and shared functions, respectively.

On the other hand, masking is not enough to protect against horizontal attacks, since the splitting of the intermediate variables can be undone by an attacker by combining different points of interest in the same trace. Such attacks often include a profiling phase to fit a model of the leakage of the device, and then an attack phase to recover the secret key. One of the most interesting horizontal attacks in the state of the art against NTT is the Soft-Analytical Side-Channel Attack (SASCA) [PPM17, VCGS14]. Such attack combines the leakage of multiple points by representing the NTT as a bipartite graph of nodes representing the intermediate variables and the operations performed on them. Then, to combine the different probability distributions and obtain a marginalized distribution of every intermediate variable, the Belief Propagation (BP) algorithm is used. Several improvements from the original attack have been proposed, such as the usage of more efficient factor-graph representations [PP19] and the usage of chosen ciphertexts to reduce the entropy in the graph [HHP+21].

In the literature, two countermeasures have been proposed to protect the NTT against SASCA: shuffling [ZBT19, RPBC20], to randomize the execution flow and local masking [RPBC20], to randomize intermediate variables without splitting by modifying the elemental NTT operation and its constants, effectively applying a multiplicative mask. Shuffling has been analyzed in terms of security against SASCA [HSST23], showing that it remains as a strong countermeasure against the attack under certain implementation considerations. However, the security of local masking against SASCA has not been analyzed yet.

This paper explores the resilience of local masking against SASCA on NTT implementations, by identifying inherent vulnerabilities of the countermeasure and leveraging such vulnerabilities. This work adapts the attack on encryption from Pessl and Primas [PP19], modifying the factor graph to take into account the effect of local masking. We perform a simulated attack, by analyzing the success rate of the attack with respect to the level of noise of the captured traces and the number *u* of masks per layer of the NTT, flexible parameter to scale the security of the local masking countermeasure.

The contributions we present are threefold. **First**, we identify the inherent vulnerabilities of local masking that can be exploited by an attacker to recover the secret key. **Second**, we propose an adaptation of the factor graph representation proposed by [PP19] for a local-masked NTT. This novel representation provides flexibility to adapt the attack to different values of number *u* of masks per layer of the NTT. **Third**, we execute a simulated SASCA using this proposed factor graph, and we evaluate the success rate of the attack relative to the parameter *u* considered and the noise level considered. We show that augmenting *u* provides an incremental increase in security and that even with the highest level of security, attacks can still be conducted, notably in the case of low *u*, where the improvement in security is marginal or non-existent.

The organization of this paper is presented as follows: Section 2, presents the necessary background on the NTT, CRYSTALS-KYBER and SASCA. Then, Section 3 shows the countermeasure of local masking against SASCA for the NTT, along with possible exploitable vulnerabilities of it. Section 5 outlines the attack, by explaining the attacker assumptions, the considered target, the factor graph and how the vulnerabilities detected in Section 3 are leveraged. Section 6 presents the results of the simulated attack and discussion of their implications. Finally, Section 7 concludes this paper.
# 2 Background

## 2.1 Notation

The ring of integers modulo $q$ is denoted as $\mathbb{Z}_q$. The polynomial ring defined over the previously mentioned ring, $\mathbb{Z}_q(x)/\phi(x)$, is represented as $R_q$, where $\phi(x)$ is the reduction polynomial. When a polynomial $f$ is defined as an element of such ring, the $i$-th coefficient of such polynomial is denoted as $f_i$. The representation of such polynomial in the number-theoretic transform domain is denoted as $\hat{f}$.

Vectors are denoted with bold letters, e.g., $\mathbf{a}$, while matrices use uppercase letters, e.g., $\mathbf{A}$.

## 2.2 The Number-Theoretic Transform

The Number-Theoretic Transform (NTT) is an operation used to reduce the complexity of polynomial multiplications to $O(n \log n)$, where $n$ is the degree of the polynomials. Such transform is key for cryptosystems based on the Ring Learning With Errors (RLWE) and Module Learning With Errors (MLWE) frameworks [LPR10, LS15], like NEWHOPE [ADPS16] and CRYSTALS-KYBER [ABD$^+$21]. The NTT works like a Fast Fourier Transform (FFT) over the ring of integers. It maps polynomials in $R_q$ to the vectorial space defined by the factorization of the reduction polynomial $\phi(x)$. To obtain only linear factors with degree 0, $\phi(x)$ must be factorized into $n$ polynomials of degree 1. This requires that the ring of integers modulo $q$ contains $2n$-th primitive roots of unity. After the transform, the polynomial multiplication becomes a Pointwise Multiplication (PWM) in the NTT domain with linear complexity. Then, a polynomial multiplication between two polynomials $f, g \in \mathbb{Z}_q$ can be executed as $f \cdot g = \text{INTT}(\text{NTT}(f) \circ \text{NTT}(g))$, where $\circ$ denotes the point-wise multiplication.

A variant of the NTT was proposed by Lyubashevsky and Seiler [LS19], where a smaller prime $q$ is used. In this case, the ring $\mathbb{Z}_q$ contains less than $2n$-th roots of unity, at the cost of a slightly more complex PWM. This approach is taken in CRYSTALS-KYBER, where $n = 256$ and its ring contains only $256$-th roots of unity. This means that its reduction polynomial is factorized into 128 polynomials of degree 2. The NTT of a polynomial $f \in \mathbb{Z}_q$ is then represented as a vector of 128 polynomials of degree 2. Its NTT is defined as follows, where $\zeta$ is the first $n$-th primitive root of unity and $\text{br}_7(\cdot)$ is the 7-bit-reversion operation:

$$ \hat{f}_{2i} = \sum_{j=0}^{127} f_{2j} \zeta^{(2\text{br}_7(i)+1)j} \qquad \hat{f}_{2i+1} = \sum_{j=0}^{127} f_{2j+1} \zeta^{(2\text{br}_7(i)+1)j} \qquad (1) $$

For memory saving purposes, the NTT is usually implemented as an in-place transform, with considerations on the ordering of the coefficients of the polynomials. In the CRYSTALS-KYBER documentation, when executing NTT, the input is in normal order and the output is in bit-reversed order. When executing Inverse Number-Theoretic Transform (INTT), the input is in bit-reversed order and the output is in normal order. This suggests the usage of basic butterfly operations of type Cooley-Tukey (CT) [CT65] for the NTT and Gentleman-Sande (GS) [GS66] for the INTT. Equations (2) and (3) show the CT and GS butterflies. In these equations, $\omega$ represents a power of $\zeta$, the first primitive $n$-th root of unity. These powers are called *twiddle factors* in the FFT/NTT literature. A graphical representation of a forward NTT with 4 coefficients is shown in Figure 1.

$$ \begin{aligned} c &= a + b \cdot \omega \\ d &= a - b \cdot \omega \end{aligned} \qquad (2) $$
<figure><img src="image_2.png" /><figcaption>Figure 1: Example for an execution of the NTT with $n = 4$.</figcaption></figure>

$$ \begin{aligned} c &= a + b \\ d &= (a - b) \cdot \omega \end{aligned} \qquad (3) $$

## 2.3 CRYSTALS-Kyber

CRYSTALS-KYBER [ABD$^{+}$21] is a KEM that was chosen by the NIST to be the base of one of the first Post-Quantum Cryptography (PQC) standards, named ML-KEM in the FIPS-203 standard [Nat24]. CRYSTALS-KYBER is constructed from two main components: an IND-CPA Public-Key Encryption Scheme (PKE) based on the hardness of breaking the MLWE problem [LS15, Reg05], and a Fujisaki-Okamoto transform [FO99] to achieve IND-CCA security by re-encrypting in decapsulation and checking ciphertext equality.

CRYSTALS-KYBER uses polynomials in the ring $R_q$, where $q = 3329$ and the reduction polynomial is a cyclotomic polynomial $\phi(x) = x^n+1$, where $n = 256$. The flexible parameter in CRYSTALS-KYBER is $k$, the rank of the module lattice, which dictates the size of vectors and matrices as well as other subparameters.

The following algorithms describe a simplified version of the underlying PKE scheme within CRYSTALS-KYBER, compliant with the Third Round submission of the algorithm [ABD$^{+}$21] for NIST's PQC contest.

In Algorithm 1, we show the procedure of the PKE key generation. First, seeds $\rho$ and $\sigma$ are chosen. Then, the public matrix $\hat{\mathbf{A}} \in R_q^{k \times k}$ is generated from the seed $\rho$, sampling it from a uniform distribution. This matrix is sampled in the NTT domain, to accelerate polynomial multiplication. Next, the vectors $\mathbf{s}, \mathbf{e}$ are sampled from a Centered Binomial Distribution (CBD) $B_{\eta_1}$ using the seed $\sigma$, where the outcome space of such distribution is $\{-\eta_1, \eta_1\}$. Afterwards, the secret vector $\mathbf{s}$ is transformed to the NTT domain. Following that, the MLWE instance $\hat{\mathbf{t}}$ is obtained by multiplying $\hat{\mathbf{A}}$ and $\hat{\mathbf{s}}$ and then adding the error $\mathbf{e}$ in the NTT domain. Finally, the keys are returned, with $pk = (\hat{\mathbf{t}}, \rho)$ as the public key and $sk = \hat{\mathbf{s}}$ as the secret key.

<caption>**Algorithm 1 CRYSTALS-Kyber.PKE.KeyGen() (Simplified)**</caption>

1: **Output:** Public key $pk$, secret key $sk$

2: Draw seeds $\rho, \sigma$

3: $\hat{\mathbf{A}} = \text{Sample}_U(\rho)$

4: $(\mathbf{s}, \mathbf{e}) = \text{Sample}_{B_{\eta_1}}(\sigma)$

5: $\hat{\mathbf{s}} = \text{NTT}(\mathbf{s})$

6: $\hat{\mathbf{t}} = \hat{\mathbf{A}} \circ \hat{\mathbf{s}} + \text{NTT}(e)$

7: **return** $pk = (\hat{\mathbf{t}}, \rho)$, $sk = \hat{\mathbf{s}}$
We now show the procedure for the PKE encryption in Algorithm 2. First, the public matrix $\hat{\mathbf{A}}$ is regenerated from $\rho$. Then, the randomizer vector $\mathbf{r}$ is sampled from a CBD with parameter $\eta_1$ from the seed $\tau$. The errors $e_1, e_2$ are sampled from another CBD with parameter $\eta_2$, with the seed $\tau$ modified with some value in order to yield different outcomes. Next, the vector $\mathbf{r}$ is transformed into the NTT domain. Then, an MLWE instance $\hat{\mathbf{u}}$ is generated from $\hat{\mathbf{A}}$ transposed, $\hat{\mathbf{r}}$ and the error $e_1$. Finally, an encoding of the message in $R_q$ is embedded into another MLWE instance, composed of $\hat{\mathbf{t}}, \hat{\mathbf{r}}$ and $e_2$. This final operation is the vector $\mathbf{v}$. Finally, the ciphertext is returned as $c = (\mathbf{u}, \mathbf{v})$.

<caption>**Algorithm 2 CRYSTALS-Kyber.PKE.Encrypt() (Simplified)**</caption>

1: **Input:** Public key $pk = (\hat{\mathbf{t}}, \rho)$, message $m$, seed $\tau$

2: **Output:** Ciphertext $c = (\mathbf{u}, \mathbf{v})$

3: $\hat{\mathbf{A}} = \text{Sample}_U(\rho)$

4: $\mathbf{r} = \text{Sample}_{B_{\eta_1}}(\tau)$

5: $(e_1, e_2) = \text{Sample}_{B_{\eta_2}}(\tau + k)$

6: $\hat{\mathbf{r}} = \text{NTT}(\mathbf{r})$

7: $\mathbf{u} = \text{NTT}^{-1}(\hat{\mathbf{A}}^T \circ \hat{\mathbf{r}}) + e_1$

8: $\mathbf{v} = \text{NTT}^{-1}(\hat{\mathbf{t}} \circ \hat{\mathbf{r}}) + e_2 + \text{Encode}(m)$

9: **return** $c = (\mathbf{u}, \mathbf{v})$

Finally, in Algorithm 3, we describe the decryption procedure. The vector $\mathbf{u}$ is transformed into the NTT domain and multiplied with the secret key $\hat{\mathbf{s}}$. Then, $\mathbf{v}$ is subtracted from the result of this multiplication. The result of this subtraction is then decoded to retrieve back the message $m$.

<caption>**Algorithm 3 CRYSTALS-Kyber.PKE.Decrypt() (Simplified)**</caption>

1: **Input:** Secret key $sk = \hat{\mathbf{s}}$, ciphertext $c = (\mathbf{u}, \mathbf{v})$

2: **Output:** Message $m$

3: $m = \text{Decode}(v - \text{NTT}^{-1}(\hat{\mathbf{s}}^T \circ \text{NTT}(\mathbf{u})))$

4: **return** $m$

The relevant parameters for this paper for each of the three proposed CRYSTALS-KYBER versions are described in Table 1.

<table><caption>**Table 1: Parameters for Kyber variants**</caption><thead><tr><th>Variant</th><th>n</th><th>k</th><th>q</th><th>η<sub>1</sub></th><th>η<sub>2</sub></th></tr></thead><tbody><tr><td>Kyber512</td><td>256</td><td>2</td><td>3329</td><td>3</td><td>2</td></tr><tr><td>Kyber768</td><td>256</td><td>3</td><td>3329</td><td>2</td><td>2</td></tr><tr><td>Kyber1024</td><td>256</td><td>4</td><td>3329</td><td>2</td><td>2</td></tr></tbody></table>

## 2.4 Soft-Analytical Side-Channel Attacks (SASCAs)

SASCAs are a type of profiled side-channel attack that combines information from power consumption measurements and from the algorithm itself. They were proposed for the first time by Veyrat-Charvillon et al. [VCGS14]. Potentially single-trace attacks, they bridge the gap between divide-and-conquer attacks and fully algorithmic attacks since they can recover multiple parts of a secret at a time but working with individual leaking variables. Such attacks work by representing them as a noisy decoding problem. The basic steps of a SASCA are as follows:
1. Create templates and perform profiling on some intermediates values [CRR03] to obtain prior conditional probability distributions on the leakage trace $\ell$, $P(T = t|\ell)$, where $T$ is an intermediate value in the algorithm.

2. Use the Belief Propagation (BP) algorithm to combine the prior distributions.

3. Retrieve probability distributions on targeted intermediate values and apply a maximum likelihood strategy to recover the secret.

BP is used to efficiently tackle the problem of marginalization. Consider $P^*(\boldsymbol{x}) = \prod_{m=1}^{M} f_m(\boldsymbol{x}_m)$ a product of $M$ factors $f_m(\boldsymbol{x}_m)$. Each of these factors depends on a subset $\boldsymbol{x}_m$ of the set $\boldsymbol{x}$ of variables, with size $n$. The BP algorithm aims to obtain the marginal functions $Z_n(x_n) = \sum_{\boldsymbol{x} \setminus \boldsymbol{x}_n} P^*(\boldsymbol{x})$. Of special interest are the normalized marginals $P_n(x_n) = Z_n(x_n)/Z$ with the normalization constant $Z = \sum_{\boldsymbol{x}} \prod_{m=1}^{M} f_m(\boldsymbol{x})$, which can be considered as the probability distribution of the intermediate value that is targeted by the side-channel attack.

BP works by passing messages between two types of agents. First, the attacked algorithm must be represented as a factor graph, i.e., a bipartite graph that contains two types of nodes: factor nodes and variable nodes. Factor nodes represent every factor $f_m$ and variable nodes represent every variable $x_n \in \boldsymbol{x}$. Then, two types of messages exist: i) from variable to factor; ii) from factor to variable. The first type of message is represented in equation (4), where $\mathcal{M}(n)$ represents the indices of the factors in which $x_n$ participates. The second type of message is shown in equation (5), where $\mathcal{N}(m)$ is the set of indices of the variables that are involved in $f_m$. And, $\boldsymbol{x}_{m \setminus n}$ is the set of variables $\boldsymbol{x}_m$ except $x_n$.

$$u_{n \to m}(x_n) = \prod_{m' \in \mathcal{M}(n) \setminus \{m\}} v_{m' \to n}(x_n) \quad (4)$$

$$v_{m \to n}(x_n) = \sum_{\boldsymbol{x}_{m \setminus n}} \left( f_m(\boldsymbol{x}_m) \prod_{n' \in \mathcal{N}(m) \setminus \{m\}} u_{n' \to m}(x_{n'}) \right) \quad (5)$$

The two types of messages are exchanged iteratively until convergence. After convergence, the marginals are recovered by multiplying all the messages from the factors to the variables as $Z_n(x_n) = \prod_{m \in \mathcal{N}} v_{m \to n}(x_n)$. After normalization, the targeted variables are guessed by applying a maximum likelihood strategy. Convergence is guaranteed when the graph does not contain loops, non-guaranteed otherwise. The presence of loops can create overconfidence on results or oscillations, preventing convergence.

## 2.5 SASCAs on NTT

Primas et al. executed the first SASCA on a lattice-based cryptosystem by targeting the NTT [PPM17]. In their work, they profiled the modular multiplication between intermediate coefficients and twiddle factors. Their work targeted the INTT in the decryption procedure of the LPR scheme [LPR10], precursor of CRYSTALS-KYBER. For CRYSTALS-KYBER, the analog target operation would be the inverse NTT in Line 3 of Algorithm 3. We show their proposed factor graph in Figure 2a. The side-channel leakage is injected by the factor $f_l$ where $f_l(b) = P(B = b|l)$, for a leakage $l$ observed on the modular multiplication between coefficient $b$ and the corresponding twiddle factor of the butterfly. The factor definitions of $f_{add}$ and $f_{sub}$ are shown in Equations (6) and (7).

$$f_{add}(a, b, c) = \begin{cases} 1 & \text{if } a + b \cdot \omega = c \mod q \\ 0 & \text{otherwise} \end{cases} \quad (6)$$
<figure><img src="image_3.png" /><figcaption>(a) Factor graph from [PPM17]. Leakage is injected to the graph by the factor $f_l$, from the template on the modular multiplication between $b$ and the twiddle factor.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) Factor graph from [PP19], also used in [HHP+21]. Leakage is injected from loads/stores on coefficients $a$ and $b$. The factors for addition and subtraction have been unified into a single factor $f_{bf}$.</figcaption></figure>

<caption>**Figure 2:** Butterfly factor graphs in the state of the art.</caption>

$$f_{sub}(a, b, d) = \begin{cases} 1 & \text{if } a - b \cdot \omega = d \mod q \\ 0 & \text{otherwise} \end{cases} \qquad (7)$$

This attack suffers from some inconveniences. For instance, the choice of the leaking operations is not optimal since the leakage is directly related only with one of the intermediate values ($b$, in Figure 2a), giving no information on the other coefficients. In the first NTT layer for example, the top half of the coefficients have no side-channel information which makes the attack more difficult. To alleviate this, the authors cut the full graph into subgraphs, to ensure convergence with the available side-channel information. The result from the BP on the subgraphs yields information on intermediate variables which lower the complexity of known cryptanalytical attacks on lattice-based cryptographic schemes, such as lattice reduction on the public key. Another inconvenience of the attack is the need of obtaining template values on every possible inputs of the modular multiplication. For the used parameters in the mentioned attack, i.e., $q = 7681$ and $n = 256$, the number of possible coefficient-twiddle factor multiplications are $q \cdot n/2 = 983168$. If 100 traces are used for every template, then the number of traces used goes up to 100 million, which raises questions over the practicality of the attack.

After this work, Pessl and Primas [PP19] made some improvements over the previous work, augmenting its practicality. Their target is the NTT of the randomizer vector $\hat{r}$ in the encryption of CRYSTALS-KYBER, in Line 6 of Algorithm 2, that is drawn from a binomial distribution with a support in $\{-\eta, \eta\}$, where $\eta = \{2, 3\}$, depending on the version of CRYSTALS-KYBER. The target of this attack is then in a smaller space, reducing the entropy of the targeted variables. Additionally, the butterfly factor graph was changed to the one in Figure 2b. This allows to change the leakage source from modular multiplications to memory loads/stores and unifying the previous factors $f_{add}$ and $f_{sub}$ to $f_{bf}$, shown in Equation (8). This merger avoids the short loop that was present in the previous representation. Finally, the templates over the load/store operations are done on the Hamming weights, i.e., the number of bits set to 1 in the coefficients. This final modification reduces the amount of required templates to $\lceil \log_2(q) \rceil + 1$.
$$f_{bf}(a, b, c, d) = \begin{cases} 1 & \text{if } a + b \cdot \omega = c \mod q \\ & \text{and } a - b \cdot \omega = d \mod q \\ 0 & \text{otherwise} \end{cases} \qquad (8)$$

Posterior to this, Hamburg et al. performed a chosen-ciphertext SASCA on CRYSTALS-KYBER [HHP+21]. They target the NTT in the decryption at Line 3 of Algorithm 3, by sending specially crafted ciphertexts. These chosen ciphertexts induce zeros after the PWM with the goal of reducing the entropy of the graph. The more sparse these ciphertexts are, the more resilient to noise the attack is, albeit requiring more traces. For example, with 64 non-zero coefficients, the attack requires $k$ traces, $k \in \{2, 3, 4\}$ being the security level of the attacked version of CRYSTALS-KYBER. Their factor graph is the same as in [PP19], in Figure 2b.

To prevent this type of attack, two countermeasures stand out in the literature: shuffling [ZBT19, RPBC20] and local masking [Saa17, RPBC20]. Shuffling is a countermeasure that permutes the execution order of operations such as NTT butterflies or loads/stores. On the other hand, local masking randomizes the intermediate values of the algorithm, without splitting the secret into shares as in usual masking schemes.

Shuffling was analyzed with respect to SASCA by Hermelink et al. [HSST23], based on the work of Hamburg et al. [HHP+21]. In this work, the authors analyzed the shuffling of butterflies and of loads/stores inside a butterfly. Against load/store shuffling, they introduce techniques such as mixing prior distributions and shuffling factor nodes, with good attack results (success rate > 0.8) up to a noise level $\sigma = 0.8$. Facing butterfly shuffling, they propose matching separately the leakage of loads and stores and extraction of permutations with subgraphs of the NTT, with more modest results (success rate > 0.8 up to $\sigma = 0.3$). They show that the shuffling countermeasure is a very valid tool and in certain instances (specially in the butterfly shuffling), it does increase the security of an NTT implementation against SASCA.

## 3 Local masking for NTT

Along with shuffling [ZBT19, RPBC20], local masking is a countermeasure proposed to thwart SASCA against the NTT. Proposed by Ravi et al. [RPBC20], this countermeasure works essentially by randomizing the twiddle factor in a butterfly. For example, take a CT butterfly as the one shown in equation (2). Let $\zeta^x$ be the twiddle factor of this butterfly. If the results $c$ and $d$ of this butterfly are multiplied by a random twiddle factor $\zeta^y$, then it yields the following:

$$ \begin{aligned} c' &= c \cdot \zeta^y \\ &= (a + b \cdot \zeta^x) \cdot \zeta^y \\ &= a \cdot \zeta^y + b \cdot \zeta^{x+y} \end{aligned} \qquad (9) $$

As it can be observed in equation (9), this masking requires one extra multiplication compared to an unmasked CT butterfly, as in equation (2).

This countermeasure is similar to the blinding proposed by Saarinen [Saa17]. Ravi et al. augment the entropy of the countermeasure by changing the mask at every layer of the NTT, not only at the input.

The usage of twiddle factors for local masking is justified from a convenience and performance point of view, which was already proposed by Zijlstra et al. [ZBT19] for the blinding countermeasure of Saarinen [Saa17]. For instance, the sampling of random twiddle factors $\omega_y$ is done in the interval $[0, n)$, instead of the whole $\mathbb{Z}_q$. Additionally, removing the
mask is equal to multiplying with the twiddle factor that has the power that is the additive inverse of $y$ mod $n$, since all the twiddle factors are $n$-th roots of unity, $\zeta^n = 1$. Moreover, multiplying with a new mask an already masked intermediate coefficient, resolves on only adding the powers of $\zeta$ of the masks. For example, if the inputs of a butterfly are $a' = a \cdot \omega_i$ and $b' = b \cdot \omega_j$, masking with $\omega_y$ is as shown in equation 10.

$$ 
\begin{aligned}
c' &= (a' + b' \cdot \omega_x) \cdot \omega_y \\
   &= a' \cdot \omega_y + b' \cdot \omega_{x+y} \\
   &= a \cdot \omega_{i+y} + b \cdot \omega_{i+x+y} \\
d' &= a \cdot \omega_{i+y} - b \cdot \omega_{i+x+y}
\end{aligned} 
\qquad (10) 
$$

This type of butterfly has the same mask for both the inputs and the outputs, and it is denoted as Masked-Same Input, Same Output (MSISO). It has a cost of two modular multiplications. Likewise, other masking strategies can be employed. For instance, if the inputs have different masks, as $a' = a \cdot \omega_i$ and $b' = b \cdot \omega_j$, the inputs can be unmasked and masked with the new $\omega_y$ in a single operation like in equation (11).

$$ 
\begin{aligned}
c' &= c \cdot \omega_y \\
   &= (a + b \cdot \omega_x) \cdot \omega_y \\
   &= (a' \cdot \omega_{n-i} + b' \cdot \omega_{n-j+x}) \cdot \omega_y \\
   &= a' \cdot \omega_{n-i+y} + b' \cdot \omega_{n-j+x+y} \\
d' &= a' \cdot \omega_{n-i+y} - b' \cdot \omega_{n-j+x+y}
\end{aligned} 
\qquad (11) 
$$

This type of butterfly is denoted as Masked-Different Input, Same Output (MDISO), and it has the same cost of two modular multiplications. If the inputs are masked with different masks and the outputs must be masked in the same way, then it becomes more complex. Take $a' = a \cdot \omega_i$ and $b' = b \cdot \omega_j$, as the inputs that are masked with different masks. If $c$ must be masked with $\omega_k$ and $d$ with $\omega_l$ then the operations are the following (equation 12):

$$ 
\begin{aligned}
c' &= c \cdot \omega_k \\
   &= (a + b \cdot \omega_x) \cdot \omega_k \\
   &= (a' \cdot \omega_{n-i} + b' \cdot \omega_{n-j+k}) \cdot \omega_k \\
   &= a' \cdot \omega_{n-i+k} + b' \cdot \omega_{n-j+x+k} \\
d' &= a' \cdot \omega_{n-i+l} - b' \cdot \omega_{n-j+x+l}
\end{aligned} 
\qquad (12) 
$$

This type of masked butterfly is denoted as Masked-Different Input, Different Output (MDIDO), and it has a cost of four modular multiplications, and it is the costlier butterfly configuration. A similar type of butterfly can be derived for inputs with the same mask and outputs with different mask, denoted as Masked-Same Input, Different Output (MSIDO), with the same complexity as the MDIDO butterfly.

A similar set of equations can be derived for the Gentleman-Sande, in equation (3), with the difference that the cost of the butterflies MSIDO and MDISO are inverted, i.e., two and four modular multiplications respectively. The cost for each of the masked butterflies is resumed in Table 2.

For a local-masked NTT execution, different configurations are proposed. If one mask is used per NTT stage, the cheapest butterflies, i.e. MSISOs, can be used. In this way, the last mask could be the additive inverse of the sum of the powers of the previous masks in
<table><caption>**Table 2:** Cost of local-masked butterflies in terms of modular multiplications.</caption><thead><tr><th>Type of masking</th><th>Modular multiplications<br>CT / GS</th></tr></thead><tbody><tr><td>MSISO</td><td>2 / 2</td></tr><tr><td>MDISO</td><td>2 / 4</td></tr><tr><td>MDIDO</td><td>4 / 4</td></tr><tr><td>MSIDO</td><td>4 / 2</td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>**Figure 3:** Example for an execution of the NTT with generic masking configuration with $n = 8$ and $u = 2$. Stages in green do not need to perform de-masking, while stages in orange do.</figcaption></figure>

In this configuration, such that the output is unmasked. This configuration is noted as *coarse masking*. Ravi *et al.* hint that this configuration can be the easiest to attack since an attacker could *brute-force* over the masking space or possibly exploit the links between the masks at the different butterflies.

To avoid this intuition, it is proposed to use *n* masks per stage, one for each coefficient, denoting it as *fine masking*. This configuration uses only the costliest MDIDO butterflies.

As a compromise between both of these versions, *generic masking* is proposed. In this version, the number *u* of masks is variable and possibly random. It is also proposed that *u* be limited to powers of 2, such that the control logic is less convoluted. Here, the kind of employed masked butterflies is dependent on the number of masks and on which stage they are used. An example is shown in Figure 3, where the type of mask per round is depicted for an NTT with $n = 8$ and $u = 2$, for an expanding NTT in Figure 3a and a shrinking NTT in 3b, which in a usual implementation of CRYSTALS-KYBER, they correspond to forward and inverse NTT respectively. In case 3a, the first butterfly is a MSIDO butterfly for providing different masks for the outputs. The rest of the butterflies are MSISO. In case 3b, all butterflies are MSISO, except the last one, since the inputs have different masks, necessitating a MDISO butterfly. *Generic masking* is not constant time, since it depends on the butterfly complexity which depends on the number *u* of masks used, but its runtime is not secret-dependent.

# 4 Vulnerabilities of local masking

Due to the nature of local masking, we have identified three key vulnerabilities. Firstly, there is a variability in the runtime depending on parameters of local masking. Secondly,
we identify that this masking scheme lacks surjectiveness, therefore possibly leaking information. Finally, local masking is essentially a multiplicative masking, which is known to present issues when dealing with 0-values.

## 4.1 Variable runtime depending on parameters

For generic masking, the number of masks $u$ determines the type of butterflies that are used, affecting the number of multiplications to be executed, causing the algorithm to run in variable time depending on $u$. This itself does not reveal any secret information to the attacker through timing. However, the information on the configuration of the algorithm is leaked. Such information is essential for the attacker to build the factor graph for the attack. Then, an attacker can observe the number of clock cycles used for the execution of the NTT to obtain the configuration of the used local masking.

To maintain a constant runtime, dummy multiplications must be introduced, aligning the performance with the maximum possible value of $u$ in the implementation. However, this approach is suboptimal for performance.

## 4.2 Non-surjective masking

Consider the set of Twiddle factors $W = \{\zeta^i \mod q | i \in [0, n-1]\}$. The masking of each coefficient in the [RPBC20] countermeasure follows the map $m: \mathbb{Z}_q \times W \to \mathbb{Z}_q$. For a fixed coefficient $x \in \mathbb{Z}_q$, the mapping becomes non-surjective. This means that for a fixed $x$, there are only $n$ possible values to which it can be mapped. This non-uniform mask reveals information about the fixed coefficient $x$.

The non-surjectiveness of the scheme can be exploited by an attacker to reduce the entropy of the intermediate values. For example, an attacker could integrate leakage from the loading of the non-uniform mask coming from the Twiddle factors into a factor graph for SASCA.

## 4.3 The 0-value problem

The 0-value problem is a well known downside of multiplicative masking schemes, since zeros cannot be masked with multiplications. The first multiplicative masking scheme for AES, proposed by Akkar and Giraud [AG01], was shown by Golić and Tymen [GT03] to be vulnerable to first-order zero-value Differential Power Analysis (DPA) because of this very same reason.

We identify two ways to leverage the 0-value problem leveraged by a SASCA attacker on local masking:

1. Since zeros are not masked by the local masking, the attacker can average several traces to detect the presence of zeros, reducing the entropy of intermediate values.

2. The strategies proposed by Hamburg et al. [HHP+21] for attacking the inverse NTT and the long term key can be applied. In their work, they craft chosen ciphertexts to force the result of PWM to zero in certain coefficients. This is to reduce the size of the graph, reducing the entropy of some variables to zero. Such strategy can also be applied here to attack an implementation of the inverse NTT equipped with the local masking countermeasure, even in the additive-masked case.

# 5 SASCA on local-masked NTT

This section outlines the strategy employed for adapting the SASCA attack to target local-masked NTT implementations.
## 5.1 Attack assumptions

This attack assumes that targeted device leaks the Hamming weight of any value that is loaded or stored in memory. This assumption aligns with previous works in the state of the art [PP19, KPP20, HHP$^+$21, HSST23], with some practical validations of this fact in [PP19, KPP20].

However, all previous works only consider the leakage of loads/stores of the intermediate values of a butterfly. For a local-masked NTT, the randomized twiddle factors also become critical values that are loaded from memory, possibly through the same bus where the butterfly intermediates were loaded. Therefore, we also consider loading leakage from the twiddle factors.

We consider the generic masked version of the local-masked NTT. We also assume that the attacker can perform timing or simple power analysis to determine the number of masks that are used per round in order to establish the graph. Additionally, the inputs and outputs of the algorithm are unmasked. We assume that we mask and demask at every round, no matter the version of the protected butterfly used. It is necessary to unmask and remask for MDISO or MDIDO type butterflies where the masks of the inputs are different. We also mask and unmask for MSISO and MSIDO to facilitate the generation of the factor graph. In any case, at some point during the execution of the local masked NTT, a factor that recombines previous masks exists. It would simply connect multiple masks (>2) instead of two. However, we do agree that the geometry of the factor graph is slightly different and may provide different results. Additionally, in cases of a high number of masks $u$, the geometry does not change ($u=64,128,256$). We also consider that variables are always positive and that reductions mod $q$ are performed after every operation.

## 5.2 Algorithm target for attack

The target of this attack is the CRYSTALS-KYBER encryption from Algorithm 2, as in [PP19], in order to take advantage of the drawing of the sensitive variable $r$ from a centered binomial distribution, with values in the set $\{-\eta_1, \eta_1\}$, which allows for a smaller search space.

Furthermore, from taking into account the narrow support in the templates of the first layer, we also take into account the limited 256 possible twiddle factors compared to the space mod $q$, which facilitate better the attack, since the entropy of each masked twiddle factor is $\log_2(n) = 8$ bits and not $\log_2(q) \approx 12.9$ bits as if it was uniformly masked.

## 5.3 Template considerations

The templates are done over the Hamming weight of the values. Then, template matching provides a conditional probability of the value of Hamming weight $h$ of an intermediate variable given a leakage $l$, $P(H = h|l)$. To obtain $P(X = x|l)$, the law of total probability along with the Bayes' theorem can be used, by relating sums of conditional probabilities and updating the prior probability of $X$ given the evidence $l$.
$$ 
\begin{aligned}
P(X = x|l) &= P(X = x|H = h, l)P(H = h|l) \\
&\quad + P(X = x|H \neq h, l)P(H \neq h|l) \\
&= P(X = x|H = h)P(H = h|l) \\
&\quad + P(X = x|H \neq h)P(H \neq h|l) \\
&= P(X = x|H = h)P(H = h|l) \\
&= \frac{P(H = h|X = x)P(X = x)}{P(H = h)}P(H = h|l) \\
&= \frac{P(X = x)}{P(H = h)}P(H = h|l)
\end{aligned} 
\quad (13) $$

The scaling factor $P(X = x)/P(H = h)$ is useful to integrate information about the variables. We use three variants of this scaling factor.

1. For uniform variables that over mod $q$. For each $P(X = x|l)$, we divide the result from $P(H = h|l)$ by the number of values that can have that given Hamming weight $h$.

2. For variables drawn from a centered binomial distribution, i.e., the inputs of the NTT in encryption. In that case, $P(X = x)$ is obtained from the centered binomial distribution, and $P(H = h)$ is calculated from the law of total probabilities as $P(H = h) = \sum_x P(H = h|X = x)P(X = x)$, approach hinted by Pessl and Primas [PP19].

3. Variables that are loaded from the possible $n$ twiddle factors. These variables are related to the non-uniform masks. In this case, the probability $P(H = h|l)$ is divided by the number of Twiddle factors that can have the given Hamming weight $h$.

## 5.4 Graph representation

Our graph representation is adapted from the graph shown in Figure 2b from Pessl and Primas [PP19], to integrate masked twiddle factors. We connect the coefficient variables with a multiplier factor that will be linked to the mask and the coefficient. We illustrate the graph with Figures 4, 5 and 6, corresponding to a protected butterfly of type MSISO at the first layer (Equation (10)), at an inner layer and the final layer, respectively. In these figures, we represent the variables with side-channel information in blue. The variables without side-channel information are in yellow and the public variables are in green. Finally, the factor nodes are color-coded in orange.

The MSISO butterfly in layer 0, shown in Figure 4, involves unmasked coefficients $a$ and $b$ used in the NTT calculation, leading to leakage information from their memory loads. The masked versions of $c$ and $d$ are denoted as $c'$ and $d'$, masked with the mask $m_0$. The public twiddle factor is represented as $tw$, and the product of the mask $m_0$ and twiddle factor $tw$ is denoted as $twm_0$. Side-channel information is available from the memory loads of $m_0$ and $twm_0$.

The graph contains two types of factors: $f_{bf}$ and $f_{mul}$. $f_{bf}$ is defined as in the work of Pessl and Primas [PP19] (Equation (8)). $f_{mul}$ is defined in Equation (14).

$$ f_{mul}(a, b, r) = \begin{cases} 1 & \text{if } a \cdot b = r \mod q \\ 0 & \text{if } a \cdot b \neq r \mod q \end{cases} \quad (14) $$

Consider a MSISO butterfly in an inner layer of the NTT, shown in Figure 5. In this butterfly, none of the unmasked coefficients have side-channel information, but there is
<figure><img src="image_6.png" /><figcaption>**Figure 4:** Graph representation for a local-masked butterfly of MSISO type in the first layer.</figcaption></figure>

information from the masked versions $a', b', c', d'$. $a'$ and $b'$ are masked with the mask of the previous layer $m_{s-1}$ and $c', d'$ are masked with the current mask $m_s$. Unless this inner layer follows the initial layer, there is no direct side-channel information on the masks. However, leakage is observed from the variable $m_{s,s-1}$ which is the multiplication of the current mask $m_s$ and the inverse of the previous mask $m_{s-1}$, due to the demask-and-mask operation. This variable is connected to the factor node $f_{dm}$ which is in charge of representing the demask-and-mask operation, shown in Equation (15).

$$f_{dm}(m_{s-1}, m_s, m_{s,s-1}) = \begin{cases} 1 & \text{if } m_{s-1}^{-1} \cdot m_s = m_{s,s-1} \\ 0 & \text{otherwise} \end{cases} \mod q \quad (15)$$

Finally, additional side-channel information is available for the variable representing the result of the multiplication of $m_{s,s-1}$ and $tw$, denoted with $twm_{s,s-1}$.

In the final layer, shown in Figure 6, the outputs $c, d$ provide leakage on their unmasked values. Additionally, the inverse of the mask of the previous layer is loaded from memory, leaking information. We denote this variable as $m'_{s-1}$, and its relationship with the previous mask $m_{s-1}$ is modeled with the demasking factor $f_d$, shown in Equation (16). The result of the multiplication of $m'_{s-1}$ and the twiddle factor is denoted with $twm'_{s-1}$.

$$f_d(m_{s-1}, m'_{s-1}) = \begin{cases} 1 & \text{if } m_{s-1}^{-1} = m'_{s-1} \mod q \\ 0 & \text{otherwise} \end{cases} \quad (16)$$

The resulting graph has short loops that could induce oscillations in the BP algorithm. However, it takes into account different numbers of masks per round without drastically changing the graph since essentially the core of the graph is unchanged.

## 5.5 Leveraging of vulnerabilities identified in Section 4

The vulnerabilities detected on the previous chapter are actively leveraged in this attack. First, the timing leakage of the variable runtime due to the number of masks per layer $u$ is used to establish the factor graph and connect the nodes of the butterflies with the different masks. Then, the non-surjectiveness of the masks is taken into consideration for
<figure><img src="image_7.png" /><figcaption>**Figure 5:** Graph representation for a local-masked butterfly of MSISO type in an inner layer.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Figure 6:** Graph representation for a local-masked butterfly of MSISO type in the final layer.</figcaption></figure>
limiting the possible values that can be loaded from memory and for the scaling factor explained in Section 5.3.

# 6 Practical methodology and results

This section presents the results of a simulated SASCA attack against local-masked NTT, exploring the impact of masking parameters ($u$) and noise levels ($\sigma$) on the attack's success rate.

## 6.1 Methodology and Implementation details

As a study case, we consider the configuration of the NTT of CRYSTALS-KYBER in the Kyber768 or Kyber1024 configuration, with the parameters from Table 1. That is, an incomplete NTT with $log_2(n) - 1$ and a parameter $\eta_1 = 2$, for the centered binomial distribution. While Kyber512 has a shorter vector $r$, it has a larger support for its centered binomial distribution of $\eta_1 = 3$, enlarging the search space of the input values and making the attack harder. We leave a specific analysis of the Kyber512 case as a future work.

We consider a simulation approach in which we model the leakage $l$ of an intermediate value $x$ with the noisy Hamming weight leakage model, $l = \text{HW}(x) + \varphi(0, \sigma)$, where $\text{HW}()$ is the Hamming weight function and $\varphi(0, \sigma)$ is a sample from a normal distribution with standard deviation $\sigma$.

An open question is if indeed a higher number of masks per layer of the NTT, plays a role into decreasing the success rate of the attack and augmenting the susceptibility to noise. Therefore, the following methodology is used: the number of masks $u$ is fixed, and performing 20 simulated attacks with noise of a fixed standard deviation $\sigma$, starting from 0.01 and 0.1. Then, $\sigma$ is increased in steps of 0.1 until the success rate of the attack drops to zero. An experiment is considered successful if, for all input coefficients, the correct guess is the one with the highest probability. Success rate is then defined as the division between successes and the number of total experiments. Experiments are performed for an implementation that sets $u$ as a power of two, i.e., $u = \{1, 2, 4, 8, 16, 32, 64, 128, 256\}$. Target inputs are generated from the Centered Binomial Distribution as defined by CRYSTALS-Kyber. Mask powers are generated uniformly at random over $\mathbb{Z}_{256}$.

As a baseline, we also performed the attack on an unmasked setting, with $u = 0$. In such case, the factor graph for the butterflies used is exactly the one used by Pessl and Primas et al. [PP19], shown in Figure 2b.

We evaluated the attack using the open-source library SCALib [CB23], targeted for evaluation of side-channel security. This tool allows for a quick evaluation of SASCA attacks, with acceptable performance, by using a friendly graph description format. In our implementation, using a server with an Intel Xeon E5-2697 CPU, the runtime for a BP iteration is around 2 to 4 minutes.

We set two possible stop conditions for the BP algorithm: either the entropy of all the variables in the input falls below 0.1 bits, or the algorithm reaches 50 iterations. For counting an experiment as successful, the correct inputs must have the highest probability. It is important to note that the value of $u$ influences the convergence of the graph. However, in low noise scenarios, the convergence remains well below 50 iterations. For example, with a noise level of $\sigma = 0.1$, the convergence occurs in approximately 5 iterations for $u = 1$ mask, and in around 12 iterations for $u = 256$ masks.

## 6.2 Results

The results of the assessment of the attack are shown in Figure 7. In such figure, the data points for every $u$ are the success rates at the specified $\sigma$. Around each data point, we
fill an area with the confidence level of the success rate with a confidence level of 95%. The statistic used is the Wilson score interval [Wil27]. Such statistic is used for a low number of Bernoulli experiments, as used by Hamburg et al. [HHP+21] in their SASCA with chosen ciphertexts. Primas et al. and Pessl et al. employ the same methodology, enabling us to compare our results with the state-of-the-art [PPM17, PP19].

<figure><img src="image_9.png" /><figcaption>**Figure 7:** Results of the SASCA on local masking. Each point represents the success rate of 20 experiments at that specific noise level. The zone around each point describes the confidence interval of the success rate.</figcaption></figure>

In Table 3, we show the $\sigma$ for which the success rate of the attack is equal or below 0.5 for each $u$.

<table><caption>**Table 3:** $\sigma$ for which the success rate of the attack is equal or below 0.5 for each $u$.</caption><thead><tr><th>u</th><th>0</th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th><th>32</th><th>64</th><th>128</th><th>256</th></tr></thead><tbody><tr><th>σ|SR ≤ 0.5</th><td>1.1</td><td>1.2</td><td>1.2</td><td>1.1</td><td>1.0</td><td>0.9</td><td>0.7</td><td>0.6</td><td>0.5</td><td>0.4</td></tr></tbody></table>

The results indicate that the attack performs similarly or better in the cases of $u = \{1, 2, 4\}$ compared to the unmasked case $u = 0$. This can be attributed to the fact that the twiddle factors loaded from memory are no longer a public variable. They contain information about the random mask and are not uniform. This extra information, along with the fact that multiple butterflies are connected to the same masks, seems to offset the randomization proposed by the local masking countermeasure.

Furthermore, from $u = 8$ there is an incremental improvement in security. Apart from adding more variables to the graph and increasing the entropy, the effect of increasing $u$ is to reduce the number of coefficients that share the same masks, therefore reducing such connections in the graph.

Finally, the highest level of security, $u = 256$, can still be attacked in low noise settings of $\sigma < 0.4$.
## 6.3 Discussion

The acceptable noise level of our simulated attack for levels of $u$ of 128 and 256 are similar to the attack from Hermelink et al. [HSST23] on the shuffling of butterfly operations. However, such attack is a chosen-ciphertext multi-trace attack designed for increasing the resilience to noise, by forcing 0-values in the factor graph. Applying a similar strategy to a local masked NTT is entirely possible since 0-values are not masked. We expect that the application in this attack scenario will also provide an improvement.

Additionally, implementing local masking represents a higher challenge in terms of overhead compared to shuffling. According to the time overhead reports of the software implementations on a STM32F407 ARM Cortex-M4 micro-controller of single-trace-attack countermeasures for the NTT by Ravi et al. [RPBC20], using $u = 256$ has a higher overhead in clock cycles, compared to full butterfly shuffling or butterfly shuffling in groups. On the other hand, randomness requirements for local masking are lower than butterfly shuffling, when using the Knuth-Yao sampler used by Ravi et al. The aforementioned overheads and randomness requirements are reported in Table 4. An implementer should be aware of these time and randomness overhead conditions with respect to the offered security, in order to make an informed decisions about the countermeasure (or countermeasures, in plural) to enforce.

<table><caption>**Table 4:** Clock cycles overheads compared to an unprotected implementation and randomness requirements of single-trace attack countermeasures, taken from [RPBC20].</caption><thead><tr><th>Countermeasure</th><th>Clock cycle overhead (NTT/INTT)(%)</th><th>Randomness requirements in bits [concrete values for n=256]</th></tr></thead><tbody><tr><td>Local masking ($u = 256$)</td><td>451.7/250.9</td><td>$n \cdot \log(n)$ [2048]</td></tr><tr><td>In-group butterfly shuffling</td><td>172.2/99.9</td><td>$\sum_{s=0}^{\log_2 n-1} \left(\frac{n}{2^s} - 1\right) \cdot \log_2\left(\frac{n}{2^s}\right) \cdot 2^s$ [4106]</td></tr><tr><td>Full butterfly shuffling</td><td>181.1/123.8</td><td>$(n/2 - 1) \cdot \log^2(n)$ [8128]</td></tr></tbody></table>

A countermeasure that is compatible with local masking is standard arithmetic masking, where a secret $s \in R_q$ can be split into two (or more) shares $(s+r, r)$, where $r$ is a polynomial in $R_q$ with its coefficients taken uniformly at random from $\mathbb{Z}_q$. Given the linearity of the NTT, it suffices to apply the transform to each share and then recombine the output results in order to ensure correctness. Since local masking only intervenes at every execution of the NTT without affecting the result, it can be used with each share, providing an extra layer of protection.

On the other hand, it must be noted that some weaknesses discussed in these article can be used in order to mount a SASCA attack on an NTT execution with these two countermeasures. The multiplicative masks in the local masking countermeasure are still not uniform. However, the 0-value problem is less of an issue, since arithmetic masking prevents the usage of trace averaging, but it does not thwart the chosen ciphertext strategy for attacking the inverse NTT, as shown by Hamburg et al. [HHP+21]. Additionally, when attacking the forward NTT on the encryption, the target of this article, one can still consider the information of the restricted values of the input from a binomial distribution, as shown by Pessl and Primas [PP19]. Considering a coefficient $x$ that is split into the shares $(x', x'')$, the variables in the factor graph for $x'$ and $x''$ can be connected with a factor $f_{bino}$ that represents that their sum $x = x' + x''$ must be drawn from a binomial distribution. Apart from this change, the factor graphs that we propose in this article for the different types of butterflies can be used without any modification. We leave the application and evaluation of SASCA against an NTT with standard arithmetic and local masking for a future work.
# 7 Conclusion

This paper demonstrated that the local masking countermeasure, while providing some resilience to noise, remains vulnerable to single-trace SASCA attacks under certain conditions, particularly with low levels of masking.

We showed an adaptation of the factor graph proposed by Pessl and Primas [PP19] to attack an execution of CRYSTALS-KYBER's NTT equipped with local masking [RPBC20] with a single trace. Such adaptation consists in taking into account the leakage from the load of the Twiddle factors that become sensitive variables because of the application of the countermeasure. The core of the factor graph of the butterfly is identical, while additional nodes are connected depending on the number of masks $u$ used in the execution. Additionally, we performed an assessment of the resilience of local masking against our proposed attack, taking into consideration the number of masks $u$ and the standard deviation $\sigma$ of the noise present in the attack. We showed that for a low number of masks $u = \{1, 2, 4\}$, the attack has a similar performance in terms of the acceptable $\sigma$ compared to an unmasked case. Moreover, we showed that there is an incremental improvement of security from $u = 8$ up to $u = 256$, where the success rate is similar to that of the chosen-ciphertext attack of Hermelink et al. [HSST23] against an in-group butterfly shuffled NTT.

While the simulated attack provides valuable insights into the vulnerability of local masking, further research is needed to explore potential improvements to the attack and to evaluate its effectiveness in real-world implementations. For instance, the chosen-ciphertext strategy from Hamburg et al. [HHP+21] can be applied in order to set zeroes in the input layer and reduce the entropy. As explained in Section 4, the application of local masking does not affect zero values, enabling the Hamburg et al. strategy. Another improvement of the attack is the application of multi-trace attacks. In such attacks, the core of the factor graph is left unchanged, and the additional side-channel information nodes from every trace are connected to the core, possibly providing a better performance. Furthermore, other chosen ciphertext strategies such as in [RBRC22, RSRCB20, UXT+21] can be used.

Finally, we leave as future work the evaluation on a real implementation of local masking, such as the software microcontroller implementation of [RPBC20] or hardware implementations [CRVBB24].

# References

[ABD+21] 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, 2021. URL: https://pq-crystals.org/kyber/.

[ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange - A new hope. In Thorsten Holz and Stefan Savage, editors, *25th USENIX Security Symposium, USENIX Security 16*, Austin, TX, USA, August 10-12, 2016, pages 327–343. USENIX Association, 2016. URL: https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/alkim.

[AG01] Mehdi-Laurent Akkar and Christophe Giraud. An Implementation of DES and AES, Secure against Some Attacks. In Cetin K. Koç, David Naccache, and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems — CHES 2001*, Lecture Notes in Computer Science, pages 309–318, Berlin, Heidelberg, 2001. Springer. doi:10.1007/3-540-44709-1_26.
[CB23] Gaëtan Cassiers and Olivier Bronchain. SCALib: A Side-Channel Analysis Library. *Journal of Open Source Software*, 8(86):5196, June 2023. URL: https://joss.theoj.org/papers/10.21105/joss.05196, doi:10.21105/joss.05196.

[CBVB23] Rafael Carrera Rodriguez, Florent Bruguier, Emanuele Valea, and Pascal Benoit. Correlation Electromagnetic Analysis on an FPGA Implementation of CRYSTALS-Kyber. In *2023 18th Conference on Ph.D Research in Micro-electronics and Electronics (PRIME)*, pages 217-220, Valencia, Spain, June 2023. IEEE. URL: https://ieeexplore.ieee.org/document/10161764/, doi:10.1109/PRIME58259.2023.10161764.

[CRR03] Suresh Chari, Josyula R. Rao, and Pankaj Rohatgi. Template Attacks. *Cryptographic Hardware and Embedded Systems - CHES 2002*, pages 13-28, 2003. doi:10.1007/3-540-36400-5_3.

[CRVBB24] Rafael Carrera Rodriguez, Emanuele Valea, Florent Bruguier, and Pascal Benoit. Hardware Implementation and Security Analysis of Local-Masked NTT for CRYSTALS-Kyber, 2024. Publication info: Preprint. URL: https://eprint.iacr.org/2024/1194.

[CT65] James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex Fourier series. *Mathematics of Computation*, 19(90):297-301, 1965. URL: https://www.ams.org/mcom/1965-19-090/S0025-5718-1965-0178586-1/, doi:10.1090/S0025-5718-1965-0178586-1.

[FO99] Eiichiro Fujisaki and Tatsuaki Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Michael Wiener, editor, *Advances in Cryptology — CRYPTO '99*, pages 537-554. Springer Berlin Heidelberg, 1999. doi:10.1007/s00145-011-9114-1.

[GS66] W. M. Gentleman and G. Sande. Fast Fourier Transforms: for fun and profit. In *Proceedings of the November 7-10, 1966, fall joint computer conference on XX - AFIPS '66 (Fall)*, page 563, San Francisco, California, 1966. ACM Press. URL: http://portal.acm.org/citation.cfm?doid=1464291.1464352, doi:10.1145/1464291.1464352.

[GT03] Jovan D. Golić and Christophe Tymen. Multiplicative Masking and Power Analysis of AES. In Burton S. Kaliski, Cetin K. Koç, and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems - CHES 2002*, Lecture Notes in Computer Science, pages 198-212, Berlin, Heidelberg, 2003. Springer. doi:10.1007/3-540-36400-5_16.

[HHP+21] Mike Hamburg, Julius Hermelink, Robert Primas, Simona Samardjiska, Thomas Schamberger, Silvan Streit, Emanuele Strieder, and Christine Van Vredendaal. Chosen Ciphertext k-Trace Attacks on Masked CCA2 Secure Kyber. *IACR Transactions on Cryptographic Hardware and Embedded Systems*, pages 88-113, August 2021. doi:10.46586/tches.v2021.i4.88-113.

[HSST23] Julius Hermelink, Silvan Streit, Emanuele Strieder, and Katharina Thieme. Adapting belief propagation to counter shuffling of ntts. *IACR Transactions on Cryptographic Hardware and Embedded Systems*, pages 60-88, October 2023. URL: https://eprint.iacr.org/2022/555/20221013:132543, doi:10.46586/tches.v2023.i1.60-88.
[KPP20] Matthias J. Kannwischer, Peter Pessl, and Robert Primas. Single-Trace Attacks on Kekek. *IACR Transactions on Cryptographic Hardware and Embedded Systems*, pages 243–268, June 2020. URL: https://tches.iacr.org/index.php/TCHES/article/view/8590, doi:10.46586/tches.v2020.i3.243-268.

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. In Henri Gilbert, editor, *Advances in Cryptology - EUROCRYP'T 2010*, pages 1–23, Berlin, Heidelberg, 2010. Springer. doi:10.1007/978-3-642-13190-5_1.

[LS15] Adeline Langlois and Damien Stehlé. Worst-Case to Average-Case Reductions for Module Lattices. *Des. Codes Cryptography*, 75(3):565–599, June 2015. doi:10.1007/s10623-014-9938-4.

[LS19] Vadim Lyubashevsky and Gregor Seiler. NTTRU: Truly Fast NTRU Using NTT. *IACR Transactions on Cryptographic Hardware and Embedded Systems*, pages 180–201, May 2019. URL: https://tches.iacr.org/index.php/TCHES/article/view/8293, doi:10.46586/tches.v2019.i3.180-201.

[MWK$^{+22}$] Catinca Mujdei, Lennert Wouters, Angshuman Karmakar, Arthur Beckers, Jose Maria Bermudo Mera, and Ingrid Verbauwhede. Side-Channel Analysis of Lattice-Based Post-Quantum Cryptography: Exploiting Polynomial Multiplication. *ACM Transactions on Embedded Computing Systems*, November 2022. doi:10.1145/3569420.

[Nat] National Institute of Standards and Technology. Post-Quantum Cryptography Standardization Process. URL: https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization.

[Nat24] National Institute of Standards and Technology. Module-Lattice-Based Key-Encapsulation Mechanism Standard, August 2024. URL: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf, doi:10.6028/NIST.FIPS.203.

[PP19] Peter Pessl and Robert Primas. More Practical Single-Trace Attacks on the Number Theoretic Transform. In *Progress in Cryptology - LATINCRYPT 2019*, pages 130–149. Springer International Publishing, 2019. doi:10.1007/978-3-030-30530-7_7.

[PPM17] Robert Primas, Peter Pessl, and Stefan Mangard. Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption. In *Lecture Notes in Computer Science*, pages 513–533. Springer International Publishing, 2017. doi:10.1007/978-3-319-66787-4_25.

[RBRC22] 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, 2022. URL: https://ieeexplore.ieee.org/docume nt/9664567/, doi:10.1109/TIFS.2021.3139268.

[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In *Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05*. ACM Press, 2005. doi:10.1145/1060 590.1060603.
[RPBC20] Prasanna Ravi, Romain Poussier, Shivam Bhasin, and Anupam Chattopadhyay. On Configurable SCA Countermeasures Against Single Trace Attacks for the NTT. In Security, Privacy, and Applied Cryptography Engineering, pages 123–146. Springer International Publishing, 2020. doi: 10.1007/978-3-030-66626-2_7.

[RSRCB20] Prasanna Ravi, Sujoy Sinha Roy, Anupam Chattopadhyay, and Shivam Bhasin. Generic Side-channel attacks on CCA-secure lattice-based PKE and KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 307–335, 2020. doi:10.46586/tches.v2020.i3.307-335.

[Saa17] Markku-Juhani O. Saarinen. Arithmetic coding and blinding countermeasures for lattice signatures. Journal of Cryptographic Engineering, 8(1):71–84, January 2017. Publisher: Springer Science and Business Media LLC. doi: 10.1007/s13389-017-0149-6.

[UXT+21] Rei Ueno, Keita Xagawa, Yutaro Tanaka, Akira Ito, Junko Takahashi, and Naofumi Homma. Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 296–322, November 2021. Publisher: Universitats-bibliothek der Ruhr-Universitat Bochum. doi:10.46586/tches.v2022.i1. 296-322.

[VCGS14] Nicolas Veyrat-Charvillon, Benoît Gérard, and François-Xavier Standaert. Soft Analytical Side-Channel Attacks. In Lecture Notes in Computer Science, pages 282–296. Springer Berlin Heidelberg, 2014. doi:10.1007/978-3-662 -45611-8_15.

[Wil27] Edwin B Wilson. Probable inference, the law of succession, and statistical inference. Journal of the American Statistical Association, 22(158):209–212, 1927. Publisher: Taylor & Francis. doi:10.1080/01621459.1927.10502953.

[ZBT19] Timo Zijlstra, Karim Bigou, and Arnaud Tisserand. FPGA Implementation and Comparison of Protections Against SCAs for RLWE. In Lecture Notes in Computer Science, pages 535–555. Springer International Publishing, 2019. doi:10.1007/978-3-030-35423-7_27.

[ZPM+23] Yiqiang Zhao, Shijian Pan, Haocheng Ma, Ya Gao, Xintong Song, Jiaji He, and Yier Jin. Side Channel Security Oriented Evaluation and Protection on Hardware Implementations of Kyber. IEEE Transactions on Circuits and Systems I: Regular Papers, 70(12):5025–5035, December 2023. Conference Name: IEEE Transactions on Circuits and Systems I: Regular Papers. URL: https://ieeexplore.ieee.org/document/10175157, doi:10.1109/TCSI .2023.3288600.