An algorithm developed by Prof. Itai Dinor at Ben Gurion University seems promising in several ranges of common parameters in encryption applications, but this algorithm, like the others, requires a lot of memory, so it is not yet certain whether it will be applicable for attacks, but it is still worth investigating
Researchers need to follow the latest techniques for cracking cryptographic codes. This allows them to probe existing applications to look for weaknesses, and refine new applications to make them more secure. For this they need to be one step ahead of the hackers.
In one of the types of attacks, better algorithms are used for solving polynomial Boolean equations. Researchers have been investigating for many years different approaches to solving Boolean algorithms. The solution of polynomials is a fundamental problem in computer science.
About five years ago, researchers began investigating new probabilistic algorithms that looked promising in theory but were never implemented. Now a team of researchers at the Technological Innovation Institute (TII) in the United Arab Emirates working together with the Polytechnic Institute of Turin in Italy have implemented and tested these algorithms in executable code.
Javier Verbal, a cryptographer at TII, said: “We wanted to try these algorithms in a practical way. The theory behind them is very understandable. But when you study something only in theory, you can sometimes miss various complicating factors. If implemented in practice, you get a more accurate idea of the degree of difficulty in solving a problem with a given system of resources."
The initial results revealed that at least one of the new algorithms showed promise in cracking ciphers more efficiently than existing techniques.
The main purpose of such activity is to evaluate the security of new and existing encryption structures. The default approach, called the power technique, is a technique for solving Boolean polynomials. The new algorithms are the first that are asymptotically faster than power techniques, in the case of Boolean systems, in any system of polynomials. None of the previously known algorithms have this feature.
Researchers have had a long-standing interest in the mathematical properties of new algorithms for more efficiently solving polynomial Boolean equations. These algorithms have shown promise in cracking various encryption methods such as multivariate encryption, 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 applications can sometimes be more complicated than the theory—and sometimes less.
And in addition, the techniques for measuring complexity are different in theory than in practice. Theoretical metrics focus on measuring the number of bit operations required by the algorithm. In practice, it is more common to measure the number of clock cycles that will be necessary for the processor to solve a problem using the same algorithm.
All of these new algorithms have been developed since 2017, and do not have formal names yet. The authors who wrote about them characterized them. But it is important to take into account the types of parameters that are used in existing encryption applications in practice. It turns out that three of the algorithms seem to be impractical.
A fourth algorithm developed by Itai Dinor at Ben Gurion University looks promising in some ranges of parameters common in encryption applications, but this algorithm, like the others, requires a lot of memory.
The researchers started with a proof of concept to see how the complexity would increase in practice. They did not yet optimize the first implementation in terms of speed because they wanted to focus on understanding how the complexity increased in practice and how it matched the theoretical claims.
"The main conclusion was that the first three algorithms are not applicable in practice, but the fourth one might be," said Verbal. Now his team is working on achieving a faster implementation that is optimized for the characteristics of central processors and graphics to see how it behaves in large parameters. He hopes this work will inspire others to find ways to improve the algorithm's use of memory as well. The code is in the public domain.
More of the topic in Hayadan:
One response
This article is well encrypted. I would love to read it after decoding.