# A Fault Analysis on SNOVA

Gustavo Banegas, Ricardo Villanueva-Polanco

► To cite this version:

Gustavo Banegas, Ricardo Villanueva-Polanco. A Fault Analysis on SNOVA. 2024. hal-04790059

HAL Id: hal-04790059

https://inria.hal.science/hal-04790059v1

Preprint submitted on 15 Sep 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 Fault Analysis on SNOVA

Gustavo Banegas¹ and Ricardo Villanueva-Polanco²

¹Inria and Laboratoire d'Informatique de l'Ecole polytechnique,
Institut Polytechnique de Paris, Palaiseau, France
gustavo@cryptme.in

²Technology Innovation Institute, UAE
ricardo.polanco@tii.ae

**Abstract.** SNOVA is a post-quantum cryptographic signature scheme known for its efficiency and compact key sizes, making it a second-round candidate in the NIST post-quantum cryptography standardization process. This paper presents a comprehensive fault analysis of SNOVA, focusing on both permanent and transient faults during signature generation. We introduce several fault injection strategies that exploit SNOVA's structure to recover partial or complete secret keys with limited faulty signatures. Our analysis reveals that as few as 22 to 68 faulty signatures, depending on the security level, can suffice for key recovery. We propose a novel fault-assisted reconciliation attack, demonstrating its effectiveness in extracting the secret key space via solving a quadratic polynomial system. Simulations show transient faults in key signature generation steps can significantly compromise SNOVA's security. To address these vulnerabilities, we propose a lightweight countermeasure to reduce the success of fault attacks without adding significant overhead. Our results highlight the importance of fault-resistant mechanisms in post-quantum cryptographic schemes like SNOVA to ensure robustness.

**Keywords:** Physical attack · Fault-attack · SNOVA · MQ-based cryptography.

## 1 Introduction

The National Institute of Standards and Technology (NIST) initiated an additional call for post-quantum digital signature proposals to introduce variability in the mathematical foundations of digital signatures. In response, NIST received 40 submissions based on diverse mathematical problems. Among these, 10 submissions were based on multivariate polynomial equations over finite fields, a branch of post-quantum cryptography known as MQ-based cryptography.

MQ-based cryptography relies on the difficulty of solving systems of multivariate quadratic equations over finite fields. The fundamental problem can be

Author list in alphabetical order; see https://www.ams.org/profession/leaders/culture/CultureStatement04.pdf.
defined as follows: given a system of $m$ quadratic equations in $n$ variables over a finite field $\mathbb{F}_q$, find a solution $\mathbf{x} = (x_1, x_2, \dots, x_n) \in \mathbb{F}_q^n$ such that:

