Publications
Click on titles for abstracts and additional information. Alternatively, look at my entry in DBLP.
Charles Bouillaguet (Tr. math. Soft.)
Evaluating a Boolean polynomial on all possible inputs (i.e. building the truth table of the corresponding Boolean function) is a simple computational problem that sometimes appears inside broader applications, for instance in cryptanalysis or in the implementation of more sophisticated algorithms to solve Boolean polynomial systems.
Two techniques share the crown to perform this task: the “Fast Exhaustive Search” (FES) algorithm from 2010 (which is based on Gray Codes) and the space-efficient Moebius transform from 2021 (which is reminiscent of the FFT). Both require operations for a degree- Boolean polynomial on variables and operate mostly in-place, but have other slightly different characteristics. They both provide an efficient iterator over the full truth table.
This article describes BeanPolE (BoolEAN POLynomial Evaluation), a concise and flexible C library that implements both algorithms, as well as many other functions to deal with Boolean multivariate polynomials in dense representation.
Charles Bouillaguet and Julia Sauvage (Comm. in Crypto.)
Biscuit is a recent multivariate signature scheme based on the MPC-in-the-Head paradigm. It has been submitted to the NIST competition for additional signature schemes. Signatures are derived from a zero-knowledge proof of knowledge of the solution of a structured polynomial system. This extra structure enables efficient proofs and compact signatures. This short note demonstrates that it also makes these polynomial systems easier to solve than random ones. As a consequence, the original parameters of Biscuit failed to meet the required security levels and had to be upgraded.
Charles Bouillaguet, Florette Martinez and Damien Vergnaud (MFCS'23)
We present attacks on a generalized subset-sum pseudorandom generator, which was proposed by von zur Gathen and Shparlinski in 2004. Our attacks rely on a sub-quadratic algorithm for solving a vectorial variant of the 3SUM problem, which is of independent interest. The attacks presented have complexities well below the brute-force attack, making the generators vulnerable. We provide a thorough analysis of the attacks and their complexities and demonstrate their practicality through implementations and experiments.
Ibrahim Buba Garba, Tommaso Morresi, Charles Bouillaguet, Michele Casula and Lorenzo Paulatto (Journal of Physics: Condensed Matter)
We present a robust reciprocal-space implementation of the temperature-dependent effective potential method, our implementation can scale easily to large cell and long sampling time. It is interoperable with standard ab-initio molecular dynamics and with Langevin dynamics. We prove that both sampling methods can be efficient and accurate if a thermostat is used to control temperature and dynamics parameters are used to optimise the sampling efficiency. By way of example, we apply it to study anharmonic phonon renormalization in weakly and strongly anharmonic materials, reproducing the temperature effect on phonon frequencies, crossing of phase transition and stabilization of high-temperature phases.
Charles Bouillaguet, Ambroise Fleury, Pierre-Alain Fouque and Paul Kirchner (Asiacrypt'23)
The Number Field Sieve (NFS) is the state-of-the art algorithm for integer factoring, and sieving is a crucial step in the NFS. It is a very time-consuming operation, whose goal is to collect many relations. The ultimate goal is to generate random smooth integers mod N with their prime decomposition, where smooth is defined on the rational and algebraic sides according to two prime factor bases.
In modern factorization tool, such as Cado-NFS, sieving is split into different stages depending on the size of the primes, but defining good parameters for all stages is based on heuristic and practical arguments. At the beginning, candidates are sieved by small primes on both sides, and if they pass the test, they continue to the next stages with bigger primes, up to the final one where we factor the remaining part using the ECM algorithm. On the one hand, first stages are fast but many false relations pass them, and we spend a lot of time with useless relations. On the other hand final stages are more time demanding but outputs less relations. It is not easy to evaluate the performance of the best strategy on the overall sieving step since it depends on the distribution of numbers that results at each stage.
In this article, we try to examine different sieving strategies to speed up this step since many improvements have been done on all other steps of the NFS. Based on the relations collected during the RSA-250 factorization and all parameters, we try to study different strategies to better understand this step. Many strategies have been defined since the discovery of NFS, and we provide here an experimental evaluation.
Charles Bouillaguet (RESSI 2023)
Links: PDF HAL ScienceConf
Ce court article décrit mes tentatives de réalisation de plate-formes en ligne pour la réalisation de travaux pratiques de cryptologie par des étudiants de master.
Charles Bouillaguet (unpublished)
This article gives improved algorithms to evaluate a multivariate Boolean polynomial over all the possible values of its input variables. Such a procedure is often used in cryptographic attacks against symmetric schemes. More precisely, we provide improved and simplified versions of the Fast Exhaustive Search algorithm presented at CHES'10 and of the space-efficient Moebius transform given by Dinur at EUROCRYPT'21. The new algorithms require $\mathcal{O}(d2^n)$ operations with a degree-d polynomial and operate in-place. We provide the full C code of a complete implementation under the form of a "user-friendly" library called BeanPolE, which we hope could be helpful to other cryptographers. This paper actually contains all the code, which is quite short.
Charles Bouillaguet (Mathematical Cryptology)
Public-key cryptographic primitives involve mathematical operations that are computationally intensive for devices with limited resources. A typical approach is to offload time-consuming operations from a (computationally weak) client device to an untrusted yet computationally powerful server. Such a delegation protocol needs to achieve the privacy of the server’s inputs. Recently, Tian, Yu, Zhang, Xue, Wang and Ren [IEEE Trans. Serv. Comput., vol. 15, no. 1, pp. 241–253, 2022] proposed a unimodular matrix transformation technique to realize secure outsourcing of modular inversion. We present an elementary cryptanalysis of their protocol and prove that it does not achieve the claimed security guarantees.
Charles Bouillaguet, Claire Delaplace and Antoine Joux (unpublished)
We present algorithms for variants of the 3XOR problem with lists consisting of random sparse $n$-bit vectors. We consider two notions of sparsity: low-density (each bit is independently biased towards zero) and low-weight (the Hamming weight of $n$-bit vectors is fixed).
We show that the random sparse 3XOR problem can be solved in strongly subquadratic time, namely less than $\mathcal{O}\left(N^{2-\epsilon}\right)$ operations for a constant $\epsilon > 0$. This stands in strong contrast with the regular case, where it has not been possible to have the exponent drop below $2 - o(1)$.
In the low-density setting, a very simple algorithm even runs in linear time with overwhelming success probability when the density is less than $0.0957$. Our algorithms exploit the randomness (and sparsity) of the input in an essential way.
Charles Bouillaguet, Claire Delaplace and Monika Trimoska (SOSA'22)
This article discusses a simple deterministic algorithm for solving quadratic Boolean systems which is essentially a special case of more sophisticated methods. The main idea fits in a single sentence: guess enough variables so that the remaining quadratic equations can be solved by linearization (i.e. by considering each remaining monomial as an independent variable and solving the resulting linear system). Under strong heuristic assumptions, this finds all the solutions of $m$ quadratic polynomials in $n$ variables with $\mathcal{\tilde O}\left(2^{n-\sqrt{2m}}\right)$ operations. Although the best known algorithms require exponentially less time, the present technique has the advantage of being simpler to describe and easy to implement. In strong contrast with the state-of-the-art, it is also quite efficient in practice.Mellila Bouam, Charles Bouillaguet, Claire Delaplace and Camille Noûs (Parallel Computing)
Links: HAL DOI PDF Code (3XOR) Code (modifier CGminer)
SHA-256 is a secure cryptographic hash function. As such, its output should not have any detectable property. This paper describes three bit strings whose hashes by SHA-256 are nevertheless correlated in a non-trivial way: the first half of their hashes XORs to zero. They were found by ``brute-force'', without exploiting any cryptographic weakness in the hash function itself. This does not threaten the security of the hash function and does not have any cryptographic implication.
This is an example of a large ``combinatorial'' computation in which at least $8.3\times 10^{22}$ integer operations have been performed. This was made possible by the combination of: 1) recent progress on algorithms for the underlying problem, 2) creative use of ``dedicated'' hardware accelerators, 3) adapted implementations of the relevant algorithms that could run on massively parallel machines.
The actual computation was done on aging hardware. It required 7 calendar months using two obsolete second-hand bitcoin mining devices converted into ``useful'' computational devices. A second step required 570 CPU-years on an 8-year old IBM BlueGene/Q computer, a few weeks before it was scrapped.
To the best of our knowledge, this is the first practical 128-bit collision-like result obtained by brute-force. It is the first bitcoin-accelerated computation and it is also one of the largest public ones.
Charles Bouillaguet, Damien Vergnaud and Florette Martinez (The Computer Journal)
Public-key cryptographic primitives are time-consuming for resource-constrained devices. A classical problem is to securely offload group exponentiations from a (comparatively) weak device — the client — to an untrusted more powerful device — the server. A delegation protocol must usually meet two security ob- jectives: privacy – the exponent or the base should not be revealed to a passive adversary — and verifiability — a malicious server should not be able to make the client accept an invalid value as the result of the delegated computation. Most proposed protocols relies on a secret splitting of the exponent and the base and a considerable amount of literature has been devoted to their analysis. Recently, Su, Zhang and Xue [The Computer Journal, 2020] and Rangasamy and Kuppusamy [Indocrypt 2018] proposed outsourcing protocols for modular exponentiations. They claim that their protocols achieve security (privacy and verifiability). We show that these claims are flawed and that their schemes are broken beyond repair. They remain insecure even if one increases significantly the proposed parameters (and consequently the protocols computational and communication complexities). Our attacks rely on standard lattice-based crypt- analytic techniques, namely the Coppersmith methods to find small integer zeroes of modular multivariate polynomials and simultaneous Diophantine approxima- tion methods for the so-called approximate greatest common divisor problem.Charles Bouillaguet and Paul Zimmermann (Mathematical Crypto.)
Links: HAL PDF Open-Access
This article describes a parallel algorithm for the Structured Gaussian Elimination step of the Number Field Sieve (NFS). NFS is the best known method for factoring large integers and computing discrete logarithms. State-of-the-art algorithms for this kind of partial sparse elimination, as implemented in the CADO-NFS software tool, were unamenable to parallel implementations. We therefore designed a new algorithm from scratch with this objective and implemented it using OpenMP. The result is not only faster sequentially, but scales reasonably well: using 32 cores, the time needed to process two landmark instances went down from 38 minutes to 20 seconds and from 6.7 hours to 2.3 minutes, respectively.
Charles Bouillaguet, Florette Martinez and Julia Sauvage (Tr. on Symmetric Crypto)
Links: HAL DOI PDF code Results
The Permuted Congruential Generators (PCG) are popular conventional (non-cryptographic) pseudo-random generators designed in 2014. They are used by default in the NumPy scientific computing package. Even though they are not of cryptographic strength, their designer stated that predicting their output should be nevertheless be "challenging".
In this article, we present a practical algorithm that recovers all the hidden parameters and reconstructs the successive internal states of the generator. This enables us to predict the next ``random'' numbers, and output the seeds of the generator. We have successfully executed the reconstruction algorithm using 512 bytes of challenge input; in the worst case, the process takes 20 000 CPU hours.
This reconstruction algorithm makes use of cryptanalytic techniques, both symmetric and lattice-based. In particular, the most computationally expensive part is a guess-and-determine procedure that solves about $2^{52}$ instances of the Closest Vector Problem on a very small lattice.
Charles Bouillaguet, Claire Delaplace and Pierre-Alain Fouque (Tr. on Symmetric Crypto)
The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. We study the 3XOR variant which is more cryptologically relevant. In this problem, the attacker is given black-box access to three random functions $F, G$ and $H$ and she has to find three inputs $x, y$ and $z$ such that $F(x) \oplus G(y) \oplus H(z) = 0$. The 3XOR problem is a difficult case of the more-general $k$-list birthday problem.
Wagner's celebrated $k$-list birthday algorithm, and the ones inspired by it, work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives some leeway to target a solution of a specific form, at the expense of processing a huge amount of data.
However, to handle such a huge amount of data can be very difficult in practice. This is why we first restricted our attention to solving the 3XOR problem for which the total number of queries to $F$, $G$ and $H$ is minimal. If they are $n$-bit random functions, it is possible to solve the problem with roughly $\mathcal{O}\left(2^{n/3}\right)$ queries. In this setting, the folklore quadratic algorithm finds a solution after $\mathcal{O}\left(2^{2n/3}\right)$ operations.
We present a 3XOR algorithm that generalizes an idea of Joux, with complexity $\mathcal{O}\left(2^{2n/3} / n\right)$ in times and $\mathcal{O}\left(2^{n/3}\right)$ in space. This algorithm is practical: it is up to $3\times$ faster than the quadratic algorithm. Furthermore, using Bernstein's ‘‘clamping trick'', we show that it is possible to adapt this algorithm to any number of queries, so that it will always be at least as good as, if not better than, Wagner's descendants in the same settings.
We also revisit a 3SUM algorithm by Baran-Demaine-P\v{a}tra\c scu which is asymptotically $n^2 / \log^2 n$ times faster than the quadratic algorithm when adapted to the 3XOR problem, but is otherwise completely impractical.
To gain a deeper understanding of these problems, we embarked on a project to solve actual 3XOR instances for the SHA256 hash function. We believe that this was very beneficial and we present practical remarks, along with a 96-bit 3XOR for SHA256.
Charles Bouillaguet, Claire Delaplace and Marie-Emilie Voge (PASCO'17)
In this paper, we present the results of our experiments to compute the rank of several large sparse matrices from Dumas's Sparse Integer Matrix Collection, by computing sparse PLUQ factorizations.
Our approach consists in identifying as many pivots as possible before performing any arithmetic operation, based solely on the location of non-zero entries in the input matrix. These ``structural'' pivots are then all eliminated in parallel, in a single pass. We describe several heuristic structural pivot selection algorithms (the problem is NP-hard).
These algorithms allows us to compute the ranks of several large sparse matrices in a few minutes, versus many days using Wiedemann's algorithm. Lastly, we describe a multi-thread implementation using OpenMP achieving 70% parallel efficiency on 24 cores on the largest benchmark.
Charles Bouillaguet, Claire Delaplace, Pierre-Alain Fouque and Paul Kirchner (PQ Crypto)
Links: PDF HAL Springer Github
The SPRING pseudo-random function (PRF) has been described by Banerjee, Brenner, Leurent, Peikert and Rosen at FSE 2014. It is quite fast, only 4.5 times slower than the AES (without hardware acceleration) when used in counter mode. SPRING is similar to the PRF of Banerjee, Peikert and Rosen from EUROCRYPT~2012, whose security relies on the hardness of the Learning With Rounding (LWR) problem, which can itself be reduced to hard lattice problems. However, there is no such chain of reductions relating SPRING to lattice problems, because it uses small parameters for efficiency reasons.
Consequently, the heuristic security of SPRING is evaluated using known attacks and the complexity of the best known algorithms for breaking the underlying hard problem.
In this paper, we revisit the efficiency and security of SPRING when used as a pseudo-random generator. We propose a new variant which is competitive with the AES in counter mode without hardware AES acceleration, and about four times slower than AES with hardware acceleration. In terms of security, we improve some previous analysis of SPRING and we estimate the security of our variant against classical algorithms and attacks. Finally, we implement our variant using AVX2 instructions, resulting in high performances on high-end desktop computers.
Charles Bouillaguet and Claire Delaplace (CASC)
This paper considers elimination algorithms for sparse matrices over finite fields. We mostly focus on computing the rank, because it raises the same challenges as solving linear systems, while being slightly simpler.
We developed a new sparse elimination algorithm inspired by the Gilbert-Peierls sparse LU factorization, which is well-known in the numerical computation community. We benchmarked it against the usual right-looking sparse gaussian elimination and the Wiedemann algorithm using the Sparse Integer Matrix Collection of Jean-Guillaume Dumas.
We obtain large speedups (1000x and more) on many cases. In particular, we are able to compute the rank of several large sparse matrices in seconds or minutes, compared to days with previous methods.
Elena Andreeva, Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque, Jonathan Hoch, John Kelsey, Adi Shamir and Sébastien Zimmer (Journal of Cryptology)
In this work, we present several 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 offers more flexibility in choosing the second-preimage message at the cost of a small computational overhead.
More concretely, our attack allows the adversary to replace only a few blocks in the original target message to obtain the second preimage. As a result, our new attack is applicable to constructions previously believed to be immune to such second-preimage attacks.
Among others, these include the dithered hash proposal of Rivest, Shoup's UOWHF, and the ROX constructions. In addition, we also suggest several time-memory-data tradeoff attack variants, allowing for a faster online phase, and even finding second preimages for shorter messages. We further extend our attack to sequences stronger than the ones suggested in Rivest's proposal.
To this end we introduce the kite generator as a new tool to attack any dithering sequence over a small alphabet. Additionally, we analyse the second-preimage security of the basic tree hash construction. Here we also propose several second-preimage attacks and their time-memory-data tradeoff variants.
Finally, we show how both our new and the previous second-preimage attacks can be applied even more efficiently when multiple short messages, rather than a single long target message, are available.
Alex Biryukov, Charles Bouillaguet and Dmitry Khovratovich (Asiacrypt)
Links: PDF ePrint Springer (Open Access)
In this paper we pick up an old challenge to design public key or white-box constructions from symmetric cipher components. We design several encryption schemes based on the ASASA structure ranging from fast and generic symmetric ciphers to compact public key and white-box constructions based on generic affine transformations combined with specially designed low degree non-linear layers. While explaining our design process we show several instructive attacks on the weaker variants of our schemes.
Charles Bouillaguet and Bastien Vayssière (SAC)
Links: PDF Springer (Open Access)
Most cryptographic hash functions are iterated constructions, in which a mode of operation specifies how a compression function or a fixed permutation is applied. The Merkle-Damgård mode of operation is the simplest and more widely deployed mode of operation, yet it suffers from generic second preimage attacks, even when the compression function is ideal.
In this paper we focus on provable security against second preimage attacks. Based on the study of several existing constructions, we describe simple properties of modes of operation and show that they are sufficient to allow some form of provable security, first in the random oracle model and then in the standard model. Our security proofs are extremely simple. We show for instance that the claims of the designers of Haifa regarding second preimage resistance are valid.
Lastly, we give arguments that proofs of second preimage resistance by a black-box reduction incur an unavoidable security loss
.Charles Bouillaguet, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen and Bo-Yin Yang (SAC)
Links: PDF DOI (Open Access) TU/e ePrint Code
In 2010, Bouillaguet et al. proposed an efficient solver for polynomial systems over $\mathbb{F}_2$ that trades memory for speed.
As a result, 48 quadratic equations in 48 variables can be solved on a graphics processing unit (GPU) in 21 min. The research question that we would like to answer in this paper is how specifically designed hardware performs on this task. We approach the answer by solving multivariate quadratic systems on reconfigurable hardware, namely Field-Programmable Gate Arrays (FPGAs). We show that, although the algorithm proposed in [BCC+10] has a better asymptotic time complexity than traditional enumeration algorithms, it does not have a better asymptotic complexity in terms of silicon area. Nevertheless, our FPGA implementation consumes 20–25 times less energy than its GPU counterpart. This is a significant improvement, not to mention that the monetary cost per unit of computational power for FPGAs is generally much cheaper than that of GPUs.
Charles Bouillaguet, Pierre-Alain Fouque and Amandine Véber (Eurocrypt)
Links: PDF HAL DOI (Open Access) ePrint
We give three new algorithms to solve the "isomorphism of polynomial" problem, which was underlying the hardness of recovering the secret-key in some multivariate trapdoor one-way functions. In this problem, the adversary is given two quadratic functions, with the promise that they are equal up to linear changes of coordinates. Her objective is to compute these changes of coordinates, a task which is known to be harder than Graph-Isomorphism. Our new algorithm build on previous work in a novel way.
Exploiting the birthday paradox, we break instances of the problem in time $q^{2n/3}$ (rigorously) and $q^{n/2}$ (heuristically), where $q^n$ is the time needed to invert the quadratic trapdoor function by exhaustive search. These results are obtained by turning the algebraic problem into a combinatorial one, namely that of recovering partial information on an isomorphism between two exponentially large graphs. These graphs, derived from the quadratic functions, are new tools in multivariate cryptanalysis.
Charles Bouillaguet, Pierre-Alain Fouque and Gilles Macario-Rat (Asiacrypt)
Links: PDF ePrint Springer (Open Access) Code
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.
Charles Bouillaguet, Patrick Derbez and Pierre-Alain Fouque (Crypto)
Links: ePrint Springer (Open Access) Code
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.Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque and Gaëtan Leurent (SAC)
Links: PDF Springer (Open Access)
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.
Charles Bouillaguet, Jean-Charles Faugère, Pierre-Alain Fouque and Ludovic Perret (PKC)
Links: PDF ePrint Springer (Open Access) code
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.
Charles Bouillaguet, Patrick Derbez, Orr Dunkelman, Nathan Keller and Pierre-Alain Fouque (IEEE Tr. on Inf. Th.)
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 attention in recent years) serves an important role in assessing the security of block ciphers and of other cryptographic primitives based on block ciphers. 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.
Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir and Bo-Yin Yang (CHES)
Links: PDF Springer (Open Access) ePrint Code
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.
Charles Bouillaguet, Gaëtan Keurent and Pierre-Alain Fouque (SAC)
Links: PDF Springer (Open Access) ePrint
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.
Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque and Gaëtan Leurent (SAC)
Links: PDF Springer (Open Access) ePrint
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.
Charles Bouillaguet, Orr Dunkelman, Gaëtan Leurent and Pierre-Alain Fouque (FSE)
Links: PDF Springer (Open Access)
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.
Charles Bouillaguet, Pierre-Alain Fouque, Antoine Joux and Joana Treger (Journal of Mathematical Cryptology)
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''.Elena Andreeva, Charles Bouillaguet, Orr Dunkelman and John Kelsey (SAC)
Links: PDF Springer (Open Access)
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.Charles Bouillaguet and Pierre-Alain Fouque (SAC)
Links: PDF Springer (Open Access)
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 pair 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.Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan Hoch, John Kelsey, Adi Shamir and Sébastien Zimmer (EUCROCRYPT)
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.Charles Bouillaguet, Viktor Kuncak, Thomas Wies, Karen Zee and Martin Rinard (VMCAI)
Links: Springer
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.