Whether it’s ensuring the confidentiality of a banking operation, updating software online or browsing the internet safely, all of these operations require the security of multiple IT protocols. A number of researchers in the field of cryptography, including various different Inria teams, are hard at work on this task. This scientific discipline covers two major fields: encryption, which involves coding messages in order to protect the confidentiality of exchanges between two parties; and authentication, which involves verifying the identity of each party in order to prevent messages being modified by any third party.
Testing the reliability of cryptography methods
One of the major challenges of our research into cryptography, as is the case for research in this field more generally, involves demonstrating the robustness of encryption and authentication algorithms
explains Gaëtan Leurent, a former member of the Secret project team, who joined Cosmiq* in 2013. Leurent was awarded a PhD in cryptography in 2010.
In order to test the reliability of cryptographic systems, researchers put themselves in the shoes of would-be attackers, devising ways of breaking encryption keys or deceiving authentication algorithms
Ordinarily, attacks are devised theoretically, in a context that favours the attacker: by supposing that both the original and the protected messages are known, for example (in reality, obviously only the encrypted message would be accessible), or by considering IT resources with varying levels of effectiveness as being available. “The aim of my research is to design more ‘realistic’ attacks, factoring in the real complexity of authentication processes, for example, or the real performance levels of available IT resources”, explains Gaëtan Leurent.
Attacking a signature algorithm
The researcher places particular emphasis on one of the key aspects of the electronic signature used for message authentication: the hash function. This performs a mathematical operation in order to produce a ‘fingerprint’ for a message, making it possible to calculate a signature. These are like actual fingerprints in that they are unique to each individual, and can be used to prove an individual’s identity without the need for any other information about them.
Messages are authenticated by verifying their fingerprints, which are sent with the message; authentication security depends partly on the fact that the hash function produces a different fingerprint for each message. If an attacker was able to generate two messages using the same fingerprint, then a signature on the first message would remain valid on the second. The attacker would then be able to forge a signature simply by copying it from one message to another.
Significant computational resources
Using a given message, a hash function produces a coded fingerprint of a fixed length made up of a series of 1s and 0s. The longer the fingerprint, the more difficult it will be to attack the hash function. Attack algorithms require a high number of calculations and their effectiveness is measured based on the complexity of the problem (see inset).
The complexity of attack algorithms
The difficulty of attacking a hash function is assessed based on the number of operations that would theoretically be necessary in order to obtain two messages with the same fingerprint. This number increases exponentially as the length of the fingerprint increases. The challenge facing researchers in cryptography is to find a way of developing efficient algorithms, the performance levels of which will be compared to this theoretical number of operations. The algorithm put forward by Gaëtan Leurent and Thomas Peyrin for attacking SHA-1 requires almost 100,000 times fewer operations than the theoretical number, enabling it to be used in a practical setting.
It took the best part of three years for Gaëtan Leurent and his colleague, Thomas Peyrin, to design their attack on the SHA-1 hash function, which was designed in the 1990s by the NSA**. This hash function had previously been attacked theoretically in 2005, before being attacked practically in 2017, but the attack proposed by these two researchers goes further than what was done previously. It gives attackers more room, enabling them to usurp the identity of users in the so-called PGP system, used most notably for exchanging encrypted emails.
Obtaining this result - which was presented to the international community in New York in early January at the Real World Crypto conference, an annual event which brings together the international community in the field - used up a significant amount of computational resources. A supercomputer with 900 graphics cards was used on a continuous basis for the best part of two months in order to perform the operation.
If these resources are accessible to a team of researchers, then they are even more accessible to States with malevolent intentions: as far as the scientific community is concerned, SHA-1 with its 160-bit fingerprint is no longer capable of offering any real guarantees in terms of IT security, yet it is still used in widespread internet protocols, including https. Its successors, SHA-2 and SHA-3, are capable of producing fingerprints with 256 or more bits: attacking these would require resources that are currently impossible to muster.
Other IT developments are emerging, including the quantum computer, which offers infinitely more in the way of computational capacity. As a consequence, there are no guarantees as to the invulnerability of cryptographic algorithms over the long term. “Researchers are interested in the consequences technological breakthroughs might have on cryptography methods: this is a new theme that Cosmiq researchers have been investigating for a few years.”
* Cosmiq: an Inria Paris team, directed by Jean-Pierre Tillich. The acronym refers to the three fields of cryptography the researchers within the team have been working on: COde based cryptography, SyMmetrIc cryptography and Quantum aspects.
** NSA (the National Security Agency): the American government agency responsible for intelligence and the security of information systems