Backdoors in Algorithms

Perhaps the most obvious, but arguably the most controversial, way of addressing the cryptography dilemma is to deploy a cryptographic algorithm with a backdoor, a secret weakness only known to the algorithm designers and those who control its use. The idea is that those who are aware of this backdoor can exploit it to recover information that has been encrypted using any cryptosystem relying on this algorithm.

Note: The term ‘backdoor’ is sometimes more widely used in this context to describe a range of techniques for subverting cryptographic security. We’ll restrict our use of this term to the deliberate design of weaknesses in cryptographic algorithms.

There are two different types of cryptographic algorithms that could most readily be designed to contain a backdoor:

• Encryption algorithm: An encryption algorithm could be designed to contain a backdoor that results in the ciphertext not being as difficult to decrypt as it first seems.

• Deterministic generator: A deterministic generator used to generate keys could be designed to contain a backdoor that results in the keys not being as random as expected.

Of these two approaches, placing a backdoor in a deterministic generator is potentially more powerful since this could be used to undermine any cryptosystem deploying this generator, independent of the encryption algorithm used.

Use of backdoors

One issue with putting a secret backdoor into an encryption algorithm is that if this backdoor is subsequently discovered and publicized, then:

1. The algorithm might become insecure as a result.

2. Even if still secure, the known existence of this backdoor might discourage the use of the algorithm.

Indeed, designing an algorithm with a secret backdoor doesn’t conform to the important Kerckhoffs’ principle. Therefore, anyone placing a backdoor in a cryptographic algorithm will need to be confident the backdoor will never become common knowledge. As we will now explain, the evolution of cryptographic technology and its use have significantly affected the viability of using backdoors to address the cryptography dilemma.

Historical use of backdoors

The earliest users of cryptography were governments and the military. One of the first manifestations of the cryptography dilemma came when some governments wanted to sell cryptographic technology to other governments that they didn’t ‘trust’ or who they wanted to gain an intelligence advantage over.

It’s alleged that backdoors were thus sometimes inserted into cryptosystems sold worldwide. There were several issues that made this a much more viable tactic to control the use of cryptography then than it would today:

• Computing technology: High-grade cryptography before the 1980s was implemented in hardware devices. This is why the mathematical details of how the cryptographic algorithms worked could be hidden in hardware in ways that were hard to extract and scrutinize.

• Proprietary algorithms: Most cryptographic algorithms were proprietary, which made inserting a backdoor into such an algorithm easier than doing so for one open to wider inspection.

• Knowledge about cryptography: Wider knowledge about cryptography was limited to a few experts. Even if details of a cryptographic algorithm became public knowledge, there were relatively few people in any position to evaluate it.

Modern use of backdoors

The modern era in cryptography is often associated with the publication of the DES standard. Even though DES was a published standard, there were genuine concerns among the fledgling cryptography community outside of the military and government that DES might contain a backdoor. One of the reasons this kind of suspicion arose was because the design criteria for DES were not made public. This concern was accentuated by the lack of public experts who could allay such fears.

Contrast this with the design process for AES, in which the development process included scrutiny of the rationale for the algorithm design. This was partly to prevent any accusations that AES contained a backdoor. This reflected the very different environment within which AES was developed in the late 1990s. Many cryptographic algorithms such as AES were expected to run in software and hardware, their details were expected to be open to public scrutiny, and there was a thriving community of cryptographic expertise outside of the military and government.

Today’s environment makes backdoors even less palatable. Modern users of cryptographic technology want assurance of the strength of the cryptography being deployed, not algorithms with potential secret weaknesses.

Dual_EC_DRBG

Perhaps the strongest illustration of the technical challenges with deploying backdoors is the example of Dual_EC_DBRG, a deterministic generator recommended for use by several standardization bodies in 2004 and 2005. This algorithm generates pseudorandom numbers based on elliptic curves. The Dual_EC_DBRG algorithm was public and available for experts to analyze.

The main concern raised about Dual_EC_DBRG was that it relied upon two specific constant values for which the rationale was not made clear. This was accentuated by the fact that the US National Security Agency (NSA) had been the main driver behind including this algorithm in the relevant standards. Nevertheless, it soon found its way into various commercial products.

Research soon showed that including a backdoor in Dual_EC_DBRG was theoretically possible. This research also revealed that an attacker with knowledge of a backdoor and who can observe a very small amount of output from the Dual_EC_DBRG generator could then predict the subsequent output. If anyone know about the backdoor, then an attack on Dual_EC_DBRG could be devastating.

Among the many revelations following the leaks of Edward Snowden was information suggesting that the NSA had indeed designed a backdoor into Dual_EC_DBRG. The news that Dual_EC_DBRG probably did have a backdoor was met with dismay by the wider community, upset that a government agency could attempt to undermine the security of cryptographic algorithms designed for general use in the modern era. The cryptographic community was also deeply concerned that an algorithm with such a flaw managed to get past expert review (although some of the affected standards included optional settings, which defeated the backdoor). Dual_EC_DBRG has now been withdrawn from the relevant standards.

These events revealed that modern cryptographic algorithms may still contain backdoors. However, the subsequent fallout from the Dual_EC_DBRG incident also suggested that many of the parties involved had regrets about the entire affair. Perhaps this is one of the last times backdoors in algorithms will be used to address the cryptography dilemma.