7.3. Backdoor Attacks

Backdoor attacks on a public-key cryptosystem refer to attacks embedded in the key generation procedure (hardware or software) by the designer of the procedure. A contaminated cryptosystem is one in which the key generation procedure comes with hidden backdoors. A good backdoor attack should meet the following criteria:

• To a user, keys generated by the contaminated system should be indistinguishable from those generated by an honest version of the cryptosystem. For example, the parameters and keys must look sufficiently random.

• Keys generated by the contaminated system should satisfy the input/output requirements of an honest system. For example, for the RSA cryptosystem the user should be allowed to opt for small public exponents.

• A contaminated key generation procedure should not run (on an average) much slower than the honest procedure.

• The designer (and nobody else) should have the exclusive capability of determining the secret information from a contaminated published public key.

• A user (other than the designer), detecting or suspecting information leakage from a contaminated system, may reverse-engineer the binaries or the smart card to identify the contaminated key generation procedure. The user may even be given the source code of the contaminated routine. Still the user should not be able to steal keys from other users of the same contaminated system. In this sense, a good backdoor protects the designer universally.

• A stronger requirement is that reverse-engineering (or source code) should also not allow a user to distinguish (in poly-time) between keys generated by the contaminated procedure and those generated by a genuine procedure. It is exclusively the designer who should possess the capability to make such distinctions in poly-time.

Young and Yung [307] have proposed using public-key cryptography itself for generating backdoors. In their schemes, the attacker (the designer) embeds the encryption routine and the encryption key of the attacker in the key generation procedure of the contaminated system. The decryption key of the attacker is not embedded in the contaminated system and is known only to the attacker. The attacker’s encryption system is assumed to be honest and unbreakable and, thereby, it gives the attacker the exclusive power to decrypt contaminated keys. Young and Yung call such a backdoor a secretly embedded trapdoor with universal protection (SETUP). They also coined the term kleptography to denote such use of cryptography against cryptography.

In the rest of this section, we denote the attacker’s encryption and decryption functions by f_e and f_d respectively. We often do not restrict these functions to public-key routines only. Since public-key routines are slow, symmetric-key routines can be employed in practice. Simple XOR-ing with a fixed bit string (known to the designer) may also suffice. However, for these faster alternatives of f_e, f_d, reverse engineering reveals the symmetric key or the XOR operand to the user who can subsequently mimic the attacker to steal keys generated elsewhere by the same contaminated system.

We use the following shorthand notations. Here, n stands for a positive integer that can be naturally identified with a unique bit string having the most significant (that is, leftmost) bit equal to 1.

|n|	=	the bit length of n.
lsbk(n)	=	the least significant k bits of n.
msbk(n)	=	the most significant k bits of n.
(a1 ‖ a2 ‖ · · · ‖ ar)	=	the concatenation of the bit strings a1, a2, . . . , ar.

7.3.1. Attacks on RSA

RSA, (seemingly) being the most popular public-key cryptosystem, has been the target of most cryptanalytic attacks. Backdoor attacks are not an exception. The backdoor attacks on RSA work by cleverly hiding some secret information in the public key (n, e) of a user. As earlier, we denote the corresponding private exponent by d and the prime factors of n by p and q.

Hiding prime factor

The simplest attack is to choose a fixed p known to the designer. The other prime q is generated randomly, and correspondingly n = pq and the key pairs (e, d) are computed. Reverse engineering such a scheme is pretty simple, since two different moduli n₁ = pq₁ and n₂ = pq₂ belch out p = gcd(n₁, n₂) easily.

A better approach is given in Algorithm 7.3. The function f_e may be RSA encryption under the designer’s public key. In that case, the RSA modulus of the attacker should be so chosen that the condition e < n is satisfied with good probability. On the other hand, if this modulus is too small, then this scheme will generate values of e much smaller than n.

In order to determine the secret exponent from a public key generated using this scheme, the attacker runs Algorithm 7.4. If f_e and f_d are RSA functions under the attacker’s keys, nobody other than the attacker can apply f_d to generate p from e. This provides the designer with the exclusive capability of stealing keys.

A problem with Algorithm 7.3 is that the attacker has little control over the length of the public exponent e. If the user demands a small modulus (like e = 3 or e = 257), this scheme fails to produce one. Algorithm 7.5 overcomes this difficulty by hiding p in the high order bits of the modulus n (instead of in the exponent e). Young and Yung [307] proposed this algorithm in the name PAP (pretty awful privacy). The name contrasts with PGP (pretty good privacy), a popular and widely used RSA implementation.

Algorithm 7.3. A simple backdoor attack on RSA

