Journal papers

International Conference papers

International Workshop papers

Ph.D. thesis :

Habilitation thesis :


A Note on the Bivariate Coppersmith Theorem


Jean-Sebastien Coron, Alexey Kirichenko and Mehdi Tibouchi


Reference : Journal of Cryptology, 26(2), 2013

Abstract : In 1997, Coppersmith proved a famous theorem for finding small roots of bivariate polynomials over Z, 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.

Download : A Note on the Bivariate Coppersmith Theorem


Cryptanalysis of ISO/IEC 9796-1


Don Coppersmith, Jean-Sebastien Coron, Francois Grieu, Shai Halevi, Charanjit Jutla and Julien Stern


Reference : Journal of Cryptology, Volume 21, Number 1, 2008

Abstract : We describe two different attacks against the ISO/IEC 9796-1 signature standard for RSA and Rabin. Both attacks consist in an existential forgery under a chosen-message attack: the attacker asks for the signature of some messages of his choice, and is then able to produce the signature of a message that was never signed by the legitimate signer. The first attack is a variant of Desmedt and Odlyzko's attack and requires a few hundreds of signatures. The second attack is more powerful and requires only three signatures.

Download : Cryptanalysis of ISO/IEC 9796-1


Deterministic Polynomial-Time Equivalence of Computing the RSA Secret Key and Factoring


Jean-Sebastien Coron and Alexander May


Reference : Journal of Cryptology, Volume 20, Number 1, January 2007.

Abstract : We address one of the most fundamental problems concerning the RSA cryptosystem: does the knowledge of the RSA public and secret key pair (e,d) yield the factorization of N = pq in polynomial time? It is well known that there is a probabilistic polynomial-time algorithm that on input (N,e,d) outputs the factors p and q. We present the first deterministic polynomial-time algorithm that factors N given (e,d) provided that e,d < N. Our approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.

Download : Deterministic Polynomial-Time Equivalence of Computing the RSA Secret Key and Factoring


Index Calculation Attacks on RSA Signature and Encryption


J.S. Coron, Y. Desmedt, D. Naccache, A. Odlyzko and J.P. Stern


Reference : Des. Codes Cryptography, vol. 38, Number 1, January, 2006

Abstract : At Crypto '85 Desmedt and Odlyzko described a chosen-ciphertext attack against plain RSA encryption. The technique can also be applied to RSA signatures and enables an existential forgery under a chosen-message attack. The potential of this attack remained untapped until a twitch in the technique made it effective against two very popular RSA signature standards, namely iso/iec 9796-1 and iso/iec 9796-2. Following these attacks, iso/iec 9796-1 was withdrawn and ISO/IEC 9796-2 amended. In this paper, we explain in detail Desmedt and Odlyzko's attack as well as its application to the cryptanalysis of iso/iec 9796-2.

Download : Index Calculation Attacks on RSA Signature and Encryption


Higher Order Masking of Look-Up Tables


J.S. Coron


Reference : Proceedings of Eurocrypt 2014, LNCS, 2014

Abstract : We describe a new algorithm for masking look-up tables of block-ciphers at any order, as a countermeasure against side-channel attacks. Our technique is a generalization of the classical randomized table countermeasure against first-order attacks. We prove the security of our new algorithm against t-th order attacks in the usual Ishai-Sahai-Wagner model from Crypto 2003; we also improve the bound on the number of shares from n>=4t+1 to n>2t+1 for an adversary who can adaptively move its probes between successive executions. Our algorithm has the same time complexity O(n^2) as the Rivain-Prouff algorithm for AES, and its extension by Carlet et al. to any look-up table. In practice for AES our algorithm is less efficient than Rivain-Prouff, which can take advantage of the special algebraic structure of the AES Sbox; however for DES our algorithm performs slightly better.

Download : Higher Order Masking of Look-Up Tables


Practical Multilinear Maps over the Integers


J.S. Coron, T. Lepoint and M. Tibouchi


Reference : Proceedings of Crypto 2013, LNCS, 2013

Abstract : Extending bilinear elliptic curve pairings to multilinear maps is a long-standing open problem. The first plausible construction of such multilinear maps has recently been described by Garg, Gentry and Halevi, based on ideal lattices. In this paper we describe a different construction that works over the integers instead of ideal lattices, similar to the DGHV fully homomorphic encryption scheme. We also describe a different technique for proving the full randomization of encodings: instead of Gaussian linear sums, we apply the classical leftover hash lemma over a quotient lattice. We show that our construction is relatively practical: for reasonable security parameters a one-round 7-party Diffie-Hellman key exchange requires about $25$ seconds per party.

Download : Practical Multilinear Maps over the Integers


Batch Fully Homomorphic Encryption over the Integers


Jung Hee Cheon, Jean-Sebastien Coron, Jinsu Kim, Moon Sung Lee, Tancrede Lepoint, Mehdi Tibouchi, Aaram Yun


Reference : Proceedings of Eurocrypt 2013, LNCS, 2013

Abstract : We extend the fully homomorphic encryption scheme over the integers of van Dijk et al. (DGHV) to batch fully homomorphic encryption, i.e. to a scheme that supports encrypting and homomorphically processing a vector of plaintext bits as a single ciphertext. Our variant remains semantically secure under the (error-free) approximate GCD problem. We also show how to perform arbitrary permutations on the underlying plaintext vector given the ciphertext and the public key. Our scheme offers competitive performance: we describe an implementation of the fully homomorphic evaluation of AES encryption, with an amortized cost of about 12 minutes per AES ciphertext on a standard desktop computer; this is comparable to the timings presented by Gentry et al. at Crypto 2012 for their implementation of a Ring-LWE based fully homomorphic encryption scheme.

Download : Batch Fully Homomorphic Encryption over the Integers


Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers


J.S. Coron, D. Naccache and M. Tibouchi


Reference : Proceedings of Eurocrypt 2012, LNCS, 2012