$$ \left\{ \begin{array}{l} Q_1(x_1, x_2, \dots, x_n) = 0 \\ Q_2(x_1, x_2, \dots, x_n) = 0 \\ \vdots \\ Q_m(x_1, x_2, \dots, x_n) = 0 \end{array} \right. $$

where each $Q_i$ is a quadratic polynomial of the form:

$$ Q_i(x_1, x_2, \dots, x_n) = \sum_{1 \le j \le k \le n} a_{ijk} x_j x_k + \sum_{1 \le j \le n} b_{ij} x_j + c_i, $$

with coefficients $a_{ijk}, b_{ij}, c_i \in \mathbb{F}_q$.

The security of MQ-based cryptography is based on the computational hardness of the Multivariate Quadratic problem. Specifically, for large values of $n$, solving a random system of such equations is known to be NP-hard, making it computationally infeasible for an attacker to solve within a reasonable time frame, even with powerful computational resources.

In addition to the inherent mathematical complexity, implementing robust protections is essential for securing MQ-based cryptographic schemes against both side-channel and fault attacks. Side-channel attacks exploit various forms of leakage—such as timing variations, power consumption, or electromagnetic emissions—to gain insights into the cryptographic process. These attacks take advantage of unintended information leaks that arise during the physical implementation of a cryptographic algorithm, rather than exploiting weaknesses in the algorithm itself.

Fault attacks, in contrast, involve deliberately introducing errors during cryptographic execution, such as memory corruption or inducing bit flips, to extract sensitive information by analyzing erroneous outputs. To mitigate these threats, countermeasures such as constant-time algorithms, masking techniques, noise generation, and redundancy checks can be integrated, significantly enhancing the robustness of cryptographic implementations. These safeguards help ensure that the theoretical security of MQ-based schemes translates into practical resilience, providing strong protection against both side-channel and fault attacks in real-world environments.

## 1.1 MQ signature schemes

One of the earliest efforts to convert the MQ problem into a digital signature scheme was introduced in 1988 with the $C^*$ scheme [20]. However, Patarin successfully attacked this scheme in 1995 [23], rendering it insecure. Since then, numerous advancements have been made in digital signature schemes based on multivariate polynomials. A prominent example of these advancements is the Unbalanced Oil-Vinegar (UOV) scheme, which offers strong security features.
The UOV-like schemes are an extension of the original Oil-Vinegar (OV) scheme and they are designed to enhance security by introducing an imbalance between the number of “oil” and “vinegar” variables. We can briefly define UOV as: let $v$ be the number of vinegar variables: $v_1, v_2, \dots, v_v$, and $o$ be the number of oil variables: $o_1, o_2, \dots, o_o$. The public key consists of $o$ quadratic polynomials $P_i$ in $n = v + o$ variables over a finite field $\mathbb{F}_q$, defined as:

$$P_i(v_1, \dots, v_v, o_1, \dots, o_o) = \sum_{1 \le j \le k \le v} a_{ijk} v_j v_k + \sum_{j=1}^{v} \sum_{k=1}^{o} b_{ijk} v_j o_k + \sum_{1 \le j \le k \le o} c_{ijk} o_j o_k + \sum_{j=1}^{v} d_{ij} v_j + \sum_{k=1}^{o} e_{ik} o_k + f_i,$$

where $a_{ijk}, b_{ijk}, c_{ijk}, d_{ij}, e_{ik}, f_i \in \mathbb{F}_q$.

The private key consists of the secret lineal transformation and the so-called central map that link the vinegar and oil variables to the public key polynomials. During the signing process, random values are selected for the vinegar variables $v_1, \dots, v_v$. These values are then substituted into the quadratic polynomials, resulting in a system of linear equations involving the oil variables. Next, the system is solved to determine the values of the oil variables $o_1, \dots, o_o$, and the signature is produced by combining the values of both the vinegar and oil variables.

To verify the signature, the signed values are substituted into the public polynomials to ensure they satisfy the equations $P_i - y_i = 0$ for all $i$.

In the world of UOV-like schemes, we can remark that there are several benefits such as small signatures, fast verification, and reasonable public key sizes. This is the case of MAYO [4, 6] and SNOVA [19, 28].

## 1.2 Fault attacks

Fault attacks are techniques used to exploit cryptographic implementations. This section provides an overview of fault attacks.

*Fault Attacks.* Fault injection attacks intentionally disrupt a device's normal operation to induce errors and extract information from cryptographic processes. Techniques such as electromagnetic pulses, lasers, voltage glitches, and DRAM row hammering are commonly used for fault injection, each varying in precision and complexity [1, 7, 16]. For example, laser-based injections offer high accuracy but are expensive, whereas DRAM row hammering requires extensive profiling. Inducing faults often requires multiple attempts; however, this does not necessarily mean causing multiple distinct faults. It may involve repeatedly inducing a specific fault over several runs to collect sufficient data for exploitation.

*Fault Attacks against other MQ-based cryptosystems* Table 1 compares previous fault injection attacks on multivariate signature schemes, highlighting key
<table><caption>**Table 1.** Comparison of Previous Fault Attacks on Multivariate Signature Schemes.</caption><thead><tr><th>Algorithm</th><th>#Signatures</th><th>#Faults</th><th>Evaluation</th><th>Assumptions</th></tr></thead><tbody><tr><td>Multiple [13]</td><td>Multiple</td><td>Multiple</td><td>Theoretical</td><td>None</td></tr><tr><td>UOV/Rainbow [17]</td><td>Multiple</td><td>Multiple</td><td>Theoretical</td><td>None</td></tr><tr><td>UOV [26]</td><td>44-103</td><td>Multiple</td><td>Theoretical</td><td>None</td></tr><tr><td>LUOV [21]</td><td>Multiple</td><td>Multiple</td><td>Practical</td><td>Key in F<sub>2</sub></td></tr><tr><td>Rainbow [3]</td><td>Multiple</td><td>1</td><td>Simulation</td><td>Exact memory reuse</td></tr><tr><td>UOV [11]</td><td>Multiple</td><td>2-40</td><td>Simulation</td><td>Enumeration 2<sup>41</sup>-2<sup>89</sup></td></tr><tr><td>MAYO [25]</td><td>2</td><td>1</td><td>Theoretical</td><td>None</td></tr><tr><td>MAYO [2]</td><td>1</td><td>1</td><td>Practical</td><td>Zero-initialization</td></tr><tr><td>MAYO [15]</td><td>1</td><td>1</td><td>Practical, Simulation</td><td>None</td></tr><tr><td>SNOVA<br>permanent fault strategy</td><td>22-68</td><td>1</td><td>Theoretical, Simulation</td><td>None</td></tr><tr><td>SNOVA<br>Fault-assisted reconciliation attack</td><td>1</td><td>Multiple</td><td>Theoretical, Simulation</td><td>None</td></tr></tbody></table>

features such as the number of signatures and faults required, the evaluation method, and any assumptions made.

Recently, [15] presented an attack on a MAYO implementation that successfully recovered the private key. This attack targeted a single execution of MAYO. However, the fault was not in MAYO itself, but rather in the C implementation of Keccak, which is responsible for generating the Vinegar and Oil variables. The paper exploits a vulnerability in the pseudorandom function, using a fault in this component to reveal information leading to private key recovery.

In this work, we explore a similar attack. However, instead of targeting Ke, we focus directly on the vinegar variables by inducing faults—i.e., fixing specific bit values—which allows us to recover the private key. Despite this similarity, our approach differs in the algorithm used for key recovery. Moreover, we introduce an SNOVA fault-assisted reconciliation attack that requires only a single signature. This approach is distinct from previous works.

## 1.3 Our contributions

In this paper, we explore fault injection attacks and their impact on the security of SNOVA. We present an analysis demonstrating that by inducing either a single permanent fault or transient faults in specific operations of the signature generation algorithm, an attacker can create faulty signatures that reveal partial private key information. Our comprehensive analysis covers several scenarios. First, we investigate which rows of $T$, the matrix representation of the SNOVA private linear map, an attacker can recover after fixing certain $\mathbb{F}_{16}$ elements in some (or all) vinegar variables during signature generation. We then generalize this by examining the recovery of rows of $T$ after fixing bits in the binary representation of the vinegar variables. In both cases, we show that collecting enough faulty signatures allows an attacker to recover $T$ partially, compromising the
private key. We then turn our attention to another scenario where, by inducing transient faults in the generation of vinegar variables, the attacker can recover the secret space via a reconciliation attack. Simulations of our fault attack are included to substantiate our claims.

Our detailed examination highlights the critical need for fault attack countermeasures to implement SNOVA. Therefore, we also provide a countermeasure and its corresponding analysis to counteract our fault attacks. Finally, our findings underscore the importance of incorporating comprehensive security strategies to protect against this type of attack, ensuring the integrity and reliability of cryptographic systems.

*Paper organization.* This paper is organized as follows. Section 2 presents a self-contained description of the SNOVA signature scheme. Section 3 presents our fault analysis on SNOVA, introducing several scenarios along with the implications of our recovery algorithms. Section 4 describes our experimental setting, our simulation of our fault attacks on SNOVA, and its results. Section 5 presents a countermeasure to protect SNOVA against the fault attack introduced previously. Finally, Section 6 concludes our work by highlighting our findings and their implications and delineating future works.

## 2 A simple non-commutative UOV scheme

In this section, we introduce SNOVA, a simple non-commutative UOV scheme. SNOVA is a recently proposed UOV-like signature scheme, as outlined in [28], and has been submitted to the NIST competition for Post-Quantum Digital Signature Schemes.

Let $v, o, l \in \mathbb{N}$ with $v > o$ and $\mathbb{F}_q$ a finite field with $q$ being a power of a prime number. Set $n = v + o$ and $m = o$. By $[m]$ we denote the set $\{1, \dots, m\}$ and by $\mathcal{R}$ we denote the ring of $l \times l$ matrices over the finite field $\mathbb{F}_q$. Also, by $U = (U_1, \dots, U_n)^t \in \mathcal{R}^n$ we denote a column vector with $n$ entries from $\mathcal{R}$. Let $Q \in \mathcal{R}$, we denote by $\Lambda_Q$, the $nl \times nl$ block diagonal matrix with $Q$-blocks along the diagonal.

The subring $\mathbb{F}_q[S]$ of $\mathcal{R}$ is defined to be

$$ \mathbb{F}_q[S] = \{a_0 + a_1S + \dots + a_{l-1}S^{l-1} | a_0, a_1, \dots, a_{l-1} \in \mathbb{F}_q\} $$

where $S$ is a $l \times l$ symmetric matrix with irreducible characteristic polynomial. Note that the elements in $\mathbb{F}_q[S]$ are symmetric and all commute. Additionally, the non-zero elements in $\mathbb{F}_q[S]$ are invertible. In particular, $\mathbb{F}_q[S]$ is a finite field with $\mathbb{F}_q[S] \cong \mathbb{F}_{q^l}$.

The central map is given by $\mathcal{F} = [\mathcal{F}_1, \mathcal{F}_2, \dots, \mathcal{F}_m] : \mathcal{R}^n \to \mathcal{R}^m$, and $\mathcal{F}_i$ is defined as
$$ \mathcal{F}_k(X_1, X_2, \dots, X_n) = \sum_{\alpha=1}^{l^2} A_\alpha \cdot \left( \sum_{(i,j) \in \Omega} X_i^t \cdot (Q_{\alpha 1} F_{k,ij} Q_{\alpha 2}) X_j \right) \cdot B_\alpha $$

where $\Omega = \{(i,j) : 1 \le i, j \le n\} \setminus \{(i,j) : m+1 \le i, j \le n\}$, $F_{k,ij} \stackrel{\$}{\leftarrow} \mathcal{R}$, $A_\alpha, B_\alpha \stackrel{\$}{\leftarrow} \mathcal{R}$ (invertibles), and $Q_{\alpha 1}, Q_{\alpha 2} \stackrel{\$}{\leftarrow} \mathbb{F}_q[S]$ (invertibles). Set $F_k = [F_{k,ij}]_{(i,j) \in \Omega}$ for each $k \in [m]$.

Invertible linear map for this scheme is the map $\mathcal{T} : \mathcal{R}^n \to \mathcal{R}^n$ corresponding to the matrix

$$ T = \begin{bmatrix} I^{11} & T^{12} \\ O & I^{22} \end{bmatrix} $$

where $T^{12}$ is a $v \times o$ matrix consisting of nonzero entries $T_{i,j}^{12}$ chosen randomly from $\mathbb{F}_q[S]$. Note that $T^{-1} = T$, if $\mathbb{F}_q$ is of characteristic 2. In addition, $I^{11}$ and $I^{22}$ are identity matrices over $\mathcal{R}$ of size $v \times v$ and $o \times o$ respectively.

Public map is defined as $\mathcal{P} := \mathcal{F} \circ \mathcal{T} = [\mathcal{P}_1 = \mathcal{F}_1 \circ \mathcal{T}, \dots, \mathcal{P}_m = \mathcal{F}_m \circ \mathcal{T}]$. Set $U = (U_1, \dots, U_n)^t \in \mathcal{R}^n$, then

$$ \mathcal{P}_k(U) = \sum_{\alpha=1}^{l^2} A_\alpha(TU)^t \Lambda_{Q_{\alpha 1}} F_k \Lambda_{Q_{\alpha 2}}(TU) \cdot B_\alpha \quad (1) $$

for any $k \in [m]$. Moreover, $\mathcal{P}_k(U)$ can be written as

$$ \mathcal{P}_k(U) = \mathcal{F}_k(\mathcal{T}(U)) = \sum_{\alpha=1}^{l^2} \sum_{i=1}^{n} \sum_{j=1}^{n} A_\alpha \cdot U_i^t(Q_{\alpha 1} P_{k,ij} Q_{\alpha 2}) U_j \cdot B_\alpha, $$

where $P_{k,ij} = \sum_{(s,t) \in \Omega} T_{is} F_{k,st} T_{tj}$, by the commutativity of $\mathbb{F}_q[S]$ and that the elements in $\mathbb{F}_q[S]$ are symmetric. Set $P_k = [P_{k,ij}]_{(i,j) \in [n] \times [n]}$ for each $k \in [m]$.

The SNOVA signature scheme [28] consists of a triple of algorithms (KeyGen, Sign, Verify). Moreover, a SNOVA parameter set is given by values for $v, o, l, \lambda$.

The KeyGen function runs a probabilistic algorithm as shown by Algorithm 1. It outputs a SNOVA key pair (sk, pk).

The public key pk is a representation of $\mathcal{P}$. A full public key consists of the list of matrices $\{P_k = \begin{bmatrix} P_k^{11} & P_k^{12} \\ P_k^{21} & P_k^{22} \end{bmatrix} : k \in [m]\}$ and the list of matrices $\{A_\alpha, B_\alpha, Q_{\alpha 1}, Q_{\alpha 2} : \alpha \in [l^2]\}$. However, it is enough to store $(\text{Spublic}, \{P_k^{22}\}_{k \in [m]})$. Indeed, the public seed Spublic is used to regenerate $P_k^{11}$, $P_k^{12}$ and $P_k^{21}$ for $k \in [m]$, and $A_\alpha, B_\alpha, Q_{\alpha 1}$ and $Q_{\alpha 2}$ for $\alpha \in \{1, \dots, l^2\}$. Therefore, the public key size is $m \cdot m^2 \cdot l^2$ field elements plus the size of the public seed Spublic.

The private key sk is a representation of $(\mathcal{F}, \mathcal{T})$. A full private key consists of a matrix $T^{12}$ and the list of matrices $\{F_k : k \in [m]\}$. In practice, a private seed
Sprivate is used to generate $T^{12}$, and the matrices $\{F_k\}_{k \in [m]}$ are computed by exploiting the relation between $F_k, P_k$ along with $T^{12}$, as shown by the lines from 8 to 11 of Algorithm 1.

Table 2 summarizes current SNOVA parameters, and public and private keys sizes, as well as, signature sizes for each security level.

**Algorithm 1** Key generation algorithm
1: **function** KeyGen($v, o, l, \lambda$)
2: m ← o;n ← o + v;
3: **Sprivate** ← $\$\{0, 1\}^{2\lambda}$
4: **Spublic** ← $\$\{0, 1\}^{2\lambda}$
5: $T^{12} \leftarrow \text{PRG}(\text{Sprivate})$, where $T_{ij}^{12} \in \mathbb{F}_{16}[S]$.
6: $\{P_k^{11}\}_{k \in [m]}, \{P_k^{12}\}_{k \in [m]}, \{P_k^{21}\}_{k \in [m]}, \{A_\alpha\}_{\alpha \in [l^2]}, \{B_\alpha\}_{\alpha \in [l^2]}, \{Q_{\alpha 1}\}_{\alpha \in [l^2]}, \{Q_{\alpha 2}\}_{\alpha \in [l^2]} \leftarrow \text{PRG}(\text{Spublic})$
7: **for** ($k \leftarrow 1, k \le m, k \leftarrow k + 1$) **do**
8: &nbsp;&nbsp;&nbsp;&nbsp; $F_k^{11} \leftarrow P_k^{11}$
9: &nbsp;&nbsp;&nbsp;&nbsp; $F_k^{12} \leftarrow P_k^{11}T^{12} + P_k^{12}$
10: &nbsp;&nbsp;&nbsp;&nbsp; $F_k^{21} \leftarrow (T^{12})^t P_k^{11} + P_k^{21}$
11: &nbsp;&nbsp;&nbsp;&nbsp; $P_k^{22} \leftarrow (T^{12})^t (P_k^{11}T^{12} + P_k^{12}) + P_k^{21}T^{12}$
12: **end for**
13: **sk** ← $(\{F_k^{11}\}_{k \in [m]}, \{F_k^{12}\}_{k \in [m]}, \{F_k^{21}\}_{k \in [m]}, T^{12})$
14: **pk** ← $(\text{Spublic}, \{P_k^{22}\}_{k \in [m]})$
15: **return** (sk, pk);
16: **end function**

<table><caption>**Table 2.** Parameters for SNOVA [19].</caption><thead><tr><th>Sec. Level</th><th>(v, o, q, l, λ)</th><th>Public key (B)</th><th>Signature (B)</th><th>Private key (B)</th></tr></thead><tbody><tr><td rowspan="3">I</td><td>(37, 17, 16, 2, 128)</td><td>9826(+16)</td><td>108(+16)</td><td>60008(+48)</td></tr><tr><td>(25, 8, 16, 3, 128)</td><td>2304(+16)</td><td>148.5(+16)</td><td>37962(+48)</td></tr><tr><td>(24, 5, 16, 4, 128)</td><td>1000(+16)</td><td>232(+16)</td><td>34112(+48)</td></tr><tr><td rowspan="3">III</td><td>(56, 25, 16, 2, 192)</td><td>31250(+16)</td><td>162(+16)</td><td>202132(+48)</td></tr><tr><td>(49, 11, 16, 3, 192)</td><td>5989.5(+16)</td><td>270(+16)</td><td>174798(+48)</td></tr><tr><td>(37, 8, 16, 4, 192)</td><td>4096(+16)</td><td>360(+16)</td><td>128384(+48)</td></tr><tr><td rowspan="3">V</td><td>(75, 33, 16, 2, 256)</td><td>71874(+16)</td><td>216(+16)</td><td>515360(+48)</td></tr><tr><td>(66, 15, 16, 3, 256)</td><td>15187.5(+16)</td><td>364.5(+16)</td><td>432297(+48)</td></tr><tr><td>(60, 10, 16, 4, 256)</td><td>8000(+16)</td><td>560(+16)</td><td>389312(+48)</td></tr></tbody></table>

The Sign function runs a UOV-like signing procedure as shown by Algorithm 2. It digitally signs a message $M$ under the private key sk. It first samples a salt from $\{0, 1\}^{2\lambda}$, then sets $Y \leftarrow \mathcal{H}_1(\text{Spublic}||\mathcal{H}_0(M)||\text{salt})$ where $Y \in \mathbb{R}^m$.
The algorithm then chooses random values $V_1, \dots, V_v \in \mathcal{R}$ as the vinegar variables. Then, it attempts to find the values $(V_{v+1}, \dots, V_n)$ by solving the equation $\mathcal{F}(V_1, \dots, V_v, V_{v+1}, \dots, V_n) = Y$. If no solution to the equation is found, the algorithm will choose random values $V'_1, \dots, V'_v \in \mathcal{R}$ and repeat the procedure until it finds a solution to the equation. Let $X = (V_1, \dots, V_v, V_{v+1}, \dots, V_n)^t$ be the solution to the equation. This algorithm then computes the signature as $S = \mathcal{T}^{-1}(X)$ and outputs $(S, \text{salt})$.

<caption>**Algorithm 2** signs message M</caption>

1: **function** sign(v, o, l, λ, sk, spublic, M)
2: m ← o
3: n ← o + v
4: ({$F_k^{11}$}$_{k \in [m]}$, {$F_k^{12}$}$_{k \in [m]}$, {$F_k^{21}$}$_{k \in [m]}$, $T^{12}$) ← sk
5: {$A_\alpha$}$_{\alpha \in [l^2]}$, {$B_\alpha$}$_{\alpha \in [l^2]}$, {$Q_{\alpha 1}$}$_{\alpha \in [l^2]}$, {$Q_{\alpha 2}$}$_{\alpha \in [l^2]}$ ← PRG(spublic)
6: digest ← $\mathcal{H}_0(M)$
7: salt ← $\mathcal{R}$ {$0, 1$} $\lambda$
8: is_done ← False
9: cont ← 0;
10: $[Y_1, Y_2, \dots, Y_m] \leftarrow \mathcal{H}_1(\text{Spublic} || \text{digest} || \text{salt})$
11: $F_k \leftarrow \sum_{\alpha=1}^{l^2} A_\alpha (\sum_{i=1}^v \sum_{j=1}^v X_i^t(Q_{\alpha 1} F_{k,ij}^{11} Q_{\alpha 2}) X_j + \sum_{i=1}^v \sum_{j=1}^m X_i^t(Q_{\alpha 1} F_{k,ij}^{12} Q_{\alpha 2}) X_j + \sum_{j=1}^m \sum_{i=1}^v X_j^t(Q_{\alpha 1} F_{k,ji}^{21} Q_{\alpha 2}) X_i) \cdot B_\alpha$ for all $i \in [m]$.
12: **while** not is_done **do**
13: $[V_1, V_2, \dots, V_v] \leftarrow \text{PRG}(\text{Sprivate} || \text{digest} || \text{salt} || \text{cont})$
14: Compute $F_{k,VV} \leftarrow \sum_{\alpha=1}^{l^2} A_\alpha (\sum_{i=1}^v \sum_{j=1}^v V_i^t(Q_{\alpha 1} F_{k,ij}^{11} Q_{\alpha 2}) V_j) \cdot B_\alpha$ for all $k \in [m]$.
15: Express $Y_k - F_{k,VV} = \sum_{\alpha=1}^{l^2} A_\alpha (\sum_{i=1}^v \sum_{j=1}^m V_i^t(Q_{\alpha 1} F_{k,ij}^{12} Q_{\alpha 2}) X_j + \sum_{j=1}^m \sum_{i=1}^v X_j^t(Q_{\alpha 1} F_{k,ji}^{21} Q_{\alpha 2}) V_i) \cdot B_\alpha$ for all $k \in [m]$ as an equation system on the oil variables $\vec{X}_1, \vec{X}_2, \dots, \vec{X}_m$.
$$M_{1,1} \vec{X}_1 + M_{1,2} \vec{X}_1 + \dots + M_{1,m} \vec{X}_m = \vec{Y}_1 - \overline{F_{1,VV}}$$
$$M_{2,1} \vec{X}_1 + M_{2,2} \vec{X}_2 + \dots + M_{2,m} \vec{X}_m = \vec{Y}_2 - \overline{F_{2,VV}}$$
$$\vdots$$
$$M_{m,1} \vec{X}_1 + M_{m,2} \vec{X}_2 + \dots + M_{m,m} \vec{X}_m = \vec{Y}_m - \overline{F_{m,VV}}$$
16: Represent this equation system as an $(ml^2) \times (ml^2 + 1)$ matrix A over $\mathbb{F}_{16}$
17: $L_O$, output ← Gauss(A)
18: **if** output **then**
19: $[V_{v+1}, V_{v+2}, \dots, V_n] \leftarrow L_O$
20: $V \leftarrow [V_1, V_2, \dots, V_v, V_{v+1}, \dots, V_n]$
21: $T \leftarrow \begin{bmatrix} I^{11} & T^{12} \\ O & I^{22} \end{bmatrix}$
22: $S \leftarrow T \cdot V^t$
23: is_done ← True
24: **else**
25: cont ← cont + 1
26: **end if**
27: **end while**
28: **return** (S, salt);
29: **end function**

The Verify function runs a deterministic algorithm. It simply verifies if a signature (S, salt) for M is valid under the public key pk. If $\mathcal{H}_1(\text{Spublic} || \mathcal{H}_0(M) || \text{salt}) = \mathcal{P}(S)$, then the signature is accepted, otherwise it is rejected.
**Reconciliation attack.** Ikematsu, and Akiyama [14], Li and Ding [18], and Nakamura, Tani, and Furue [22] analyzed the security of SNOVA against key-recovery attacks, unveiling all known key-recovery attacks for an instance of SNOVA can be seen as key-recovery attacks to instances of an equivalent UOV signature scheme. Particularly, [14] and [18] concluded that all known key-recovery attacks for SNOVA with parameters $(v, o, l, q)$ can be seen as attacks to a UOV signature scheme with $lo^2$ equations and $l(v+o)$ variables over $\mathbb{F}_q$. In particular, for the reconciliation attack, the attacker must find a specific solution $\mathbf{u}_0 \in \mathbb{F}_q^{ln}$ from among many solutions of a quadratic polynomial system of the form

$$ \mathbf{u}_0^t(\Lambda_{S^i} P_k \Lambda_{S^j}) \mathbf{u}_0 = 0 \in \mathbb{F}_q, \qquad (2) $$

for $k \in [m], i, j \in \{0, 1, \dots, l-1\}$.

Once $\mathbf{u}_0$ is found, any $\mathbf{u}$ in the linearly independent set $\{\Lambda_{S^j} \mathbf{u}_0 : 0 \le j \le l-1\}$ will also satisfy Eq. (2). Additionally, the remaining vectors in the secret space $\mathcal{O}$ can be determined by leveraging the fact that for any $\mathbf{u}, \mathbf{v} \in \mathcal{O}$, it holds

$$ \mathbf{v}^t(\Lambda_{S^i} P_k \Lambda_{S^j}) \mathbf{u} = 0 \in \mathbb{F}_q \text{ for } k \in [m], 0 \le i, j \le l-1. \qquad (3) $$

Finally, for any $U \in \mathcal{K}$, it holds $\mathcal{P}_k(U) = 0$ for all $k \in [m]$, where

$$ \mathcal{K} := \mathcal{O} \otimes \mathbb{F}_q^l = \{\mathbf{u} \otimes \mathbf{e}^t \in \mathbb{R}^n : \mathbf{u} \in \mathcal{O}, \mathbf{e} \in \mathbb{F}_q^l\}. \qquad (4) $$

Thus, the complexity of the reconciliation attack is dominated by finding a solution to the quadratic system in Eq. (2). A recent paper [9] introduces a new algorithm that exploits the stability of the quadratic system in Eq. (2) under the action of a commutative group of matrices, reducing the complexity of solving SNOVA systems, over generic ones. In particular, they show how their new algorithm decreases the complexity of solving such a system. On the other hand, we here explore other directions by introducing a new fault-assisted reconciliation attack in Section 3.7. This attack leverages induced transient faults to recover the secret key space by solving the system as mentioned earlier.

# 3 Fault analysis on SNOVA

In this section, we present our comprehensive fault analysis on SNOVA. We first state our attack model, then explore a first unsuccessful attempt at mounting a fault attack, and then turn our attention to our successful attempts at mounting a fault attack against SNOVA.

## 3.1 Adversarial Model

We consider an adversarial model similar to those assumed in previous works, particularly in [17], within the context of UOV and RAINBOW.
In this model, the attacker targets the signature generation process and can induce transient or permanent faults affecting specific operations within Algorithm 2. These faults enable the attacker to manipulate certain values during the execution of the signature generation algorithm. Importantly, the attacker may be unaware of the exact number of manipulated values or their specific content.

Subsequently, the attacker can invoke the faulty Algorithm 2 multiple times –where the number of invocations depends on the attack strategy– to gather message-signature pairs. Each signature is generated with the tampered values, and the attacker’s ultimate goal is to analyze these pairs to extract partial information about the private key.

## 3.2 Attack strategy by fixing field elements of the central map

1. The attacker causes a single permanent fault, which affects line 4 of Algorithm 2, such that some $\mathbb{F}_q$ elements in $F_i \in \mathbb{F}_q^{\ln q \times \ln q}$, for $i \in I \subseteq [m]$ and $|I| \ge 1$, are fixed and unknown. In particular, for $F_i$, there is a fixed non-empty subset $J_i \subseteq [nl] \times [nl]$, such that $\tilde{F}_{i,(r_0,r_1)} \in \mathbb{F}_q$, $(r_0, r_1) \in J_i$ is fixed and unknown. We remark the line 4 in practice is an expansion of a private seed along with other operations to compute the list of matrices $\{F_k\}_{k \in [m]}$.

2. For each $\omega \in [N_{msg}]$, the attacker calls Algorithm 2 for the randomly chosen message $\mathbf{M}^{(\omega)} \in \mathcal{R}^m$ and receives the signatures $(\mathbf{S}^{(\omega)}, \text{salt}^{(\omega)})$.

Let $\tilde{\mathcal{F}}$ be the faulty central map and $\tilde{\mathcal{P}} = \tilde{\mathcal{F}} \circ \mathcal{T}$ be the faulty public map. Recall that the SNOVA public map is defined as

$$ \mathcal{P}_k(\mathbf{S}^{(\omega)}) = \sum_{\alpha=1}^{l^2} A_{\alpha}(\mathbf{T}\mathbf{S}^{(\omega)})^t \Lambda_{Q_{\alpha 1}} F_k \Lambda_{Q_{\alpha 2}}(\mathbf{T}\mathbf{S}^{(\omega)}) \cdot B_{\alpha} $$

for any $k \in [m]$. Therefore, it holds

$$ \tilde{\mathcal{P}}_k(\mathbf{S}^{(\omega)}) - \mathcal{P}_k(\mathbf{S}^{(\omega)}) = \sum_{\alpha=1}^{l^2} A_{\alpha}(\mathbf{V}^{(\omega)})^t \Lambda_{Q_{\alpha 1}} (\tilde{F}_k - F_k) \Lambda_{Q_{\alpha 2}}(\mathbf{V}^{(\omega)}) \cdot B_{\alpha} \quad (5) $$

where $\mathbf{T}\mathbf{S}^{(\omega)} = \mathbf{V}^{(\omega)}$ with $\mathbf{V}^{(\omega)} = (\mathbf{V}_1^{(\omega)}, \dots, \mathbf{V}_n^{(\omega)})^t$, by the line 22 of Algorithm 2.

We remark the attacker can compute the left hand of Eq. (5), since $\tilde{\mathcal{P}}_k(\mathbf{S}^{(\omega)}) = \mathcal{H}_1(\text{Spublic} \| \mathcal{H}_0(\mathbf{M}^{(\omega)}) \| \text{salt}^{(\omega)})_k$ and $\mathcal{P}$ is public.

Moreover, for any $i \in [m] \setminus I$, both sides of Eq. (5) vanish. However, for any $i \in I$, the left hand of Eq. (5) is expected to be a non-zero element in $\mathcal{R}$, and $\tilde{F}_i = \tilde{F}_i - F_i \in \mathbb{F}_q^{\ln q \times \ln q}$, on the right side of Eq. (5), is expected to become a sparse matrix, since the entries $\tilde{F}_{i,st} \in \mathbb{F}_q$ with $(s, t) \in J_i$ are the only ones expected to be non-zero.

We remark, nonetheless, that these observations may not be easily exploitable for the attacker to gain information on $T$, since the attacker does not know $I, \tilde{F}_i, J_i, \mathbf{V}^{(\omega)}$ and $\tilde{F}_i$. Therefore, our following scenario focuses on inducing a permanent fault affecting the line 13 of Algorithm 2 to further exploit the relation $\mathbf{T}\mathbf{S}^{(\omega)} = \mathbf{V}^{(\omega)}$.
### 3.3 Attack strategy by fixing field elements of vinegar variables

1. The attacker introduces a single permanent fault, which affects line 13 of Algorithm 2, causing certain $\mathbb{F}_q$ elements in $V_i \in \mathbb{R}$, for $i \in I \subseteq [v]$ with $|I| \ge 1$, to be fixed and unknown. Specifically, for each variable $V_i$, there is a fixed non-empty subset $J_i \subseteq [l] \times [l]$, such that $\bar{V}_{i,(r_0,r_1)} \in \mathbb{F}_q$ for $(r_0, r_1) \in J_i$ is fixed and unknown.

2. For each $\omega \in [N_{msg}]$, the attacker calls Algorithm 2 for the randomly chosen message $\mathbf{M}^{(\omega)} \in \mathbb{R}^m$ and receives the signature $(\mathbf{S}^{(\omega)}, \mathbf{salt}^{(\omega)})$.

3. The attacker then calls Algorithm 3 with parameters $v, o, l, [\mathbf{S}^{(1)}, \dots, \mathbf{S}^{(N_{msg})}]$ to obtain dic, a dictionary-like data structure indexed by $[v] \times [l]^2$. When $N_{msg} > lo + 1$, Algorithm 3 will output dic such that dic[(i, r₀, r₁)] = [Tᵢ¹², ..., Tᵢ₀] for i ∈ I and (r₀, r₁) ∈ Jᵢ, and dic[(i, r₀, r₁)] = None otherwise.

*Why is Step 3 of the attack strategy expected to work correctly?* As seen in Section 2, the invertible linear map $\mathcal{T}$ for the SNOVA scheme is given by the matrix

$$T = \begin{bmatrix} I^{11} & T^{12} \\ O & I^{22} \end{bmatrix},$$

where $T^{12}$ is a $v \times o$ matrix with nonzero entries $T_{ij}^{12}$ chosen randomly from $\mathbb{F}_q[S]$. From the line 22 of Algorithm 2, it holds $TS^{(\omega)} = V^{(\omega)}$, that is,

$$\begin{bmatrix} 1 & 0 & \dots & 0 & T_{11}^{12} & \dots & T_{1o}^{12} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 & T_{v1}^{12} & \dots & T_{vo}^{12} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 0 & \dots & 1 \end{bmatrix} \begin{bmatrix} \mathbf{S}_1^{(\omega)} \\ \vdots \\ \mathbf{S}_v^{(\omega)} \\ \vdots \\ \mathbf{S}_n^{(\omega)} \end{bmatrix} = \begin{bmatrix} \mathbf{V}_1^{(\omega)} \\ \vdots \\ \mathbf{V}_v^{(\omega)} \\ \vdots \\ \mathbf{V}_n^{(\omega)} \end{bmatrix}.$$

Since $T_{ij}^{12} \in \mathbb{F}_q[S]$, it holds $T_{ij}^{1,2} = \sum_{j_1=1}^l t_{ij,j_1}^{12} S^{j_1-1}$, where $t_{ij,j_1}^{12} \in \mathbb{F}_q$, and

$$\mathbf{S}_i^{(\omega)} + \sum_{j=1}^{o} T_{ij}^{12} \mathbf{S}_{v+j}^{(\omega)} = \mathbf{S}_i^{(\omega)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S^{j_1-1} \mathbf{S}_{v+j}^{(\omega)} = \mathbf{v}_i^{(\omega)}, i \in [v] \\ \mathbf{S}_i^{(\omega)} = \mathbf{v}_i^{(\omega)}, v+1 \le i \le n$$

For $2 \le \omega \le N_{msg}$, we can write

$$\mathbf{S}_i^{(\omega)} - \mathbf{S}_i^{(1)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S^{j_1-1} (\mathbf{S}_{v+j}^{(\omega)} - \mathbf{S}_{v+j}^{(1)}) = \mathbf{v}_i^{(\omega)} - \mathbf{v}_i^{(1)}, i \in [v] \\ \mathbf{S}_i^{(\omega)} - \mathbf{S}_i^{(1)} = \mathbf{v}_i^{(\omega)} - \mathbf{v}_i^{(1)}, v+1 \le i \le n$$
Let us fix $2 \le \omega \le N_{msg}$ and $i \in [v]$. Also, let us set $S_i^{(\omega,1)} = S_i^{(\omega)} - S_i^{(1)}$, $S_{v+j}^{(j_1,\omega,1)} = S^{j_1-1}(S_{v+j}^{(\omega)} - S_{v+j}^{(1)})$ and $V_i^{(\omega,1)} = V_i^{(\omega)} - V_i^{(1)}$. Consider

$$S_i^{(\omega,1)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S_{v+j}^{(j_1,\omega,1)} = V_i^{(\omega,1)}. \quad (6)$$

Since Eq. (6) is defined over $\mathcal{R}$, it is equivalent to $l^2$ equations on $lo$ unknowns over $\mathbb{F}_q$. Therefore,

$$S_{i,(r_0,r_1)}^{(\omega,1)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S_{v+j,(r_0,r_1)}^{(j_1,\omega,1)} = V_{i,(r_0,r_1)}^{(\omega,1)}, \quad \text{for } r_0, r_1 \in [l]. \quad (7)$$

Note that the attacker can compute $S^{(\omega,1)}$ and $S^{(j_1,\omega,1)}$ on the left hand of Eq. (6). Additionally, for a fixed $i \in I$ and for $2 \le \omega \le N_{msg}$, a linear system of $(N_{msg} - 1)|J_i|$ equations and $lo$ unknowns over $\mathbb{F}_q$ can be obtained and is given by

$$\{S_{i,(r_0,r_1)}^{(\omega,1)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S_{v+j,(r_0,r_1)}^{(j_1,\omega,1)} = 0, \text{ for } (r_0, r_1) \in J_i\}_{2 \le \omega \le N_{msg}}. \quad (8)$$

However the attacker does not know either $I$ or $J_i$. If $J_i$ were known by the attacker, collecting $N_{msg} > \frac{o \cdot l}{|J_i|} + 1$ would be enough to guarantee an unique solution to the linear system of Eq. (8).

In order for the attacker to gain knowledge of $I$ and $J_i$ for $i \in I$, and recover $T_{i,j}^{12}$ for $i \in I, j \in [o]$, the attacker may try to solve $v \cdot l^2$ linear systems separately, i.e. one for $i \in [v]$ and $(r_0, r_1) \in [l]^2$,

$$\{S_{i,(r_0,r_1)}^{(\omega,1)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S_{v+j,(r_0,r_1)}^{(j_1,\omega,1)} = 0\}_{2 \le \omega \le N_{msg}}, \quad (9)$$

where each has $N_{msg} - 1$ equations and $lo$ unknowns. If $N_{msg} > l \cdot o + 1$, then the linear systems for $(r_0, r_1) \in J_i, i \in I$ will have a unique solution, while the other linear systems are expected to have no solution. Therefore, when $N_{msg} > lo + 1$, Algorithm 3 will output dic such that dic[(i, r_0, r_1)] = [T_{i1}^{12}, \dots, T_{io}^{12}] for $i \in I, (r_0, r_1) \in J_i$ and dic[(i, r_0, r_1)] = None otherwise.

Furthermore, if the attacker is able to fix at least an entry of each vinegar variable (i.e. $I = [v]$ and so $|J_i| \ge 1$) and collect at least $lo + 2$ signatures, Algorithm 3 will recover the entire matrix $T^{12}$.

### 3.4 What if the attacker only can fix some bits of $V_i$ for $i \in I$?

In this section, we assume a variable $V_i$ is represented as a bit-string of length $N_{bits} \cdot l^2$, where $q = 2^{N_{bits}}$ as it is the case for SNOVA. The attack strategy is as follows.
<caption>**Algorithm 3** partially recovers $T^{12}$ from fixed field elements.</caption>

1: **function** recover_partial_T_F16(v, o, l, [S<sup>(1)</sup>, ..., S<sup>(Nmsg)</sup>])
2: S ← getS(l)
3: dic ← {}
4: **for** (i ← 1, i ≤ v, i ← i + 1) **do**
5:     **for** (r<sub>0</sub> ← 1, r<sub>0</sub> ≤ l, r<sub>0</sub> ← r<sub>0</sub> + 1) **do**
6:         **for** (r<sub>1</sub> ← 1, r<sub>1</sub> ≤ l, r<sub>1</sub> ← r<sub>1</sub> + 1) **do**
7:         A ← F<sup>(N<sub>msg</sub>-1)×ol</sup><sub>16</sub>
8:         Y ← F<sup>(N<sub>msg</sub>-1)×l</sup><sub>16</sub>
9:         **for** (ω ← 2, ω ≤ N<sub>msg</sub>, ω ← ω + 1) **do**
10:        S<sup>(ω,1)</sup><sub>i</sub> ← S<sup>(1)</sup><sub>i</sub> - S<sup>(ω)</sup><sub>i</sub>
11:        **for** (j ← 1, j ≤ o, j ← j + 1) **do**
12:         **for** (j<sub>1</sub> ← 1, j<sub>1</sub> ≤ l, j<sub>1</sub> ← j<sub>1</sub> + 1) **do**
13:          S<sup>(j<sub>1</sub>,k,1)</sup><sub>v+j</sub> ← S<sup>j<sub>1</sub>-1</sup><sub>v+j</sub>(S<sup>(ω)</sup><sub>v+j</sub> - S<sup>(1)</sup><sub>v+j</sub>)
14:          A<sup>(ω-1),j,l+j<sub>1</sub></sup> ← S<sup>(j<sub>1</sub>,k,1)</sup><sub>v+j,(r<sub>0</sub>,r<sub>1</sub>)</sub>
15:        **end for**
16:        **end for**
17:        Y<sup>(ω-1),0</sup><sub>i,(r<sub>0</sub>,r<sub>1</sub>)</sub> ← S<sup>(ω,1)</sup><sub>i,(r<sub>0</sub>,r<sub>1</sub>)</sub>
18:        **end for**
19:    X, output ← Gauss(A, Y)
20:    **if** output then
21:        [T<sup>12</sup><sub>i1</sub>, ..., T<sup>12</sup><sub>io</sub>] ← get_elements_in_FqS(X, l)
22:        dic[(i, r<sub>0</sub>, r<sub>1</sub>)] ← [T<sup>12</sup><sub>i1</sub>, ..., T<sup>12</sup><sub>io</sub>]
23:    **else**
24:        dic[(i, r<sub>0</sub>, r<sub>1</sub>)] ← None
25:    **end if**
26:    **end for**
27:    **end for**
28:    **end for**
29:    **return** dic
30: **end function**
1. The attacker causes a single permanent fault, which affects the line 13 of Algorithm 2, such that some bits of $V_i \in \mathbb{R}$, with $i \in I \subseteq [v]$ and $|I| \ge 1$, are fixed and unknown. In particular, for the variable $V_i$, there is a fixed non-empty subset $B_i \subseteq [l] \times [l] \times [N_{bits}]$, such that $\tilde{V}_{i,(r_0,r_1,b)} \in \mathbb{F}_2$, $(r_0, r_1, b) \in B_i$ is fixed and unknown.

2. For each $\omega \in [N_{msg}]$, the attacker calls Algorithm 2 for the randomly chosen message $\mathbf{M}(\omega) \in \mathbb{R}^m$ and receives the signature $(\mathbf{S}^{(\omega)}, \mathbf{salt}^{(\omega)})$.

3. The attacker calls Algorithm 4 with parameters $v, o, l$, $[\mathbf{S}^{(1)}, \dots, \mathbf{S}^{(N_{msg})}]$ to get dic, a dictionary-like data structure indexed by $[v] \times [l]^2 \times [N_{bits}]$. When $N_{msg} > N_{bits} \cdot lo+1$, Algorithm 4 will output dic such that $\text{dic}[(i, r_0, r_1, b)] = [T_{i1}^{12}, \dots, T_{io}^{12}]$ for $i \in I$, $(r_0, r_1, b) \in B_i$ and $\text{dic}[(i, r_0, r_1, b)] = \text{None}$ otherwise.

*Why is Step 3 of the attack strategy expected to work correctly?* Since $\mathbb{F}_q$ can be seen as a vector space of dimension $N_{bits}$ over $\mathbb{F}_2$, we can obtain similar equations to those of Eq. (8). That is, for $i \in I$, we have

$$ \{\mathbf{S}_{i,(r_0,r_1,b)}^{(\omega,1)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} \kappa_{(r_0,r_1,b)}^{i,j,j_1,\omega,1} = 0, \text{ for } (r_0,r_1,b) \in B_i\}_{2 \le \omega \le N_{msg}}. \quad (10) $$

where $\kappa_{(r_0,r_1)}^{i,j,j_1,\omega,1} = t_{ij,j_1}^{12} \mathbf{S}_{v+j,(r_0,r_1)}^{(j_1,\omega,1)}$. Eq. (10) represents a linear system with $|B_i| \cdot (N_{msg} - 1)$ equations and $N_{bits} \cdot l \cdot o$ unknowns over $\mathbb{F}_2$. However, the attacker does not know either $I$ or $B_i$. For the attacker to gain knowledge of $I$ and $B_i$ for $i \in I$, and recover $T_{i,j}^{12}$ for $i \in I, j \in [o]$, the attacker may try to solve $N_{bits} \cdot v \cdot l^2$ linear systems separately, i.e. one for $i \in [v]$ and $(r_0, r_1, b) \in [l] \times [l] \times [N_{bits}]$,

$$ \{\mathbf{S}_{i,(r_0,r_1,b)}^{(\omega,1)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} \kappa_{(r_0,r_1,b)}^{i,j,j_1,\omega,1} = 0\}_{2 \le \omega \le N_{msg}}, \quad (11) $$

where each has $N_{msg} - 1$ equations and $N_{bits} \cdot l \cdot o$ unknowns over $\mathbb{F}_2$. If $N_{msg} > N_{bits} \cdot l \cdot o + 1$, then the linear systems for $(r_0, r_1, b) \in B_i, i \in I$ will have a unique solution, while the other linear systems are expected to have no solution. Algorithm 4 details the recovery strategy by the attacker and exploits the fact that $\mathbb{F}_{16} \cong \mathbb{F}_2[x]/\langle x^4 + x + 1 \rangle$ for SNOVA.

Therefore, when $N_{msg} > N_{bits} \cdot lo+1$, Algorithm 4 will output dic such that $\text{dic}[(i, r_0, r_1, b)] = [T_{i1}^{12}, \dots, T_{io}^{12}]$ for $i \in I$, $(r_0, r_1, b) \in B_i$ and $\text{dic}[(i, r_0, r_1, b)] = \text{None}$ otherwise.

### 3.5 How can the attacker recover $T_{i,j}^{12}$ for a fixed $i \in [v] \setminus I, j \in [o]$?

For $1 \le \omega \le N_{msg}$, we have
$$S_i^{(\omega)} + \sum_{j=1}^{o} T_{ij}^{12} S_{v+j}^{(\omega)} = S_i^{(\omega)} + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S_{v+j}^{(\omega)} = V_i^{(\omega)}, i \in [v] \setminus I,$$

Note that the previous equations can always be arranged as

$$S_i + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S_{j_1,j} = V_i$$

$$\text{with } \mathbf{S}_i = \begin{bmatrix} \mathbf{S}_i^{(1)} \\ \vdots \\ \mathbf{S}_i^{(N_{msg})} \end{bmatrix}^t, \mathbf{S}_{j_1,j} = \begin{bmatrix} S_{j_1-1}^{(1)} \mathbf{S}_{v+j}^{(1)} \\ \vdots \\ S_{j_1-1}^{(1)} \mathbf{S}_{v+j}^{(N_{msg})} \end{bmatrix}^t, \mathbf{V}_i = \begin{bmatrix} \mathbf{V}_i^{(1)} \\ \vdots \\ \mathbf{V}_i^{(N_{msg})} \end{bmatrix}^t \in \mathcal{R}^{1 \times N_{msg}}.$$

This indeed induces an instance of the MinRank problem [8] over $\mathbb{F}_q$. Note that by setting $\mathbf{M} = (\mathbf{S}_i, \mathbf{S}_{1,1}, \dots, \mathbf{S}_{l,o}) \in (\mathbb{F}_q^{l \times (N_{msg} \cdot l)})^{l \cdot o+1}$, there exists a $(t_{i1,1}, \dots, t_{io,l}) \in \mathbb{F}_q^{ol}$ and a matrix $\mathfrak{M} \in \mathbb{F}_q^{l \times (N_{msg}-1) \cdot l}$ such that

$$(S_i + \sum_{j=1}^{o} \sum_{j_1=1}^{l} t_{ij,j_1}^{12} S_{j_1,j}) \begin{bmatrix} \mathfrak{J} \\ -\mathfrak{M} \end{bmatrix} = 0$$

where $\mathfrak{J} \in \mathbb{F}_q^{(N_{msg}-1) \cdot l \times (N_{msg}-1) \cdot l}$ is a non-singular matrix.

## 3.6 Discussion of previous scenarios

We remark that the scenarios described in Sections 3.3 and 3.4 are particular cases of related randomness attacks [24] because what the attacker accomplishes by injecting a permanent fault is force the signature algorithm to reuse the same sub-bitstrings within the $N_{bits}vl^2$ bitstring that represent the vinegar values $V_1, V_2, \dots, V_v$, even though these fixed sub-bitstrings are unknown to the attacker each time a valid signature is generated for a random message. Therefore, partially recovering the private linear map represented by $T$ is always possible by using the techniques presented in Sections 3.3 and 3.4, as long as the attacker finds any other means of fixing sub-bitstrings within the $N_{bits}vl^2$ bitstring and collects enough valid signatures generated using these fixed values.

Moreover, if the attacker might distinguish a bit at a fixed position of each $V_i$ during signature generation, then the attacker could leverage Algorithm 4 to recover $T$ after collecting a sufficient number of signatures. Indeed, define $\mathcal{J} := [v] \times [l]^2 \times [N_{bits}]$, $\mathcal{G}$ and $\mathcal{O}_I$ as shown by Algorithm 5. Suppose that the attacker is given access to the set $\mathcal{I} \leftarrow \mathcal{G}(\cdot)$ and the oracle $\mathcal{O}_I$.

This adversary can leverage his knowledge of $\mathcal{I}$, his access to $\mathcal{O}_I$ and Algorithm 4 to fully recover the private linear transformation $\mathcal{T}$ as follows.
<caption>**Algorithm 4 Partially Recovers $T^{12}$ from Fixed Bits**</caption>

1: **function recover_partial_T_F2(v, o, l, [S<sup>(1)</sup>, ..., S<sup>(Nmsg)</sup>])**
2: S ← getS(l)
3: dic ← {}
4: **for** i ← 1 **to** v **do**
5:     **for** r<sub>0</sub> ← 1 **to** l **do**
6:         **for** r<sub>1</sub> ← 1 **to** l **do**
7:             **for** b ← 1 **to** 4 **do**
8:                 **A** ← F<sub>2</sub><sup>(N<sub>msg</sub>-1)×4·ol</sup>
9:                 **Y** ← F<sub>2</sub><sup>(N<sub>msg</sub>-1)×1</sup>
10:             **for** ω ← 2 **to** N<sub>msg</sub> **do**
11:                 S<sub>i</sub><sup>(ω,1)</sup> ← S<sub>i</sub><sup>(1)</sup> - S<sub>i</sub><sup>(ω)</sup>
12:             **for** j ← 1 **to** o **do**
13:                 **for** j<sub>1</sub> ← 1 **to** l **do**
14:                     S<sub>v+j</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup> ← S<sub>v+j</sub><sup>j<sub>1</sub>-1</sup>(S<sub>v+j</sub><sup>(ω)</sup> - S<sub>v+j</sub><sup>(1)</sup>)
15:                 **if** b = 1 **then**
16:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+1</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,1)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
17:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+2</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,4)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
18:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+3</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,3)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
19:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+4</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,2)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
20:                 **else if** b = 2 **then**
21:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+1</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,2)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
22:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+2</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,4)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup> + S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,1)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
23:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+3</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,4)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup> + S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,3)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
24:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+4</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,3)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup> + S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,2)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
25:                 **else if** b = 3 **then**
26:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+1</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,3)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
27:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+2</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,2)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
28:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+3</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,1)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup> + S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,4)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
29:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+4</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,4)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup> + S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,3)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
30:                 **else**
31:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+1</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,4)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
32:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+2</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,3)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
33:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+3</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,2)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
34:                     **A**<sub>(ω-1),j·l+4·j<sub>1</sub>+4</sub> ← S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,4)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup> + S<sub>v+j,(r<sub>0</sub>,r<sub>1</sub>,1)</sub><sup>(j<sub>1</sub>,k<sub>1</sub>)</sup>
35:             **end if**
36:         **end for**
37:     **end for**
38:     **Y**<sub>(ω-1),0</sub> ← S<sub>i,(r<sub>0</sub>,r<sub>1</sub>,b)</sub><sup>(ω,1)</sup>
39:     **end for**
40:     **X**, output ← Gauss(**A**, **Y**)
41:     **if** output **then**
42:         [T<sub>i1</sub><sup>12</sup>, ..., T<sub>io</sub><sup>12</sup>] ← get_elements_in_FqS_from_bits(X, l)
43:         dic[(i, r<sub>0</sub>, r<sub>1</sub>, b)] ← [T<sub>i1</sub><sup>12</sup>, ..., T<sub>io</sub><sup>12</sup>]
44:     **else**
45:         dic[(i, r<sub>0</sub>, r<sub>1</sub>, b)] ← None
46:     **end if**
47:     **end for**
48:     **end for**
49:     **end for**
50:     **end for**
51:     **return** dic
52: **end function**
<caption>**Algorithm 5** defines functions $\mathcal{G}$ and $\mathcal{O}_I$.</caption>

