Abu Dhabi, UAE: 22 April 2022: Researchers need to stay abreast of the latest techniques for cracking cryptographic codes. This allows them to probe existing implementations for weaknesses and refine new implementations to be more secure.
One class of attacks takes advantage of better algorithms for solving Boolean polynomial equations. Researchers have been exploring various approaches to solve Boolean algorithms for many years. Solving polynomials has been a fundamental problem in computer science.
About five years ago, researchers began investigating new probabilistic algorithms that have shown promise in theory but were never implemented. Now, a team of researchers at Technology Innovation Institute (TII) in the United Arab Emirates and the Politecnico di Torino in Italy have implemented and tested these algorithms in runnable code.
Javier Verbel, Senior Cryptanalyst, TII, said, “We wanted to test these algorithms in practice. The theory behind them was well understood. But when you only explore something in theory, you can sometimes miss various complex factors. If you implement it in practice, you have a more precise idea of how hard it is to solve a problem with a given set of resources”.
The initial results revealed that at least one of the new algorithms shows promise for cracking codes more efficiently than existing techniques.
Breaking codes more efficiently
The main goal of such efforts is to estimate the security of new and existing cryptographic constructions. The default approach, called a brute force technique, is a technique to solve Boolean polynomials. The new algorithms are the first ones to be asymptotically faster than brute force techniques, in the case of Boolean systems, for any system of polynomials. None of the algorithms known before satisfied this property.
Researchers have a long-running interest in the mathematical properties of new algorithms for solving Boolean polynomial equations more efficiently. These have shown promise in cracking various encryption schemes such as multivariate-based cryptography, block ciphers, and hash functions more efficiently than other techniques.
Specifically, the team decided to implement four approaches that had been developed and described by other researchers. But no one had implemented them into runnable code. This is important because practical implementations can sometimes be more complex than theorised – and sometimes, less.
Also, the techniques for measuring complexity are different in theory than in practice. Theoretical metrics focus on measuring the number of bit-operations an algorithm requires. In practice, it is more common to measure the number of clock-cycles a CPU would need to solve a problem using the same algorithm.
These new algorithms have all been developed since 2017, and don’t have formal names yet. The authors that wrote about them have characterised them. However, it’s important to consider the types of parameters used in existing cryptographic implementations in practice. As it turns out, three of the algorithms don’t seem to be practical.
A fourth one developed by Itai Dinur at Ben-Gurion University in Israel showed promise for some ranges of common parameters in cryptographic implementations. However, this algorithm as with the others, requires a lot of memory.
Verbel said, “It may be that the memory required for real-world problem solving of Boolean polynomials is likely to be so large that it could also slow down the algorithm. This has been a limitation for all of them and may also be the case for the Dinur algorithm”.
Coding a proof of concept
Researchers took an intellectual curiosity in the first couple of algorithms, but none of these were implemented in code. “It was expected they would not outperform exhaustive search for small parameters”, Verbel said. The latest ones showed more promise, and his team started implementing them in the C programming language as soon as they came out.
They started with a proof of concept to see how the complexity would grow in practice. They have not yet optimised this first implementation for speed since they wanted to focus on understanding how the actual complexity grows in practice and how it matches the theoretical claims.
“The main takeaway was that the first three algorithms were not feasible in practice, but the fourth one could be”, Verbel said. Now his team is working on achieving a faster implementation that is optimized for CPU and GPU characteristics to see how it behaves for larger parameters. He hopes this work could inspire others to find ways to improve the memory usage of the algorithm as well. The code is in the public domain.
Verbel conjectured that some of the older algorithms might show more promise if implemented in a quantum circuit. TII is working on a GPU-optimised implementation, and Verbel hopes to include it in a cryptographic library the group plans to release later this year.
