We need to talk about mathematical backdoors in encryption algorithms

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

By John Leyden


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


More from The Register

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

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

Western Digital bought Upthere, and just sent its software out there

Storage company's core project joins the GitHub undead

Weak flash demand and disk sales leave Western Digital scrabbling to claw back $800m a year

Revenue drops 20% as market slackens, with worse to come

Seagate and Western Digital neck-and-neck at the nearline drive-in

Seagate ships more units, WD more capacity – it's a wash

Shingled-minded Western Digital insists its latest hard drive sets disk capacity record

15TB Ultrastar DC HC620 targets hyperscale crowd

Array with it: Western Digital's finance arm slings a few million at Excelero

Tech collab could see Excelero support WD’s OpenFlex and Kingfish

Western Digital deploys heatsink on remodelled M.2 to tempt gamers

Bringing a 'tangible, next-level competitive boost' apparently...


Faster Response with CrowdStrike and MITRE ATT&CK

Today’s threat landscape has created new challenges for security analysts and incident responders.

Delivering Instant Experiences: Optimizing the Performance, Cost and Capacity of Data-Driven Applications

The question is, how can you accelerate data processing to keep up with accelerating business demands for an instant experience? Get the answer to this question and more in this upcoming webinar hosted by The Register’s Elena Perez. With insight from Sheryl Sage, Director of Partner Marketing at Redis Labs, and Frank Ober, a Non-Volatile Memory Solutions Architect from Intel Corporation.

Defending Against the Siege of Ransomware

Ransomware is big business. But to win the war against this cyber threat, without paying a king’s ransom, you need a strong defense.

Evolving Datacenters without Complexity

In this session, we’ll talk about how IT leaders are advancing the capabilities of their datacenters to rise to today’s challenges. Our guest speaker, Chris Bradford, Product Manager at DataStax will bring first-hand expertise to a discussion with The Register host Elena Perez.