Pierre-Alain Fouque

Daniel De Almeida Braga, Pierre-Alain Fouque, Mohamed Sabt

Recently, the Dragonblood attacks have attracted new interests on the security of WPA-3 implementation and in particular on the Dragonfly code deployed on many open-source libraries. One attack concerns the protection of users passwords during authentication. In the Password Authentication Key Exchange (PAKE) protocol called Dragonfly, the secret, namely the password, is mapped to an elliptic curve point. This operation is sensitive, as it involves the secret password, and therefore its resistance against side-channel attacks is of utmost importance. Following the initial disclosure of Dragonblood, we notice that this particular attack has been partially patched by only a few implementations. In this work, we show that the patches implemented after the disclosure of Dragonblood are insufficient. We took advantage of state-of-the-art techniques to extend the original attack, demonstrating that we are able to recover the password with only a third of the measurements needed in Dragonblood attack. We mainly apply our attack on two open-source projects: iwd (iNet Wireless Daemon) and FreeRADIUS, in order underline the practicability of our attack. Indeed, the iwd package, written by Intel, is already deployed in the Arch Linux distribution, which is well-known among security experts, and aims to offer an alternative to wpa\_supplicant. As for FreeRADIUS, it is widely deployed and well-maintained upstream open-source project. We publish a full Proof of Concept of our attack, and actively participated in the process of patching the vulnerable code. Here, in a backward compatibility perspective, we advise the use of a branch-free implementation as a mitigation technique, as what was used in hostapd, due to its quite simplicity and its negligible incurred overhead.

Paul Kirchner, Pierre-Alain Fouque

In this paper, we study the Learning With Errors problem and its binary variant, where secrets and errors are binary or taken in a small interval. We introduce a new variant of the Blum, Kalai and Wasserman algorithm, relying on a quantization step that generalizes and fine-tunes modulus switching. In general this new technique yields a significant gain in the constant in front of the exponent in the overall complexity. We illustrate this by solving p within half a day a LWE instance with dimension n = 128, modulus $q = n^2$, Gaussian noise $α= 1/(\sqrt{n/π} \log^2 n)$ and binary secret, using $2^{28}$ samples, while the previous best result based on BKW claims a time complexity of $2^{74}$ with $2^{60}$ samples for the same parameters. We then introduce variants of BDD, GapSVP and UniqueSVP, where the target point is required to lie in the fundamental parallelepiped, and show how the previous algorithm is able to solve these variants in subexponential time. Moreover, we also show how the previous algorithm can be used to solve the BinaryLWE problem with n samples in subexponential time $2^{(\ln 2/2+o(1))n/\log \log n}$. This analysis does not require any heuristic assumption, contrary to other algebraic approaches; instead, it uses a variant of an idea by Lyubashevsky to generate many samples from a small number of samples. This makes it possible to asymptotically and heuristically break the NTRU cryptosystem in subexponential time (without contradicting its security assumption). We are also able to solve subset sum problems in subexponential time for density $o(1)$, which is of independent interest: for such density, the previous best algorithm requires exponential time. As a direct application, we can solve in subexponential time the parameters of a cryptosystem based on this problem proposed at TCC 2010.

Pierre-Alain Fouque, Mehdi Tibouchi

In this paper, we analyze several variants of a simple method for generating prime numbers with fewer random bits. To generate a prime $p$ less than $x$, the basic idea is to fix a constant $q\propto x^{1-\varepsilon}$, pick a uniformly random $a<q$ coprime to $q$, and choose $p$ of the form $a+t\cdot q$, where only $t$ is updated if the primality test fails. We prove that variants of this approach provide prime generation algorithms requiring few random bits and whose output distribution is close to uniform, under less and less expensive assumptions: first a relatively strong conjecture by H.L. Montgomery, made precise by Friedlander and Granville; then the Extended Riemann Hypothesis; and finally fully unconditionally using the Barban-Davenport-Halberstam theorem. We argue that this approach has a number of desirable properties compared to previous algorithms.

Jérôme Plût, Pierre-Alain Fouque, Gilles Macario-Rat

We study the Isomorphism of Polynomial (IP2S) problem with m=2 homogeneous quadratic polynomials of n variables over a finite field of odd characteristic: given two quadratic polynomials (a, b) on n variables, we find two bijective linear maps (s,t) such that b=t . a . s. We give an algorithm computing s and t in time complexity O~(n^4) for all instances, and O~(n^3) in a dominant set of instances. The IP2S problem was introduced in cryptography by Patarin back in 1996. The special case of this problem when t is the identity is called the isomorphism with one secret (IP1S) problem. Generic algebraic equation solvers (for example using Gröbner bases) solve quite well random instances of the IP1S problem. For the particular cyclic instances of IP1S, a cubic-time algorithm was later given and explained in terms of pencils of quadratic forms over all finite fields; in particular, the cyclic IP1S problem in odd characteristic reduces to the computation of the square root of a matrix. We give here an algorithm solving all cases of the IP1S problem in odd characteristic using two new tools, the Kronecker form for a singular quadratic pencil, and the reduction of bilinear forms over a non-commutative algebra. Finally, we show that the second secret in the IP2S problem may be recovered in cubic time.