1: **function** $\mathcal{G}()$
2: $\mathcal{I} \leftarrow \emptyset$
3: **for** $(i \leftarrow 1, i \le v, i \leftarrow i + 1)$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;$(r_0, r_1, b) \leftarrow \$ [l] \times [l] \times [N_{bits}]$
5: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{I} \leftarrow \mathcal{I} \cup \{(i, r_0, r_1, b)\}$
6: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
7: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\mathcal{I}$
8: **end function**

1: **function** $\mathcal{O}_I(\iota \in \mathcal{J}, b \in \mathbb{F}_2)$
2: **if** $\iota \in \mathcal{J} \setminus \mathcal{I}$ **then**
3: &nbsp;&nbsp;&nbsp;&nbsp;$c \leftarrow \$ \mathbb{F}_2$
4: &nbsp;&nbsp;&nbsp;&nbsp;**return** $c$
5: **end if**
6: **Let** $\mathcal{V}_\iota$ **be the random bit chosen by**
&nbsp;&nbsp;&nbsp;&nbsp;the line 13 of Algorithm 2 in the most
&nbsp;&nbsp;&nbsp;&nbsp;recent call.
7: **if** $b = \mathcal{V}_\iota$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;**return** 1
9: **end if**
10: **return** 0
11: **end function**

