Tools to facilitate quantum cryptanalysis

After five years of international competition, the U.S. Department of Commerce's Institute of Standards and Technology (NIST) recently selected the Falcon algorithm as a digital signature standard capable of withstanding the computing power of future quantum computers. Capsule, the project team^[1] at the Inria Center at Rennes University specializing in cryptography, was the driving force behind this application. But alongside the design of new “post-quantum” encryption schemes, there is another equally crucial imperative: the search for possible vulnerabilities that could compromise the long-term security of symmetric cryptography systems. Widely used in digital life, symmetrical encryption tools are reputed to be fast and efficient, relying on a secret key shared by sender and receiver. A special feature of these tools is that they can only be trusted through analysis.

Cryptanalysts try out different types of attack and determine their ability to penetrate the targeted cipher (or not). In the Capsule team, this is one of André Schrottenloher's specialties. The French National Research Agency (ANR) has just awarded him a Jeune Chercheur Jeune Chercheuse (JCJC) grant to extend his work in the direction of quantum security analysis. The project is called QATS: Quantum Attacks and new Tools for Symmetric Cryptanalysis.

Quantifying the unattainable

Measuring the level of security is first and foremost the quantification of a number of operations: the computational effort required to break a given encryption scheme.

As things stand, quantum cryptanalysis is essentially carried out “on a sheet of paper or a blackboard. And mathematically analyzing quantum algorithms by hand, I can confirm, is no picnic!”

Automate cryptanalysis

One aspect of the QATS project is the development of tools to automate this tedious task. “On the one hand, it would simplify our lives. On the other hand, it would make it easier to study a larger number of ciphers. Which would be interesting, because there are a lot of them out there.” The Capsule team already has considerable expertise in the field of automatic analysis of classical symmetric cryptography.

The idea is to merge this know-how with quantum cryptanalysis techniques to develop automatic tools that are both efficient and easy to use. Admittedly, designing these tools initially requires a lot of work, but afterwards it saves a lot of time.

Distribute tools

In practice, the aim is to find the best possible attacks. “We delimit the type of attack we're interested in. In reality, there aren't thousands of methods, just a few. Once we know what we're looking for, the computer will help us find those attacks. It's a fairly complicated optimization problem, and the machine is stronger than the human being at solving it.”

The project will last four years. “We hope to end up with something reusable by the rest of the scientific community, which would already be a good goal. We're in a fledgling field, where prototypes are certainly used to support publications, but they're not maintained over time, and may even be difficult to re-use. At research level, there's a lack of transmission and availability of all these tools. And in the QATS project, we're going to do our utmost to disseminate as much as possible.”

^[1]Capsule is a project-team of the Inria Center at Rennes University, the CNRS and the Rennes Université, together with Irisa.