We need to talk about mathematical backdoors in encryption algorithms

Yo, NSA maths chaps, can you hear me? – Black Hat man

80 Got Tips?

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 (from the 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. ®

Sign up to our NewsletterGet IT in your inbox daily


Keep Reading

Western Digital shingled out in lawsuit for sneaking RAID-unfriendly tech into drives for RAID arrays

Probing by El Reg's Chris Mellor highlighted in class-action complaint

Western Digital hands chief exec seat to boss of Cisco's networking and security biz

David Goeckeler finally gets keys to his own kingdom, says he's stoked to ride 'massive wave of new opportunity'

Zoom will offer proper end-to-end encryption to free vid-chat accounts – not just paid-up bods – once you verify your phone number...

Just in case the Feds take an interest in your calls

Western Digital: We're just about DDN with these data centre systems

IntelliFlash flogged to big data storage firm, ActiveScale on the block

MAMR Mia! Western Digital's 18TB and 20TB microwave-energy hard drives out soon

No volume ships until mid-2020, though

Western Digital invites frenemies to help hash out storage standards of the future-ture-ture-ture

Call for industry giants to get zoned in on SMR, ZNS drives

Super-leaker Snowden punts free PDF* of tell-all NSA book with censored parts about China restored, underlined

* In Simplified Chinese

WD you like to know the damage? Analyst predicts sales dip ahead for Western Digital

NAND revenues and disk drive topline downbound until mid-year - Wells Fargo

RISC-V Xmas gifts: SiFive emits vector-enabled cores, Western Digital teases new SweRVs, VxWorks hugs ISA, Samsung rolls it into 5G...

Updated More stuff that'll get under Arm's skin

Tech Resources

Latency is the New Outage

More organizations are tying their future success to digital and online business.

Navigating the CTI Noise

We all want better threat intelligence, but it’s not easy to build a CTI program and deliver it considering all the moving parts, people, processes, and technology. Sure you need to gather the data, but how do you separate intel and priorities from the noise? How do you turn this into actionable information that improves the security of your business?

CrowdStrike Falcon Complete

Guidance for taking any organization to the highest level of endpoint protection regardless of internal resources.

10 Examples of Smarter Alerting

A guide for SRE, Dev and Ops teams who need to be proactive in finding problems before service is affected, without debilitating alert noise.