GORILLA

Research project funded by the french Agence Nationale de la Recherche (2021-2025).

Partners

• LIP6 (Charles Bouillaguet)
• CISPA Helmotz (Antoine Joux)

• Beginning and duration of the scientific project: April 2021 - 48 Months

Project Summary

The GORILLA project aims to improve our understanding of the security level provided by cryptographic schemes used to secure sensitive data and communications, be them widely used or only in development. Its main goal consists in improving the concrete efficiency of some cryptographic "attacks" capable of breaking security guarantees offered by these cryptographic schemes.

Public-key cryptographic schemes, including digital signature and key-exchange, are required in the TLS protocol to establish secure connections all over the internet. Their security relies on the assumption that well-known computational problems are hard, including integer factoring, computation of discrete logarithms modulo a prime or in elliptic curves, solving systems of boolean quadratic equations, etc.

Brutal, unpredictable algorithm improvement and regular progress in computational power may both allow cryptanalysts to break larger and larger instances of these hard problems that have become "security assumptions" in modern cryptography. This calls for periodically reevaluating the sizes of parameters of the corresponding cryptographic schemes. For this reason, 1024-bit RSA keys, that were once common, are now deprecated.

It is therefore necessary to continuously reasses the hardness of some hard computational problems, both in theory and in practice.

The project fits into this perspective, through three main objectives: first, improve some algorithms used in cryptographic attacks or invent new, more efficient ones. Second, produce high-quality software implementations of some cryptographic attacks and put them into the public domain. Third, run these program on large parallel computers.

The existence of public reference implementations of cryptographic attacks is invaluable to allow the public (or other researchers) to evaluate the security of cryptographic mechanisms and elaborate their own opinion. They may be used to break weak cryptographic schemes (or weak parameters in good cryptographic schemes, such as in the LOGJAM attack), but this is then a public service.

The project intends to run the attack software it will develop on a record size scale using a large computing infrastructure in order to demonstrate their quality but above all to make a public statement about the feasability scale of the attacks.

More precisely, the project focuses on selected specific algorithmic problems, which play an important role in the security of either current or future cryptographic schemes.

The project first intends to improve some algorithmic aspect of the Number Field Sieve, which is the state-of-the-art algorithm to factor large integers or compute discrete logarithms modulo a prime. The planned improvements concern both the sieving phase and the linear algebra phase; they will be incorporated into CADO-NFS, the reference open-source software developped at INRIA.

The, the project will focus on the parallel collision search algorithm of van Oorschor and Wiener, which has many applications in cryptanalysis; it is notably the best algorithm to compute discrete logarithms on elliptic curves. The project will produce a public high-quality implementation and use it to break the Certicom ECC2K-130 challenge, which consists in computing a discrete logarithm over an elliptic curve defined over a 130-bit binary field. The project will then use the same implementation to demonstrate a large "meet-in-the-middle" attack against double encryption, for instance by breaking the double-DES in practice (this has never been done).

Lastly, the project will tackle the issue of solving systems of boolean quadratic equations. This problem is relied upon by "post-quantum" digital signature schemes currently competing for standardization. The point is to better understand the behavior of a recent algorithm of Joux-Vitse and to compare its practical efficiency with that of exhaustive search (or to combine both). Lastly, a significant computational record is sought.

(pictures credit: upklyak / Freepik)