Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Audience Injection Attacks: A New Class of Attacks on Web-Based Authorization and Authentication Standards
Full text linkWe introduce audience injection attacks, a novel class of vulnerabilities that impact widely used Web-based authentication and authorization protocols, including OAuth 2.0, OpenID Connect, FAPI, CIBA, the Device Authorization Grant, and various well-established extensions, such as Pushed Authorization Requests, Token Revocation, Token Introspection, and their numerous combinations.
These protocols underpin services for billions of users across diverse ecosystems worldwide, spanning low-risk applications like social logins to high-risk domains such as open banking, insurance, and healthcare.
Audience injection attacks exploit a critical weakness in a core security mechanism of these protocols - the handling of so-called audiences in signature-based client authentication mechanisms. This vulnerability allows attackers to compromise fundamental security objectives whenever these mechanisms are utilized across two or more server endpoints. They enable the attacker to impersonate users and gain unauthorized access to their resources, even in high-security protocol families specifically designed for sensitive applications.
We responsibly disclosed these vulnerabilities to the relevant standardization bodies, which recognized their severity.
In collaboration with these organizations, we developed fixes and supported a coordinated response, leading to an ongoing effort to update a dozen of standards, numerous major implementations, and far-reaching ecosystems
Improving the Masked Division for the FALCON Signature
Full text linkFALCON is a post-quantum signature selected by the National Institute of Standards and Technology (NIST). Although its side-channel resilience has been studied and a masking countermeasure proposed, the division is a major performance bottleneck. This work proposes a different approach to the masked FALCON division. We use the Newton-Raphson method and a convergent sequence to approximate this operation. The first term of the sequence is evaluated using pre-calculated second-order minimax polynomials. As a consequence, computing the inverse only requires 5 masked additions and 8 masked multiplications, compared to the roughly 55 masked additions required by the previous state-of-the-art. Formal security proofs using the MIMO-SNI criteria are also provided
Insecurity of One Decentralized Attribute-based Signature Scheme for Social Co-governance
Full text linkWe show that the attribute-based signature scheme [Information Sciences, 654(2024), 119839] is insecure, because an adversary can generate valid signatures for any message even though he cannot access the signer\u27s secret key. The four components of signature are not tightly bound to the target message and the signer\u27s public key. The dependency between the signer\u27s public key and secret key is not properly used to construct any intractable problem. The inherent flaw results in that the adversary can find an efficient signing algorithm functionally equivalent to the valid signing algorithm
Lifeboats on the Titanic Cryptography
Full text linkThe Titanic was the ship that could not sink, fortunately its designers installed lifeboats (not enough) despite having no logical grounding for this waste of space and material. It was out of respect for unforeseen surprises. NIST-Post Quantum Ciphers represent the best and the brightest in world crypto intelligence. They are certified as good for their purpose. And likely so, alas, not surely so. If we could find a crypto equivalent for the Titanic Lifeboats, should not we load them up for our journey? Indeed, pattern-devoid cryptography is the crypto equivalent of the lifeboats that mitigated the Titanic disaster. Pattern-Devoid cryptography (PDC) may be deemed inelegant, inconvenient, and bloated, but it will hold up against quantum computers more powerful than expected, and more importantly, it will hold up against adversarial mathematical talent greater than expected. Which is why we should put up with its negatives, and install it just in case the Titanic story repeats itself in cyberspace. This article elaborates on this proposition
Solving Data Availability Limitations in Client-Side Validation with UTxO Binding
Full text linkIssuing tokens on Bitcoin remains a highly sought-after goal, driven by its market dominance and robust security. However, Bitcoin\u27s limited on-chain storage and functionality pose significant challenges. Among the various approaches to token issuance on Bitcoin, client-side validation (CSV) has emerged as a prominent solution. CSV delegates data storage and functionalities beyond Bitcoin’s native capabilities to off-chain clients, while leveraging the blockchain to validate tokens and prevent double-spending. Nevertheless, these protocols require participants to maintain token ownership and transactional data, rendering them vulnerable to data loss and malicious data withholding. In this paper, we propose UTxO binding, a novel framework that achieves both robust data availability and enhanced functionality compared to existing CSV designs. This approach securely binds a Bitcoin UTxO, which prevents double-spending, to a UTxO on an auxiliary blockchain, providing data storage and programmability. We formally prove its security and implement our design using Nervos CKB as the auxiliary blockchain
Attacking soundness for an optimization of the Gemini Polynomial Commitment Scheme
Full text linkWe demonstrate an attack on the soundness of a widely
known optimization of the Gemini multilinear Polynomial Commitment
Scheme (PCS). The attack allows a malicious prover to falsely claim that
a multilinear polynomial takes a value of their choice, for any input point.
We stress that the original Gemini multilinear PCS and HyperKZG, an
adaptation of Gemini, are not affected by the attack
Efficient Proofs of Possession for Legacy Signatures
Full text linkDigital signatures underpin identity, authenticity, and trust in modern computer systems. Cryptography research has shown that it is possible to prove possession of a valid message and signature for some public key, without revealing the message or signature. These proofs of possession work only for specially-designed signature schemes. Though these proofs of possession have many useful applications to improving security, privacy, and anonymity, they are not currently usable for widely deployed, legacy signature schemes such as RSA, ECDSA, and Ed25519. Unlocking practical proofs of possession for these legacy signature schemes requires closing a huge efficiency gap.
This work brings proofs of possession for legacy signature schemes very close to practicality. Our design strategy is to encode the signature\u27s verification algorithm as a rank-one constraint system (R1CS), then use a zkSNARK to prove knowledge of a solution. To do this efficiently we (1) design and analyze a new zkSNARK called Dorian that supports randomized computations, (2) introduce several new techniques for encoding hashes, elliptic curve operations, and modular arithmetic, (3) give a new approach that allows performing the most expensive parts of ECDSA and Ed25519 verifications outside R1CS, and (4) generate a novel elliptic curve that allows expressing Ed25519 curve operations very efficiently. Our techniques reduce R1CS sizes by up to 200 and prover times by 3-22.
We can generate a 240-byte proof of possession of an RSA signature over a message the size of a typical TLS certificate (two kilobytes) in only three seconds
Plonkify: R1CS-to-Plonk transpiler
Full text linkRank-1 Constraint Systems (R1CS) and Plonk constraint systems are two commonly used circuit formats for zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs). We present Plonkify, a tool that converts a circuit in an R1CS arithmetization to Plonk, with support for both vanilla gates and custom gates. Our tool is able to convert an R1CS circuit (compiled from the Circom circuit description language) with 250,938 constraints to a vanilla Plonk circuit with 589,829 constraints, or a jellyfish turbo Plonk circuit with 370,086 constraints. This represents a and reduction in the number of constraints over the respective naïve conversions.
Further, we make several optimizations to the Circom compiler in order to minimize the number of non-zero elements in the generated R1CS circuits, and to facilitate conversion to Plonks. When recompiled with our optimized version of Circom, the aforementioned circuit sees a 49% reduction in the number of non-zero elements, with only a 0.4% increase in the number of constraints. The same circuit can now be represented in just 422,610 vanilla Plonk constraints, or 312,163 high-degree ones
Masking-Friendly Post-Quantum Signatures in the Threshold-Computation-in-the-Head Framework
Full text linkSide-channel attacks pose significant threats to cryptographic implementations, which require the inclusion of countermeasures to mitigate these attacks. In this work, we study the masking of state-of-the-art post-quantum signatures based on the MPC-in-the-head paradigm. More precisely, we focus on the recent threshold-computation-in-the-head (TCitH) framework that applies to some NIST candidates of the post-quantum standardization process. We first provide an analysis of side-channel attack paths in the signature algorithms based on the TCitH framework. We then explain how to apply standard masking to achieve a -probing secure implementation of such schemes, with performance scaling in , for the masking order.
Our main contribution is to introduce different ways to tweak those signature schemes towards their masking friendliness. While the TCitH framework comes in two variants, the GGM variant and the Merkle tree variant, we introduce a specific tweak for each of these variants. These tweaks allow us to achieve complexities of and at the cost of non-constant signature size, caused by the inclusion of additional seeds in the signature. We also propose a third tweak that takes advantage of the threshold secret sharing used in TCitH. With the right choice of parameters, we show how, by design, some parts of the TCitH algorithms satisfy probing security without additional countermeasures. While this approach can substantially reduce the cost of masking in some part of the signature algorithm, it degrades the soundness of the core zero-knowledge proof, hence slightly increasing the size of the signature.
We analyze the complexity of the masked implementations of our tweaked TCitH signatures and provide benchmarks on a RISC-V platform with built-in hash accelerator. We use a modular benchmarking approach, allowing to estimate the performance of diverse signature instances with different tweaks and parameters. Our results illustrate how the different variants scale for an increasing masking order. For instance, for a masking order , we obtain signatures of around kB that run in second on a the target RISC-V CPU with a MHz frequency. This is to be compared with the seconds required by the original signature scheme masked at the same order on the same platform. For a masking order , we obtain a signature of kB running in second, to be compared with seconds for the stardard masked signature.
Finally, we discuss the extension of our techniques to signature schemes based on the VOLE-in-the-Head framework, which shares similarities with the GGM variant of TCitH. One key takeaway of our work is that the Merkle tree variant of TCitH is inherently more amenable to efficient masking than frameworks based on GGM trees, such as TCitH-GGM or VOLE-in-the-Head
On Extractability of the KZG Family of Polynomial Commitment Schemes
Full text linkWe present a unifying framework for proving the knowledge-soundness of KZG-like polynomial commitment schemes, encompassing both univariate and multivariate variants. By conceptualizing the proof technique of Lipmaa, Parisella, and Siim for the univariate KZG scheme (EUROCRYPT 2024), we present tools and falsifiable hardness assumptions that permit black-box extraction of the multivariate KZG scheme. Central to our approach is the notion of a canonical Proof-of-Knowledge of a Polynomial (PoKoP) of a polynomial commitment scheme, which we use to capture the extractability notion required in constructions of practical zk-SNARKs. We further present an explicit polynomial decomposition lemma for multivariate polynomials, enabling a more direct analysis of interpolating extractors and bridging the gap between univariate and multivariate commitments. Our results provide the first standard-model proofs of extractability for the multivariate KZG scheme and many of its variants under falsifiable assumptions