## Jean-Sébastien Coron

### Journal papers

- Practical Cryptanalysis of ISO 9796-2 and EMV Signatures (Journal of Cryptology, 2016)
- How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction (Journal of Cryptology, 2016)
- A Note on the Bivariate Coppersmith Theorem (Journal of Cryptology, 2013)
- Cryptanalysis of ISO/IEC 9796-1 (Journal of Cryptology, 2008)
- Deterministic Polynomial-Time Equivalence of Computing the RSA Secret Key and Factoring (Journal of Cryptology, 2007)
- Index Calculation Attacks on RSA Signature and Encryption (Designs, Codes and Cryptography, 2006)

### International Conference papers

- Cryptanalysis of GGH15 Multilinear Maps (Crypto 2016)
- Zeroizing Without Low-Level Zeroes: New MMAP Attacks and Their Limitations (Crypto 2015)
- New Multilinear Maps over the Integers (Crypto 2015)
- Higher Order Masking of Look-Up Tables (Eurocrypt 2014)
- Practical Multilinear Maps over the Integers (Crypto 2013)
- Batch Fully Homomorphic Encryption over the Integers (Eurocrypt 2013)
- Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers (Eurocrypt 2012)
- Fully Homomorphic Encryption over the Integers with Shorter Public Keys (Crypto 2011)
- Improved Generic Algorithms for Hard Knapsacks (Eurocrypt 2011)
- Efficient Indifferentiable Hashing into Ordinary Elliptic Curves (Crypto 2010)
- PSS is Secure against Random Fault Attacks (Asiacrypt 2009)
- Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures (Crypto 2009)
- The Random Oracle Model and the Ideal Cipher Model are Equivalent (Crypto 2008)
- Finding Small Roots of Bivariate Integer Polynomial Equations: a Direct Approach (Crypto 2007)
- Merkle-Damgard Revisited: how to construct a hash-function (Crypto 2005)
- Finding small roots of bivariate integer equations revisited (Eurocrypt 2004)
- Boneh et al's k-Element Aggregate Extraction Assumption Is Equivalent to The Diffie-Hellman Assumption (Asiacrypt 2003)
- Security Proof for Partial-Domain Hash Signature Schemes (Crypto '02)
- Universal padding schemes for RSA (Crypto '02)
- Optimal security proofs for PSS and other signature schemes (Eurocrypt '02)
- Cryptanalysis of RSA signatures with fixed pattern padding (Crypto '01)
- From fixed-length to arbitrary length RSA padding schemes (Asiacrypt '00)
- On the exact security of Full Domain Hash (Crypto 2000)
- Security analysis of the Gennaro-Halevi-Rabin signature scheme (Eurocrypt 2000)
- New attacks on PKCS#1 v1.5 encryption (Eurocrypt 2000)
- Elliptic Curve Cryptography : do we need to count ? (Asiacrypt '99)
- On the security of RSA padding (Crypto '99)

### International Workshop papers

- Faster Evaluation of SBoxes via Common Shares (CHES 2016)
- Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking Scheme (CHES 2016)
- Factoring N=p^r q^s for Large r and s (CT-RSA 2016)
- Improved Side-Channel Analysis of Finite-Field Multiplication (CHES 2015)
- Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity (FSE 2015)
- Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-channel Countermeasures (CHES 2014)
- Secure Conversion between Boolean and Arithmetic Masking of Any Order (CHES 2014)
- Scale-Invariant Fully Homomorphic Encryption over the Integers (PKC 2014)
- Higher-Order Side Channel Security and Mask Refreshing (FSE 2013)
- Supplemental Access Control (PACE v2): Security Analysis of PACE Integrated Mapping (Cryptography and Security 2012)
- On the Use of Shamir's Secret Sharing against Side-Channel Analysis (CARDIS 2012)
- Conversion of Security Proofs from One Leakage Model to Another: A New Issue (COSADE 2012)
- Cryptanalysis of the RSA Subgroup Assumption from TCC 2005 (PKC 2011)
- Analysis and Improvement of the Random Delay Countermeasure of CHES 2009 (CHES 2010)
- A Domain Extender for the Ideal Cipher (TCC 2010)
- Fault Attacks Against EMV Signatures (CT-RSA 2010)
- Fault Attacks on RSA Signatures with Partially Unknown Messages (CHES 2009)
- An Efficient Method for Random Delay Generation in Embedded Software (CHES 2009)
- A New DPA Countermeasure Based on Permutation Tables (SCN 2008)
- Attack and Improvement of a Secure S-Box Calculation Based on the Fourier Transform (CHES 2008)
- Side Channel Cryptanalysis of a High Order Masking Scheme (CHES 2007)
- On the Implementation of a Fast Prime Generation Algorithm (CHES 2007)
- A New Baby-Step Giant-Step Algorithm and Some Applications to Cryptanalysis (CHES 2005)
- Cryptanalysis of a Zero-Knowledge Identification Protocol of Eurocrypt '95 (CT-RSA 2004)
- A New Algorithm for Switching from Arithmetic to Boolean Masking (CHES '03)
- Optimal Chosen-Ciphertext Secure Encryption of Arbitrary-Length Messages (PKC '02)
- GEM: a Generic Chosen-Ciphertext Secure Encryption Method (CT-RSA '02)
- Fast Generation of Pairs (k, [k]P) for Koblitz Elliptic Curves (SAC '01)
- Differential Power Analysis in the Presence of Hardware Countermeasures (CHES '00)
- On Boolean and Arithmetic Masking against Differential Power Analysis (CHES '00)
- Statistics and secret leakage (Financial Crypto '00)
- Resistance against Differential Power Analysis for elliptic curves cryptosystems (CHES '99)
- On the security of RSA screening (PKC '99)
- On the security of random sources (PKC '99)
- An accurate evaluation of maurer's universal test (SAC '98)

### Ph.D. thesis :

### Habilitation thesis :

Practical Cryptanalysis of ISO 9796-2 and EMV Signatures

### Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann

**Reference :**Journal of Cryptology, Volume 29, Number 3, 2016

**Abstract :**At Crypto 1999, Coron, Naccache and Stern described an existential signature forgery against two popular RSA signature standards, ISO 9796-1 and ISO 9796-2. Following this attack, ISO 9796-1 was withdrawn, and ISO 9796-2 was amended by increasing the message digest to at least 160 bits. In this paper, we describe an attack against the amended version of ISO 9796-2, for all modulus sizes. Our new attack is based on Bernstein's algorithm for detecting smooth numbers, instead of trial division. In practice, we were able to compute a forgery in only 2 days on a network of 19 servers. Our attack can also be extended to EMV signatures, an ISO 9796-2-compliant format with extra redundancy. In response to this new attack, the ISO 9796-2 standard was amended again in late 2010.

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

How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction

### Jean-Sebastien Coron, Thomas Holenstein, Robin Kunzler, Jacques Patarin, Yannick Seurin and Stefano Tessaro

**Reference :**Journal of Cryptology, 2016

**Abstract :**This paper provides the first provably secure construction of an invertible random permutation (and of an ideal cipher) from a public random function that can be evaluated by all parties in the system, including the adversary. The associated security goal was formalized via the notion of indifferentiability by Maurer et al. (TCC 2004). The problem is the natural extension of that of building (invertible) random permutations from (private) random functions, first solved by Luby and Rackoff (SIAM J Comput 17(2):373-386, 1988) via the four-round Feistel construction. As our main result, we prove that the Feistel construction with fourteen rounds is indifferentiable from an invertible random permutation. We also provide a new lower bound showing that five rounds are not sufficient to achieve indifferentiability. A major corollary of our result is the equivalence (in a well-defined sense) of the random oracle model and the ideal cipher model.

**Download :**How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction

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

Cryptanalysis of GGH15 Multilinear Maps

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

**Reference :**Proceedings of Crypto 2016, LNCS, 2016

**Abstract :**We describe a cryptanalysis of the GGH15 multilinear maps. Our attack breaks the multipartite key-agreement protocol in polynomial time by generating an equivalent user private key; it also applies to GGH15 with safeguards. We also describe attacks against variants of the GGH13 multilinear maps proposed by Halevi (ePrint 2015/866) aiming at supporting graph-induced constraints, as in GGH15.

**Download :**Cryptanalysis of GGH15 Multilinear Maps

Zeroizing Without Low-Level Zeroes: New MMAP Attacks and Their Limitations

### J.S. Coron, C. Gentry, S. Halevi, T. Lepoint H. K. Maji, E. Miles, M. Raykova, A. Sahai and Mehdi Tibouchi

**Reference :**Proceedings of CRYPTO 2015, LNCS, 2015

**Abstract :**We extend the recent zeroizing attacks of Cheon, Han, Lee, Ryu and Stehle (Eurocrypt'15) on multilinear maps to settings where no encodings of zero below the maximal level are available. Some of the new attacks apply to the CLT13 scheme (resulting in a total break) while others apply to (a variant of) the GGH13 scheme (resulting in a weak-DL attack). We also note the limits of these zeroizing attacks.

**Download :**Zeroizing Without Low-Level Zeroes: New MMAP Attacks and Their Limitations

New Multilinear Maps over the Integers

### Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi

**Reference :**Proceedings of CRYPTO 2015, LNCS, 2015

**Abstract :**In the last few years, cryptographic multilinear maps have proved their tremendous potential as building blocks for new constructions, in particular the first viable approach to general program obfuscation. After the first candidate construction by Garg, Gentry and Halevi (GGH) based on ideal lattices, a second construction over the integers was described by Coron, Lepoint and Tibouchi (CLT). However the CLT scheme was recently broken by Cheon et al.; the attack works by computing the eigenvalues of a diagonalizable matrix over Q derived from the multilinear map. In this paper we describe a new candidate multilinear map over the integers. Our construction is based on CLT but with a new arithmetic technique that makes the zero-testing element non-linear in the encoding, which prevents the Cheon et al. attack. Our new construction is relatively practical as its efficiency is comparable to the original CLT scheme. Moreover the subgroup membership and decisional linear assumptions appear to hold in the new setting.

**Download :**New Multilinear Maps over the Integers

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

Faster Evaluation of SBoxes via Common Shares

### Jean-Sebastien Coron , Aurelien Greuet, Emmanuel Prouff and Rina Zeitoun

**Reference :**Proceedings of CHES 2016, LNCS, 2016

**Abstract :**We describe a new technique for improving the efficiency of the masking countermeasure against side-channel attacks. Our technique is based on using common shares between secret variables, in order to reduce the number of finite field multiplications. Our algorithms are proven secure in the ISW probing model with n >= t+1 shares against t probes. For AES, we get an equivalent of 2.8 non-linear multiplications for every SBox evaluation, instead of 4 in the Rivain-Prouff countermeasure. We obtain similar improvements for other block-ciphers. Our technique is easy to implement and performs relatively well in practice, with roughly a 20 % speed-up compared to existing algorithms.

**Download :**Faster Evaluation of SBoxes via Common Shares

Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking Scheme

### Alberto Battistello, Jean-Sebastien Coron, Emmanuel Prouff and Rina Zeitoun

**Reference :**Proceedings of CHES 2016, LNCS, 2016

**Abstract :**A common countermeasure against side-channel attacks consists in using the masking scheme originally introduced by Ishai, Sahai and Wagner (ISW) at Crypto 2003, and further generalized by Rivain and Prouff at CHES 2010. The countermeasure is provably secure in the probing model, and it was showed by Duc, Dziembowski and Faust at Eurocrypt 2014 that the proof can be extended to the more realistic noisy leakage model. However the extension only applies if the leakage noise increases at least linearly with the masking order, which is not necessarily possible in practice. In this paper we investigate the security of an implementation when the previous condition is not satisfied, for example when the masking order increases for a constant noise. We exhibit two (template) horizontal side-channel attacks against the Rivain-Prouff’s secure multiplication scheme and we analyze their efficiency thanks to several simulations and experiments. Eventually, we describe a variant of Rivain-Prouff’s multiplication that is still provably secure in the original ISW model, and also heuristically secure against our new attacks.

**Download :**Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking Scheme

Factoring N=p^r q^s for Large r and s

### J.S. Coron, J.C. Faugere, G. Renault and R. Zeitoun

**Reference :**Proceedings of CT-RSA 2016, LNCS, 2016

**Abstract :**Boneh et al. showed at Crypto 99 that moduli of the form N=p^r q can be factored in polynomial time when r=log p. Their algorithm is based on Coppersmith's technique for finding small roots of polynomial equations. In this paper we show that N=p^r q^s can also be factored in polynomial time when r or s is at least (log p)^3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli N with k prime factors; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the k exponents is large enough.

**Download :**Factoring N=p^r q^s for Large r and s

Improved Side-Channel Analysis of Finite-Field Multiplication

### S. Belaid, J.S. Coron, P.A. Fouque, B. Gerard, J.G. Kammerer and E. Prouff

**Reference :**Proceedings of CHES 2015, LNCS, 2015

**Abstract :**A side-channel analysis of multiplication in GF(2^{128}) has recently been published by Belaid, Fouque and Gerard at Asiacrypt 2014, with an application to AES-GCM. Using the least significant bit of the Hamming weight of the multiplication result, the authors have shown how to recover the secret multiplier efficiently. However such least significant bit is very sensitive to noise measurement; this implies that without averaging their attack can only work for high signal-to-noise ratios (SNR > 128). In this paper we describe a new side-channel attack against the multiplication in GF(2^{128}) that uses the most significant bits of the Hamming weight. We show that much higher values of noise can be then tolerated. For instance with an SNR equal to 8, the key can be recovered using 2^{20} consumption traces with time and memory complexities respectively equal to 2^{51.68} and 2^{36}. We moreover show that the new method can be extended to attack the fresh re-keying countermeasure proposed by Medwed, Standaert, Groszschadl and Regazzoni at Africacrypt 2010.

**Download :**Improved Side-Channel Analysis of Finite-Field Multiplication

Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity

### Jean-Sebastien Coron and Johann Groszschaedl and Praveen Kumar Vadnala and Mehdi Tibouchi

**Reference :**Proceedings of FSE 2015, LNCS, 2015

**Abstract :**A general method to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with O(k) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity O(log k) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in O(log k) instead of O(k) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo 2^k directly on Boolean shares, with the same complexity O(log k) instead of O(k). We prove the security of our new algorithms against first-order attacks.

**Download :**Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity

Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-channel Countermeasures

### Jean-Sebastien Coron and Arnab Roy and Srinivas Vivek

**Reference :**Proceedings of CHES 2014, LNCS, 2014

**Abstract :**We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite field. In practice we can evaluate any 8-bit S-box in 10 non-linear multiplications instead of 16 in the Roy-Vivek paper from CHES 2013, and the DES S-boxes in 4 non-linear multiplications instead of 7. We also evaluate any 4-bit S-box in 2 non-linear multiplications instead of 3. Hence our method achieves optimal complexity for the PRESENT S-box.

**Download :**Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-channel Countermeasures

Secure Conversion between Boolean and Arithmetic Masking of Any Order

### Jean-Sebastien Coron, Johann Groszschadl, Praveen Kumar Vadnala

**Reference :**Proceedings of CHES 2014, LNCS, 2014

**Abstract :**An effective countermeasure against side-channel attacks is to mask all sensitive intermediate variables with one (or more) random value(s). When a cryptographic algorithm involves both arithmetic and Boolean operations, it is necessary to convert from arithmetic masking to Boolean masking and vice versa. At CHES 2001, Goubin introduced two algorithms for secure conversion between arithmetic and Boolean masks, but his approach can only be applied to first-order masking. In this paper, we present and evaluate new conversion algorithms that are secure against attacks of any order. To convert masks of a size of k bits securely against attacks of order n, the proposed algorithms have a time complexity in both directions and are proven to be secure in the Ishai, Sahai, and Wagner (ISW) framework for private circuits. We evaluate our algorithms using HMAC-SHA-1 as example and report the execution times we achieved on a 32-bit AVR microcontroller.

**Download :**Secure Conversion between Boolean and Arithmetic Masking of Any Order

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

Higher-Order Side Channel Security and Mask Refreshing

### Jean-Sebastien Coron and Emmanuel Prouff and Matthieu Rivain and Thomas Roche

**Reference :**Proceedings of FSE 2013, LNCS, 2013

**Abstract :**Masking is a widely used countermeasure to protect block cipher implementations against side-channel attacks. The principle is to split every sensitive intermediate variable occurring in the computation into d + 1 shares, where d is called the masking order and plays the role of a security parameter. A masked implementation is then said to achieve dth-order security if any set of d (or less) intermediate variables does not reveal key-dependent information. At CHES 2010, Rivain and Prouff have proposed a higher-order masking scheme for AES that works for any arbitrary order d. This scheme, and its subsequent extensions, are based on an improved version of the shared multiplication processing published by Ishai et al. at CRYPTO 2003. This improvement enables better memory/timing performances but its security relies on the refreshing of the masks at some points in the algorithm. In this paper, we show that the method proposed at CHES 2010 to do such mask refreshing introduces a security flaw in the overall masking scheme. Specically, we show that it is vulnerable to an attack of order d/2 + 1 whereas the scheme is supposed to achieve dth-order security. After exhibiting and analyzing the flaw, we propose a new solution which avoids the use of mask refreshing, and we prove its security. We also provide some implementation trick that makes our proposed solution, not only secure, but also faster than the original scheme.

**Download :**Higher-Order Side Channel Security and Mask Refreshing

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