1. The attacker sets $S = []$, creates the lists $L_i = []$ and sets $b_i \leftarrow \$ \mathbb{F}_2$ for all $i \in \mathcal{I}$.

2. The attacker calls Algorithm 2 for the random message $M^{(j)}$, which outputs $(S^{(j)}, \text{salt}^{(j)})$, and then updates $S.append((S^{(j)}, \text{salt}^{(j)}))$. Additionally, the attacker updates its lists $L_i$ for all $i \in \mathcal{I}$ as follows.

(a) For each $i \in \mathcal{I}$, $L_i.append(\mathcal{O}_I(i, b_i))$.

3. After collecting sufficient signatures, $N_{msg}$, the attacker stops. In particular, once $\sum_{i=1}^{N_{msg}} L_i[i] > N_{bits} \cdot l \cdot o + 1$ for all $l \in \mathcal{I}$, it will stop.

4. The attacker then uses the collected signatures and calls Algorithm 4 $|\mathcal{I}|$ times to recover the matrix $T$.

(a) For each $i = (i, r_0, r_1, b) \in \mathcal{I}$, the attacker creates $S_i = [S[j]$ for $j \in [N_{msg}]$ if $L_i[j] = 1$] and calls Algorithm 4 with parameters $v, o, l$ and $S_i$. From Section 3.4, it follows each call of Algorithm 4 with parameters $v, o, l$ and $S_i$ will return $\text{dic}[l] = [T_{i1}^{12}, \dots, T_{io}^{12}]$.