Input: Output: An RSA modulus n = pq with |p| = |q| = k, and exponents (e, d). Steps: Generate a random k-bit prime q. while (1) {     Generate a random k-bit prime p.     n := pq.     e := fe(p).     if ((e < n) and (gcd(e, φ(n)) = 1)) {         Compute d with ed ≡ 1 (mod φ(n)).         Return (n, e, d).     } }

Algorithm 7.4. Retrieving the secret exponent

Input: An RSA public key (n, e). Output: The corresponding secret (p, q, d) or failure. Steps: p := fd(e). if (p|n) {     q := n/p.     φ := (p – 1)(q – 1).     d := e–1 (mod φ).     Return (p, q, d). } else {     /* The key is not generated by Algorithm 7.3 */     Return failure. }

Algorithm 7.5 works as follows. Following Young and Yung [307], we assume that the attacker uses RSA to realize f_e and f_d. The RSA modulus of the attacker is denoted by N. The attack requires |N| = k, where |p| = |q| = k. To start with, a random prime p of the desired bit length k is generated. This prime is to be encrypted using f_e and so one requires p < N. Instead of encrypting p directly, the attacker uses a permutation function π keyed by K + i for some fixed K and for i = 1, 2, . . . , B, where B is a small bound (typically B = 16). This permutation helps the attacker in two ways. First, one may now have p > N, so a suspicion regarding bounded values of p does not arise. Second, it is cheaper to apply the permutation instead of generating fresh candidates for p. (In an (honest) RSA key generation routine, the prime generation part typically takes the most of the running time.)

Algorithm 7.5. Backdoor attack on RSA: Young and Yung’s PAP scheme

Input: . Output: An RSA modulus n = pq with |p| = |q| = k, and exponents (e, d). Steps: while (1) {     /* Try to generate a suitable p */     Generate a random k-bit prime p.     i = 1.     while (i ≤ B) {         p′ := πK+i(p).    /* Use a keyed permutation πK+i. */         if (p′ < N) { break } else { i++ }     }     /* Try to generate n and q */     if (i ≤ B) {         p″ := fe(p′).  /* Encrypt p′ by the designere’s public key */         j := 1.         while (j ≤ B′) {             .   /*  is a keyed permutation and |p‴| = k or k – 1. */             Generate a pseudorandom bit string a of length k.             X := (p‴ ‖ a).             q := X quot p.             if (|q| = k) and (q is prime) {                 n := pq.                 e := 17.                 while (gcd(e, φ(n)) ≠ 1) { e + = 2. }                 d := e–1 (mod φ(n)).                 Return (n, e, d).             } else { j ++ }         }     } }

Once a suitable p and the corresponding p′ = π_K+i(p) are generated, the encryption function f_e is applied to generate p″ = f_e(p′). Now, instead of embedding p″ directly in the modulus n, another keyed permutation is applied on p″ to generate . This permutation facilitates investigating several choices for q and so is a faster alternative than restarting the entire process afresh, every time an unsuitable q is computed. A pseudorandom bit string a of length k is appended to p‴ to obtain an approximation X for n. If q := ⌊X/p⌋ happens to be a prime of bit length k, the exact n = pq is computed, else another j is tried. If all values of (for some small bound B′) fail, the entire procedure is repeated with a new k-bit prime p.

For random choices of a, the quotients q = ⌊X/p⌋ behave like random integers and so the probability that q is prime is almost the same as random integers of bit length k. Write X = qp + r with r = X rem p. If r > a, then n = X – r has p‴ – 1 embedded in its higher bits, whereas if r ≤ a, then p‴ itself is embedded in the higher bits of n.

Once suitable p and q are found, the PAP routine generates (like PGP) a small encryption exponent e relatively prime to φ(n) and its inverse d modulo φ(n). One can anyway opt for bigger values of e. In that case, instead of choosing e successively from the sequence 17, 19, 21, 23, . . . one writes one’s customized steps for generating candidate values for e. Choosing small e in Algorithm 7.5 indicates resemblance with PGP and the flexibility of doing so.

The authors of PAP compare their implementation of Algorithm 7.5 with that of the honest PGP key generation procedure. The contaminated routine has been found to run on an average only 20 per cent slower than the honest routine.

Algorithm 7.6 recovers the prime factor p of n from a public key (n, e) generated by PAP, using the RSA decryption function f_d of the attacker. Reverse engineering may make available to the user the permutation functions π and π′, the fixed constants K, B, B′ and the designer’s public key. But this knowledge alone does not empower the user to steal PAP-generated keys.

Algorithm 7.6. Retrieving the prime divisor

Input: An RSA public key (n, e) with n = pq. Output: The prime divisor p of n or failure. Steps: Write n = (U ‖ V) with |V | = k. for      for j = 1, 2, . . . , B′ {                  p′ := fd(p″).         for i = 1, 2, . . . , B {             p := (πK+i)–1(p′).             if (p|n) { Return p. }         }     } } /* (n, e) is not generated by Algorithm 7.5 */ Return failure.

