A Computation Record for Computer Security

The security of information and communication systems is one of this century’s major challenges. At the core of many exchange protocols, encryption keys ensure the security of data exchange. “The confidentiality of data exchange is based on the use of two security keys,” explains Aurore Guillevic, research scientist on the CARAMBA* team, which spans both Inria and Loria. “The first, called a public key, allows the sender to encrypt a message intended for the recipient; and the second, called a private key, allows the recipient to decrypt that message. The two keys work together. Ensuring that the protocol is secure means guaranteeing that the private key cannot be derived from the public key. “

Making encryption uncrackable

 “The ability of public keys to withstand potential attack relies on encryption techniques that use mathematical problems that are extremely difficult to solve,” says Emmanuel Thomé, Inria research director and head of the CARAMBA team.

One of these problems is known as “integer factorization”. This consists of creating a key by multiplying together two very large prime numbers. Cryptanalysis, or “cracking”, consists of finding the two original prime numbers. For example, 21 is the product of 3 and 7, two prime numbers. In this case, a quick calculation gives the result. For increasingly large numbers, the solution cannot be found without computers and sophisticated algorithms.

A second algorithm, known as a “discrete logarithm”, is also based on finding the solution to a complex algebraic equation.** In both cases, the longer the encryption key, the harder it is to find the solution, and the more robust the encryption.

Testing the security of keys

The CARAMBA team's research focuses primarily on developing cryptanalysis methods to quickly resolve these two problems, thereby testing the soundness of encryption procedures or enhancing their robustness. The researchers use CADO-NFS, a software package developed at Nancy in 2007. With some 300,000 lines of code, it required the work of numerous experts, three of them CARAMBA researchers (Pierrick Gaudry at CNRS, and Emmanuel Thomé and Paul Zimmermann at Inria) who have been working on it for over ten years. It is designed to use the computational power of supercomputers, like that of the Grid'5000/SILECS platform or the European consortium PRACE.***

“We are interested in 795-bit keys. You can find small keys like those in some embedded applications, for example in telecommunications, because they need less computing power,” say Emmanuel Thomé and Aurore Guillevic. “With 795 bits, we're coding 240-digit integers, which means using the factorization algorithm to find two prime numbers 120 digits long. The process involves handling a massive amount of data (more than 10 TB!).**** It takes 35 million computing hours to break a 795-bit key. “

Make security recommendations

Working with other cryptanalysis experts including Nadia Heninger at the University of California and Fabrice Boudot at the University of Limoges, the CARAMBA team has set a new computation record and assessed the efficacy of the innovation brought to cryptanalysis methods. It has accelerated the ongoing improvement of processing power (Moore's Law). The researchers have also shown that the two algorithms performed comparably, although the discrete logarithm method had previously been thought more complex than integer factorization.

The exercise is not merely theoretical. Although the computer resources allocated to it seem extravagant and the scientific expertise needed to operate them highly advanced, they are affordable for governments intent on developing extremely efficient cryptanalysis tools.

Among other benefits, this work is helping to develop cybersecurity recommendations that can be taken up by cybersecurity agencies, such as ANSSI in France.***** “Our calculations show the reliability limits of encryption keys and clearly demonstrate that 795-bit keys are not robust! To date, only longer ones, exceeding 2048 bits, offer adequate guarantees.” Until another new record demonstrates otherwise?

From left to right: Emmanuel Thomé, Pierrick Gaudry, Aurore Guillevic and Paul Zimmermann