We remark that the previous example scenario is yet another case of related randomness attacks, since the attacker at step 2a marks what signatures share the bit $b_i$ in $V_i$. However, we stress that we do not know how to instantiate this oracle $\mathcal{O}_I$ in a real scenario effectively, and therefore this question remains open.

## 3.7 Fault-assisted reconciliation attack

As seen in Section 2, for the reconciliation attack, the attacker must find a specific solution $\mathbf{u}_0 \in \mathbb{F}_q^{ln}$ from among many solutions to the quadratic system of the form

$$ \mathbf{u}_0^t(\Lambda_{S^i} P_k \Lambda_{S^j}) \mathbf{u}_0 = 0 \in \mathbb{F}_q, \qquad (12) $$

for $k \in [m]$, $i, j \in \{0, 1, \dots, l-1\}$. Furthermore, for any valid signature $(S, \text{salt})$, it holds $S = T^{-1}\mathbf{V}$, with $\mathbf{V} = (\mathbf{V}_1, \dots, \mathbf{V}_v, \mathbf{0}_1, \dots, \mathbf{0}_o)^t$ and $T^{-1} = T$. Consequently, for any $\beta \in [l]$, we have
$$ S_{\beta} = \begin{bmatrix} S_{1;\beta} \\ \vdots \\ S_{v;\beta} \\ \vdots \\ S_{n;\beta} \end{bmatrix} = \begin{bmatrix} 1 & 0 & \dots & 0 & T_{1,1}^{12} & \dots & T_{1,o}^{12} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 & T_{v,1}^{12} & \dots & T_{v,o}^{12} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & \dots & 0 & \dots & 1 \end{bmatrix} \begin{bmatrix} V_{1;\beta} \\ \vdots \\ V_{v;\beta} \\ O_{1;\beta} \\ \vdots \\ O_{o;\beta} \end{bmatrix} = \begin{bmatrix} V_{1;\beta} - \sum_{j=1}^{o} T_{1j}^{12} O_{j;\beta} \\ \vdots \\ V_{v;\beta} - \sum_{j=1}^{o} T_{vj}^{12} O_{j;\beta} \\ O_{1;\beta} \\ \vdots \\ O_{o;\beta} \end{bmatrix} $$

where $S_{\beta}$ denotes the $\beta$-th column of $S$. If an attacker knows $V_{1;\beta}, \dots, V_{v;\beta}$, then the attacker can set

$$ \mathbf{u}_0 = \begin{bmatrix} S_{1;\beta} - V_{1;\beta} \\ \vdots \\ S_{v;\beta} - V_{v;\beta} \\ \vdots \\ S_{n;\beta} \end{bmatrix}, $$

which will satisfy Eq. (12). Therefore, the main task of the attacker is to find $V_{1;\beta}, \dots, V_{v;\beta}$ for a valid signature $(S, \text{salt})$ and some $\beta \in [l]$.

## Attack strategy

1. The attacker introduces transient faults affecting line 13 of Algorithm 2, specifically targeting $V_{i,j\beta}$ for all $i \in [v]$, $j \in [l]$ and $\beta \in C \subseteq [l]$ independently. In particular, for the variable $V_i$, there is a fixed non-empty subset $J_i \subseteq [l] \times C$ such that $\bar{V}_{i,(r_0,r_1)} = \omega$ for $(r_0, r_1) \in J_i$, where $\omega \in F_q$ is some unknown and fixed value.

2. The attacker then calls Algorithm 2 with a randomly chosen message $M \in \mathcal{R}^m$ and receives the signature $(S, \text{salt})$.

3. If Step 2 succeeds, then call Algorithm 6 with parameters $v, o, l, S, C, \Gamma_{\beta}$ for $\beta \in C^1$, where $\Gamma_{\beta} \subseteq [lv]$. Furthermore, $F_{\gamma}$ denotes the set of all subsets of $\gamma$ integers that can be selected from $[lv]$ and $A^c = [lv] \setminus A$ with $A \in F_{\gamma}$.

We remark that by choosing proper $\Gamma_{\beta}$'s, the attacker can ensure that the quadratic systems to be solved at the line 9 of Algorithm 6 have $ol^2$ equations and $lv - \gamma < ol^2$ unknowns. Thus, they are expected to have either no solution or very few solutions.

Let $V = (V_1^t, \dots, V_v^t)^t \in F_q^{vl^2}$. If after carrying out Steps 1 and 2, there exists $\beta \in C$ such that $V_{i\beta} = \omega$, for $i \in A$, with $A \in F_{\gamma}$ and $\gamma \in \Gamma_{\beta}$, then Algorithm 6 will find an $U$ satisfying Eq. (12) and an secret space $\mathcal{O}$. Otherwise, the attacker may start the attack again. In Appendix B, we analyse Algorithm 6's runtime complexity.

<footnote n="1">¹ If $C$ is unknown, the attacker can always set $C = [l]$.</footnote>
**Algorithm 6** attempts to find $\mathcal{O}$ after having run the attack strategy.

1: function fault_assisted_reconciliation attack(v, o, l, S, C, $\Gamma_{\beta}$ for $\beta \in C$)

2: for $\beta \in C$ do

3: for $\gamma \in \Gamma_{\beta}$ do

4: for $A \in F_{\gamma}$ do

5: for $\omega \in \mathbb{F}_{q}$ do

6: Set $\Omega \leftarrow (x_{1}, \dots, x_{lv}, 0, \dots, 0)^{t} \in \mathbb{F}_{q}^{ln}$

7: Set $\Omega_{i} \leftarrow w$ for $i \in A$

8: X $\leftarrow S_{i\beta} - \Omega$

9: Attempt to solve the quadratic system

$$X^t(\Lambda_{S_i} P_k \Lambda_{S_j})X = 0 \in \mathbb{F}_q,$$

for $k \in [m], i, j \in \{0, 1, \dots, l-1\}$. This system has $ml^2$ equations and $lv - \gamma$ unknowns, namely $x_i$ for $i \in A^c$

10: if $x_i$ for $i \in A^c$ are found then

11: Set $U$ as the solution.

