Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Cryptanalysis of rank-2 module-LIP: a single real embedding is all it takes
Get PDFThe rank- module-LIP problem was introduced in cryptography by (Ducas, Postlethwaite, Pulles, van Woerden, Asiacrypt 2022), to construct the highly performant HAWK scheme. A first cryptanalytic work by (Mureau, Pellet--Mary, Pliatsok, Wallet, Eurocrypt 2024) showed a heuristic polynomial time attack against the rank- module-LIP problem over totally real number fields. While mathematically interesting, this attack focuses on number fields that are not relevant for cryptography. The main families of fields used in cryptography are the highly predominant cyclotomic fields (used for instance in the HAWK scheme), as well as the NTRU Prime fields, used for instance in the eponymous NTRU Prime scheme (Bernstein, Chuengsatiansup, Lange, van Vredendaal, SAC 2017).
In this work, we generalize the attack of Mureau et al. against rank- module-LIP to the family of all number fields with at least one real embedding, which contains the NTRU Prime fields. We present three variants of our attack, firstly a heuristic one that runs in quantum polynomial time. Secondly, under the extra assumption that the defining polynomial of has a -transitive Galois group (which is the case for the NTRU Prime fields), we give a provable attack that runs in quantum polynomial time. And thirdly, with the same -transitivity assumption we give a heuristic attack that runs in classical polynomial time. For the latter we use a generalization of the Gentry--Szydlo algorithm to any number field which might be of independent interest
Finding and Protecting the Weakest Link - On Side-Channel Attacks on y in Masked ML-DSA
Get PDFNIST standardized ML-KEM and ML-DSA as post-quantum key exchanges and digital signatures. Both schemes have already seen analysis with respect to side-channels, and first fully masked implementations of ML-DSA have been published. Previous attacks focused on unprotected implementations or assumed only hiding countermeasures to be in-place. Thus, in contrast to ML-KEM, the threat of side-channel attacks for protected ML-DSA implementations is mostly unclear.
In this work, we analyze the side-channel vulnerability of masked ML-DSA implementations. We first systematically assess the vulnerability of several potential points of attacks in different leakage models using information theory. Then, we explain how an adversary could launch first, second, and higher-order attacks using a recently presented framework for side-channel information in lattice-based schemes. In this context, we propose a filtering technique that allows the framework to solve for the secret key from a large number of hints; this had previously been prevented by numerical instabilities. We simulate the presented attacks and discuss the relation to the information-theoretic analysis.
Finally, we carry out relevant attacks on physical devices, discuss recent masked implementations, and instantiate a countermeasure against the most threatening attacks. The countermeasure mitigates the attacks with the highest noise-tolerance while having very little overhead. The results on the physical devices validate our simulations
Authentication and sole control at a high level of assurance on widespread smartphones with threshold signatures
Get PDFHow to be assured that a user entered their PIN on their smartphone? The question is especially relevant when deploying remotely secured services such as with mobile wallets for digital identity and banking, which typically deploy a server side backed by a hardware security module (HSM). As long as the server can be trusted, authentication can be performed with high assurance, but it is challenging to guarantee sole control. This report defines an approach in terms of an abstract security problem and a concrete solution based on threshold signatures. It can be applied to use cases such as HSM-backed mobile identity wallets and other identification means
Tighter Security Notions for a Modular Approach to Private Circuits
Get PDFTo counteract side-channel attacks, a masking scheme splits each intermediate variable into shares and transforms each elementary operation (e.g., field addition and multiplication) to the masked correspondence called gadget, such that intrinsic noise in the leakages renders secret recovery infeasible in practice. A simple and efficient security notion is the probing model ensuring that any shares are independently distributed from the secret input. One requirement of the probing model is the noise in the leakages should increase with the number of shares, largely restricting the side-channel security in the low-noise scenario. Another security notion for masking, called the random probing model, allows each variable to leak with a probability . While this model reflects the physical reality of side channels much better, it brings significant overhead. At Crypto 2018, Ananth et al. proposed a modular approach that can provide random probing security for any security level by expanding small base gadgets with share recursively, such that the tolerable leakage probability decreases with while the security increases exponentially with the recursion depth of expansion. Then, Belaïd et al. provided a formal security definition called Random Probing Expandability (RPE) and an explicit framework using the modular approach to construct masking schemes at Crypto 2020.
In this paper, we investigate how to tighten the RPE definition via allowing the dependent failure probabilities of multiple inputs, which results in a new definition called related RPE. It can be directly used for the expansion of multiplication gates and reduce the complexity of the base multiplication gadget from proposed at Asiacrypt 2021 to and maintain the same security level. Furthermore, we describe a method to expand any gates (rather than only multiplication) with the related RPE gadgets.
Besides, we denote another new RPE definition called Multiple inputs RPE used for the expansion of multiple-input gates composed with any gates. Utilizing these methods, we reduce the complexity of 3-share circuit compiler to , where is the size of the unprotected circuit and the protection failure probability of the global circuit is . In comparison, the complexity of the state-of-the-art work, proposed at Eurocrypt 2021, is for the same value of . Additionally, we provide the construction of a 5-share circuit compiler with a complexity
On the Power of Polynomial Preprocessing: Proving Computations in Sublinear Time, and More
Get PDFCryptographic proof systems enable a verifier to be convinced of a computation\u27s correctness without re-executing it; common efficiency requirements include both succinct proofs and fast verification. In this work we put forth the general study of cryptographic proof systems with \textit{sublinear} proving time (after a preprocessing).
Prior work has achieved sublinear proving only for limited computational settings (e.g., vector commitments and lookup arguments), relying on specific assumptions or through non-black-box use of cryptographic primitives. In this work we lift many of these limitations through the systematic study of a specific object: polynomial commitments (PC) with sublinear proving time, a choice motivated by the crucial role that PC play in the design of efficient cryptographic schemes.
We show a simple construction of a PC with sublinear prover based on any vector commitment scheme (VC) and any preprocessing technique for fast polynomial evaluation. We prove that this PC satisfies \emph{evaluation binding}, which is the standard security notion for PC, and show how to expand our construction to achieve the stronger notion of knowledge soundness (extractability).
Next, we study applications of PCs with sublinear prover. The first one is to construct \emph{index-efficient} SNARKs, that are SNARKs where the prover is sublinear, after preprocessing, in the size of the index (i.e., the NP-relation describing the proven statement). We propose a method to transform a class of standard Polynomial Interactive Oracle Proofs (PIOPs) into index-efficient PIOPs, obtaining two results that advance the state of the art: the first lookup argument for unstructured tables in which the prover is sublinear in the size of the table, while making only black-box use of a VC and thus allowing instantiations from generic assumptions such as collision-resistant hash functions, and the first transparent SNARK for circuits where the prover is sublinear in the number of addition gates.
Finally, our last application is a transformation that builds \emph{UC-secure} SNARKs from simulation-extractable ones, with an approximately linear overhead in proving time (as opposed to quadratic in prior work)
NoIC: PAKE from KEM without Ideal Ciphers
Get PDFWe show a generic compiler from KEM to (Universally Composable) PAKE in the Random Oracle Model (ROM) and without requiring an Ideal Cipher. The compiler is akin to Encrypted Key Exchange (EKE) by Bellovin-Merritt, but following the work of McQuoid et al. it uses only a 2-round Feistel to password-encrypt a KEM public key. The resulting PAKE incurs only insignificant cost overhead over the underlying KEM, and it is a secure UC PAKE if KEM is secure and key-anonymous under the Plaintext-Checking Attack (PCA).
Several KEM-to-PAKE compilers were shown recently, secure under the OW-PCA and ANO-PCA assumptions on KEM, but all used an Ideal Cipher in addition to ROM. While there are techniques for emulating ROM against quantum attackers, it is currently unknown how to extend many of such techniques to the Ideal Cipher Model. Consequently, doing without the Ideal Cipher in protocol design makes the resulting construction a more plausible candidate for post-quantum secure PAKE if instantiated with post-quantum PCA-secure and anonymous KEM, such as the ML-KEM standard itself.
Our construction and proofs build on many of the ideas underlying the KEM-to-PAKE compiler using 2-round Feistel given by McQuoid et al, but our protocol is more efficient and our proofs address limitations in the analysis therein
Rejected Signatures\u27 Challenges Pose New Challenges: Key Recovery of CRYSTALS-Dilithium via Side-Channel Attacks
Get PDFRejection sampling is a crucial security mechanism in lattice-based signature schemes that follow the Fiat-Shamir with aborts paradigm, such as ML-DSA/CRYSTALS-Dilithium. This technique transforms secret-dependent signature samples into ones that are statistically close to a secret-independent distribution (in the random oracle model). While many side-channel attacks have directly targeted sensitive data such as nonces, secret keys, and decomposed commitments, fewer studies have explored the potential leakage associated with rejection sampling. Notably, at HOST 2021, Karabulut \etal showed that leakage from rejected signatures\u27 challenges can undermine, but not entirely break, the security of the Dilithium scheme.
Motivated by the above, we convert the problem of key recovery (from the leakage of rejection sampling) to an integer linear programming problem (ILP), where rejected responses of unique Hamming weights set upper/lower constraints of the product between the challenge and the private key. We formally study the worst-case complexity of the problem as well as empirically confirm the practicality of the rejected signature\u27s challenge attack. For all three security levels of Dilithium-2/3/5, our attack recovers the private key in seconds or minutes with a 100\% Success Rate (SR).
Our attack leverages knowledge of the rejected signature\u27s challenge and response, and thus we propose methods to extract this information by exploiting single-trace side-channel leakage from Number Theoretic Transform (NTT) operations and functions associated with the response generation procedure. We demonstrate the practicality of this rejected signature\u27s challenge attack by using real power consumption on an ARM Cortex-M4 microcontroller. To the best of our knowledge, it is the first practical and efficient side-channel key recovery attack on ML-DSA/Dilithium that targets the rejection sampling procedure. Furthermore, we discuss some countermeasures to mitigate this security issue
On the Average Random Probing Model
Get PDFMasking is one of the main countermeasures against side-channel analysis
since it relies on provable security. In this context, “provable” means that a security
bound can be exhibited for the masked implementation through a theoretical analysis
in a given threat model. The main goal in this line of research is therefore to provide
the tightest security bound, in the most realistic model, in the most generic way.
Yet, all of these objectives cannot be reached together. That is why the masking
literature has introduced a large spectrum of threat models and reductions between
them, depending on the desired trade-off with respect to these three goals. In this
paper, we focus on three threat models, namely the noisy-leakage model (realistic
yet hard to work with), the random probing (unrealistic yet easy to work with), and
more particularly a third intermediate model called average random probing. Average
random probing has been introduced by Dziembowski et al. at Eurocrypt 2015, in
order to exhibit a tight reduction between noisy-leakage and random probing models,
recently proven by Brian et al. at Eurocrypt 2024. This milestone has strong
practical consequences, since otherwise the reduction from the noisy leakage model
to the random probing model introduces a prohibitively high constant factor in the
security bound, preventing security evaluators to use it in practice. However, we
exhibit a gap between the average random probing definitions of Dziembowski et al.
(denoted hereafter by DFS-ARP) and Brian et al. (simply denoted by ARP). Whereas
any noisy leakage can be tightly reduced to DFS-ARP, we show in this paper that
it cannot be tightly reduced to ARP, unless requiring extra assumptions, e.g., if the
noisy leakage is deterministic. Our proof techniques do not involve more tools than
the one used so far in such reductions, namely basic probability facts, and known
properties of the total variation distance. As a consequence, the reduction from the
noisy leakage to the random probing — without high constant factor — remains
unproven. This stresses the need to clarify the practical relevance of analyzing the
security of masking in the random probing model since most of the current efforts
towards improving the constructions and their security proofs in the random probing
model might be hindered by potentially unavoidable loss in the reduction from more
realistic but currently less investigated leakage models
Probing Secure Composability Without Fresh Randomness: Theory and Application to Ascon
Get PDFSide-channel attacks (SCAs) pose a significant threat to the implementations of lightweight ciphers, particularly in resource-constrained environments where masking—the primary countermeasure—is constrained by tight resource limitations. This makes it crucial to reduce the resource and randomness requirements of masking schemes. In this work, we investigate an approach to minimize the randomness
complexity of masking algorithms. Specifically, we explore the theoretical foundations of higher-order masking schemes that eliminate the need for online (fresh) randomness by relying solely on offline randomness present in the initial input shares.
We demonstrate that round-based ciphers with linear diffusion layers can support such deterministic composition, where the diffusion layer acts as a refresh subcircuit. This ensures that, up to a threshold number, probes placed across rounds remain independent. Based on this observation, we propose composition theorems for probing-secure masking. On the practical side, we instantiate our framework using known deterministic first- and second-order masked S-boxes and provide software
implementations of Ascon’s protected permutation
Improved Differential and Linear Cryptanalysis on Round-Reduced SIMON
Get PDFSIMON is a lightweight block cipher proposed by the National Security Agency.
According to previous cryptanalytic results on SIMON, differential and linear cryptanalysis are the two most effective attacks on it.
Usually, there are many trails sharing the same input and output differences (resp. masks).
These trails comprise the differential (resp. linear hull) and can be used together when mounting attacks.
In ASIACRYPT 2021, Leurent et al. proposed a matrix-based method on SIMON-like ciphers, where only trails whose active bits stay in a -bit window are considered.
The static window in each round is chosen to be least significant bits.
They applied this efficient framework on SIMON and SIMECK, and have obtained many better differentials and linear hulls than before. For SIMON, they also found that there seems to be some potential for improvement, which should be further investigated.
In this paper, we dynamically choose window for each round to achieve better distinguishers. Benefiting from these dynamic windows, we can obtain stronger differentials and linear hulls than previously proposed for almost all versions of SIMON.
Finally, we provided the best differential/linear attacks on SIMON48, SIMON64, and SIMON96 in terms of round number, complexity, or success rate