Hiding small private exponent

Another possible backdoor is hiding an RSA key pair (∊, δ) with small δ inside a key pair (e, d). Crépeau and Slakmon [70] realize this backdoor using a result from Boneh and Durfee [32], which describes a polynomial-time (in |n|) algorithm for computing δ from the public key (n, ∊), provided that δ is less than n^0.292. This attack is explained in Algorithm 7.7. Here, the modulus is a genuine random RSA modulus. The mischievous key ∊ is neatly hidden by the attacker’s encryption routine f_e. The resulting output key pair (e, d) looks reasonably random. However, this scheme has a drawback similar to Algorithm 7.3; that is, it cannot easily generate small values of e.

Algorithm 7.7. Backdoor attack on RSA: small private exponent

Input: . Output: An RSA modulus n = pq with |n| = k and a key pair (e, d). Steps: Generate random primes p, q of bit length ~ k/2, such that n := pq has |n| = k. do {    Generate random  with gcd(δ, φ(n)) = 1 and |δ| < 0.292|n|.    ∊ := δ–1 (mod φ(n)).    e := fe(∊).    /* Hide ∊ */ } while (gcd(e, φ(n)) ≠ 1). d := e–1 (mod φ(n)). Return (n, e, d).

Algorithm 7.8 retrieves d from a public key (n, e) generated by Algorithm 7.7.

Algorithm 7.8. Retrieving the secret exponent

Input: An RSA public key (n, e) generated by Algorithm 7.7. Output: The corresponding private key d. Steps: ∊ := fd(e).     /* Recover the hidden exponent */ Use Boneh and Durfee’s algorithm to recover δ ≡ ∊–1 (mod φ(n)). Use ∊ and δ to compute φ(n). Compute d ≡ e–1 (mod φ(n)).

The correctness of Algorithm 7.8 is evident. In order to see how the knowledge of ∊ and δ reveals φ(n), note that x := ∊δ – 1 is a multiple of φ(n); that is,

Equation 7.7

for some integer l. Since δ < n^0.292 and ∊ < n, we have x < n^1.292. But φ(n) ≈ n and so l cannot be much larger than n^0.292. Since |p| ≈ k/2 ≈ |q|, we have l(p+q–1) < n. Now, if we write

x = an + b = (a + 1)n – (n – b)

with a = x quot n and b = x rem n, comparison with Equation (7.7) reveals that l = a + 1. This gives φ(n) = x/l.

Although not needed explicitly here, the factorization of n can be easily obtained by solving the equations pq = n and p + q = n – φ(n) + 1. If ∊ and δ are not small, we may have l(p + q – 1) ≥ n, and φ(n) cannot be calculated so easily as above. A randomized polynomial-time algorithm can still factor n from the knowledge of ∊, δ and n. For the details, solve Exercise 7.9.

Hiding small public exponent

Crépeau and Slakmon propose another backdoor attack based on the following result due to Boneh et al. [33]. Let (∊, δ) be a key pair for an RSA modulus n = pq. Further, let and 2^t–1 ≤ ∊ < 2^t. There exists a polynomial-time algorithm that, given n, ∊, and t most significant and |n|/4 least significant bits of δ, recovers the full private exponent δ.

Algorithm 7.9. Backdoor attack on RSA: small public exponent

Input: and . Output: An RSA modulus n = pq with |n| = k and a key pair (e, d). Steps: Generate random primes p, q of bit length ~ k/2, such that n := pq has |n| = k. do {    Generate random  with gcd(∊, φ(n)) = 1 and |∊| = t.    δ := ∊–1 (mod φ(n)).    . } while (gcd(e, φ(n)) ≠ 1). d := e–1 (mod φ(n)). Return (n, e, d).

Algorithm 7.9 uses f_e to hide in e a small ∊, t most significant bits of δ and |n|/4 least significant bits of δ. A string of bit length 2t + k/4 is encrypted by f_e. Applying the decryption routine f_d on e recovers these hidden values, from which ∊ and δ and hence φ(n) can be obtained. Algorithm 7.10 does this task. This scheme also fails, in general, to produce small public exponents e.

Algorithm 7.10. Retrieving the secret exponent

Input: An RSA public key (n, e) generated by Algorithm 7.9 and the matching . Output: The corresponding private key d. Steps: Compute fd(e) and retrieve the following:    (a) the hidden public exponent ∊,    (b) the t most significant bits of the hidden private exponent δ and    (c) the |n|/4 least significant bits of δ. Apply the Boneh-Durfee-Frankel algorithm to recover δ completely. Use ∊ and δ to compute φ(n).       /* See Exercise 7.9 */ Compute d ≡ e–1 (mod φ(n)).

7.3.2. An Attack on ElGamal Signatures