12: Recover $\mathcal{O}$ from the linearly independent set $\{\Lambda_{S_j} U : 0 \le j \le l-1\}$

13: return $\mathcal{O}$

14: end if

15: end for

16: end for

17: end for

18: end for

19: return $\perp$

*Success Probability of our Attack Strategy.* For $i \in [vl], j \in C$, let $X_{ij} \in \{0, 1\}$ be a Bernoulli random variable that indicates whether $V_{ij}$ is fixed to $\omega$ due to the corresponding transient fault. Let $Pr(X_{ij}) = p_{ij}$ be the probability that $X_{ij} = 1$, i.e., that $V_{ij}$ is fixed to $\omega$. Define $Y_{\beta} = \sum_{i=1}^{lv} X_{i\beta}$. The probability of obtaining $0 \le \gamma \le lv$ successful fixes out of a total of $lv$ in the $\beta$-th column of $V$ can be expressed as

$$Pr(Y_{\beta} = \gamma) = \sum_{A \in F_{\gamma}} \prod_{i \in A} p_{i\beta} \prod_{j \in A^{c}} (1 - p_{j\beta}).$$

Let $\rho_{\beta}$ be the probability there exists $\gamma \in \Gamma_{\beta}$ such that $Y_{\beta} = \gamma$. Therefore,

$$\rho_{\beta} = \sum_{\gamma \in \Gamma_{\beta}} \mathrm{Pr}(Y_{\beta} = \gamma).$$

Let $\rho$ denote the success probability of Algorithm 6, meaning there exists $\beta \in C$ such that $V_{i\beta} = \omega$, for $i \in A$, with $A \in F_{\gamma}$ and $\gamma \in \Gamma_{\beta}$. Therefore,

$$\rho = \mathrm{Pr}(Y_{\beta} = \gamma \text{ for some } \beta \in C \text{ with } A \in F_{\gamma} \text{ and } \gamma \in \Gamma_{\beta}) = \max\{p_{\beta} : \beta \in C\}.$$

Overall, a run of the attack strategy is successful with probability $\rho(1 - \delta)$, where $\delta$ is the failure probability of Step 2 of the attack strategy (i.e., when Algorithm 2 fails to return a signature after one iteration). Furthermore, if the
$p_{ij}$'s remain constant for each run of the attack strategy, the attacker is expected to execute the attack strategy $1/\rho(1 - \delta)$ times.

We note that Step 1 of this attack strategy can potentially be implemented by inducing a single transient fault, similar to the one found in the C implementation of Ke'accak used to generate the vinegar variables for MAYO [15]. For SNOVA, such a transient fault would target $V_{i\beta}$ for $i \in [lv]$, $\beta \in [l]$. Therefore, the attacker would need to run the attack strategy $1/(1 - \delta)$ times if $p_{i\beta} = 1$ for all $i$ and $\beta$. However, if the attacker only can ensure $\epsilon \le p_{i\beta} \le 1$ with $\epsilon \ge 0$, they can choose some $\Gamma_{\epsilon}$ for all $\beta \in [l]$, and hence

$$ (1-\delta) \sum_{\gamma \in \Gamma_{\epsilon}} \binom{lv}{\gamma} \epsilon^{\gamma} (1-\epsilon)^{lv-\gamma} \le (1-\delta) \max\{\rho_{\beta} = \sum_{\gamma \in \Gamma_{\epsilon}} \Pr(Y_{\beta} = \gamma) : \beta \in \mathcal{C}\} \le (1-\delta). $$

Moreover, the attacker might improve the attack strategy's success probability by inducing transient faults that specifically target $V_{i\beta}$ for all $i \in [lv]$, and $\beta \in \mathcal{C}$ with $|\mathcal{C}| = 1$. In such a case, $\delta$ is expected to be very low. Therefore, if the attacker only can ensure $\epsilon \le p_{i\beta} \le 1$ for a $\epsilon \ge 0$, they might set a proper $\Gamma_{\epsilon}$ such that $\sum_{\gamma \in \Gamma_{\beta}} \binom{lv}{\gamma} \epsilon^{\gamma} (1-\epsilon)^{lv-\gamma} \approx 1$, and expect to run the attack strategy<fnref n="2" /> only once. We analyze various scenarios in our simulations in Section 4.2.

## 3.8 Alternative Versions of SNOVA

The SNOVA team recently released a preprint [27] that proposes two new versions of SNOVA to counteract Buellen's attack [5].

The first alternative version of SNOVA is choose random matrices $A_{k,\alpha}$, $B_{k,\alpha} \in \mathcal{R}$ and $Q_{k,\alpha1}$, $Q_{k,\alpha2} \in \mathbb{F}_q[S]$, for $k \in [o]$ and $\alpha \in [l^2]$, and define the k-th coordinate of the public map $\mathcal{P}(U)$ as

$$ \mathcal{P}_k(U_1, \dots, U_n) = \sum_{\alpha=1}^{l^2} \sum_{i=1}^{n} \sum_{j=1}^{n} A_{k,\alpha} \cdot U_i^t(Q_{k,\alpha1}P_{k,i,j}Q_{k,\alpha2})U_j \cdot B_{k,\alpha}. $$

The second alternative version of SNOVA defines the k-th coordinate of the public map $\mathcal{P}(U)$ as follows

$$ \mathcal{P}_k(U) = \sum_{\alpha=1}^{l^4} \sum_{i=1}^{n} \sum_{j=1}^{n} A_{\alpha} \cdot U_i^t(Q_{\alpha1}P_{k,i,j}Q_{\alpha2})U_j \cdot B_{\alpha}, $$

where the matrices $A_{\alpha}$, $B_{\alpha} \in \mathcal{R}$, and $Q_{\alpha1}$, $Q_{\alpha2} \in \mathbb{F}_q[S]$, for $\alpha \in [l^4]$, are determined by fixed matrices $\tilde{E}_{i,j} \in \mathbb{F}_q^{l^2 \times l^2}$, for $i, j \in [l]$, specified in [27].

We remark that either alternative version is still vulnerable to our fault attacks described in Sections 3.3 and 3.4 since we exploit the related randomness present in the vinegar variables $V^{(\omega)} = (V_1^{(\omega)}, \dots, V_n^{(\omega)})^t$ when a permanent fault has been established and the relation $S^{(\omega)} = T^{-1}V^{(\omega)}$. Additionally, the proposed alternatives do not affect the reconciliation attack.

<footnote n="2">² The runtime of Algorithm 6 depends on $\Gamma_{\epsilon}$.</footnote>
# 4 Experiments of our fault attacks

To validate our claims, we conducted simulations of our fault attack and presented a step-by-step procedure for our tests along with their results. We begin by explaining the conceptual framework of the attack. We implement the SNOVA signature scheme in SAGE, adhering to its specification document [19]. This implementation serves as the foundation for our analysis. Additionally, we utilized the latest version of the SNOVA code provided by the SNOVA team<fnref n="3" /> to generate the signatures. In these simulations, we introduced faults by fixing specific values in the vinegar variables, thereby mimicking the fault injection process described in our attack model in Section 3.1.

## 4.1 Evaluating the fault attack from Sections 3.3 and 3.4

We evaluate our attack by considering two scenarios.

In *Scenario I*, we replace line 13 of Algorithm 2 with the function described in Algorithm 7. This function takes a set of SNOVA parameters, a binary string $x$ of size $l^2v$, and a list $L$ of the same size containing random field elements from $\mathbb{F}_{16}$. The binary string $x$ directs Algorithm 7 regarding which elements are to be drawn from $L$ and which are to be generated randomly. This approach ensures that each time the signature algorithm is executed, the same field elements in each $V_i$ remain fixed.

**Algorithm 7** simulates a fault by fixing $\mathbb{F}_{16}$ elements in the vinegar variables.

1: **function** assign_values_to_vinegar_variables_fault_F16(v, o, l, x, L)
2: V ← []
3: **for** (i ← 1, i ≤ v, i ← i + 1) **do**
4: Vᵢ ← [0]¹×l
5: **for** (r₀ ← 1, r₀ ≤ l, r₀ ← r₀ + 1) **do**
6: **for** (r₁ ← 1, r₁ ≤ l, r₁ ← r₁ + 1) **do**
7: **if** (xᵢ·l²+r₀·l+r₁ = 1) **then**
8: Vᵢ[r₀, r₁] ← Lᵢ·l²+r₀·l+r₁
9: **else**
10: Vᵢ[r₀, r₁] ← $\mathbb{F}_{16}$
11: **end if**
12: **end for**
13: **end for**
14: V.append(Vᵢ)
15: **end for**
16: **return** V

In *Scenario II*, we replace line 13 of Algorithm 2 with the function represented by Algorithm 8. This function takes a SNOVA parameter set, a binary string $x$

<footnote n="3">³ https://github.com/PQCLAB-SNOVA/SNOVA using commit 3d7e8c7cebdd57293d74dc6c2608656697b99597.</footnote>
of size $4l^2v$, and a list $L$ of size $4l^2v$ containing random field elements from $\mathbb{F}_2$. Similar to the previous scenario, Algorithm 8 guarantees that the same bits in the binary representation of each $V_i$ are fixed each time Algorithm 2 is executed.

**Algorithm 8** simulates a fault by fixing $\mathbb{F}_2$ elements in the vinegar variables.

1: **function assign_values_to_vinegar_variables_fault F2(v, o, l, x, L)**
2:   **V** ← []
3:   **for** (i ← 1, i ≤ v, i ← i + 1) **do**
4:     **V**<sub>i</sub> ← [0]<sup>l×l</sup>
5:     **for** (r<sub>0</sub> ← 1, r<sub>0</sub> ≤ l, r<sub>0</sub> ← r<sub>0</sub> + 1) **do**
6:     **for** (r<sub>1</sub> ← 1, r<sub>1</sub> ≤ l, r<sub>1</sub> ← r<sub>1</sub> + 1) **do**
7:     **e** ← [0]<sup>4</sup>
8:     **for** (r<sub>2</sub> ← 1, r<sub>2</sub> ≤ 4, r<sub>2</sub> ← r<sub>2</sub> + 1) **do**
9:     **if** (x<sub>i·l<sup>2</sup>+r<sub>0</sub>·l+4·r<sub>1</sub>+r<sub>2</sub></sub> = 1) **then**
10:      **e**[r<sub>2</sub>] ← L<sub>i·l<sup>2</sup>+r<sub>0</sub>·l+4·r<sub>1</sub>+r<sub>2</sub></sub>
11:      **else**
12:        **e**[r<sub>2</sub>] ← $\mathbb{F}_2$
13:      **end if**
14:    **end for**
15:  **V**<sub>i</sub>[r<sub>0</sub>, r<sub>1</sub>] ← **e**
16:  **end for**
17:  **end for**
18:  **V**.append(V<sub>i</sub>)
19:  **end for**
20:  **return** **V**

In summary, our *test experiments* run the following step-by-step procedure:

1. Select a SNOVA parameter set and then create a key pair (sk, pk) by calling Algorithm 1.

2. In either scenario, create the bitstring $x$ by performing either $l^2v$ or $4 \cdot l^2v$ Bernoulli trials given a probability $0 < \rho < 1$. Furthermore, create $L$ by generating a list of size $|x|$ of random field elements (from either $\mathbb{F}_{16}$ or $\mathbb{F}_2$).

3. Collect $N_{msg}$ signatures by calling the tweaked version of Algorithm 2. The value of $N_{msg}$ depends on the scenario we are running. For the scenario I, $N_{msg}$ is set to $o \cdot l + 2$, while, for the scenario II, $N_{msg}$ is set to $4 \cdot o \cdot l + 2$.

4. Once $N_{msg}$ signatures are collected, then call the corresponding recovery algorithm, i.e. either Algorithm 3 for Scenario I or Algorithm 4 for Scenario II.

5. Compare the recovered part of $T$ with the corresponding part of the real $T$ to verify the effectiveness of our recovery algorithms.

Our *experimental results* confirm that our recovery algorithms perform as expected. Specifically, when provided with the required number of faulty signatures, they successfully recover the correct components of $T$, as outlined in
Sections 3.3 and 3.4. Table 3 summarizes the minimum number of faulty signatures required for each SNOVA parameter set to guarantee the success of our recovery algorithms.

<table><caption>**Table 3.** Minimum number of signatures per SNOVA parameter set</caption><thead><tr><th>Security Level</th><th>(v, o, q, l, λ)</th><th>Recovery from fixed field elements by Algorithm 3</th><th>Recovery from fixed bits by Algorithm 4</th></tr></thead><tbody><tr><td rowspan="3">I</td><td>(37, 17, 16, 2, 128)</td><td>34</td><td>138</td></tr><tr><td>(25, 8, 16, 3, 128)</td><td>26</td><td>98</td></tr><tr><td>(24, 5, 16, 4, 128)</td><td>22</td><td>82</td></tr><tr><td rowspan="3">III</td><td>(56, 25, 16, 2, 192)</td><td>52</td><td>202</td></tr><tr><td>(49, 11, 16, 3, 192)</td><td>35</td><td>134</td></tr><tr><td>(37, 8, 16, 4, 192)</td><td>34</td><td>130</td></tr><tr><td rowspan="3">V</td><td>(75, 33, 16, 2, 256)</td><td>68</td><td>266</td></tr><tr><td>(66, 15, 16, 3, 256)</td><td>47</td><td>182</td></tr><tr><td>(60, 10, 16, 4, 256)</td><td>42</td><td>162</td></tr></tbody></table>

