International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Mehdi Tibouchi

Publications

Year
Venue
Title
2022
TCHES
Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
The lattice reduction attack on (EC)DSA (and other Schnorr-like signature schemes) with partially known nonces, originally due to Howgrave-Graham and Smart, has been at the core of many concrete cryptanalytic works, side-channel based or otherwise, in the past 20 years. The attack itself has seen limited development, however: improved analyses have been carried out, and the use of stronger lattice reduction algorithms has pushed the range of practically vulnerable parameters further, but the lattice construction based on the signatures and known nonce bits remain the same. In this paper, we propose a simple idea to improve the attack based on the same data in exchange for additional computation: carry out an exhaustive search on some bits of the secret key. This turns the problem from a single bounded distance decoding (BDD) instance in a certain lattice to multiple BDD instances in a fixed lattice of larger volume but with the same bound (making the BDD problem substantially easier). Furthermore, the fact that the lattice is fixed lets us use batch/preprocessing variants of BDD solvers that are far more efficient than repeated lattice reductions on non-preprocessed lattices of the same size. As a result, our analysis suggests that our technique is competitive or outperforms the state of the art for parameter ranges corresponding to the limit of what is achievable using lattice attacks so far (around 2-bit leakage on 160-bit groups, or 3-bit leakage on 256-bit groups). We also show that variants of this idea can also be applied to bits of the nonces (leading to a similar improvement) or to filtering signature data (leading to a data-time trade-off for the lattice attack). Finally, we use our technique to obtain an improved exploitation of the TPM–FAIL dataset similar to what was achieved in the Minerva attack.
2021
PKC
Two-round n-out-of-n and Multi-Signatures and Trapdoor Commitment from Lattice 📺
Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures, however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signature schemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs. In this paper, we construct several lattice-based distributed signing protocols with low round complexity following the Fiat--Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message---which can inevitably happen in the Fiat--Shamir with Aborts setting. We manage to do so using homomorphic commitments. Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.'s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round n-out-of-n distributed signing and multi-signature in the plain public key model, by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.
2020
EUROCRYPT
Key Recovery from Gram--Schmidt Norm Leakage in Hash-and-Sign Signatures over NTRU Lattices 📺
In this paper, we initiate the study of side-channel leakage in hash-and-sign lattice-based signatures, with particular emphasis on the two efficient implementations of the original GPV lattice-trapdoor paradigm for signatures, namely NIST second-round candidate Falcon and its simpler predecessor DLP. Both of these schemes implement the GPV signature scheme over NTRU lattices, achieving great speed-ups over the general lattice case. Our results are mainly threefold. First, we identify a specific source of side-channel leakage in most implementations of those schemes, namely, the one-dimensional Gaussian sampling steps within lattice Gaussian sampling. It turns out that the implementations of these steps often leak the Gram--Schmidt norms of the secret lattice basis. Second, we elucidate the link between this leakage and the secret key, by showing that the entire secret key can be efficiently reconstructed solely from those Gram--Schmidt norms. The result makes heavy use of the algebraic structure of the corresponding schemes, which work over a power-of-two cyclotomic field. Third, we concretely demonstrate the side-channel attack against DLP (but not Falcon due to the different structures of the two schemes). The challenge is that timing information only provides an approximation of the Gram--Schmidt norms, so our algebraic recovery technique needs to be combined with pruned tree search in order to apply it to approximate values. Experimentally, we show that around $2^{35}$ DLP traces are enough to reconstruct the entire key with good probability.
2019
JOFC
Efficient Fully Structure-Preserving Signatures and Shrinking Commitments
In structure-preserving signatures, public keys, messages, and signatures are all collections of source group elements of some bilinear groups. In this paper, we introduce fully structure-preserving signature schemes, with the additional requirement that even secret keys are group elements. This strong property allows efficient non-interactive proofs of knowledge of the secret key, which is useful in designing cryptographic protocols under simulation-based security where online extraction of the secret key is needed. We present efficient constructions under simple standard assumptions and pursue even more efficient constructions with the extra property of randomizability based on the generic bilinear group model. An essential building block for our efficient standard model construction is a shrinking structure-preserving trapdoor commitment scheme, which is by itself an important primitive and of independent interest as it appears to contradict a known impossibility result that structure-preserving commitments cannot be shrinking. We argue that a relaxed binding property lets us circumvent the impossibility while still retaining the usefulness of the primitive in important applications as mentioned above.
2018
EUROCRYPT
2018
TCHES
New Bleichenbacher Records: Fault Attacks on qDSA Signatures
Akira Takahashi Mehdi Tibouchi Masayuki Abe
In this paper, we optimize Bleichenbacher’s statistical attack technique against (EC)DSA and other Schnorr-like signature schemes with biased or partially exposed nonces. Previous approaches to Bleichenbacher’s attack suffered from very large memory consumption during the so-called “range reduction” phase. Using a carefully analyzed and highly parallelizable approach to this range reduction based on the Schroeppel–Shamir algorithm for knapsacks, we manage to overcome the memory barrier of previous work while maintaining a practical level of efficiency in terms of time complexity.As a separate contribution, we present new fault attacks against the qDSA signature scheme of Renes and Smith (ASIACRYPT 2017) when instantiated over the Curve25519 Montgomery curve, and we validate some of them on the AVR microcontroller implementation of qDSA using actual fault experiments on the ChipWhisperer-Lite evaluation board. These fault attacks enable an adversary to generate signatures with 2 or 3 bits of the nonces known.Combining our two contributions, we are able to achieve a full secret key recovery on qDSA by applying our version of Bleichenbacher’s attack to these faulty signatures. Using a hybrid parallelization model relying on both shared and distributed memory, we achieve a very efficient implementation of our highly scalable range reduction algorithm. This allows us to complete Bleichenbacher’s attack in the 252-bit prime order subgroup of Curve25519 within a reasonable time frame and using relatively modest computational resources both for 3-bit nonce exposure and for the much harder case of 2-bit nonce exposure. Both of these computations, and particularly the latter, set new records in the implementation of Bleichenbacher’s attack.
2018
ASIACRYPT
LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS
This paper is devoted to analyzing the variant of Regev’s learning with errors (LWE) problem in which modular reduction is omitted: namely, the problem (ILWE) of recovering a vector $$\mathbf {s}\in \mathbb {Z}^n$$ given polynomially many samples of the form $$(\mathbf {a},\langle \mathbf {a},\mathbf {s}\rangle + e)\in \mathbb {Z}^{n+1}$$ where $$\mathbf { a}$$ and e follow fixed distributions. Unsurprisingly, this problem is much easier than LWE: under mild conditions on the distributions, we show that the problem can be solved efficiently as long as the variance of e is not superpolynomially larger than that of $$\mathbf { a}$$. We also provide almost tight bounds on the number of samples needed to recover $$\mathbf {s}$$.Our interest in studying this problem stems from the side-channel attack against the BLISS lattice-based signature scheme described by Espitau et al. at CCS 2017. The attack targets a quadratic function of the secret that leaks in the rejection sampling step of BLISS. The same part of the algorithm also suffers from a linear leakage, but the authors claimed that this leakage could not be exploited due to signature compression: the linear system arising from it turns out to be noisy, and hence key recovery amounts to solving a high-dimensional problem analogous to LWE, which seemed infeasible. However, this noisy linear algebra problem does not involve any modular reduction: it is essentially an instance of ILWE, and can therefore be solved efficiently using our techniques. This allows us to obtain an improved side-channel attack on BLISS, which applies to 100% of secret keys (as opposed to $${\approx }7\%$$ in the CCS paper), and is also considerably faster.
2017
PKC
2016
CRYPTO
2016
PKC
2016
JOFC
2016
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
FSE
2015
PKC
2015
EUROCRYPT
2015
CRYPTO
2015
CRYPTO
2015
CRYPTO
2014
CRYPTO
2014
PKC
2014
TCC
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
ASIACRYPT
2014
CHES
2013
CRYPTO
2013
EUROCRYPT
2013
JOFC
A Note on the Bivariate Coppersmith Theorem
In 1997, Coppersmith proved a famous theorem for finding small roots of bivariate polynomials over ℤ, with important applications to cryptography.While it seems to have been overlooked until now, we found the proof of the most commonly cited version of this theorem to be incomplete. Filling in the gap requires technical manipulations which we carry out in this paper.
2012
EUROCRYPT
2012
EUROCRYPT
2012
CHES
2011
PKC
2011
CRYPTO
2011
CHES
2010
EPRINT
Estimating the Size of the Image of Deterministic Hash Functions to Elliptic Curves
Pierre-Alain Fouque Mehdi Tibouchi
Let E be a non-supersingular elliptic curve over a finite field F_q. At CRYPTO 2009, Icart introduced a deterministic function F_q->E(F_q) which can be computed efficiently, and allowed him and Coron to define well-behaved hash functions with values in E(F_q). Some properties of this function rely on a conjecture which was left as an open problem in Icart's paper. We prove this conjecture as well as analogues for other hash functions. See also Farahashi, Shparlinski and Voloch, _On Hashing into Elliptic Curves_, for independent results of a similar form.
2010
EPRINT
On The Broadcast and Validity-Checking Security of PKCS \#1 v1.5 Encryption
This paper describes new attacks on PKCS \#1 v1.5, a deprecated but still widely used RSA encryption standard. The first cryptanalysis is a broadcast attack, allowing the opponent to reveal an identical plaintext sent to different recipients. This is nontrivial because different randomizers are used for different encryptions (in other words, plaintexts coincide only partially). The second attack predicts, using a single query to a validity checking oracle, which of two chosen plaintexts corresponds to a challenge ciphertext. The attack's success odds are very high. The two new attacks rely on different mathematical tools and underline the need to accelerate the phase out of PKCS \#1 v1.5.
2010
EPRINT
Deterministic Encoding and Hashing to Odd Hyperelliptic Curves
Pierre-Alain Fouque Mehdi Tibouchi
In this paper we propose a very simple and efficient encoding function from F_q to points of a hyperelliptic curve over F_q of the form H: y^2=f(x) where f is an odd polynomial. Hyperelliptic curves of this type have been frequently considered in the literature to obtain Jacobians of good order and pairing-friendly curves. Our new encoding is nearly a bijection to the set of F_q-rational points on H. This makes it easy to construct well-behaved hash functions to the Jacobian J of H, as well as injective maps to J(F_q) which can be used to encode scalars for such applications as ElGamal encryption. The new encoding is already interesting in the genus 1 case, where it provides a well-behaved encoding to Joux's supersingular elliptic curves.
2010
EPRINT
Huff's Model for Elliptic Curves
Marc Joye Mehdi Tibouchi Damien Vergnaud
This paper revisits a model for elliptic curves over Q introduced by Huff in 1948 to study a diophantine problem. Huff's model readily extends over fields of odd characteristic. Every elliptic curve over such a field and containing a copy of Z/4Z×Z/2Z is birationally equivalent to a Huff curve over the original field. This paper extends and generalizes Huff's model. It presents fast explicit formulas for point addition and doubling on Huff curves. It also addresses the problem of the efficient evaluation of pairings over Huff curves. Remarkably, the formulas we obtain feature some useful properties, including completeness and independence of the curve parameters.
2010
CRYPTO
2009
CRYPTO

Program Committees

Asiacrypt 2020
CHES 2020 (Program chair)
Asiacrypt 2019
Eurocrypt 2019
CHES 2019
Asiacrypt 2018
PKC 2018
Asiacrypt 2017
CHES 2017
Crypto 2017
CHES 2016
Asiacrypt 2016
PKC 2016
Crypto 2016
CHES 2015
Asiacrypt 2015
CHES 2014
CHES 2013