Software Production

While of my research is of theoretical nature, a significant fraction of my research 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-2022)

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.

This code should be at least 10x faster than the original implementation by Joux-Vitse.

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

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:

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.

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.

FES benchmark

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)

The BeanPole library is a concise and easy-to-use implementation of both Fast Exhaustive Search (and a memory-efficient Moebius transform). It is not a speed demon, but is easy to use as a component in other software projects.

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)