In addition to the SAGE implementation, we utilize the C version of the SNOVA code to evaluate our attack by generating faulty signatures. Specifically, we incorporate Algorithm 7 into the C code. The vinegar values are generated within the function `sign_digest_core_ref` found in the file `snova_kernel.h`. To generate these values, SNOVA uses Keccak, and in the reference implementation, the authors rely on the eXtended Keccak Code Package (XKCP)<fnref n="4" />. Listing 1.1 details the method for generating these values and demonstrates how they are assigned to the appropriate structure, a matrix variable named `X_IN_GF16MATRIX`.

```c
// generate the vinegar value
Keccak_HashInstance hashInstance;
Keccak_HashInitialize_SHAKE256(&hashInstance);
Keccak_HashUpdate(&hashInstance, pt_private_key_seed, 8 * seed_length_private);
Keccak_HashUpdate(&hashInstance, digest, 8 * bytes_digest);
Keccak_HashUpdate(&hashInstance, array salt, 8 * bytes salt);
Keccak_HashUpdate(&hashInstance, &num_sign, 8);
Keccak_HashFinal(&hashInstance, NULL);
Keccak_HashSqueeze(&hashInstance, vinegar_in_byte, 8 * ((v_SNOVA * lsq_SNOVA + 1) >> 1));

counter = 0;
for (int index = 0; index < v_SNOVA; index++) {
    for (int i = 0; i < rank; ++i) {
        for (int j = 0; j < rank; ++j) {
            set_gf16m(X_in_GF16Matrix[index], i, j,
                       ((counter & 1) ? (vinegar_in_byte(counter >> 1]
                                       >> 4) : (vinegar_in_byte(counter >> 1] & 0xF)));
            counter++;
```

<footnote n="4">⁴ https://github.com/XKCP/XKCP</footnote>
<figure><img src="image_2.png" /><figcaption>Listing 1.1. Code snippet of generation of vinegar values.</figcaption></figure>

To generate faulty signatures, we employ the `get_F16` function, which generates random field elements in $\mathbb{F}_{16}$ and creates a binomial random variable array, denoted as $x$. This array plays a crucial role in determining which entries in the matrix `X_IN_GF16MATRIX` will be assigned random values versus those that will be derived from the vinegar variables. As illustrated in Listing 1.2, we modify the variable `X_in_GF16Matrix` to incorporate these random values, replacing the original values obtained from the hash function. For more details about the implementation of the function `get_F16`, see Appendix A.

<figure><img src="image_3.png" /><figcaption>Listing 1.2. Code snippet for setting random values as Algorithm 6.</figcaption></figure>

Now, we use the faulty 'X_IN_GF16MATRIX' to generate the signature, where the matrix 'T12' is part of the private key. The process is shown in Listing 1.3. Specifically, the matrix 'T12' is multiplied with parts of the 'X_IN_GF16MATRIX', and the results are accumulated to form the final signature.

<figure><img src="image_4.png" /><figcaption>Listing 1.3. Usage of `X_IN_GF16MATRIX` to generate the final signature.</figcaption></figure>

As one expects, the results obtained from SAGE—when generating signatures and employing our recovery algorithms—are quite comparable to those produced
by the C code for generating faulty signatures, followed by the execution of recovery algorithms in SAGE. The C code and SAGE scripts are publicly accessible in this repository: https://github.com/gbanegas/fault_sim_snova.

## 4.2 Evaluating the fault-assisted reconciliation attack

Using our SAGE implementation and the C version, we also evaluated the fault attack described in Section 3.7.

Let $P$ be a matrix of size $v \times l \times l$, where the elements $P_{ijk}$ represent the probabilities $p_{i,j,k}$ as described in Section 3.7. We replace line 13 of Algorithm 2 with a function that takes a set of SNOVA parameters and the matrix $P$, randomly selects $\omega \in \mathbb{F}_q$ and returns the vinegar variables $V_i$, where each $V_{i,j,k}$ is equal to $\omega$ with probability $P_{ijk}$.

We conducted experiments, each consisting of 100 runs of SNOVA and our algorithms. In each trial, probabilities for $P_{i,j,k}$ are set, and the modified version of Algorithm 2 is run. A “failure” in Step 2 occurs if the modified algorithm cannot compute a signature after one iteration. A success in Algorithm 6 occurs if the secret space can be computed after Step 2 has completed successfully. Therefore, the success rate of Algorithm 6 is the number of successful computations divided by the number of trials, excluding those that failed in Step 2. Finally, the overall success rate of the attack strategy is the number of successes in Algorithm 6 divided by the total number of trials.

In our experiments we set $\epsilon \in \{1, 0.97, 0.95, 0.93\}$ and $\Gamma_{\epsilon,r} = \{\lfloor \mu+r\sigma \rfloor, \dots, \lfloor \mu-r\sigma \rfloor\}$, where $\mu = lv\epsilon$, $\sigma = \sqrt{lv\epsilon(1-\epsilon)}$ and $r \in \{1, 2\}$. Table 4 shows our results for different assignment for $P$ and the SNOVA parameter (37, 17, 16, 2, 128). Algorithm 6's runtime was computed by using Eq. (13) and the Cryptographic Estimators library [10].

<table><caption>**Table 4.** Table with the results of our experiments for the SNOVA parameter (37, 17, 16, 2, 128), where $C_{\beta} := \{(i, j, \beta) : i \in [v], j \in [l]\}$ for some $\beta \in [l]$.</caption><thead><tr><th rowspan="2">Assignments for P</th><th rowspan="2">Failure Rate Step 2</th><th colspan="2">Algorithm 6</th><th colspan="2">Attack Strategy</th><th colspan="2">Algorithm 6</th></tr><tr><th>Success Rate r = 1</th><th>Success Rate r = 2</th><th>Success Rate r = 1</th><th>Success Rate r = 2</th><th>Runtime (bits) r = 1</th><th>Runtime (bits) r = 2</th></tr></thead><tbody><tr><td>P<sub>i</sub> = 1 for i &isin; [v] &times; [l]<sup>2</sup></td><td>6%</td><td>100%</td><td>100%</td><td>94%</td><td>94%</td><td>6</td><td>7</td></tr><tr><td>0.97 &le; P<sub>i</sub> &le; 1 for i &isin; [v] &times; [l]<sup>2</sup></td><td>6%</td><td>44%</td><td>100%</td><td>41%</td><td>94%</td><td>42</td><td>52</td></tr><tr><td>0.95 &le; P<sub>i</sub> &le; 1 for i &isin; [v] &times; [l]<sup>2</sup></td><td>7%</td><td>33%</td><td>100%</td><td>31%</td><td>93%</td><td>52</td><td>60</td></tr><tr><td>0.93 &le; P<sub>i</sub> &le; 1 for i &isin; [v] &times; [l]<sup>2</sup></td><td>5%</td><td>19%</td><td>100%</td><td>18%</td><td>95%</td><td>60</td><td>67</td></tr><tr><td>P<sub>i</sub> = 1 for i &isin; C<sub>&beta;</sub></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>P<sub>i</sub> = 1/q for i &isin; [v] &times; [l]<sup>2</sup> &setminus; C<sub>&beta;</sub></td><td>2%</td><td>100%</td><td>100%</td><td>98%</td><td>98%</td><td>5</td><td>6</td></tr><tr><td>0.97 &le; P<sub>i</sub> &le; 1 for i &isin; C<sub>&beta;</sub></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>P<sub>i</sub> = 1/q for i &isin; [v] &times; [l]<sup>2</sup> &setminus; C<sub>&beta;</sub></td><td>8%</td><td>41%</td><td>100%</td><td>38%</td><td>92%</td><td>41</td><td>51</td></tr><tr><td>0.95 &le; P<sub>i</sub> &le; 1 for i &isin; C<sub>&beta;</sub></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>P<sub>i</sub> = 1/q for i &isin; [v] &times; [l]<sup>2</sup> &setminus; C<sub>&beta;</sub></td><td>5%</td><td>37%</td><td>100%</td><td>35%</td><td>95%</td><td>51</td><td>59</td></tr><tr><td>0.93 &le; P<sub>i</sub> &le; 1 for i &isin; C<sub>&beta;</sub></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>P<sub>i</sub> = 1/q for i &isin; [v] &times; [l]<sup>2</sup> &setminus; C<sub>&beta;</sub></td><td>4%</td><td>40%</td><td>93%</td><td>38%</td><td>89%</td><td>59</td><td>66</td></tr></tbody></table>
# 5 Countermeasure

In this section, we present a countermeasure for the fault attacks described in Section 3.

This countermeasure adapts a general strategy designed to defend against fault attacks targeting multivariate public key cryptosystems. This strategy was initially proposed in [12] and later extended and tailored for the UOV and Rainbow schemes in [17].

Specifically, Algorithm 9 implements this countermeasure for SNOVA and should be invoked by Algorithm 2 immediately after executing line 13.

Algorithm 9 accepts three positive integers, $\Gamma$ and $\Lambda$, with the condition that $\Gamma < \Lambda$, and $\Upsilon$, as well as a tuple of finite field elements $(\alpha_1, \dots, \alpha_{l^2v})$ of size $l^2v$. This tuple represents the SNOVA vinegar values $[V_1, V_2, \dots, V_v]$ generated at line 13 of Algorithm 2. Furthermore, the function *compare*, called by Algorithm 9 at line 14, takes two tuples of size $l^2v$: $(\alpha_1, \dots, \alpha_{l^2v})$ and $(\beta_1, \dots, \beta_{l^2v})$. It returns a tuple of size $l^2v$ where the j-th entry is 1 if $\alpha_j \neq \beta_j$ and 0 otherwise. Finally, the function *checkColumn* takes $(\alpha_1, \dots, \alpha_{l^2v})$, $x, \beta, \Upsilon$ and checks if there are at least $\Upsilon$ occurrences of $x$ in the sequence $V_{1,1\beta}, \dots, V_{1,l\beta}, \dots, V_{v,l\beta}$.

<caption>**Algorithm 9 Countermeasure by checking and storing vinegar values**</caption>

1: **function** countermesure($\Gamma, \Lambda, \Upsilon, (\alpha_1, \dots, \alpha_{l^2v})$)
2:   **for** $x \in F_q$ **do**
3:     **for** $\beta \in \{1, 2, \dots, l\}$ **do**
4:     **if** checkColumn((\alpha_1, \dots, \alpha_{l^2v}), x, $\beta, \Upsilon$) **then**
5:     **return** fail
6:   **end if**
7:   **end for**
8:   **end for**
9:   **if** L has not been created **then**
10:   L $\leftarrow$ []
11:   **end if**
12:   count $\leftarrow$ $[0]^{vl^2}$
13:   **for** ($i \leftarrow 0, i < |L|, i \leftarrow i + 1$) **do**
14:     count $\leftarrow$ count + compare(L[i], $(\alpha_1, \dots, \alpha_{l^2v})$)
15:   **end for**
16:   **if** count[j] > $\Gamma$ for some $j \in [l^2v]$ **then**
17:     **return** fail
18:   **end if**
19:   **if** $|L| = \Lambda$ **then**
20:     L.removeEntryAtIndex(0)
21:   **end if**
22:   L.append((\alpha_1, \dots, \alpha_{l^2v}))
23:   **return** success
Why does this countermeasure work? Let us assume that the countermeasure is already in place in the signing algorithm, with $\Lambda = l \cdot o$ and $\Gamma < \Lambda$.

We begin by analyzing the check performed between lines 1 and 8, which targets the attack strategy outlined in Section 3.7. Let $V = (V_1^t, \dots, V_v^t)^t$ and let $Z_\beta$ be the random variable that counts the number of occurrences of $x \in \mathbb{F}_q$ in the $\beta$-th column of $V$. $Z_\beta$ follows a binomial distribution with probability $p = 1/q$ in the absence of faults. Therefore, we have to take $\Upsilon$ such that $\Pr(Z_\beta \ge \Upsilon)$, the probability of checkColumn returning True at line 3, is negligible. For any current SNOVA parameters, $\Upsilon = [l \cdot v \cdot p + r\sqrt{l \cdot v \cdot p(1-p)}]$, where $r \ge 6$ is natural number.

On the one hand, if the step described in Section 3.7 successfully fixes at least $\Upsilon$ entries in the $\beta$-th column of $V$ to $x$, the function checkColumn will return True. On the other hand, if the faults fix at most $\Upsilon - 1$ entries in any column of $V$ to $x$, the corresponding checks will return False. In this case, the attacker can proceed with the attack strategy. However, running Algorithm 6 under these conditions would lead to a prohibitive runtime, as discussed in Appendix B.

We now examine the countermeasure against the attack strategy described in Section 3.3.

Assume that $|L| = \Lambda$, meaning the list maintained by Algorithm 9 has reached its maximum allowed size, and that the countermeasure function is called with parameters $\Gamma$, $\Lambda$, and $(\alpha_1, \dots, \alpha_{l^2 v})$.