Abstract : We describe a compression technique that reduces the public key size of van Dijk, Gentry, Halevi and Vaikuntanathan's (DGHV) fully homomorphic scheme over the integers from lambda^7 to lambda^5. Our variant remains semantically secure, but in the random oracle model. We obtain an implementation of the full scheme with a 10.1 MB public key instead of 802 MB using similar parameters as in cite{cmnt2011}. Additionally we show how to extend the quadratic encryption technique of cite{cmnt2011} to higher degrees, to obtain a shorter public-key for the basic scheme. This paper also describes a new modulus switching technique for the DGHV scheme that enables to use the new FHE framework without bootstrapping from Brakerski, Gentry and Vaikuntanathan with the DGHV scheme. Finally we describe an improved attack against the Approximate GCD Problem on which the DGHV scheme is based, with complexity 2^rho instead of 2^{3rho/2}.

Download : Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers


Fully Homomorphic Encryption over the Integers with Shorter Public Keys


J.S. Coron, A. Mandal, D. Naccache and M. Tibouchi


Reference : Proceedings of CRYPTO 2011, LNCS, 2011

Abstract : At Eurocrypt 2010 van Dijk {sl et al.} described a fully homomorphic encryption scheme over the integers. The main appeal of this scheme (compared to Gentry's) is its conceptual simplicity. This simplicity comes at the expense of a public key size in ${cal tilde O}(lambda^{10})$ which is too large for any practical system. In this paper we reduce the public key size to ${cal tilde O}(lambda^{7})$ by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk {sl et al}. We also describe the first implementation of the resulting fully homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry's scheme, we obtain roughly the same level of efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.

Download : Fully Homomorphic Encryption over the Integers with Shorter Public Keys


Improved Generic Algorithms for Hard Knapsacks


A. Becker, J.S. Coron and A. Joux


Reference : Proceedings of Eurocrypt 2011, LNCS, 2011

Abstract : At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of density close to 1 in time O(2^0.337n) and memory O(2^0.256n), thereby improving a 30-year old algorithm by Shamir and Schroeppel. In this paper we extend the Howgrave-Graham- Joux technique to get an algorithm with running time down to O(2^0.291n). An implementation shows the practicability of the technique. Another challenge is to reduce the memory requirement. We describe a constant memory algorithm based on cycle finding with running time O(2^0.72n); we also show a time-memory tradeoff.

Download : Improved Generic Algorithms for Hard Knapsacks


Efficient Indifferentiable Hashing into Ordinary Elliptic Curves


E. Brier, J.S. Coron, T. Icart, D. Madore, H. Randriam and M. Tibouchi


Reference : Proceedings of CRYPTO 2010, LNCS, 2010

Abstract : We provide the first construction of a hash function into ordinary elliptic curves that is indifferentiable from a random oracle, based on Icart's deterministic encoding from Crypto 2009. While almost as efficient as Icart's encoding, this hash function can be plugged into any cryptosystem that requires hashing into elliptic curves, while not compromising proofs of security in the random oracle model. We also describe a more general (but less efficient) construction that works for a large class of encodings into elliptic curves, for example the Shallue-Woestijne-Ulas (SWU) algorithm. Finally we describe the first deterministic encoding algorithm into elliptic curves in characteristic 3

Download : Efficient Indifferentiable Hashing into Ordinary Elliptic Curves


PSS is Secure against Random Fault Attacks


J.S. Coron and A. Mandal


Reference : Proceedings of ASIACRYPT 2009, LNCS, 2009

Abstract : A fault attack consists in inducing hardware malfunctions in order to recover secrets from electronic devices. One of the most famous fault attack is Bellcore's attack against RSA with CRT; it consists in inducing a fault modulo p but not modulo q at signature generation step; then by taking a gcd the attacker can recover the factorization of N=pq. The Bellcore attack applies to any encoding function that is deterministic, for example FDH. Recently, the attack was extended to randomized encodings based on the iso/iec 9796-2 signature standard. Extending the attack to other randomized encodings remains an open problem. In this paper, we show that the Bellcore attack cannot be applied to the PSS encoding; namely we show that PSS is provably secure against random fault attacks in the random oracle model, assuming that inverting RSA is hard.

Download : PSS is Secure against Random Fault Attacks


Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures


J.S. Coron, D. Naccache, M. Tibouchi and R.-P. Weinmann


Reference : Proceedings of Crypto 2009, LNCS, 2009

Abstract : In 1999, Coron, Naccache and Stern discovered an existential signature forgery for two popular RSA signature standards, ISO/IEC 9796-1 and 2. Following this attack ISO/IEC 9796-1 was withdrawn. ISO/IEC 9796-2 was amended by increasing the message digest to at least 160 bits. Attacking this amended version required at least 2^61 operations. In this paper, we exhibit algorithmic refinements allowing to attack the amended (currently valid) version of ISO/IEC 9796-2 for all modulus sizes. A practical forgery was computed in only two days using 19 servers on the Amazon EC2 grid for a total cost of roughly $800. The forgery was implemented for e=2 but attacking odd exponents will not take longer. The forgery was computed for the RSA-2048 challenge modulus, whose factorization is still unknown. The new attack blends several theoretical tools. These do not change the asymptotic complexity of Coron et al. technique but significantly accelerate it for parameter values previously considered beyond reach. While less efficient ($45,000), the acceleration also extends to EMV signatures. EMV is an ISO/IEC 9796-2-compliant format with extra redundancy. Luckily, this attack does not threaten any of the 730 million EMV payment cards in circulation for operational reasons. Costs are per modulus: after a first forgery for a given modulus, obtaining more forgeries is virtually immediate.

Download : Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures


The Random Oracle Model and the Ideal Cipher Model are Equivalent


J.S. Coron, J. Patarin and Y. Seurin


Reference : Proceedings of Crypto 2008, LNCS, 2008

Abstract : The Random Oracle Model and the Ideal Cipher Model are two well known idealised models of computation for proving the security of cryptosystems. At Crypto 2005, Coron et al. showed that security in the random oracle model implies security in the ideal cipher model; namely they showed that a random oracle can be replaced by a block cipher-based construction, and the resulting scheme remains secure in the ideal cipher model. The other direction was left as an open problem, i.e. constructing an ideal cipher from a random oracle. In this paper we solve this open problem and show that the Feistel construction with 6 rounds is enough to obtain an ideal cipher; we also show that 5 rounds are insufficient by providing a simple attack. This contrasts with the classical Luby-Rackoff result that 4 rounds are necessary and sufficient to obtain a (strong) pseudo-random permutation from a pseudo-random function.

Download : The Random Oracle Model and the Ideal Cipher Model are Equivalent


Finding Small Roots of Bivariate Integer Polynomial Equations: a Direct Approach


J.S. Coron


Reference : Proceedings of Crypto 2007, LNCS, 2007

Abstract : Coppersmith described at Eurocrypt 96 an algorithm for finding small roots of bivariate integer polynomial equations, based on lattice reduction. A simpler algorithm was later proposed in [9], but it was asymptotically less efficient than Coppersmith's algorithm. In this paper, we describe an analogous simplification but with the same asymptotic complexity as Coppersmith. We illustrate our new algorithm with the problem of factoring RSA moduli with high-order bits known; in practical experiments our method is several orders of magnitude faster than [9].

Download : Finding Small Roots of Bivariate Integer Polynomial Equations: a Direct Approach


Merkle-Damgard Revisited: how to construct a hash-function


J.S. Coron, Y. Dodis, C. Malinaud and P. Puniya


Reference : Proceedings of Crypto 2005, LNCS, 2005

Abstract : The most common way of constructing a hash function {e.g., SHA-1) is to iterate a compression function on the input message. The compression function is usually designed from scratch or made out of a block-cipher. In this paper, we introduce a new security notion for hash-functions, stronger than collision-resistance. Under this notion, the arbitrary length hash function H must behave as a random oracle when the fixed-length building block is viewed as a random oracle or an ideal block-cipher. The key property is that if a particular construction meets this definition, then any cryptosystem proven secure assuming H is a random oracle remains secure if one plugs in this construction (still assuming that the underlying fixed-length primitive is ideal). In this paper, we show that the current design principle behind hash functions such as SHA-1 and MD5 - the (strengthened) Merkle-Damgard transformation - does not satisfy this security notion. We provide several constructions that provably satisfy this notion; those new constructions introduce minimal changes to the plain MD construction and are easily implementable in practice.

Download : Merkle-Damgard Revisited: how to construct a hash-function


Finding small roots of bivariate integer equations revisited


J.S. Coron


Reference : Proceedings of Eurocrypt 2004, LNCS, 2004

Abstract : At Eurocrypt '96, Coppersmith proposed an algorithm for finding small roots of bivariate integer polynomial equations, based on lattice reduction techniques. But the approach is difficult to understand. In this paper, we present a much simpler algorithm for solving the same problem. Our simplification is analogous to the simplification brought by Howgrave-Graham to Coppersmith's algorithm for finding small roots of univariate modular polynomial equations. As an application, we illustrate the new algorithm with the problem of finding the factors of n=pq if we are given the half high order bits of p.

Download : Finding small roots of bivariate integer equations revisited


Boneh et al's k-Element Aggregate Extraction Assumption Is Equivalent to The Diffie-Hellman Assumption


J.S. Coron and D. Naccache


Reference : Proceedings of Asiacrypt '03, Lecture Notes in Computer Science, Springer-Verlag, 2003

Abstract : In Eurocrypt 2003, Boneh et al. presented a novel cryptographic primitive called aggregate signatures. An aggregate signature scheme is a digital signature that supports aggregation: i.e. given k signatures on k distinct messages from k different users it is possible to aggregate all these signatures into a single short signature. Applying the above concept to verifiably encrypted signatures, Boneh et al. introduced a new complexity assumption called the k-Element Aggregate Extraction Problem. In this paper we show that the k-Element Aggregate Extraction Problem is nothing but a Computational Diffie-Hellman Problem in disguise.

Download : Boneh et al's k-Element Aggregate Extraction Assumption Is Equivalent to The Diffie-Hellman Assumption


Security Proof for Partial-Domain Hash Signature Schemes


J.S. Coron


Reference : Proceedgins of Crypto '02, LNCS, Springer-Verlag, 2002

Abstract : A common practice for signing with RSA or Rabin consists in first hashing the message, padding the digest with some fixed or message-dependent block, and eventually raising the result to the private exponent modulo N. This "hash-and-sign" paradigm is the basis for numerous signature schemes, including the Full Domain Hash (FDH) scheme, and standards, such as PKCS#1 v1.5 and ISO 9796-2. FDH is provably secure against chosen message attacks in the random oracle model, assuming that inverting RSA is hard. On the contrary, although widely used in commercial applications, no security proofs are known for PKCS#1 v1.5 and ISO 9796-2. Moreover it was shown that ISO 9796-2 was insecure if the hash size was too small, and the standard was subsequently revised. In this paper, we provide the first security proof against chosen-message attacks for partial-domain hash signature schemes, in the random oracle model, for e=2 (Rabin). We show that partial-domain hash signature schemes are provably secure, assuming that factoring is hard, if the hash size is larger than 2/3 the modulus size. This provides the first security proof for the signature standards PKCS#1 v1.5, ISO 9796-2, SSL-3.02 and ANSI x9.31.

Download : Security Proof for Partial-Domain Hash Signature Schemes


Universal padding schemes for RSA


J.S. Coron, M. Joye, D. Naccache and P. Paillier


Reference : Proceedings of Crypto '02, Lecture Notes in Computer Science, Springer-Verlag, 2002

Abstract : A common practice to encrypt with RSA is to first apply a padding scheme to the message and then to exponentiate the result with the public exponent; an example of this is OAEP. Similarly, the usual way of signing with RSA is to apply some padding scheme and then to exponentiate the result with the private exponent, as for example in PSS. Usually, the RSA modulus used for encrypting is different from the one used for signing. The goal of this paper is to simplify this common setting. First, we show that PSS can also be used for encryption, and gives an encryption scheme semantically secure against adaptive chosen-ciphertext attacks, in the random oracle model. As a result, PSS can be used indifferently for encryption or signature. Moreover, we show that PSS allows to safely use the same RSA key-pairs for both encryption and signature, in a concurrent manner. More generally, we show that using PSS the same set of keys can be used for both encryption and signature for any trapdoor partial-domain one-way permutation. The practical consequences of our result are important: PKIs and public-key implementations can be significantly simplified.

Download : Universal padding schemes for RSA


Optimal security proofs for PSS and other signature schemes


J.S. Coron


Reference : Proceedings of Eurocrypt '02, Lecture Notes in Computer Science, Springer-Verlag, 2002

Abstract : The Probabilistic Signature Scheme (PSS) designed by Bellare and Rogaway is a signature scheme provably secure against chosen message attacks in the random oracle model, whose security can be tightly related to the security of RSA. We derive a new security proof for PSS in which a much shorter random salt is used to achieve the same security leve. When PSS is used with message recovery, a better bandwidth is obtained because longer messages can now be recovered. In this paper, we also introduce a new technique for proving that the security proof of a signature scheme is optimal. In particular, we show that the size of the random salt that we have obtained for PSS is optimal. Our technique applies to other signature schemes such as the Full Domain Hash scheme and Gennaro-Halevi-Rabin's scheme, whose security proofs are shown to be optimal.

Download : Optimal security proofs for PSS and other signature schemes


Cryptanalysis of RSA signatures with fixed pattern padding


E. Brier, C. Clavier, J.S. Coron and D. Naccache


Reference : Proceedings of Crypto '01, Lecture Notes in Computer Science, Springer-Verlag, 2001

Abstract : A fixed-pattern padding consists in concatenating to the message m a fixed pattern P. The RSA signature is then obtained by computing (P|m)^d mod N where d is the private exponent and N the modulus. In Eurocrypt '97, Girault and Misarsky showed that the size of P must be at least half the size of N (in other words the parameter configurations |P|<|N|/2 are insecure) but the security of RSA fixed-pattern padding remained unknown for |P|>|N|/2. In this paper we show that the size of P must be at least two-thirds of the size of N, i.e. we show that |P|<2|N|/3 is insecure.

Download : Cryptanalysis of RSA signatures with fixed pattern padding


From fixed-length to arbitrary length RSA padding schemes


J.S. Coron, F. Koeune and D. Naccache


Reference : Proceedings of Asiacrypt '00, Lecture Notes in Computer Science, Springer-Verlag, 2000

Abstract : A common practice for signing with RSA is to first apply a hash function or a redundancy function to the message, add some padding and exponentiate the resulting padded message using the decryption exponent. This is the basis of several existing standards. In this paper we show how to build a secure padding scheme for signing arbitrarily long messages with a secure padding scheme for fixed-size messages. This focuses more sharply the question of finding a secure encoding for RSA signatures, by showing that the difficulty is not in handling messages of arbitrary length, but rather in finding a secure redundancy function for short messages, which remains an open problem.

Download : From fixed-length to arbitrary length RSA padding schemes


On the exact security of Full Domain Hash


J.S. Coron


Reference : Proceedings of Crypto '00, Lecture Notes in Computer Science, Springer-Verlag, 2000

Abstract : The Full Domain Hash (FDH) scheme is a RSA-based signature scheme in which the message is hashed onto the full domain of the RSA function. The FDH scheme is provably secure in the random oracle model, assuming that inverting RSA is hard. In this paper we exhibit a slightly different proof which provides a tighter security reduction. This in turn improves the efficiency of the scheme since smaller RSA moduli can be used for the same level of security. The same method can be used to obtain a tighter security reduction for Rabin signature scheme, Paillier signature scheme, and the Gennaro-Halevi-Rabin signature scheme.

Download : On the exact security of Full Domain Hash


Security analysis of the Gennaro-Halevi-Rabin signature scheme


J.S. Coron and D. Naccache


Reference : Proceedings of Eurocrypt '00, Lecture Notes in Computer Science, Springer-Verlag, 2000

Abstract : We exhibit an attack against a signature scheme recently proposed by Gennaro, Halevi and Rabin. The scheme's security is based on two assumptions namely the strong RSA assumption and the existence of a division-intractable hash-function. For the latter, the authors conjectured a security level exponential in the hash-function's digest size whereas our attack is sub-exponential with respect to the digest size. Moreover, since the new attack is optimal, the length of the hash function can now be rigorously fixed. In particular, to get a security level equivalent to 1024-bit RSA, one should use a digest size of approximately 1024 bits instead of the 512 bits.

Download : Security analysis of the Gennaro-Halevi-Rabin signature scheme


New attacks on PKCS#1 v1.5 encryption


J.S. Coron, D. Naccache, M. Joye and P. Paillier


Reference : Proceedings of Eurocrypt '00, Lecture Notes in Computer Science, Springer-Verlag, 2000

Abstract : This paper introduces two new attacks on PKCS#1 v1.5, an RSA-based encryption standard proposed by RSA Laboratories. As opposed to Bleichenbacher's attack, our attacks are chosen-plaintext only, i.e.they do not make use of a decryption oracle. The first attack applies to small public exponents and shows that plaintexts ending by sufficiently many zeroes can be recovered efficiently from their ciphertexts. We believe the technique we employ to be of independent interest, as it extends Coppersmith's low-exponent attack to certain length parameters. Our second attack is applicable to arbitrary public exponents, provided that most message bits are zeroes. It seems to constitute the first chosen-plaintext attack on an RSA-based encryption standard that yields to practical results for any public exponent

Download : New attacks on PKCS#1 v1.5 encryption


Elliptic Curve Cryptography : do we need to count ?


J.S. Coron, H. Handschuh and D. Naccache


Reference : Proceedings of Asiacrypt '99, Lecture Notes in Computer Science, Springer-Verlag, 1999

Abstract : A prohibitive barrier faced by elliptic curve users is the difficulty of computing the curves' cardinalities. Despite recent theoretical breakthroughs, point counting still remains very cumbersome and intensively time consuming. In this paper we show that point counting can be avoided at the cost of a protocol slow-down. This slow-down factor is typically about 165 and proves that the existence of secure elliptic-curve signatures is not necessarily conditioned by point counting.

Download : Elliptic Curve Cryptography : do we need to count ?


On the security of RSA padding


J.S. Coron, D. Naccache and J.P. Stern


Reference : Proceedings of Crypto '99, Lecture Notes in Computer Science, Springer-Verlag, 1999.

Abstract : We present a new forgery strategy for RSA signatures which is a variant of the Desmedt and Odlyzko attack. It consists in obtaining the signature of a set of chosen messages and exhibiting the signature of a message which has never been signed by the legitimate owner of the key.
The messages are chosen so that they can be represented as the product of small primes. A message is then expressed as a multiplicative combination of the others. Using the homomorphic property of RSA, one signature can be expressed as a multiplicative combination of the others.
The attack efficiency depends on the padding scheme used for signature generation. A padding format that differs from ISO 9796-1 by one single bit was broken experimentally, but we could not extend our attack to ISO 9796-1. For ISO 9796-2 the attack is more demanding but much more efficient than collision-search or factoring.
For DIN NI-17.4, PKCS #1 v2.0 and SSL-3.02, the attack is only theoretical since it only applies to specific moduli and happens to be less efficient than factoring; therefore, the attack does not endanger any of these standards.

Download : On the security of RSA padding


Scale-Invariant Fully Homomorphic Encryption over the Integers


Jean-Sebastien Coron, Tancrede Lepoint, Mehdi Tibouchi


Reference : Proceedings of PKC, LNCS, 2014

Abstract : At Crypto 2012, Brakerski constructed a scale-invariant fully homomorphic encryption scheme based on the LWE problem, in which the same modulus is used throughout the evaluation process, instead of a ladder of moduli when doing “modulus switching”. In this paper we describe a variant of the van Dijk et al. FHE scheme over the integers with the same scale-invariant property. Our scheme has a single secret modulus whose size is linear in the multiplicative depth of the circuit to be homomorphically evaluated, instead of exponential; we therefore construct a leveled fully homomorphic encryption scheme. This scheme can be transformed into a pure fully homomorphic encryption scheme using bootstrapping, and its security is still based on the Approximate-GCD problem. We also describe an implementation of the homomorphic evaluation of the full AES encryption circuit, and obtain significantly improved performance compared to previous implementations: about 23 seconds (resp. 3 minutes) per AES block at the 72-bit (resp. 80-bit) security level on a mid-range workstation. Finally, we prove the equivalence between the (error-free) decisional Approximate-GCD problem introduced by Cheon et al. (Eurocrypt 2013) and the classical computational Approximate-GCD problem. This equivalence allows to get rid of the additional noise in all the integer-based FHE schemes described so far, and therefore to simplify their security proof.

Download : Scale-Invariant Fully Homomorphic Encryption over the Integers


Supplemental Access Control (PACE v2): Security Analysis of PACE Integrated Mapping


Jean-Sebastien Coron, Aline Gouget, Thomas Icart, Pascal Paillier


Reference : Proceedings of Cryptography and Security, LNCS, 2012

Abstract : We describe and analyze the password-based key establishment protocol PACE v2 Integrated Mapping (IM), an evolution of PACE v1 jointly proposed by Gemalto and Sagem Securite. PACE v2 IM enjoys the following properties: patent-freeness (to the best of current knowledge in the field); full resistance to dictionary attacks, secrecy and forward secrecy in the security model agreed upon by the CEN TC224 WG16 group; optimal performances. The PACE v2 IM protocol is intended to provide an alternative to the German PACE v1 protocol, which is also the German PACE v2 Generic Mapping (GM) protocol, proposed by the German Federal Office for Information Security (BSI). In this document, we provide a description of PACE v2 IM, a description of the security requirements one expects from a password-based key establishment protocol in order to support secure applications, and a security proof of PACE v2 IM in the so-called Bellare-Pointcheval-Rogaway (BPR) security model.

Download : Supplemental Access Control (PACE v2): Security Analysis of PACE Integrated Mapping


On the Use of Shamir's Secret Sharing against Side-Channel Analysis


Jean-Sebastien Coron, Emmanuel Prouff, Thomas Roche


Reference : Proceedings of CARDIS, LNCS, 2012

Abstract : At CHES 2011 Goubin and Martinelli described a new countermeasure against side-channel analysis for AES based on Shamir’s secret-sharing scheme. In the present paper, we exhibit a flaw in this scheme and we show that it is always theoretically broken by a first-order side-channel analysis. As a consequence of this attack, only a slight adaptation of the scheme proposed by Ben-Or et al.at STOC in 1988 can securely process multiplications on data shared with Shamir’s technique. In the second part of this paper, we propose an improvement of this scheme that leads to a complexity O(d^2) instead of O(d^3) , where d is the number of shares per data.

Download : On the Use of Shamir's Secret Sharing against Side-Channel Analysis


Conversion of Security Proofs from One Leakage Model to Another: A New Issue


Jean-Sebastien Coron, Christophe Giraud, Emmanuel Prouff, Soline Renner, Matthieu Rivain, Praveen Kumar Vadnala


Reference : Proceedings of COSADE, LNCS, 2012

Abstract : To guarantee the security of a cryptographic implementation against Side Channel Attacks, a common approach is to formally prove the security of the corresponding scheme in a model as pertinent as possible. Nowadays, security proofs for masking schemes in the literature are usually conducted for models where only the manipulated data are assumed to leak. However in practice, the leakage is better modeled encompassing the memory transitions as e.g. the Hamming distance model. From this observation, a natural question is to decide at which extent a countermeasure proved to be secure in the first model stays secure in the second. In this paper, we look at this issue and we show that it must definitely be taken into account. Indeed, we show that a countermeasure proved to be secure against second-order side-channel attacks in the first model becomes vulnerable against a first-order side-channel attack in the second model. Our result emphasize the issue of porting an implementation from devices leaking only on the manipulated data to devices leaking on the memory transitions.

Download : Conversion of Security Proofs from One Leakage Model to Another: A New Issue


Cryptanalysis of the RSA Subgroup Assumption from TCC 2005


J.S. Coron, A. Joux, A. Mandal, D. Naccache and M. Tibouchi


Reference : Proceedings of PKC 2011, LNCS, 2011

Abstract : At TCC 2005, Groth underlined the usefulness of working in small RSA subgroups of hidden order. In assessing the security of the relevant hard problems, however, the best attack considered for a subgroup of size 2^{2k} had a complexity of O{2^k}. Accordingly, k=100 bits was suggested as a concrete parameter. This paper exhibits an attack with a complexity of roughly 2^{k/2} operations, suggesting that Groth's original choice of parameters was overly aggressive. It also discusses the practicality of this new attack and various implementation issues.

Download : Cryptanalysis of the RSA Subgroup Assumption from TCC 2005


Analysis and Improvement of the Random Delay Countermeasure of CHES 2009


J.S. Coron and I. Kizhvatov


Reference : Proceedings of CHES 2010, LNCS, 2010

Abstract : Random delays are often inserted in embedded software to protect against side-channel and fault attacks. At CHES 2009 a new method for generation of random delays was described that increases the attacker's uncertainty about the position of sensitive operations. In this paper we show that the CHES 2009 method is less secure than claimed. We describe an improved method for random delay generation which does not suffer from the same security weakness. We also show that the paper's criterion to measure the security of random delays can be misleading, so we introduce a new criterion for random delays which is directly connected to the number of acquisitions required to break an implementation. We mount a power analysis attack against an 8-bit implementation of the improved method verifying its higher security in practice.

Download : Analysis and Improvement of the Random Delay Countermeasure of CHES 2009


A Domain Extender for the Ideal Cipher


J.S. Coron, Y. Dodis, A. Mandal and Y. Seurin


Reference : Proceedings of TCC 2010, LNCS, 2010

Abstract : We describe the first domain extender for ideal ciphers, i.e. we show a construction that is indifferentiable from a 2n-bit ideal cipher, given a n-bit ideal cipher. Our construction is based on a 3-round Feistel, and is more efficient than first building a n-bit random oracle from a n-bit ideal cipher (as in [9]) and then a 2n-bit ideal cipher from a n-bit random oracle (as in [10], using a 6-round Feistel). We also show that 2 rounds are not enough for indifferentiability by exhibiting a simple attack. We also consider our construction in the standard model: we show that 2 rounds are enough to get a 2n-bit tweakable block-cipher from a n-bit tweakable block-cipher and we show that with 3 rounds we can get beyond the birthday security bound.

Download : A Domain Extender for the Ideal Cipher


Fault Attacks Against EMV Signatures


J.S. Coron, D. Naccache and M. Tibouchi


Reference : Proceedings of CT-RSA 2010, LNCS, 2010

Abstract : At ches 2009, Coron, Joux, Kizhvatov, Naccache and Paillier (cjknp) exhibited a fault attack against rsa signatures with partially known messages. This fault attack allows factoring the public modulus N. While the size of the unknown message part (ump) increases with the number of faulty signatures available, the complexity of cjknp's attack increases exponentially with the number of faulty signatures. This paper describes a simpler attack, whose complexity remains polynomial in the number of faults; consequently, the new attack can handle much larger umps. The new technique can factor N in a fraction of a second using ten faulty emv signatures - a target beyond cjknp's reach. We also show how to apply the attack even when N is unknown, a frequent situation in real-life attacks.

Download : Fault Attacks Against EMV Signatures


Fault Attacks on RSA Signatures with Partially Unknown Messages


J.S. Coron, A. Joux, I. Kizhvatov and P. Paillier


Reference : Proceedings of CHES 2009, LNCS, 2009

Abstract : Fault attacks exploit hardware malfunctions to recover secrets from embedded electronic devices. In the late 90's, Boneh, DeMillo and Lipton introduced fault-based attacks on {sc crt-rsa}. These attacks factor the signer's modulus when the message padding function is deterministic. However, the attack does not apply when the message is partially unknown, for example when messages contain some randomness which is recovered only when verifying a {sl correct} signature. In this paper we successfully extends RSA fault attacks to a large class of partially known message configurations. The new attacks rely on Coppersmith's algorithm for finding small roots of multivariate polynomial equations. We illustrate the approach by successfully attacking several randomized versions of the ISO 9796-2 encoding standard. Practical experiments show that a $2048$-bit modulus can be factored in less than a minute given one faulty signature containing $160$ random bits and an unknown $160$-bit message digest.

Download : Fault Attacks on RSA Signatures with Partially Unknown Messages


An Efficient Method for Random Delay Generation in Embedded Software


J.S. Coron and I. Kizhvatov


Reference : Proceedings of CHES 2009, LNCS, 2009

Abstract : Random delays are a countermeasure against a range of side channel and fault attacks that is often implemented in embedded software. We propose a new method for generation of random delays and a criterion for measuring the efficiency of a random delay countermeasure. We implement this new method along with the existing ones on an 8-bit platform and mount practical side-channel attacks against the implementations. We show that the new method is significantly more secure in practice than the previously published solutions and also more lightweight.

Download : An Efficient Method for Random Delay Generation in Embedded Software


A New DPA Countermeasure Based on Permutation Tables


J.S. Coron


Reference : Proceedings of SCN 2008, LNCS, 2008

Abstract : We propose and analyse a new countermeasure against Differential Power Analysis (DPA) for the AES encryption algorithm, based on permutation tables. As opposed to existing AES countermeasures, it does not use random masking. We prove that our new countermeasure is resistant against first-order DPA; we also show that it is quite efficient in practice.

Download : A New DPA Countermeasure Based on Permutation Tables


Attack and Improvement of a Secure S-Box Calculation Based on the Fourier Transform


J.S. Coron, C. Giraud, E. Prouff and M. Rivain


Reference : Proceedings of CHES 2008, LNCS, 2008

Abstract : At CHES 2006, a DPA countermeasure based on the Fourier Transform was published. This generic countermeasure aims at protecting from DPA any S-box calculation used in symmetric cryptosystems implementations. In this paper, we show that this countermeasure has a flaw and that it can be broken by first order DPA. Moreover, we have successfully put into practice our attack on two different S-box implementations. Finally, we propose an improvement of the original countermeasure and we prove its security against first order DPA.

Download : Attack and Improvement of a Secure S-Box Calculation Based on the Fourier Transform


Side Channel Cryptanalysis of a High Order Masking Scheme


J.S. Coron and E. Prouff and M. Rivain


Reference : Proceedings of CHES 2007, LNCS, 2007

Abstract : In the recent years, DPA attacks have been widely investigated. In particular, 2-nd order DPA have been improved and successfully applied to break many masked implementations. In this context a higher order masking scheme has been proposed by Schramm and Paar at CT-RSA 2006. The authors claimed that the scheme is resistant against d-th order DPA for any arbitrary chosen order d. In this paper, we prove that this assertion is false and we exhibit several 3-rd order DPA attacks that can defeat Schramm and Paar's countermeasure for any value of d.

Download : Side Channel Cryptanalysis of a High Order Masking Scheme


On the Implementation of a Fast Prime Generation Algorithm


C. Clavier and J.S. Coron


Reference : Proceedings of CHES 2007, LNCS, 2007

Abstract : A side-channel analysis of a cryptographic algorithm generally concentrates on the encryption or decryption phases, rarely on the key generation phase. In this paper, we show that, when not properly implemented, the fast prime generation algorithm proposed by Joye and Paillier at CHES 2006 is susceptible to side-channel analysis; its main application is the generation of RSA key-pairs for embedded platforms like smart-cards. Our attack assumes that some parity bit can be recovered through SPA when it appears in a branch condition. Our attack can be combined with Coppersmith's theorem to improve its efficiency; we show that for 1024-bit RSA moduli, one can recover the factorization of roughly 1/1000 of the RSA moduli.

Download : On the Implementation of a Fast Prime Generation Algorithm


A New Baby-Step Giant-Step Algorithm and Some Applications to Cryptanalysis


J.S. Coron, D. Lefranc and G. Poupard


Reference : Proceedings of CHES 2005, LNCS, 2005

Abstract : We describe a new variant of the well known Baby-Step Giant-Step algorithm in the case of some discrete logarithms with a special structure. More precisely, we focus on discrete logarithms equal to products in groups of unknown order. As an example of application, we show that this new algorithm enables to cryptanalyse a variant of the GPS scheme proposed by Girault and Lefranc at CHES 2004 conference in which the private key is equal to the product of two sub-private keys of low Hamming weight. We also describe a second attack based on a known variant of the Baby-Step Giant-Step algorithm using the low Hamming weight of the sub-private keys.

Download : A New Baby-Step Giant-Step Algorithm and Some Applications to Cryptanalysis


Cryptanalysis of a Zero-Knowledge Identification Protocol of Eurocrypt '95


J.S. Coron and D. Naccache


Reference : Proceedings of CT-RSA 2004, Lecture Notes in Computer Science, Springer-Verlag, 2004

Abstract : We present a cryptanalysis of a zero-knowledge identification protocol introduced by Naccache et al. at Eurocrypt '95. Our cryptanalysis enables a polynomial-time attacker to pass the identification protocol with probability one, without knowing the private key.

Download : Cryptanalysis of a Zero-Knowledge Identification Protocol of Eurocrypt '95


A New Algorithm for Switching from Arithmetic to Boolean Masking


J.S. Coron and A. Tchulkine


Reference : Proceedings of CHES '03, Lecture Notes in Computer Science, Springer-Verlag, 2003

Abstract : To protect a cryptographic algorithm against Differential Power Analysis, a general method consists in masking all intermediate data with a random value. When a cryptographic algorithm combines boolean operations with arithmetic operations, it is then necessary to perform conversions between boolean masking and arithmetic masking. A very efficient method was proposed by Louis Goubin to convert from boolean masking to arithmetic masking. However, the method for converting from arithmetic to boolean masking is less efficient. In some implementations, this conversion can be a bottleneck. In this paper, we propose an improved algorithm to convert from arithmetic masking to boolean masking. Our method can be applied to encryption schemes such as IDEA and RC6, and hashing algorithms such as SHA-1.

Download : A New Algorithm for Switching from Arithmetic to Boolean Masking


Optimal Chosen-Ciphertext Secure Encryption of Arbitrary-Length Messages


J.S. Coron, H. Handschuh, M. Joye, P. Paillier, D. Pointcheval and C. Tymen


Reference : Proceedings of PKC '02, Lecture Notes in Computer Science, Springer-Verlag, 2002

Abstract : This paper considers arbitrary-length chosen-ciphertext secure asymmetric encryption, thus addressing what is actually needed for a practical usage of strong public-key cryptography in the real world. We put forward two generic constructions, Gem-1 and Gem-2, which apply to explicit fixed-length weakly secure primitives and provide a strongly secure (CCA) public-key encryption scheme for messages of unfixed length (typically computer files). Our techniques optimally combine a single call to any one-way trapdoor function with repeated encryptions through some weak block-cipher (a simple xor is fine) and hash functions of fixed-length input so that a minimal number of calls to these functions is needed. Our encryption/decryption throughputs are comparable to the ones of standard methods (asymmetric encryption of a session key + symmetric encryption with multiple modes). In our case, however, we formally prove that our designs are secure in the strongest sense and provide complete security reductions holding in the random oracle model.

Download : Optimal Chosen-Ciphertext Secure Encryption of Arbitrary-Length Messages


GEM: a Generic Chosen-Ciphertext Secure Encryption Method


J.S. Coron, H. Handschuh, M. Joye, P. Paillier, D. Pointcheval and C. Tymen


Reference : Proceedings of CT-RSA '02, Lecture Notes in Computer Science, Springer-Verlag, 2002

Abstract : This paper proposes an efficient and provably secure transform to encrypt a message with any asymmetric one-way cryptosystem. The resulting scheme achieves adaptive chosen-ciphertext security in the random oracle model. Compared to previous known generic constructions (Bellare, Rogaway, Fujisaki, Okamoto, and Pointcheval), our embedding reduces the encryption size and/or speeds up the decryption process. It applies to numerous cryptosystems, including (to name a few) ElGamal, RSA, Okamoto-Uchiyama and Paillier systems.

Download : GEM: a Generic Chosen-Ciphertext Secure Encryption Method


Fast Generation of Pairs (k, [k]P) for Koblitz Elliptic Curves


J.S. Coron, D. M'Raihi and C. Tymen


Reference : Proceedings of SAC '01, Lecture Notes in Computer Science, Springer-Verlag, 200

Abstract : We propose a method for increasing the speed of scalar multiplication on binary anomalous (Koblitz) elliptic curves. By introducing a generator which produces random pairs (k,[k]P) of special shape, we exhibit a specific setting where the number of elliptic curve operations is reduced by 25% to 50 % compared with the general case when k is chosen uniformly. This generator can be used when an ephemeral pair (k,[k]P) is needed by a cryptographic algorithm, and especially for Elliptic Curve Diffie-Hellman key exchange, ECDSA signature and El-Gamal encryption. The presented algorithm combines normal and polynomial basis operations to achieve optimal performance. We prove that a probabilistic signature scheme using our generator remains secure against chosen message attacks.

Download : Fast Generation of Pairs (k, [k]P) for Koblitz Elliptic Curves


Differential Power Analysis in the Presence of Hardware Countermeasures


C. Clavier, J.S. Coron and N. Dabbous


Reference : Proceedings of CHES '00, Lecture Notes in Computer Science, Springer-Verlag, 2000

Abstract : The silicon industry has lately been focusing on side channel attacks, that is attacks that exploit information that leaks from the physical devices. Although different countermeasures to thwart these attacks have been proposed and implemented in general, such protections do not make attacks infeasible, but increase the attacker's experimental (data acquisition) and computational (data processing) workload beyond reasonable limits.

Download : Differential Power Analysis in the Presence of Hardware Countermeasures


On Boolean and Arithmetic Masking against Differential Power Analysis


J.S. Coron and L. Goubin


Reference : Proceedings of CHES '00, Lecture Notes in Computer Science, Springer-Verlag, 2000

Abstract : Since the announcement of the Differential Power Analysis (DPA) by Paul Kocher and al., several countermeasures were proposed in order to protect software implementations of cryptographic algorithms. In an attempt to reduce the resulting memory and execution time overhead, Thomas Messerges recently proposed a general method that ``masks'' all the intermediate data. This masking strategy is possible if all the fundamental operations used in a given algorithm can be rewritten with masked input data, giving masked output data. This is easily seen to be the case in classical algorithms such as DES or RSA. However, for algorithms that combine Boolean and arithmetic functions, such as IDEA or several of the AES candidates, two different kinds of masking have to be used. There is thus a need for a method to convert back and forth between Boolean masking and arithmetic masking. In the present paper, we show that the `BooleanToArithmetic' algorithm proposed by T. Messerges is not sufficient to prevent Differential Power Analysis. In a similar way, the 'ArithmeticToBoolean' algorithm is not secure either.

Download : On Boolean and Arithmetic Masking against Differential Power Analysis


Statistics and secret leakage


J.S. Coron, P. Kocher and D. Naccache


Reference : Proceedings of Financial Cryptography '00, Lecture Notes in Computer Science, Springer-Verlag, 2000

Abstract : In addition to its usual complexity assumptions, cryptography silently assumes that information can be physically protected in a single location. As one can easily imagine, real-life devices are not ideal and information may leak through different physical channels. This paper gives a rigorous definition of leakage immunity and presents several leakage detection tests. In these tests, failure confirms the probable existence of secret-correlated emanations and indicates how likely the leakage is. Success does not refute the existence of emanations but indicates that significant emanations were not detectedl on the strength of the evidence presented, which of course, leaves the door open to reconsider the situation if further evidence comes to hand at a later date.

Download : Statistics and secret leakage


Resistance against Differential Power Analysis for elliptic curves cryptosystems


J.S. Coron


Reference : Proceedings of CHES '99, Lecture Notes in Computer Science, Springer-Verlag, 1999

Abstract : Differential Power Analysis, first introduced by Kocher et al., is a powerful technique allowing to recover secret smart card information by monitoring power signals. A specific DPA attack against smart-cards running the DES algorithm was described by Kocher. As few as 1000 encryptions were sufficient to recover the secret key. In this paper we generalize DPA attack to elliptic curve (EC) cryptosystems and describe a DPA on EC Diffie-Hellman key exchange and EC El-Gamal type encryption. Those attacks enable to recover the private key stored inside the smart-card. Moreover, we suggest countermeasures that thwart our attack.

Download : Resistance against Differential Power Analysis for elliptic curves cryptosystems


On the security of RSA screening


J.S. Coron and D. Naccache


Reference : Proceedings of PKC'99, Lecture Notes in Computer Science, Springer-Verlag, 1999

Abstract : Since many applications require the verification of large sets of signatures, it is sometimes advantageous to perform a simultaneous verification instead of checking each signature separately. The simultaneous processing, called batching, must be provably equivalent to the sequential verification of all signatures. In Eurocrypt'98, Bellare et al. presented a fast RSA batch verification scheme, called screening . Here we succesfully attack this algorithm by forcing it to accept a false signature and repair it by implementing an additional test.

Download : On the security of RSA screening


On the security of random sources


J.S. Coron


Reference : Proceedings of PKC '99, Lecture Notes in Computer Science, Springer-Verlag, 1999

Abstract : Many applications rely on the security of their random number generator. It is therefore essential that such devices be extensively tested for malfunction. The purpose of a statistical test is to detect certain kind of weaknesses a random generator may have. Maurer's universal test is a very common randomness test, capable of detecting a wide range of statistical defect. Maurer's test is based on the computation of a function which is asymptotically related to the source's entropy, which is known to be the correct quality measure of a random source. In this work we modify Maurer's universal test so that the test parameter is exactly the source's entropy, thereby enabling a more accurate detection of the defects in the tested random source.

Download : On the security of random sources


An accurate evaluation of maurer's universal test


J.S. Coron and D. Naccache


Reference : Proceedings of SAC'98, Lecture Notes in Computer Science, Springer-Verlag, 1998

Abstract : Maurer's universal test is a very common randomness test, capable of detecting a wide gamut of statistical defects. The algorithm is simple (a few Java code lines), flexible (a variety of parameter combinations can be chosen by the tester) and fast. Although the test is based on sound probabilistic grounds, one of its crucial parts uses the heuristic approximation: c(L,K) = 0.7 - 0.8/L + (1.6 + 12.8/L)K-4/L In this work we compute the precise value of c(L,K) and show that the inaccuracy due to the heuristic estimate can make the test 2.67 times more permissive than what is theoretically admitted. Moreover, we etablish a new asymptotic relation between the test parameter and the source's entropy.

Download : An accurate evaluation of maurer's universal test