Here is a list of my publications. Click on titles for abstracts and additionnal information.

1. Practical Key-recovery For All Possible Parameters of SFLASH (Asiacrypt'11)
   Charles Bouillaguet, Pierre-Alain Fouque, and Gilles Macario-Rat May 2011 hide

   • paper : [ PDF ]
   • MAGMA code of the attack : here.
   • Abstract :
     In this paper we present a new practical key-recovery attack on the SFLASH signature scheme. SFLASH is a derivative of the older C* encryption and signature scheme that was broken in 1995 by Patarin. In SFLASH, the public key is truncated, and this simple countermeasure prevents Patarin's attack. The scheme is well-known for having been considered secure and selected in 2004 by the NESSIE project of the European Union to be standardized. However, SFLASH was practically broken in 2007 by Dubois, Fouque, Stern and Shamir. Their attack breaks the original (and most relevant) parameters, but does not apply when more than half of the public key is truncated. It is therefore possible to choose parameters such that SFLASH is not broken by the existing attacks, although it is less efficient. We show a key-recovery attack that breaks the full range of parameters in practice, as soon as the information-theoretically required amount of information is available from the public-key. The attack uses new cryptanalytic tools, most notably pencils of matrices and quadratic forms.
2. Automatic Search of Attacks on round-reduced AES and Applications (Crypto'11)
   Charles Bouillaguet, Patrick Derbez and Pierre-Alain Fouque, August 2011 hide

   • paper : [ PDF ] (long version currently in preparation)
   • C code of some attack, and of the tool used to find them : here.
   • Abstract :
     In this paper, we describe versatile and powerful algorithms for searching guess-and-determine and meet-in-the-middle attacks on byte-oriented symmetric primitives. To demonstrate the strengh of these tool, we show that they allows to automatically discover new attacks on round-reduced AES with very low data complexity, and to find improved attacks on the AES-based MACs Alpha-MAC and Pelican-MAC, and also on the AES-based stream cipher LEX. Finally, the tools can be used in the context of fault attacks. These algorithms exploit the algebraically simple byte-oriented structure of the AES. When the attack found by the tool are practical, they have been implemented and validated.
3. New Insights on Impossible Differential Cryptanalysis (SAC'11)
   Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque and Gaëtan Leurent, August 2011 hide

   • paper : [ PDF ]
   • Abstract :
     Since its introduction, impossible differential cryptanalysis has been applied to many ciphers. Besides the specific application of the technique in various instances, there are some very basic results which apply to generic structures of ciphers, e.g., the well known 5-round impossible differential of Feistel ciphers with bijective round functions. In this paper we present a new approach for the construction and the usage of impossible differentials for Generalized Feistel structures. The results allow to extend some of the previous impossible differentials by one round (or more), answer an open problem about the ability to perform this kind of analysis, and tackle, for the first time the case of non-bijective round functions.
4. Low Data Complexity Attacks on AES (submitted)
   Charles Bouillaguet, Patrick Derbez, Orr Dunkelman, Nathan Keller, and Pierre-Alain Fouque, December 2010 hide

   • paper : [ PDF ]
   • Available on the eprint archive (report 2010/633).
   • The C code of some of the (practical) attacks is available here.
   • Abstract :
     The majority of current attacks on reduced-round variants of block ciphers seeks to maximize the number of rounds that can be broken, using less data than the entire codebook and less time than exhaustive key search. In this paper, we pursue a different approach, restricting the data available to the adversary to a few plaintext/ciphertext pairs. We show that consideration of such attacks (which received little atten- tion in recent years) serves an important role in assessing the security of block ciphers and of other cryptographic primitives based on block ci- phers. In particular, we show that these attacks can be leveraged to more complex attacks, either on the block cipher itself or on other primitives (e.g., stream ciphers, MACs, or hash functions) that use a small number of rounds of the block cipher as one of their components. As a case study, we consider the AES — the most widely used block cipher, whose round function is used in various cryptographic primitives. We present attacks on up to four rounds of AES that require at most 10 known/chosen plaintexts. We then apply these attacks to cryptanalyze a variant of the stream cipher LEX, and to mount a new known plaintext attack on 6-round AES.
5. Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial With One Secret Problem (PKC'11)
   Charles Bouillaguet, Jean-Charles Faugère, Pierre-Alain Fouque and Ludovic Perret, May 2010 hide

   • paper : [ PDF ]
   • Available on the eprint archive (report 2010/504).
   • MAGMA code of the algorithms : quadratic and cubic cases.
   • Abstract :
     This paper presents a practical cryptanalysis of the Identification Scheme proposed by Patarin at Crypto 1996. This scheme relies on the hardness of the Isomorphism of Polynomial with One Secret (IP1S), and enjoys shorter key than many other schemes based on the hardness of a combinatorial problem (as opposed to number-theoretic problems). Patarin proposed concrete parameters that have not been broken faster than exhaustive search so far. On the theoretical side, IP1S has been shown to be harder than Graph Isomorphism, which makes it an interesting target. We present two new deterministic algorithms to attack the IP1S problem, and we rigorously analyze their complexity and success probability. We show that they can solve a (big) constant fraction of all the instances of degree two in polynomial time. We verified that our algorithms are very efficient in practice. All the parameters with degree two proposed by Patarin are now broken in a few seconds. The parameters with degree three can be broken in less than a CPU-month. The identification scheme is thus quite badly broken.
6. Fast Exhaustive Search for Polynomial Systems in F_2 (CHES'10)
   Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir, and Bo-Yin Yang hide

   • paper (long version) : [ PDF ]
   • Full version available on the eprint archive (report 2010/313).
   • Abstract :
     We analyze how fast we can solve general systems of multivariate equations of various low degrees over GF_2 ; this is a well known hard problem which is important both in itself and as part of many types of algebraic cryptanalysis. Compared to the standard exhaustive search technique, our improved approach is more efficient both asymptotically and practically. We implemented several optimized versions of our techniques on CPUs and GPUs. Our technique runs more than 10 times faster on modern graphic cards than on the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a 500-dollar NVIDIA GTX 295 graphics card in 21 minutes. With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the computational power of GPUs in solving many types of combinatorial and cryptanalytic problems.
7. Security Analysis of SIMD (SAC'10)
   Charles Bouillaguet, Gaëtan Keurent and Pierre-Alain Fouque, August 2010 hide

   • paper : [ PDF ]
   • Full version available on the eprint archive (report 2010/323).
   • Abstract :
     In this paper we study the security of the SHA-3 candidate SIMD. We first show a new free-start distinguisher based on symmetry relations. It allows to distinguish the compression function of SIMD from a random function with a single evaluation. However, we also show that this property is very hard to exploit to mount any attack on the hash function because of the mode of operation of the compression function. Essentially, if one can build a pair of symmetric states, the symmetry property can only be triggered once. In the second part, we show that a class of free-start distinguishers is not a threat to the wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the hash function, and we still have a security proof for the SIMD hash function. Intuitively, the reason why this distinguisher does not weaken the function is that getting into a symmetric state is about as hard as finding a preimage. Finally, in the third part we study differential path in SIMD, and give an upper bound on the probability of related key differential paths. Our bound is in the order of 2^{-n/2} using very weak assumptions. Resistance to related key attacks is often overlooked, but it is very important for hash function designs.
8. Attacks on Hash Functions based on Generalized Feistel, Application to Reduced-Round Lesamnta and SHAvite-3/512 (SAC'10)
   Charles Bouillaguet, Orr Dunkelman, Gaëtan Keurent and Pierre-Alain Fouque, August 2010 hide

   • paper : [ PDF ]
   • Abstract :
     In this paper we study the strength of two hash functions which are based on Generalized Feistels. We describe a new kind of attack based on a cancellation property in the round function. This new technique allows to efficiently use the degrees of freedom available to attack a hash function. Using the cancellation property, we can avoid the non-linear parts of the round function, at the expense of some freedom degrees. Our attacks are mostly independent of the round function in use, and can be applied to similar hash functions which share the same structure but have different round functions. We start with a 22-round generic attack on the structure of Lesamnta, and adapt it to the actual round function to attack 24-round Lesamnta (the full function has 32 rounds). We follow with an attack on 9-round SHAvite-3/512 which also works for the tweaked version of SHAvite-3/512.
9. Practical Hash Functions Constructions Resistant to Generic Second Preimage Attacks Beyond the Birthday Bound (Submitted)
   Charles Bouillaguet and Pierre-Alain Fouque, June 2010 hide

   • paper : [ PDF ]
   • Abstract :
     Most cryptographic hash functions rely on a simpler primitive called a compression function, and in nearly all cases, there is a reduction between some of the security properties of the full hash function and those of the compression function. For instance, a celebrated result of Merkle and Damgaard from 1989 states that a collision on the hash function cannot be found without finding a collision on the compression function at the same time. This is however not the case for another basic requirement, namely second preimage resistance. In fact, on many popular hash functions it is possible to find a second preimage on the iteration without breaking the compression function. This paper studies the resistance of two practical modes of operations of hash functions against such attacks. We prove that the known generic second preimage attacks against the Merkle-Damgaard construction are optimal, and that there is no generic second preimage attack faster than exhaustive search on HAIFA, a recent proposal by Biham and Dunkelman.
10. Another Look at Complementation Properties (FSE'10)
    Charles Bouillaguet, Orr Dunkelman, Gaëtan Leurent and Pierre-Alain Fouque, February 2010 hide

    • paper : [ PDF ]
    • Abstract :

      In this paper we present a collection of attacks based on generalisations of the complementation property of DES. We find symmetry relations in the key schedule and in the actual rounds, and we use these symmetries to build distinguishers for any number of rounds when the relation is deterministic. This can be seen as a generalisation of the complementation property of DES or of slide/related-key attacks, using different kinds of relations. We further explore these properties, and show that if the relations have easily found fixed points, a new kind of attacks can be applied.

      Our main result is a self-similarity property on the Sha-3 candidate Lesamnta, which gives a very surprising result on its compression function. Despite the use of round constants which were designed to thwart any such attack, we show a distinguisher on the full compression function which needs only one query, and works for any number of rounds. We also show how to use this self-similarity property to find collisions on the full compression function of Lesamnta much faster than generic attacks. The main reason for this is the structure found in these round constants, which introduce an interesting and unexpected symmetry relation. This casts some doubt on the use of highly structured constants, as it is the case in many designs, including the AES and several Sha-3 candidates.

      Our second main contribution is a new related-key differential attack on round-reduced versions of the XTEA block-cipher. We exploit the weakness of the key-schedule to suggest an iterative related-key differential. It can be used to recover the secret key faster than exhaustive search using two related keys on 37 rounds. We then isolate a big class of weak keys for which we can attack 51 rounds out of the cipher's 64 rounds.

      We also apply our techniques to ESSENCE and PURE.

11. A Family of Weak Keys in HFE and the Corresponding Practical Key-Recovery (Journal of Mathematical Cryptology,2009)
    Charles Bouillaguet, Pierre-Alain Fouque, Antoine Joux and Joana Treger, June 2010 hide

    • paper : [ PDF ]
    • Available on the eprint, or on the site of the Journal
    • Abstract :
      The HFE (Hidden Field Equations) cryptosystem is one of the most interesting public-key multivariate scheme. It has been proposed more than 10 years ago by Patarin and seems to withstand the attacks that break many other multivariate schemes, since only subexponential ones have been proposed. The public key is a system of quadratic equations in many variables. These equations are generated from the composition of the secret elements: two linear mappings and a polynomial of small degree over an extension field. In this paper we show that there exist weak keys in HFE when the coefficients of the internal polynomial are defined in the ground field. In this case, we reduce the secret key recovery problem to an instance of the Isomorphism of Polynomials (IP) problem between the equations of the public key and themselves. Even though for schemes such as SFLASH or C^* the hardness of key-recovery relies on the hardness of the IP problem, this is normally not the case for HFE, since the internal polynomial is kept secret. However, when a weak key is used, we show how to recover all the components of the secret key in practical time, given a solution to an instance of the IP problem. This breaks in particular a variant of HFE proposed by Patarin to reduce the size of the public key and called the ``subfield variant''.
12. Herding, Second Preimage and Trojan Message Attacks Beyond Merkle-Damgaard (SAC'09)
    Elena Andreeva and Charles Bouillaguet and Orr Dunkelman and John Kelsey, July 2009 hide

    • Available on the Springer's website
    • paper : [ PDF ]
    • Abstract :
      In this paper we present new attack techniques to analyze the structure of hash functions that are not based on the classical Merkle-Damgaard construction. We extend the herding attack to concatenated hashes, and to certain hash functions that process each message block several times. Using this technique, we show a second preimage attack on the folklore ``hash-twice'' construction which process two concatenated copies of the message. We follow with showing how to apply the herding attack to tree hashes. Finally, we present a new type of attack --- the trojan message attack, which allows for producing second preimages of unknown messages (from a small known space) when they are appended with a fixed suffix.
13. Analysis of the Collision Resistance of RadioGatún using Algebraic Techniques (SAC'08)
    Charles Bouillaguet and Pierre-Alain Fouque, June 2008 hide

    • paper : [ PS, PDF ]
    • Abstract :
      In this paper, we present some preliminary results on the security of the RadioGatún hash function. RadioGatún has an internal state of 58 words, and is parameterized by the word size, from one to 64 bits. We study the one-bit version of RadioGatún since according to the authors, attacks on this version also affect the reasonably-sized versions. On this toy version, we revisit the claims of the designers and first improve some results. Secondly, given a differential path, we show how to find a message pairs colliding more efficiently than the strategy proposed by the authors using algebraic techniques. We experimented this strategy on the one-bit version since we can efficiently find differential path by brute force. Even though the complexity of this collision attack is higher than the general security claim on RadioGatún[1], it is still less than the birthday paradox on the size of the internal state.
14. Second Preimage Attacks on Dithered Hash Functions (submitted + EUCROCRYPT'08)
    Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan Hoch, John Kelsey, Adi Shamir and Sebastien Zimmer, April 2008 hide

    • A longer version [ PDF ] has been submitted to a journal
      
    • Accepted in EUROCRYPT'08 [ PS, PDF ]
      
    • Available on the ePrint and on Springer's website
    • Abstract :
      In this work we present new generic second preimage attacks on hash functions. Our first attack is based on the herding attack, and applies to various Merkle-Damgård-based iterative hash functions. Compared to the previously known long-message second preimage attacks, our attack adds only a small computational overhead. In exchange, our attack gives the adversary a much greater control over the contents of the second message and in particular allows all the difference to be concentrated in a few message blocks. As a result, the new second preimage attack is applicable to hash function constructions such as the dithered hash proposal of Rivest, Shoup's UOWHF, and the ROX hash construction, which were thought to be immune to the earlier known second preimage attacks. We also suggest a few time-memory-data tradeoff variants for this type of attacks, allowing for faster online computations, and attacking significantly shorter messages. Furthermore, we analyze the properties of the dithering sequence used in Rivest's hash function proposal, and develop a time-memory tradeoff which allows us to apply our second preimage attack to a much stronger than those in Rivest's proposals. Parts of our results rely on the kite generator, a new time-memory tradeoff tool. We also exhibit a time-memory-data tradeoff attack on tree hashes for second preimages. Finally, we show how both the existing second preimage attacks and our new attacks can be applied even more effiently when given multiple short target messages rather than a single long target message.
15. Sécurité et preuves de sécurité des fonctions de hachage (Master's thesis, in french)
    Charles Bouillaguet, September 2007 hide

    • Master's thesis : [ PS, PDF ]
      
    • Also see the presentations list
16. Using First-Order Theorem Provers in the Jahob Data Structure Verification System (VMCAI'07)
    Charles Bouillaguet, Viktor Kuncak, Thomas Wies, Karen Zee and Martin Rinard, January 2007 hide

    • Long version : [ PS, PDF ]
    • Tech report : [ PS, PDF ]
      
    • Also see the presentations list
    • Abstract :

      This paper presents our integration of efficient resolution-based theorem provers into the Jahob data structure verification system. Our experimental results show that this approach enables Jahob to automatically verify the correctness of a range of complex dynamically instantiable data structures, including data structures such as hash tables and search trees, without the need for interactive theorem proving or techniques tailored to individual data structures.

      Our primary technical results include: (1) a translation from higher-order logic to first-order logic that enables the application of resolution-based theorem provers and (2) a proof that eliminating type (sort) information in formulas is both sound and complete, even in the presence of a generic equality operator. Moreover, our experimental results show that the elimination of this type information dramatically decreases the time required to prove the resulting formulas.

      These techniques enabled us to verify complex correctness properties of Java programs such as a mutable set implemented as an imperative linked list, a finite map implemented as a functional ordered tree, a hash table with a mutable array, and a simple library system example that uses these container data structures. Our system verifies (in a matter of minutes) that data structure operations correctly update the finite map, that they preserve data structure invariants (such as ordering of elements, membership in appropriate hash table buckets, or relationships between sets and relations), and that there are no run-time errors such as null dereferences or array out of bounds accesses.