Software Production

While some of my research is of a theoretical nature, a significant fraction of my work has resulted in actual code being written and run. Therefore, these codes are a non-negligible output of my work.

A High-Performance implementation of the Crossbred algorithm (2020-2023)

I embarked on a project to write a "record-smashing capable" implementation of the crossbred algorithm of Joux-Vitse. The result is available here. At the same time, this program is meant to be easy to use on either a laptop or a computation server.

I started by implementing a particularly simple special case put forward by Monika Trimoska. This already gets faster than exhaustive search!

I had to implement a library called BeanPolE to perform various operations on dense Boolean polynomials.

The resulting software has succesfully been used to break new challenges on the mqchallenge.org website. It is currently the state-of-the-art.

Attacks against "Secure" delegation protocols (2021-2022)

I implemented several attacks against the MCExp and MExpSOS modular exponentiation delegation protocols, using the Sagemath computer algebra system. These attacks are available here. This includes the use of Coppersmith's algorithm in 3 variables.

I also implemented a pure-python lattice-based attack against a modular inversion delegation scheme. The attack requires only a constant factor more computation than what the lightweight client has to do in the protocol.

Predicting the PCG Pseudo-Random Number Generator (2019-2020)

The PCG pseudo-random number generator is a popular algorithm, which is supposed to be "challenging" to predict. Julia Sauvage and I wrote an efficient state reconstruction algorithm that enabled us to predict it in practice using 512 byte of challenge input and 12 500 CPU hours.

White-Box AES Attempts (2019)

I submitted two entries to the WhibOx contest held before CHES'19: entry 103 (wizardly allen) and before that entry 82 (stoic thompson). These two program implement the AES encryption under two (different) fixed keys. The intention is that it is difficult to retrieve the keys. These white boxes were broken. I got the fourth rank in the contest.

These codes have been produced by an ad hoc compiler from a subset of ML to an obscure low-level machine. They contain an (obfuscated) generational garbage collector (stop-and-copy on the young generation, mark-and-sweep on the old generation) !

3XOR Computations (2016-2021)

128 bits of SHA-256 using bitcoin miners (2016-2019)

I wrote optimized implementations of 3XOR algorithms: the quadratic algorithm (using vectorized hash probes, about 2 CPU cycles / probe on recent intel CPUs) and the iterated Joux algorithm. The latter has been heavily optimized to run on the IBM Bluegene/Q massively parallel computer (turing) at IDRIS. It ran for 4 million CPU-hours on 65536 cores simultaneously.

This resulted in a 3XOR on 128-bit of the full SHA-256 cryptographic hash function, as demonstrated by this short program.

This code is available on github. The modified mining program that was used to prepare the input data on an AntMiner S7 bitcoin mining device is also available on github.

Sparse 3XORs on the full SHA-512 hash functions (2019-2021)

I have also invented and implemented algorithms for sparse 3XORs. I applied them to the full SHA-512 hash functions, where the inputs are combinations of the titles of cryptology papers:

• "Secrets of the Codebreakers". Curiously mentions my PhD advisor, P.-A. Fouque and my coauthor P. Derbez.
• "Corporate Espionage". Suspiciously mentions C. Peikert and my coauthor G. Leurent ---the latter built SPRING based on ideas by the former, and I worked on SPRING !
• "the Bible Code". Bizarrely mentions the first published paper of A. Canteaut. Also mentions G. Poupard ---current head of the ANSSI---, P.-A. Fouque ---my PhD advisor, again!--- and G. Leurent ---again!.
• "Crypto-only". Amazingly contains my own name!

Sparse Linear Algebra (2014-2019)

CADO-NFS (2019)

I contributed some code to CADO-NFS, in order to parallelize the "merge" step using OpenMP. The resulting code has been used in recent record factorization and discrete log computations.

SpaSM (2014-2019)

Most of my code is part of SpaSM.

Exhaustive Search for Quadratic Boolean Equations (2010-2019)

libFES (2013)

I wrote libFES, which solves system of multivariate polynomials (in any degree) by exhaustive search. This runs very efficiently by using SSE vector instructions on intel CPUs (it tests 3.7 candidates per CPU cycle). At some point, libFES was available from the SageMath computer algebra system as an experimental package, but it is no longer the case.

libFES Benchmark

This benchmark shows the time needed by several pieces of software to solve random, dense systems of n quadratic polynomials in n variables over $\mathbb{F}_2$. Of course, this comparison is biased in our favor, because random dense systems are essentially a worst-case for the other methods. In a lot of interesting cases, the other methods may clearly outperform libFES.

• Solving with a SAT solver is done in two phases: the polynomials are first converted to CNF, and the resulting SAT instance is fed to a SAT-solver (Glucose 2.2).

• The implementation of F4 in the MAGMA computer algebra system (V2.19-1) was probably the best available at that time. It could only be tested up to $n=29$ variables, afterwards it used more than the 74Gbyte of RAM that were available.

• Hybrid-F4 denotes the following algorithm: "guess" the value of k variables, and solve the system of $n$ polynomials in $n−k$ variables using F4. The last step has to be repeated $2^k$ times. The optimal value of k has been chosen.

libFES-lite (2016-2022)

The code of libFES was heavy and difficult to maintain, so I gave up and wrote libFES-lite, which specializes in solving 32 quadratic equations in (less than) 32 variables. libFES-lite is much simpler and almost twice faster than its big brother thanks to the use of AVX2 or AVX512 instructions (it tests about 16 candidates per CPU cycle). On a pair of 16-cores Intel Xeon Gold 6130 CPU @ 2.10GHz, libFES-lite solves a system of 48 equations in 48 variables in 4 minutes (that's 2 CPU*hours).

libFES-lite comes with a "demonstration" program that solves a system of Boolean quadratic equations read from a text file, using all available threads.

BeanPole (2022)

Attacks Against Multivariate Public-key Schemes (2010-2013)

SFLASH Signatures (2011)

The MAGMA code of a practical key-recovery attack against the SFLASH signature scheme.

"Isomorphism of Polynomials with One Secret" (2011)

The MAGMA code of an algorithm that breaks the quadratic IP1S problem or the cubic IP1S problem.

"Quadratic Maps Linear Equivalence" (2013)

The MAGMA code of several algorithms that solve the quadratic IP2S/QMLE problem.

Low-Data Complexity Attacks Against the AES (2010-2011)

• An automatically-generated attack on one full round of AES with one known plaintext. Performs 2^40 operations. Here.
• An automatically-found, manually-written state-recovery on Pelican-MAC, given one collision. Performs 2^32 operations, uses 36GB of RAM and 80 GB of storage. Here.
• An automatically-found, manually-written state-recovery part of a fault attack on the full AES, where a fault is introduced in round 8. Runs in a few seconds. Here.
• A tool to find attacks on reduced versions of the AES automatically is available Here.