Modern Cryptography: Applied Mathematics for Encryption and Informanion Security (2016)
PART IV. Applications
Chapter 18. Cryptographic Backdoors
In this chapter we will cover the following:
What are cryptographic backdoors?
General concepts of cryptographic backdoors
Specific examples of cryptographic backdoors
Prevalence of cryptographic backdoors
Countermeasures
In 2013 Edward Snowden released classified documents that demonstrated that the U.S. National Security Agency (NSA) had placed a cryptographic backdoor into a particular pseudo-random-number generator (PRNG), the DUAL_EC_DRBG, or Dual Elliptic Curve Deterministic Random Bit Generator (some sources cite it as DUAL_ECC_DRBG, emphasizing the elliptic curve cryptography). This made quite a bit of news in the computer security world. Suddenly everyone was talking about cryptographic backdoors, but few people knew what such a backdoor was or what it meant. Did it mean the NSA could read your e-mail as easily as reading the New York Times? Did it mean you were vulnerable to hackers exploiting that backdoor? In this chapter we are going to address these questions.
This chapter provides a general overview of cryptographic backdoors, including how they function and the specific types. We will also discuss a few general countermeasures for defeating cryptographic backdoors. Although these details are quite interesting, the most important part of this chapter is the general concepts. By the end of this chapter, you should have a working understanding of what a cryptographic backdoor is and how it affects security.
What Are Cryptographic Backdoors?
The concept of a “backdoor” is borrowed from computer security and computer programming. In computer programming, a backdoor is a defect or feature of a computer system that provides a way for someone to bypass normal authentication. A backdoor is usually included in the application code by the programmer, often for benign purposes, such as the ability to circumvent the normal authentication process (which may be cumbersome) for testing purposes. It is important that these backdoors be removed from the code before the final product is distributed, however. In security, a backdoor can allow an attacker to circumvent the normal authentication for a target computer. An attacker might send a Trojan horse that contains some remote desktop software to a victim machine, such as Timbuktu, or he may use a tool such as Netcat to open a reverse command shell. Then the attacker could circumvent normal authentication methods and directly access the target computer.
Note
Netcat is a popular tool with network administrators and with hackers that provides a robust set of networking tools. Most relevant to the current discussion is the fact that Netcat allows the administrator or hacker to set up remote command-line connections with a target computer.
The concept of a cryptographic backdoor is not exactly the same, but it is related. A software backdoor provides unfettered access to the intruder. A cryptographic backdoor makes the encrypted message more susceptible to cryptanalysis—in other words, some element of a cipher is susceptible to an attack. For example, if the PRNG used to generate a key for a symmetric cipher contains a backdoor, then that key is not really random.
Author Nick Sullivan describes the issue in the following way:
TrueCrypt, like most cryptographic systems, uses the system’s random number generator to create secret keys. If an attacker can control or predict the random numbers produced by a system, they can often break otherwise secure cryptographic algorithms. Any predictability in a system’s random number generator can render it vulnerable to attacks. …It’s absolutely essential to have an unpredictable source of random numbers in secure systems that rely on them.1
General Properties
A kleptographic attack occurs when an attacker uses cryptographic algorithms that resemble the original or actual algorithms to provide an advantage in cracking encrypted messages. In both cryptographic backdoors and kleptography, some basic properties are necessary for success:
Output indistinguishability If you compare the output of the standard algorithm without the backdoor to the output of the algorithm with the backdoor, no difference is discernible.2 Without output indistinguishability, anyone with even moderate cryptographic skills could simply compare the output of your algorithm implementation with the backdoor to other algorithm implementations and discover the existence of the backdoor.
Confidentiality If a cryptographic algorithm has a backdoor, that backdoor should not generally reduce the security of the cipher. In other words, the vulnerability should be available only to the person who created the backdoor. A random attacker, unaware of the existence of the backdoor, should not have an increased chance to break the cipher.
Ability to compromise the backdoor Obviously, the backdoor must provide a means whereby the person who created the backdoor can compromise the cipher. This is, indeed, the entire purpose of having a cryptographic backdoor. As mentioned, however, that should not make the cipher more susceptible to general attacks.
Bruce Schneier described three other properties that he believed a successful cryptographic backdoor should possess:3
Low discoverability The less the backdoor affects the normal operations of the program and the smaller the backdoor, the better. Ideally, the backdoor should not affect functionality and should just look like regular functional code. For example, an e-mail encryption backdoor that appends a plain-text copy to the encrypted copy is much less desirable than a backdoor that reuses most of the key bits in a public initialization vector.
High deniability If the backdoor is discovered, it should look like a mistake—such as a change in the operation code, a “mistyped” constant, or an “accidental” reuse of a single-use key multiple times. According to Schneier, “This is the main reason I am skeptical about _NSAKEY as a deliberate backdoor, and why so many people don’t believe the DUAL_EC_DRBG backdoor is real: they’re both too obvious.”
Minimal conspiracy A good backdoor should be known to very few people. Says Schneier, “That’s why the [2013] described potential vulnerability in Intel’s random number generator worries me so much; one person could make this change during mask generation, and no one else would know.”
In general, a cryptographic backdoor needs to, first and foremost, allow the attacker to subvert the security of the backdoored cipher.4 It must also be relatively easy to use. Preferably, it would compromise a wide number of ciphers, giving the attacker the greatest range of potential access.
Examples of Backdoors
The following examples of specific cryptographic backdoors provide a practical illustration of the general principles. The RSA example is probably the easiest to understand. The Dual_EC_DRBG backdoor has received so much attention in the media that it would be impossible to have a discussion of backdoor and not discuss it.
Note
It is not critical that you memorize the backdoor techniques discussed in this section, but you should understand the general concepts.
Dual_EC_DRBG
The Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG) was promoted as a cryptographically secure PRNG (CSPRNG) by the National Institute of Standards and Technology (NIST). This PRNG is based on the elliptic curve discrete logarithm problem (ECDLP) and is one of the four CSPRNGs standardized in NIST SP 800-90A. As early as 2006, cryptography researcher Gjøsteen suggested that the algorithm had significant security issues.5 In 2007, researchers Brown and Gjøsteen discovered issues with the efficiency of Dual_EC_DRBG6 and questioned why the government would endorse such an inefficient algorithm. Then, in 2007, Shumow and Ferguson published an informal presentation suggesting that Dual_EC_DRBG might have a cryptographic backdoor.7
In 2013, the New York Times reported that internal NSA memos leaked by Edward Snowden suggest that an RNG generated by the NSA that was used in the Dual_EC_DRBG standard does indeed contain a backdoor for the NSA.8 Given that there had been discussions regarding the security of Dual_EC_DRBG for many years, this revelation was not a particular shock to the cryptographic community. However, it generated a great deal of surprise in the general security community.
Note
The following section is much easier to understand if you have a good understanding of elliptic curve cryptography in general. You might review Chapter 11 before proceeding.
Details The Dual_EC_DRBG algorithm specification specifies an elliptic curve, which is basically just a finite cyclic group G. The algorithm also specifies two group elements, P and Q. The NIST standard for Dual_EC_DRBG provides no insight into how P and Q are chosen. Normally you would expect these to be chosen randomly, but in the case of Dual_EC_DRBG, they were selected by the NSA. It is the choice of P and Q that forms the basis for the backdoor.
The following information provides insight into the backdoor within Dual_EC_DRBG.
In the simplified algorithm, the state of the PRNG at time t is some integer s. To run the PRNG forward one step, you would do the following:
1. Compute sP and produce the result as an integer labeled r.
2. Compute rP and produce the result as an integer s ′ (this will become the new state in the next step).
3. Compute rQ (remember we started with two points, P and Q) and output it as this step’s output from the PRNG.
It should be obvious that P = eQ for some integer e. Not knowing e makes it completely impractical to compute P from Q. However, since the NSA chose the values P and Q, it could have chosen them by picking Q randomly, picking e randomly, and setting P = eQ. In particular, the NSA could have chosen them so that they know e.
Thus, it is this number e that functions as a backdoor and facilitates someone breaking the PRNG. You can observe one output from the PRNG—namely, rQ. This can be multiplied by e, to get erQ. Note that erQ = r(eQ) = rP = s ′. So the attacker can infer what the next state of the PRNG will be and predict the state of the PRNG and thus the next random number produced by the PRNG. If this PRNG is being used to generate keys, the attacker could consider the first key generated and predict subsequent keys that would be generated by that PRNG.
Recall in Chapter 12 the discussion of German standards for a PRNG; one of the desirable properties for a PRNG is that no one should be able to predict future states of a PRNG from the current state. By placing a backdoor in Dual_EC_DRBG, this standard is violated.
RSA Backdoor
The RSA backdoor involves compromising the generation of keys for RSA. This example is based on an example by Yung & Young RSA labs.9 The specific steps are similar to the usual method of generating RSA keys, but slightly modified.
Before we delve into the steps of the backdoor version of RSA, it might be useful for you to refresh your memory regarding the typical RSA process. RSA key generation is accomplished with the following steps:
1. Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length (such as 2048 bits, 4096 bits, and so on).
2. Let n = pq.
3. Let m = (p–1)(q–1).
4. Choose a small number e, co-prime to m. (Note: Two numbers are co-prime if they have no common factors.)
5. Find d, such that de % m = 1.
6. Publish e and n as the public key. Keep d and n as the secret key.
To encrypt with RSA,
C = Me % n
where M is the message and C is the cipher text.
To decrypt with RSA:
P = Cd % n
Now the backdoor steps are as follows:
1. Choose a large value x randomly that is of the appropriate size for an RSA key (such as 2048 bits, 4096 bits, and so on).
2. Compute the cryptographic hash of this x value, denoted as H(x). We will call that hash value p.
3. If the cryptographic hash of x, the value p, is either a composite number or if p–1 is not relatively prime to e, then repeat step 1 until p is a prime. Then proceed to step 4. (Note that you may need to repeat this step several times to find a suitable H(x), so this entire process is not particularly efficient.)
4. Choose some large random number we will call R.
5. Encrypt the value of x with the attacker’s own private key. Denote this value as c. Essentially c is the digital signature of x, signed by the attacker. (Note that this is yet another flaw in this particular approach. You have to ensure you generate a public/private key pair just for this purpose. If you use a private/public key pair that you use for general communication, you will have just signed your backdoor.)
6. Now you solve for (q,r) in (c || R) = pq + r.
7. Much like computing H(x), if it turns out that q is composite or q–1 is not co-prime to e, then go back to step 1.
8. Next, output the public key (n = pq,e) and the private key p.
The victim’s private key can then be recovered in the following manner:
1. The attacker obtains the public key (n,e) of the user. Let u be the 512 uppermost bits of n.
2. The attacker sets c1 = u and c2 = u + 1. (c2 accounts for a potential borrow bit having been taken from the computation.)
n = pq = (c || R) – r
3. The attacker decrypts c1 and c2 to get s1 and s2, respectively
4. Either p1 = H(s1) or p2 = H(s2) will divide n.
Only the attacker can perform this operation since only the attacker knows the needed private decryption key.
Compromising a Hashing Algorithm
Some researchers have even been exploring methods for compromising cryptographic hashing algorithms. Several cryptographers created a cryptographic backdoor for SHA-1 and then wrote the following:
SHA-1 as a target because it is (allegedly) the most deployed hash function and because of its background as an NSA/NIST design. We exploit the freedom of the four 32-bit round constants of SHA-1 to efficiently construct 1-block collisions such that two valid executables collide for this malicious SHA-1. Such a backdoor could be trivially added if a new constant is used in every step of the hash function. However, in SHA-1 only four different 32-bit round constants are used within its 80 steps, which significantly reduces the freedom of adding a backdoor. Actually our attack only modifies at most 80 (or, on average, 40) of the 128 bits of the constants.10
The details of their approach are not important to our current discussion. What is important is that this is one more avenue for compromising cryptographic algorithms—not only symmetric ciphers and asymmetric ciphers, but cryptographic hashes as well.
Other Ways to Compromise Cryptography
Cryptographic backdoors are an obvious way to compromise cryptography, and they are clearly of interest to anyone studying cryptography. However, other mechanisms could be used. Frequently, the implementation of cryptography is flawed, either intentionally or accidentally. This means that the algorithms have not been tampered with, but that the encryption is circumvented.
Heartbleed Bug
The Heartbleed Bug is an excellent example of such a vulnerability, which was discovered in the OpenSSL software in December 2011 and publically disclosed in April 2014. The issue involves the Heartbeat extension for TLS used by OpenSSL, which is a mechanism whereby a client and server using OpenSSL can verify that the other machine is still alive (or still has a heartbeat). To do this, the client sends a heartbeat request message with a 16-bit payload. The server responds by sending back 16 bits from RAM. It is impossible for those 16 bits to provide any meaningful data to the client, other than that the server is still functioning. The bug involved a failure to check bounds, however, and the attacker could get up to 64 kilobytes of the server’s memory.
This is a particularly critical issue because OpenSSL is widely used on e-commerce servers. So 64KB of data from an e-commerce server is likely to include cryptographic keys of other users, credit card information, and other sensitive data.
This is a classic example in which the cryptographic algorithm was not compromised and the key was not broken via cryptanalysis, but the data that was intended to be protected was exposed. What makes this especially pertinent to our discussions in this chapter is that it appears that the NSA and possibly other intelligence agencies were aware of this bug, but did not publically disclose it. Essentially, these intelligence agencies did not create this backdoor, but they found it and exploited it.
Key Escrow
Another vulnerability issue involves key escrows. To understand this vulnerability, you must first understand key escrows. Consider a company wherein all employees are issued digital certificates so they can exchange encrypted information as needed. Each employee has his or her private key on his or her own machine. Eventually someone’s machine will crash and that user’s private key will be lost. To prevent this situation, many companies create a key escrow server, which has a copy of everyone’s private key. Clearly this is a security risk.
The correct way to set up a key escrow server involves several requirements:
The server should have no other function than to store the keys.
No one person should be able to access the keys. For example, one person can have access to the machine itself and another can have the password for the encrypted folder on that server that stores everyone else’s key. These two individuals must collaborate to get a key out of escrow. That makes malicious activity more difficult.
This server should not be networked. You must physically go to the server to retrieve a lost key.
The server itself, and the room it is in, must be highly secured.
If all of these measures are not taken, someone could breach the security of the escrow server and get the private keys of all the individuals. Consider, for example, the ramifications if spyware was on that server. This is yet another example of circumventing cryptography without actually breaking any algorithm or keys.
The Prevalence of Backdoors
Although a cryptographic backdoor can be a significant security issue, the problem is not particularly prevalent. Consider the resources that are needed to implement a cryptographic backdoor. As you have seen in this chapter, the algorithms are not overly difficult, but how does an attacker get a target organization to use a cipher, PRNG, key generator, or hash that contains a backdoor? Clearly, there are two primary methods for doing this, a governmental method and a private method, and here we will look at both.
Governmental Approach
Government agencies either implement backdoors in standards, as with DUAL_EC_DRBG, or work with a company to include a backdoor in its product. This method always runs the risk of being discovered, however. Even the most secure intelligence agency, when working with outside vendors, runs a risk of operational security being compromised.
Let’s look at an example. This example was not really a backdoor, so much as a method whereby law enforcement, with a warrant, could gain access to symmetric keys used in secure voice communications. The Skipjack symmetric cipher was implemented on the Clipper chip. However, negative reactions to the possibility of the federal government being able to listen in on secure communications prevented this project from moving forward.
According to Schneier,
The FBI tried to get backdoor access embedded in an AT&T secure telephone system in the mid-1990s. The Clipper Chip included something called a LEAF: a Law Enforcement Access Field. It was the key used to encrypt the phone conversation, itself encrypted in a special key known to the FBI, and it was transmitted along with the phone conversation. An FBI eavesdropper could intercept the LEAF and decrypt it, then use the data to eavesdrop on the phone call.11
Snowden also alleged that Cisco cooperated with the NSA to introduce backdoors in Cisco products. Specifically, Snowden said that Cisco routers built for export (not for use in the United States) were equipped with surveillance tools. He further claimed that this was done without the knowledge of Cisco. According to an article in InfoWorld, “Routers, switches, and servers made by Cisco are booby-trapped with surveillance equipment that intercepts traffic handled by those devices and copies it to the NSA’s network.”12
In other cases, a government agency may gain the full cooperation of a technology company. Several sources claim that the computer security firm RSA took $10 million from the NSA to make the Dual_EC_DRBG the default for its BSAFE encryption toolkit.13, 14
Private Citizen/Group Approach
It may seem like cryptographic backdoors are a tool that only government agencies—generally intelligence gathering agencies—can use, but that is not the case. A small group, or even an individual, might also introduce a cryptographic backdoor, and although I am not aware of any real-world cases of this occurring, it is certainly possible. Following are three ways that an individual or small group might implement a cryptographic backdoor. Clearly this makes such backdoors a serious concern.
PRNG People often select third-party products to generate random numbers for cryptographic keys. Any competent programmer with a working knowledge of cryptographic backdoors could create a product that generated random numbers/keys with a backdoor. Such a product could then be released as freeware, or via a web site, guaranteeing a significant number of people might use the PRNG.
Product tampering Any individual working in a technology company, if that individual works in the appropriate section of the company, could potentially introduce a backdoor without the company being aware of it.
Hacking Although this is more difficult and thus less likely to occur, there is always the potential of someone hacking into a device and compromising its cryptography. For example, a router with VPN capabilities must generate new keys for each VPN session. Theoretically, someone could hack that router and alter its key generation. Such a task would be difficult, however.
Note
Although I indicate that I have not yet heard of individuals or small groups creating cryptographic backdoors, that may be due simply to a lack of skills on their part. The primary purpose in my writing this book was to provide a real understanding of cryptography. The same lack of knowledge about the details of cryptography also permeates the hacking community.
Countermeasures
Detecting cryptographic backdoors is a very difficult task. As you have seen earlier in this chapter, one of the goals of a cryptographic backdoor is to be undetectable. You could, of course, subject any random number generator or cipher to extensive cryptanalysis to determine if a backdoor is likely, but that process is very time-consuming and beyond the capabilities of most organizations. And waiting until some researcher discovers a likely backdoor is inefficient. You could be using that backdoor cipher for quite a few years before some researcher discovers the backdoor.
The first issue is key generation. There is always a risk when you rely on a third party for key generation. The best solution, assuming you have the necessary skills in programming and basic mathematics, is to write code for your own key generation. For symmetric keys, I recommend implementing Blum, Blum, Shub, Yarrow, or Fortuna. Crépeau and Slakmon state the following: “This suggests that nobody should rely on RSA key generation schemes provided by a third party. This is most striking in the smartcard model, unless some guarantees are provided that all such attacks to key generation cannot have been embedded.”15
For many, writing code for key generation is not a viable option. For example, many programmers who write applications for Microsoft Windows rely on the Microsoft CryptoAPI for key generation. A simple mechanism, at least for generating symmetric keys, would be to take that API (or any other) and subject it to a cryptographic hash that has the appropriate sized output, and then use that output as the key. An even simpler approach would be to generate two random numbers, and then XOR them together using the resulting number as the key. Either technique will essentially bury the cryptographic backdoor in another operation. The cryptographic hashing technique is the more secure and reliable of the two methods.
There have been some attempts in the industry to address this issue as well. The Open Crypto Audit Project is an attempt to detect cryptographic flaws, including backdoors, in open source software. The group includes a number of respected cryptographers. Its web site (https://opencryptoaudit.org/) lists the organization’s charter:
Provide technical assistance to free open source software (“FOSS”) projects in the public interest
Coordinate volunteer technical experts in security, software engineering, and cryptography
Conduct analysis and research on FOSS and other widely used software in the public interest
Contract with professional security researchers and information security firms to provide highly specialized technical assistance, analysis, and research on FOSS and other widely used software in the public interest
Conclusions
This chapter provided an introduction to cryptographic backdoors. Since the Snowden revelations of 2013, this topic has become very widely discussed in the security community. Cryptographic researchers have been exploring backdoors for many years before those revelations, however.
You need not know the details of the specific implementations discussed in this chapter; however, the general concepts of output indistinguishability, confidentiality, and so on, are critical, and you should have a solid working knowledge of these topics. It is also important that you have some knowledge of the countermeasures discussed in this chapter.
Test Your Knowledge
1. With regard to cryptographic backdoors, what is output indistinguishability?
2. With regard to cryptographic backdoors, what is confidentiality?
3. What made the Clipper chip relevant to backdoors?
4. ____________ is a colloquial term for creating cryptographic algorithms that resemble the original/actual algorithms, but provide the creator an advantage in cracking encrypted messages.
5. In simple terms, the backdoor in Dual_EC_DRBG is based on what?
Answers
1. With output indistinguishability, you cannot distinguish the backdoor version of a cipher from the traditional version of the cipher.
2. The cipher with the backdoor should still be secure from attackers who don’t know about the backdoor.
3. It was designed so that all cryptographic keys would be kept in an escrow that would be available to law enforcement.
4. Kleptography
5. The selection of P and Q
Endnotes
1. N. Sullivan, “How the NSA (may have) put a backdoor in RSA’s cryptography: A technical primer,” 2014, http://arstechnica.com/security/2014/01/how-the-nsa-may-have-put-a-backdoor-in-rsas-cryptography-a-technical-primer/.
2. A. Young and M. Yung, “Kleptography: Using Cryptography Against Cryptography,” 2002, http://cryptome.org/2013/09/klepto-crypto.pdf.
3. B. Schneier, “Defending Against Crypto Backdoors,” 2013, www.schneier.com/blog/archives/2013/10/defending_again_1.html.
4. B. Schneier, M. Fredrikson, T. Kohno, and T. Ristenpart, “Surreptitiously Weakening Cryptographic Systems,” 2015, https://eprint.iacr.org/2015/097.pdf.
5. K. Gjøsteen, “Comments on Dual-EC-DRBG/NIST SP 800-90, Draft December 2005,” 2006, www.math.ntnu.no/~kristiag/drafts/dual-ec-drbg-comments.pdf.
6. D. Brown and K. Gjøsteen, “A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator,” 2007, http://eprint.iacr.org/2007/048.pdf.
7. D. Shumow and N. Ferguson, “On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng,” 2007, http://rump2007.cr.yp.to/15-shumow.pdf.
8. M. Scott, “Backdoors in NIST elliptic curves,” 2013, www.certivox.com/blog/bid/344797/Backdoors-in-NIST-elliptic-curves.
9. A. Young and M. Yung, “Malicious Cryptography: Kleptographic Aspects,” 2005, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.6265&rep=rep1&type=pdf.
10. A. Albertini, J. Aumasson, M. Eichlseder, F. Mendel, and M. Schläffer, “Malicious Hashing: Eve’s Variant of SHA-1,” 2014, https://malicioussha1.github.io/doc/malsha1.pdf.
11. Schneier, 2013.
12. B. Snyder, “Snowden: The NSA planted backdoors in Cisco products,” InfoWorld, 2014, www.infoworld.com/article/2608141/internet-privacy/snowden--the-nsa-planted-backdoors-in-cisco-products.html.
13. J. Menn, “Exclusive: Secret contract tied NSA and security industry pioneer,” 2013, www.reuters.com/article/2013/12/20/us-usa-security-rsa-idUSBRE9BJ1C220131220.
14. A. Glaser, “After NSA Backdoors, Security Experts Leave RSA for a Conference They Can Trust,” 2014, www.eff.org/deeplinks/2014/01/after-nsa-backdoors-security-experts-leave-rsa-conference-they-can-trust.
15. C. Crépeau and A. Slakmon, “Simple Backdoors for RSA Key Generation,” 2003, http://link.springer.com/chapter/10.1007%2F3-540-36563-X_28#page-2.