We now describe a backdoor attack on the ElGamal signature Algorithm 5.36. This attack does not work when the user’s permanent key pair is generated. It manipulates the session-key generation in such a way that the user’s permanent private key is revealed to the attacker from two successive signatures.

Let p be a prime, g a generator of , and (d, g^d(mod p)) the permanent key pair of Alice. The attacker uses the same field and a key pair (D, g^D (mod p)) with g^D supplied to the signing device. Suppose that Alice signs two messages m₁ and m₂ to generate signatures (s₁, t₁) and (s₂, t₂) respectively, where

The attack proceeds by letting d₁ arbitrary, but by taking

d₂ ≡ (g^D)^d₁ (mod p).

Since , we have

that is,

The private key D of the attacker (or d₁) is required for computing d; so nobody other than the designer can retrieve Alice’s secret by observing the contaminated signatures (s₁, t₁) and (s₂, t₂).

7.3.3. An Attack on ElGamal Encryption

For ElGamal encryption (Algorithm 5.15) and for Diffie–Hellman key exchange (Algorithm 5.27) over , a party (Alice) generates random session key pairs of the form (d′, g^d′(mod p)) and communicates the public session key g^d′ to another party. The following backdoor manipulates the session-key generation in such a way that two public session keys reveal the second private session key (but not the permanent private key). We assume that the attacker learns the public session keys by eavesdropping. The attacker’s key-pair is (D, g^D(mod p)). The contaminated routine contains the public key g^D(mod p), but not the private key D.

Let (d₁, r₁) and (d₂, r₂) be two session keys used by Alice, where

r1	≡	gd1 (mod p),
r2	≡	gd2 (mod p).

The contaminated routine that generates the session keys uses a fixed odd integer u, a hash function H and a random bit to generate d₂ from d₁ as follows:

z	≡	gd1+ub(gD)d1 (mod p),
d2	≡	H(z) (mod p – 1).

The attacker knows r₁ and r₂ by eavesdropping. She computes d₂ by Algorithm 7.11, the correctness of which is established from that .

Algorithm 7.11. Backdoor attack on ElGamal encryption

.                                                                     /* corresponding to b = 0 */ if (r2 ≡ gH(z0) (mod p)) { Return H(z0). } z1 := z0gu (mod p).                                                                   /* corresponding to b = 1 */ if (r2 ≡ gH(z1) (mod p)) { Return H(z1). } Return failure.              /* The attackeres routine was not used for key generation. */

Algorithm 7.11 requires the attacker’s private key D (or d₁) and can be performed only by the attacker. Now, d₂ can be analogously used to generate the third session key d₃ and so on, that is, the attacker can steal all the private session keys (except the first).

The odd integer u is used for additional safety. In order to see what might happen without it (that is, with b = 0 always), assume that H can be inverted. This gives z and (mod p). If D is even, y is always a quadratic residue modulo p. If D is odd, y is a quadratic residue or non-residue modulo p depending on whether d₁ is even or odd. The randomly added odd bias u destroys this correlation of z with quadratic residues.

7.3.4. Countermeasures

Using trustworthy implementations (hardware or software) of cryptographic routines (in particular, key generation routines) eliminates or reduces the risk of backdoor attacks. Preferences should be given to software applications with source codes (rather than to the more capable ones without source codes). Random number generators should be given specific attention. Cascading products from different independent sources also minimizes the possibility of hidden backdoors.

If the desired grain of trust is missing from the available products, the only safe alternative is to write the codes oneself. Complete trust on cryptographic devices and packages and using them as black boxes without bothering about the internals is often called black-box cryptography. Users should learn to question black-box cryptography. The motto is: Be aware or bring peril.

Exercise Set 7.3

7.8

Argue that reverse engineering the PAP routine (Algorithm 7.5) can enable a user to distinguish in polynomial time between key pairs generated by PAP and those generated by honest procedures.

7.9

Let n = pq be an RSA modulus and (e, d) a key pair under this modulus. Write ed – 1 = 2st, where s = v2(ed – 1) (so that t is odd). Since ed – 1 is a multiple of φ(n) = (p – 1)(q – 1) with odd p, q, we have s ≥ 2. Show that for any the multiplicative order ordn(at) divides 2s. [H] Let be such that at has different orders modulo p and modulo q. Show that gcd(a2σt – 1, n) is a non-trivial divisor of n for some . Let g be a generator of . Take a := gk (mod p) for some and let ordp(at) = 2σ. Show that σ = v2(p – 1) if k is odd, and σ < v2(p – 1) if k is even. [H] An analogous result holds for the other prime q. Demonstrate that there are at least φ(n)/2 elements a in with the property that at has different orders modulo p and q. [H] Suggest a randomized poly-time algorithm for factoring n from the knowledge of n, e and d.