Abu Dhabi, UAE: April 22, 2022: Researchers should keep abreast of the latest techniques for cracking cryptographic codes. This allows them to probe weaknesses in existing implementations and fine-tune 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 solving Boolean algorithms for many years. Solving polynomials is a fundamental problem in computer science.
About five years ago, researchers began investigating new probabilistic algorithms that showed promise in theory but were never implemented. Today, a team of researchers from the Technology Innovation Institute (TII) in the United Arab Emirates and the Politecnico di Torino in Italy have implemented and tested these algorithms in executable code.
Javier Verbel, Principal Cryptoanalyst, 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, sometimes you can miss various complex factors. If you implement it in practice, you get a better idea of how difficult it is to solve a problem with a given set of resources.”
Early results have revealed that at least one of the new algorithms shows promise for cracking codes more efficiently than existing techniques.
Crack codes more efficiently
The primary goal of these efforts is to estimate the security of new and existing cryptographic constructs. The default approach, called the brute force technique, is a technique for solving Boolean polynomials. The new algorithms are the first to be asymptotically faster than brute force techniques, in the case of Boolean systems, for any system of polynomials. None of the previously known algorithms satisfied this property.
Researchers have long been interested in the mathematical properties of new algorithms to more efficiently solve Boolean polynomial equations. These have shown promise for cracking various encryption schemes such as multivariate 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 in executable code. This is important because practical implementations can sometimes be more complex than theoretical – and sometimes less.
Moreover, complexity measurement techniques are different in theory and in practice. Theoretical metrics focus on measuring the number of bitwise operations required by an algorithm. 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 do not yet have official names. The authors who wrote about them characterized them. However, it is important to consider the types of parameters used in existing cryptographic implementations in practice. It turns out that three of the algorithms don’t seem practical.
A fourth developed by Itai Dinur at Ben-Gurion University in Israel has shown promise for some common parameter ranges in cryptographic implementations. However, this algorithm like the others, requires a lot of memory.
Verbel said, “It may be that the memory required for solving real Boolean polynomial problems is likely to be so large that it could also slow down the algorithm. This has been a limitation for all and may also be the case for Dinur’s algorithm”.
Code a proof of concept
The researchers took an intellectual interest in the first two algorithms, but neither of them was implemented in code. “They were expected not to outperform the exhaustive search for small parameters,” Verbel said. The later ones showed more promise, and his team started implementing them in the C programming language as soon as they were released.
They started with a proof of concept to see how the complexity would increase in practice. They haven’t optimized this first implementation for speed yet because they wanted to focus on understanding how real complexity increases in practice and how it matches theoretical claims.
“The main takeaway was that the first three algorithms weren’t practically feasible, but the fourth might be,” Verbel said. Now his team is working on making a faster implementation optimized for CPU and GPU specs to see how it performs at larger settings. He hopes this work can inspire others to find ways to improve the algorithm’s memory usage as well. The code is in the public domain.
Verbel speculated that some of the older algorithms might hold more promise if implemented in a quantum circuit. TII is working on a GPU-optimized implementation, and Verbel hopes to include it in a cryptographic library the group plans to release later this year.