Governments and intelligence agencies strive to control or bypass the encryption protections on data and communications, and creating a backdoor in encryption algorithms is seen as the best way to achieve encryption control. Security researchers often look for vulnerabilities in the implementation of encryption algorithms but do not invest much effort in searching for mathematical backdoors.
In encryption protection, researchers have begun to verify the supporting technologies for information security exchange and e-commerce. Eric Filiol, head of the operational cryptography and virology laboratory at the École supérieure d’informatique, d’électronique et d’automatique (ESIEA) in France, believes that only when backdoors at the protocol/implementation/management levels are widely considered, will the effort put into searching for mathematical backdoors or designing backdoors still be far from enough.
At the European Black Hat Conference held last week, Filiol and his colleague Arnold Pénalva gave a talk titled “Backdoors in Cryptographic System Design — Can We Trust Foreign Encryption Algorithms?“, discussing the possibility of designing mathematical backdoors.
During the presentation, the two researchers introduced the BEA-1 block cipher algorithm. This algorithm is similar to AES but contains a mathematical backdoor that allows for effective cryptanalysis.
The two French cryptographers explained: “Without knowing our backdoor, BEA-1 successfully passed all statistical tests and cryptanalysis, and both NIST and NSA officially considered it for cryptographic validation. In particular, the BEA-1 algorithm (80-bit block size, 120-bit key, 11 rounds of encryption) was designed to resist linear and differential cryptanalysis. Our algorithm was made public in February 2017, and no one has proven that this backdoor can be easily detected, nor has anyone demonstrated methods for exploiting it.”
How They Did It
During the Black Hat Conference presentation, Filiol and Pénalva publicly revealed the intentionally set backdoor, demonstrating how to exploit this backdoor to recover a 120-bit key in just 10 seconds with only 600KB of data (300KB plaintext + 300KB ciphertext). This is just a proof of concept, and more complex backdoors could be constructed.
“
Inserting a backdoor into an algorithm and detecting and proving the existence of a backdoor is very asymmetric mathematically. In other words, we must create some kind of conceptual one-way function.
Filiol has been researching mathematical backdoors in encryption algorithms for many years, and earlier this year published a paper on potential issues with block cipher algorithms.
Why Is Mathematics Unpopular Even in Research?
Researching mathematical backdoors is very difficult and does not attract researchers who need to frequently publish papers on trendy topics. This type of research is mostly done in the R&D labs of intelligence agencies (GCHQ, NSA, etc.), and is more about backdoor design rather than detection.
Snowden revealed that the NSA spent $10 million to have RSA Security use a weak Dual_EC_DRBG random number generation algorithm by default in its encryption toolkit. This demonstrates that mathematical backdoors, or designed backdoors, exist not only in theory but are very real. Moreover, Dual_EC_DRBG is not an isolated case.
There are many examples of mathematical backdoors, but only a few are well-known.
“
I am convinced that all exported encryption systems will have backdoors embedded in some way, which directly violates the Wassenaar Arrangement. The case of Crypto AG (a Swiss communication and information security company) exporting encryption machines that contained NSA backdoors is a prime example. There are also some lesser-known examples.
How Many Mathematical Backdoors Exist?
It is difficult to ascertain the prevalence and significance of implemented backdoors and mathematical backdoors. Proving the existence of a backdoor is a very difficult mathematical problem. However, by analyzing international regulations, it is clear that at least exported encryption devices/technologies contain backdoors. More worryingly, in an environment of mass surveillance, could the encryption technologies used domestically also have backdoors?
So, can peer review exempt mathematical backdoors?
Filiol states that this probably requires reform:
“
Being able to prove security is far more difficult than being able to prove insecurity. The biggest problem is that the academic neglect of the difficulty of proving security leads us to take “no evidence of insecurity” directly as “evidence of security”.
Attackers do not disclose everything they can do, especially in the field of cryptography where intelligence agencies have significant power. Thus, experts and the academic community can only refer to known attack cases. Imagine what an organization like the NSA, which has 300 of the smartest mathematicians at its service for 40 years, could produce? That is a complete collection of mathematical knowledge!
Filiol also believes that the AES algorithm, which has been widely reviewed as an industry standard, may not be secure, although he has no evidence to prove that it is insecure.
“
Even if I cannot prove that AES has vulnerabilities, no one can prove that there are no vulnerabilities in this algorithm. To be honest, would the U.S. provide a sufficiently secure military-grade encryption algorithm without any form of control? I certainly do not believe that.
The AES competition was organized by NIST, with technical support from the NSA (this is well known). In an era of rampant terrorism threats, the U.S. would not be foolish enough not to prepare something as a conventional weapon “countermeasure.” Countries like the U.S., U.K., Germany, and France, which have some decency, would not use foreign algorithms in matters with high security demands. They enforce the use of domestic products and standards—from algorithms to their implementations.
The selection, analysis, and standardization of encryption algorithms need reform. This must be a process driven mainly by the open cryptography community and completely open.
Related Reading
Artificial Neural Networks Can Have Backdoors!
High Alert: Encrypted Communication Can Conceal Undetectable Backdoors
You Thought Only WannaCry Exploited NSA Vulnerabilities? Hidden Backdoors Have Been Ahead of the Game