Let $E$ denote the event where line 17 of Algorithm 9 returns fail in the absence of fault injection. For this event to occur, there must exist some $j \in [l^2 v]$ such that count[j] > $\Gamma$, meaning the tuple $(L[i][j])_{i=0}^{\Lambda-1}$ contains count[j] instances of $\alpha_j$. Let $X_j$ be the random variable that counts the number of occurrences of $\alpha_j$ in the tuple $(L[i][j])_{i=0}^{\Lambda-1}$. Each $X_j$ follows a binomial distribution with probability $p_j = \frac{1}{|\mathbb{F}_q|}$, and the variables are mutually independent. Therefore, the probability that Algorithm 9 reaches line 17 is

$$ 
\begin{aligned}
p_{\text{fail}} &= \Pr(X_j > \Gamma \text{ for some } j \in [l^2 v]) \\
&= 1 - \Pr(X_j \le \Gamma \text{ for all } j \in [l^2 v]).
\end{aligned}
$$

On the other hand, if an attacker introduces a permanent fault injection, as described in Section 3.3, the signing algorithm will abort after producing $\Gamma$ faulty signatures. In this case, the attacker could construct $v^2l$ linear systems (as in Eq. (9)), each consisting of $\Gamma - 1$ equations and $lo$ unknowns. Since $\Gamma - 1 < \Lambda = lo$, these linear systems are under-determined, meaning they have multiple solutions. Moreover, the attacker is unaware of which field elements, if any, from each vinegar variable $V_i$ are fixed by the permanent fault. In other words, out of the total $vl^2$ field elements representing a vinegar variable set, the attacker does not know the indices of the fixed elements or their values.

Let us consider the $j$-th linear system. To solve this system, the attacker could specialize $lo - \Gamma + 1$ variables (i.e., assign random values to $lo - \Gamma + 1$ variables) and then solve the resulting linear system with $\Gamma - 1$ equations and $\Gamma - 1$ unknowns. Consequently, the probability of finding the correct solution
for this particular system is approximately $p_j^{\Gamma - lo - 1}$. However, the attacker will not be able to verify whether a given solution is correct.

Therefore, $\Gamma$ must be chosen such that both $p_{\text{fail}}$ and the probability of successfully executing a key recovery attack via fault injection is negligible. Table 5 provides possible values for $\Gamma$ and $\Lambda$ corresponding to each SNOVA parameter set.

<table><caption>**Table 5.** Suggested values for $\Gamma$ and $\Lambda$.</caption><thead><tr><th>Security level</th><th>(v, o, q, l, λ)</th><th>Γ</th><th>Λ</th></tr></thead><tbody><tr><td rowspan="3">I</td><td>(37, 17, 16, 2, 128)</td><td>10</td><td>34</td></tr><tr><td>(25, 8, 16, 3, 128)</td><td>10</td><td>24</td></tr><tr><td>(24, 5, 16, 4, 128)</td><td>6</td><td>20</td></tr><tr><td rowspan="3">III</td><td>(56, 25, 16, 2, 192)</td><td>14</td><td>50</td></tr><tr><td>(49, 11, 16, 3, 192)</td><td>9</td><td>33</td></tr><tr><td>(37, 8, 16, 4, 192)</td><td>8</td><td>32</td></tr><tr><td rowspan="3">V</td><td>(75, 33, 16, 2, 256)</td><td>15</td><td>66</td></tr><tr><td>(66, 15, 16, 3, 256)</td><td>14</td><td>45</td></tr><tr><td>(60, 10, 16, 4, 256)</td><td>9</td><td>40</td></tr></tbody></table>

# 6 Conclusion

In this paper, we presented several fault attack strategies against the SNOVA cryptographic scheme. Initially, we proposed two methods of executing a fault attack, showing that our novel key recovery algorithm can recover the secret key with as few as 22 to 34 faulty signatures at the lowest security level, and up to 42 or 68 signatures at the highest level. Our experiments, implemented in both SAGE and C, demonstrated the efficiency of our algorithm under varying fault conditions.

In addition to these earlier methods, we introduced a new fault-assisted reconciliation attack in Section 3.7. This attack leverages induced transient faults to recover the secret key space by solving a quadratic system. The attack was evaluated using the lowest security parameter set for SNOVA, and the results indicated a high success rate under specific probability conditions for fault occurrence. Our experiments validated the feasibility of this attack, emphasizing its potential to weaken SNOVA's security when fault injections are possible.

To mitigate these vulnerabilities, we proposed a lightweight countermeasure that can effectively reduce the probability of successful key recovery without significantly impacting SNOVA's performance. This countermeasure is flexible and scalable, making it applicable across various SNOVA parameter sets.
Our findings underline the importance of robust fault-resistant implemen-
tations in post-quantum cryptographic schemes such as SNOVA. Future work
could focus on further optimizing the countermeasures and exploring the impact
of these attacks on other cryptographic systems.

References

1. Manuel Agoyan, Jean-Michel Dutertre, Philippe Hoogvorst, Emmanuel Jaulmes, Alfredo Tria, and Florent Valette. Efficient fault attacks on AES. In *IEEE Workhop on Fault Diagnosis and Tolerance in Cryptography*, pages 16–23. IEEE, 2010.

2. Tobias Aulbach and Florian König. Exploring the implementation security of the post-quantum signature scheme MAYO. In *Workshop on Fault Diagnosis and Tolerance in Cryptography - FDTC 2023*, pages 10–30, 2023.

3. Tobias Aulbach, Florian König, and Jürgen Kraämer. Recovering Rainbow's secret key with a first-order fault attack. In *Progress in Cryptology - AFRICACRYPT 2022*, pages 348–368, 2022.

4. Ward Beullens. MAYO: practical post-quantum signatures from oil-and-vinegar maps. In Riham AlTawy and Andreas Hülsing, editors, *Selected Areas in Cryptography - 28th International Conference, SAC 2021, Virtual Event, September 29 - October 1, 2021, Revised Selected Papers*, volume 13203 of *Lecture Notes in Computer Science*, pages 355–376. Springer, 2021.

5. Ward Beullens. Improved cryptanalysis of SNOVA. Cryptology ePrint Archive, Paper 2024/1297, 2024.

6. Ward Beullens, Fabio Campos, Sofía Celi, Basil Hess, and Matthias J. Kannwischer. MAYO, June 2023. Available at https://pqmayo.org/assets/specs/mayo.pdf.

7. Eli Biham and Adi Shamir. Differential fault analysis of secret key cryptosystems. *Advances in Cryptology—CRYPTO’97*, pages 513–525, 1997.

8. Jonathan F Buss, Gudmund S Frandsen, and Jeffrey O Shallit. The computational complexity of some problems of linear algebra. *Journal of Computer and System Sciences*, 58(3):572–596, 1999.

9. Daniel Cabarcas, Peigen Li, Javier Verbel, and Ricardo Villanueva-Polanco. Improved attacks for SNOVA by exploiting stability under a group action. Cryptology ePrint Archive, Paper 2024/1770, 2024.

10. Andre Esser, Javier A. Verbel, Floyd Zweydinger, and Emanuele Bellini. {CryptographicEstimators}: a software library for cryptographic hardness estimation. {IACR} Cryptol. ePrint Arch., page 589, 2023.

11. Hiroshi Furue, Yuichi Kiyomura, and Takashi Takagi. A new fault attack on uov multivariate signature scheme. In *Post-Quantum Cryptography - PQCrypto 2022*, pages 124–143, 2022.

12. Yasufumi Hashimoto, Tsuyoshi Takagi, and Kouichi Sakurai. General fault attacks on multivariate public key cryptosystems. In Bo-Yin Yang, editor, *Post-Quantum Cryptography*, pages 1–18, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.

13. Yoshinori Hashimoto, Tsuyoshi Takagi, and Kouichi Sakurai. General fault attacks on multivariate public key cryptosystems. *Post-Quantum Cryptography*, pages 1–18, 2011.

14. Yasuhiko Ikematsu and Rika Akiyama. Revisiting the security analysis of SNOVA. Cryptology ePrint Archive, Paper 2024/096, 2024. https://eprint.iacr.org/2024/096.
15. Sönke Jendral and Elena Dubrova. MAYO key recovery by fixing vinegar seeds. Cryptology ePrint Archive, Paper 2024/1550, 2024.

16. Yoongu Kim, Peter Daly, Jeremie Kim, Christopher Fallin, Ji Hye Lee, Donghyuk Lee, Chris Lusky, Justin Meza, and Onur Mutlu. Flipping bits in memory without accessing them: An experimental study of dram disturbance errors. *ACM SIGARCH Computer Architecture News*, 42(3):361–372, 2014.

17. Joachim Krämer and Maurus Loiero. Fault attacks on uov and rainbow. *Construc- tive Side-Channel Analysis and Secure Design*, pages 193–214, 2019.

18. Peigen Li and Jintai Ding. Cryptanalysis of the SNOVA signature scheme. Cryptol- ogy ePrint Archive, Paper 2024/110, 2024. https://eprint.iacr.org/2024/110.

19. Chun-Yen Chou Lih-Chung Wang, Jintai Ding, Yen-Liang Kuan, Ming-Siou Li, Bo-Shu Tseng, Po-En Tseng, and Chia-Chun Wang. Snova: Proposal for nist- pqc: Digital signature schemes project. Proposal for NISTPQC: Digital Signature Schemes project, 2023. https://snova.pqclab.org/.

20. Tsutomu Matsumoto and Hideki Imai. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In D. Barstow, W. Brauer, P. Brinch Hansen, D. Gries, D. Luckham, C. Moler, A. Pnueli, G. Seegmüller, J. Stoer, N. Wirth, and Christoph G. Günther, editors, *Advances in Cryptology — EUROCRYPT '88*, pages 419–453, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg.

21. Kaan Mus, Seungwon Shin, and Berk Sunar. Quantumhammer: A practical hybrid attack on the luov signature scheme. In *ACM SIGSAC Conference on Computer and Communications Security*, pages 1071–1084, 2020.

22. Shuhei Nakamura, Yusuke Tani, and Hiroki Furue. Lifting approach against the SNOVA scheme. Cryptology ePrint Archive, Paper 2024/1374, 2024.

23. Jacques Patarin. Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt'88. In Don Coppersmith, editor, *Advances in Cryptology - CRYPTO '95, 15th Annual International Cryptology Conference, Santa Barbara, California, USA, August 27-31, 1995, Proceedings*, volume 963 of *Lecture Notes in Computer Science*, pages 248–261. Springer, 1995.

24. Kenneth G. Paterson, Jacob C. N. Schuldt, and Dale L. Sibborn. Related randomness attacks for public key encryption. Cryptology ePrint Archive, Paper 2014/337, 2014. https://eprint.iacr.org/2014/337.

25. Anis Sayari, Denis Butin, and Thomas Fuhr. Practical fault injection attacks on multivariate signature schemes. In *Constructive Side-Channel Analysis and Secure Design - COSADE 2021*, pages 101–121, 2021.

26. Ki Shim and Bum Kyu Koo. Full key recovery on uov with fault injection. *ICISC 2009*, pages 123–140, 2009.

27. Lih-Chung Wang, Chun-Yen Chou, Jintai Ding, Yen-Liang Kuan, Jan Adriaan Leegwater, Ming-Siou Li, Bo-Shu Tseng, Po-En Tseng, and Chia-Chun Wang. A note on the SNOVA security. Cryptology ePrint Archive, Paper 2024/1517, 2024.

28. Lih-Chung Wang, Po-En Tseng, Yen-Liang Kuan, and Chun-Yen Chou. A simple noncommutative uov scheme. Cryptology ePrint Archive, Paper 2022/1742, 2022. https://eprint.iacr.org/2022/1742.

A Implementation details

1. // Function to generate random field element

2. uint8_t random_field element() {
```c
        return rand() % 16; // Adjust based on field size (for GF(2^k), mod appropriately)
    }

    // Function to generate binomial random variable (Bernoulli trial)
    uint8_t binomial帅trials(double prob) {
        double r = (double)rand() / RAND_MAX;
        return r < prob ? 1 : 0;
    }

    // Function equivalent to get_F16
    void get_F16(int v, int o, int l, uint8_t *I, uint8_t *x, double prob) {
        int size = v * l * l;
        // Generate I array with random field elements
        for (int i = 0; i < size; i++) {
            I[i] = random_fieldElement();
        }
        // Generate x array with binomial random variables
        for (int i = 0; i < size; i++) {
            x[i] = binomial帅trials(prob);
        }
    }
```

<caption>Listing 1.4. Generate random elements of $\mathbb{F}_{16}$.</caption>

## B Algorithm 6's runtime complexity

Given a homogeneous multivariate quadratic map $\mathcal{P} : \mathbb{F}_q^N \to \mathbb{F}_q^M$, we denote $\text{MQ}(N, M, q)$ the field multiplications required to find a non-trivial solution $u$ satisfying $\mathcal{P}(u) = a \in \mathbb{F}_q^M$ if such solution exists. The runtime complexity of Algorithm 6 is bounded by

$$ \mathcal{O}(q \sum_{\beta \in \mathcal{C}} \sum_{\gamma \in \Gamma_{\beta}} \binom{\lambda v}{\gamma} \cdot \text{MQ}(\lambda v - \gamma, ml^2, q)) \quad (13) $$

field multiplications.