Security researchers regularly set out to find implementation problems in cryptographic algorithms, but not enough effort is going towards the search for mathematical backdoors, two cryptography professors have argued.
Governments and intelligence agencies strive to control and bypass or circumvent cryptographic protection of data and communications. Backdooring encryption algorithms is considered as the best way to enforce cryptographic control.
In defence of cryptography, researchers have set out to validate technology that underpins the secure exchange of information and e-commerce. Eric Filiol,head of research at ESIEA, the operational cryptology and virology lab, argued that only implementation backdoors (at the protocol/implementation/management level) are generally considered. Not enough effort is being put into looking for mathematical backdoors or by-design backdoors, he maintains.
During a presentation at Black Hat Europe last week, titled By-design Backdooring of Encryption System - Can We Trust Foreign Encryption Algorithms?, Filiol and his colleague Arnaud Bannier, explained how it is possible to design a mathematical backdoor.
RSA: That NSA crypto-algorithm we put in our products? Stop using that
During a presentation, the two researchers presented BEA-1, a block cipher algorithm which is similar to the AES and which contains a mathematical backdoor enabling an operational and effective cryptanalysis. “Without the knowledge of our backdoor, BEA-1 has successfully passed all the statistical tests and cryptographic analyses that NIST and NSA officially consider for cryptographic validation,” the French crypto boffins explain. “In particular, the BEA-1 algorithm (80-bit block size, 120-bit key, 11 rounds) is designed to resist linear and differential crypto-analyses. Our algorithm [was] made public in February 2017 and no one has proved that the backdoor is easily detectable [nor] have shown how to exploit it.”
How they did it
During the Black Hat talk, Filiol and Bannier went on to lift the lid on the backdoor they had deliberately planted and how to exploit it to recover the 120-bit key in around 10 seconds with only 600kB of data (300kB of plaintexts + 300kB of corresponding ciphertexts). This was a proof-of-concept exercise, they added, saying that more complex backdoors might be constructed.
“There is a strong asymmetry (based on the mathematics) between inserting a backdoor into an algorithm (what we did and which is supposed to be feasible and easy, at least from a computational aspect) and being able to prove its existence, detect and extract a backdoor,” Filiol told El Reg. “In a sense we have to create some sort of conceptual one-way function.”
The researcher has been looking into the topic of mathematical backdoors in crypto algorithms for years. His previous work has included a paper looking into possible issues in block encryption algorithms, which was published earlier this year.
Why, even in these circles, maths is uncool
“Research on mathematical backdoors is much more difficult (mathematical stuff) – and does not attract researchers that need to publish quickly and regularly on fashionable topics,” Filiol added. “This is the reason why this kind of research is essentially done in R&D lab of intelligence agencies (GCHQ, NSA...) and [is designed] more for designing backdoors than detecting them.”
Revelations from papers leaked by former NSA sysadmin Edward Snowden that the NSA paid RSA Security $10m to use the weak Dual_EC_DRBG technology by default in its cryptographic toolset show that concerns about mathematical or by-design backdoors are far from theoretical. The Dual_EC_DRBG example is not isolated, according to Filiol.
“There are a lot of examples but only a few are known,” Filiol said. “This was precisely the purpose of the 'History' part in my slides [PDF].
"I am convinced that all export versions of encryption system contain backdoors in one way or another. This is a direct constraint from the Wassenaar agreement. In this respect, the crypto AG and other companies (revealed by the Hans Buehler case) are the best examples. There are other less known [examples].
“In this context and when analysing the different documents, standardisation process the Dual_EC_DRBG precisely IS a known but certain case,” he added.
How many mathematical backdoors are out there?
Filiol admitted it was difficult to know or even gain some sense of the mix between the prevalence and importance of implementation backdoors (at the protocol/implementation/management level) versus mathematical backdoors.
“This is a difficult question to answer, since proving that there may be a backdoor is an intractable mathematical issue,” Filiol responded. "Analyzing the international regulations clearly proves that at least export versions contains backdoors.
"What is more concerning is that now we have to fear that [this] is also the case for domestic use, in the context of population [level] and mass surveillance."
Asked whether the peer-review process weeded out mathematical backdoors, Filiol argued for reform.
"Defending (proving security) is far more difficult than attacking (proving insecurity)," Filiol said. "And the big issue lies in the fact that academic ignorance [of it has] had as [its] result that we consider the absence of proof of insecurity as a proof of security.
NSA mathematicians and proving a negative
"We are in a realm where the attacker does not publish everything they can do (especially in cryptography where the activity of intelligence entities is still prevalent). So the experts and academics can only work with the known attacks as a working reference. Just imagine what the NSA (300 of the most brilliant mathematicians working for nearly four decades) can have produced: a mathematical corpus of knowledge."
Filiol does not accept the industry-standard and widely reviewed AES algorithm is necessarily secure, even though he doesn’t have evidence to the contrary at hand.
“If I cannot prove that the AES has a backdoor; no one can prove that there is none,” Filiol told El Reg. “And honestly, who would be mad enough to think that the USA would offer a strongly secure, military grade encryption algorithm without any form of control?"
He added: “I do not. The AES contest has been organised by the NIST with the technical support of the NSA (it is of public knowledge). Do you really think that in a time of growing terrorist threat, the USA would have been so stupid not to organise what is known as ‘countermeasures’ in conventional weaponry? Serious countries (USA, UK, Germany, France) do not use foreign algorithms for high-security needs. They mandatorily have to use national products and standards (fromthe algorithm to its implementation),” he added.
Filiol concluded that reforms were needed in the way that cryptographic algorithms are selected, analysed and standardised. “It should be a fully open process mainly driven by the open crypto community,” he maintains. ®
