We need to talk about mathematical backdoors in encryption algorithms

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


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

READ MORE

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. ®

Similar topics


Other stories you might like

  • UK science suffers as lawmakers continue to dither over Brexit negotiations

    Horizons Europe carrot dangled amid protocol wrangling

    A report from the UK House of Commons' European Scrutiny Committee has blamed delays in Brussels for choking off revenue streams to British institutions and businesses.

    The UK departed the European Union following a 2016 referendum. One of the results was that UK businesses were no longer able to tender for lucrative contracts within the bloc.

    The Brexit Divorce Bill uncomfortably laid out the facts back in 2018. The satellite navigation system Galileo was one victim despite substantial involvement from the UK in its development. Another was the Copernicus Earth monitoring programme; the UK was infamously snubbed when the European Space Agency (ESA) handed out six juicy contracts to institutions from the Continent.

    Continue reading
  • Warehouse belonging to Chinese payment terminal manufacturer raided by FBI

    PAX Technology devices allegedly infected with malware

    US feds were spotted raiding a warehouse belonging to Chinese payment terminal manufacturer PAX Technology in Jacksonville, Florida, on Tuesday, with speculation abounding that the machines contained preinstalled malware.

    PAX Technology is headquartered in Shenzhen, China, and is one of the largest electronic payment providers in the world. It operates around 60 million point-of-sale (PoS) payment terminals in more than 120 countries.

    Local Jacksonville news anchor Courtney Cole tweeted photos of the scene.

    Continue reading
  • Everything you wanted to know about modern network congestion control but were perhaps too afraid to ask

    In which a little unfairness can be quite beneficial

    Systems Approach It’s hard not to be amazed by the amount of active research on congestion control over the past 30-plus years. From theory to practice, and with more than its fair share of flame wars, the question of how to manage congestion in the network is a technical challenge that resists an optimal solution while offering countless options for incremental improvement.

    This seems like a good time to take stock of where we are, and ask ourselves what might happen next.

    Congestion control is fundamentally an issue of resource allocation — trying to meet the competing demands that applications have for resources (in a network, these are primarily link bandwidth and router buffers), which ultimately reduces to deciding when to say no and to whom. The best framing of the problem I know traces back to a paper [PDF] by Frank Kelly in 1997, when he characterized congestion control as “a distributed algorithm to share network resources among competing sources, where the goal is to choose source rate so as to maximize aggregate source utility subject to capacity constraints.”

    Continue reading
  • How business makes streaming faster and cheaper with CDN and HESP support

    Ensure a high video streaming transmission rate

    Paid Post Here is everything about how the HESP integration helps CDN and the streaming platform by G-Core Labs ensure a high video streaming transmission rate for e-sports and gaming, efficient scalability for e-learning and telemedicine and high quality and minimum latencies for online streams, media and TV broadcasters.

    HESP (High Efficiency Stream Protocol) is a brand new adaptive video streaming protocol. It allows delivery of content with latencies of up to 2 seconds without compromising video quality and broadcasting stability. Unlike comparable solutions, this protocol requires less bandwidth for streaming, which allows businesses to save a lot of money on delivery of content to a large audience.

    Since HESP is based on HTTP, it is suitable for video transmission over CDNs. G-Core Labs was among the world’s first companies to have embedded this protocol in its CDN. With 120 points of presence across 5 continents and over 6,000 peer-to-peer partners, this allows a service provider to deliver videos to millions of viewers, to any devices, anywhere in the world without compromising even 8K video quality. And all this comes at a minimum streaming cost.

    Continue reading
  • Cisco deprecates Microsoft management integrations for UCS servers

    Working on Azure integration – but not there yet

    Cisco has deprecated support for some third-party management integrations for its UCS servers, and emerged unable to play nice with Microsoft's most recent offerings.

    Late last week the server contender slipped out an end-of-life notice [PDF] for integrations with Microsoft System Center's Configuration Manager, Operations Manager, and Virtual Machine Manager. Support for plugins to VMware vCenter Orchestrator and vRealize Orchestrator have also been taken out behind an empty rack with a shotgun.

    The Register inquired about the deprecations, and has good news and bad news.

    Continue reading
  • Protonmail celebrates Swiss court victory exempting it from telco data retention laws

    Doesn't stop local courts' surveillance orders, though

    Encrypted email provider Protonmail has hailed a recent Swiss legal ruling as a "victory for privacy," after winning a lawsuit that sees it exempted from data retention laws in the mountainous realm.

    Referring to a previous ruling that exempted instant messaging services from data capture and storage laws, the Protonmail team said this week: "Together, these two rulings are a victory for privacy in Switzerland as many Swiss companies are now exempted from handing over certain user information in response to Swiss legal orders."

    Switzerland's Federal Administrative Court ruled on October 22 that email providers in Switzerland are not considered telecommunications providers under Swiss law, thereby removing them from the scope of data retention requirements imposed on telcos.

    Continue reading
  • Japan picks AWS and Google for first gov cloud push

    Local players passed over for Digital Agency’s first project

    Japan's Digital Agency has picked Amazon Web Services and Google Cloud for its first big reform push.

    The Agency started operations in September 2021, years after efforts like the UK's Government Digital Service (GDS) or Australia's Digital Transformation Agency (DTA). The body was a signature reform initiated by Prime Minister Yoshihide Suga, who spent his year-long stint in the top job trying to curb Japan's reliance on paper documents, manual processes, and faxes. Japan's many government agencies also operated their websites independently of each other, most with their own design and interface.

    The new Agency therefore has a remit to "cut across all ministries" and "provide services that are driven not toward ministries, agency, laws, or systems, but toward users and to improve user-experience".

    Continue reading
  • Singaporean minister touts internet 'kill switch' that finds kids reading net nasties and cuts 'em off ASAP

    Fancies a real-time crowdsourced content rating scheme too

    A Minister in the Singapore government has suggested the creation of an internet kill switch that would prevent minors from reading questionable material online – perhaps using ratings of content created in real time by crowdsourced contributors.

    "The post-COVID world will bring new challenges globally, including to us in the security arena," said Minister for Defence Dr Ng Eng Hen at a Tuesday ceremony to award the city-state's 2021 Defense Technology Prize.

    "For operations, the SAF (Singapore Armed Force) has to expand its capabilities in the digital domain. Whether for administrative or operational purposes, I think that we will need to leverage technology to the maximum," he declared.

    Continue reading

Biting the hand that feeds IT © 1998–2021