Chapter 10

Subliminal Channels

Subliminal channels form the cornerstone of modern kleptography. They can be utilized in the payloads of cryptoviruses and cryptotrojans to implement robust backdoors in cryptographic algorithms. Subliminal channels were originally investigated to demonstrate a weakness in a nuclear arms control verification protocol. In this regard subliminal channels demonstrated a plausibility result: given a carefully selected cryptosystem, a sneaky Trojan horse program could be developed for that cryptosystem that leaks which missile silos contain nuclear missiles. The applications of subliminal channels grew to encompass devastating smart-card insider threats. The classic abuse of subliminal channels is in the Prisoner's Problem that was formulated by Gus Simmons. This problem is described in this chapter along with numerous known subliminal channels.

On the surface it would seem that whenever a subliminal channel exists in a cryptosystem, this is a bad thing. However, ironically enough, this is not the case. It has been shown that this communication channel can sometimes be used in a non-subversive and publicly advertisable way. The chapter concludes with a description of how a subliminal channel can be used to help solve the key escrow problem. In a nutshell it is often possible to utilize a subliminal channel to securely transmit a private key to the key escrow authorities in a key escrow system. In this regard, subliminal channels are entirely beneficial. This was an intriguing development since it took a subversive technology and turned it into a very useful technology.

10.1 Brief History of Subliminal Channels

Gus Simmons is the father of subliminal channels. His investigations into the subject began in the 1970s and it is instructional to explain¹ the origin of this fantastic cryptographic phenomenon [280]. In 1978 the Carter administration was seriously considering the adoption of a national security protocol that was designed to allow Russia to verify how many minuteman missiles the United States had fielded in the 1,000 U.S. silos without exposing which silos were actually armed. To constitute an acceptable solution to Russia, the compliance messages would have to be digitally signed in a way that would not be possible for the United States to forge. At any given time the United States was permitted to have 100 minuteman missiles residing in randomly chosen silos. Any more than this would be a violation of the SALT II treaty, a treaty devised to control the arms race [281].

The scheme that the Carter administration was endorsing was often referred to in the press as the missile shell game. This is because the 100 missiles would be shuttled randomly using trucks among the 1,000 silos on a continual basis. It was envisioned that these trucks would even haul fake payloads, such as water, to conceal whether or not a given payload actually contained a live missile. This was necessary since the trucks could be observed via spy satellites. However, simply hauling fake loads would, of course, not be enough. The trucks would all have to exhibit the same acceleration, lest they be distinguished using elementary kinematics.²

The proposed solution, one that would allow Russia to verify the number of minuteman missiles the United States had placed afield, utilized both sensors and cryptographic devices. The sensors were to be placed in the silos. The data acquired by the sensors would indicate the presence or absence of a missile in a given silo, thus constituting a single bit of information. This bit had to be protected so that it could not be forged or falsely attributed. Both countries agreed that the sensor technology was acceptable. Gravimetric sensors could be used to detect underground features versus voids, tilt sensors could also be used, and so on. In the proposed solution each country would provide its own cryptographic algorithm.

This problem was being solved at about the same time that the Diffie-Hellman key exchange was devised. Symmetric ciphers were the norm at that time. The basic idea was to have the cipher use a secret key to encrypt a message. Both the ciphertext and plaintext would be output by the device. Signature verification amounted to decrypting the ciphertext and comparing the result to the plaintext. Implicit in this approach was that it should not be possible to leak information in each ciphertext. The ability to do so could potentially compromise the identity of the silo and give the enemy the opportunity to launch a devastating first strike.

As the story goes, the NSA viewed the SALT II treaty as an opportunity to learn more about the state of cryptography in Russia. It was suggested that the Russians come up with their own cipher to place in the device. Gus Simmons saw the peril in this rationale. He called a meeting with the NSA, armed with the fact that the recently discovered Rabin cipher could be used to leak a single bit out of the device to the Russians. To sign a message in Rabin, the message is transformed into a square modulo the public key. A square root of the message is then computed using the two prime factors of the public key (see Appendix C.1.6). Four square roots exist, and so any of the four square roots can be used as the signature on the message. This was an incredibly important discovery. The device had the elbow room to leak information out from under the noses of the United States.³ Exactly two of these roots can safely be used to leak a single bit. It is these two roots that have a Jacobi symbol of 1.

This was conveyed to the NSA and the response was largely that of disinterest. They indicated that they would never approve of such a cipher and said that a one-bit channel is insignificant. Ten bits would allow the unambiguous identification of a given silo since 2¹⁰ = 1024 > 1000. Ultimately, it was the projected cost of the solution, not this channel, that caused it to be abandoned.

Gus Simmons was nonetheless determined to demonstrate the importance of his finding. He had found a major hole in the protocol used to verify the compliance of the SALT II treaty, a protocol developed by TRW and approved by the NSA. Yet, as will be shown in this chapter, this was merely the tip of the iceberg of Simmons' contributions to the subject.

10.2 The Difference Between a Subliminal and a Covert Channel

The difference between a covert channel and a subliminal channel is subtle at best. Typically, the term subliminal channel is used to refer to an information transmission channel that can be used to send information out of (or potentially into) a cryptosystem. A covert channel, on the other hand, is a somewhat older notion that is broader in scope.

A concrete example will go a long way to explain what a covert channel is. Suppose that Alice and Bob are connected to a computer that is running a multiuser operating system. In a secure operating system that can be used for sensitive (e.g., military) applications it should not be possible for a process that Alice is running to transmit information covertly to a process that Bob is running. But, suppose that a printer is connected to this machine. Each process can make an operating system call to print data. This call will return a result code indicating success or failure. The result code will also indicate if the printer is busy printing out a document. Alice's process can utilize a special communication protocol to speak with a process that Bob is running. For example, printing out two short documents with a brief pause in between could correspond to a binary “1” and printing out one document could be a binary “0.” Bob's process calls the operating system routine in a busy waiting fashion to receive bits from Alice's process.

The problem of confining a program during its execution so that it cannot transmit information to any program other than its caller is known as the Confinement Problem. This problem was introduced by Butler Lampson [167]. A simple example of this problem is a text editor that secretly saves some data from one user's text file and exposes the stolen data to another user. A program that cannot do this is said to be confined. If a process can covertly establish such a channel with a process other than its caller, then this channel constitutes a covert channel. Covert channels exist in all forms of software and hardware systems, and there have been efforts to develop multilevel security systems that avoid this problem.

To summarize, a subliminal channel can be categorized as a covert channel, but the converse is not always the case. Subliminal channels are particular to cryptosystems.

10.3 The Prisoner's Problem of Gustavus Simmons

The work in analyzing the SALT II treaty compliance led to subsequent investigations on the negative impact of subliminal channels in digital signature algorithms. The Prisoner's Problem⁴ clearly accentuates the hazards of digital signature algorithms [274]. In the Prisoner's Problem, Alice and Bob are two inmates who wish to coordinate a jailbreak. All of their communications must pass through a warden named Willy. If Willy sees any information that appears to be ciphertext and is not a valid digital signature, he does not forward it to the receiver. The problem that the prisoner faces is to devise a way to communicate with the other prisoner via digital signatures despite the fact that Willy will read everything and verify every digital signature. It is assumed that Willy is actively looking for misbehavior by the inmates and that he will refuse to forward invalid digital signatures. This prevents the prisoners from abusing their privileges by sending ciphertexts to each other. The problem is only regarded as being satisfactorily solved provided that the following two properties hold:

1. The subliminal channel algorithm can be made public without compromising Alice and Bob's ability to coordinate a jail break.
2. Willy can neither read information from the subliminal channel nor even detect that it is being used.

Property (1) eliminates simplistic solutions that are not secure. For example, suppose that before going to prison Alice and Bob agreed to use the following scheme to communicate. To send a subliminal message, the sender concocts an ASCII message such that the least significant bit in each sentence matches a bit in the subliminal message. This solution hides information from Willy by virtue of the fact Willy is not privy to it.⁵ Using this solution is perilous since Willy may record every transmission and later discover the steganographic channel. The attack is actually a very simple form of steganography. A comprehensive treatise on steganographic methods was given by Johnson, Duric, and Jajodia [141].

Simmons presented the first acceptable solution to this problem. The solution assumes that Alice and Bob both know Alice's signing private key x before they are sentenced. This solution is as follows.

1. The sender Alice generates an innocuous message to be signed.
2. Alice signs the innocuous message using x with the modified signing algorithm in such a way that the subliminal message is encoded within the signature that is output.
3. The signature and innocuous message are given to the warden Willy.
4. Willy verifies the signature, and after finding nothing amiss, forwards the information along to Bob.
5. Bob verifies the signature and if it is valid, Bob assumes that the signature is authentic.
6. Bob then extracts the subliminal message from the signature using x.

The primary difference between this solution and the aforementioned steganographic solution is that even if Willy knows the particulars of the subliminal channel, he still cannot detect the use of the channel nor read from it since he does not know x.

Definition 2 A subliminal channel is a channel that exists within a cryptographic protocol, authentication system, digital signature algorithm, and so on, that transmits additional messages to a (special) receiver that is hidden, such that the messages cannot be read by other receivers (or a warden).

10.4 Subliminal Channels New and Old

Simmons demonstrated subliminal channels in the ElGamal and Schnorr digital signature algorithms [275]. The following is the subliminal channel he found in ElGamal. Let m′ mod p − 1 be the subliminal message that Alice wants to send to Bob. It is required that m′ and p − 1 be relatively prime. To sign the innocuous message m, Alice calculates the signature value r = g^m′ mod p. The signature on m is the pair of values (r, s) where s is computed as in equation 10.1.

Bob recovers m′ by computing m′ = s⁻¹(H(m) − xr) mod p − 1. Note that x is required to recover m′. Clearly a sufficient portion of m′ must be randomly chosen, otherwise the warden could guess m′ and compute x. This would not only expose the use of the subliminal channel, but also its contents and Alice's private signing key.

10.4.1 The Legendre Channel of Gus Simmons

Simmons proposed a couple of narrowband channels. In this subsection a narrowband channel of Simmons will be described that is based on quadratic residuosity. It solves the Prisoner's Problem and does not require Alice to divulge her private signing key to Bob. This channel is suitable for numerous discrete-log based signature algorithms and it was described by attacking DSA in particular [277, 278].

In this attack, Alice and Bob both agree on 14 distinct large prime numbers p₁, p₂, ..., p₁₄ prior to being arrested. Each of these primes is greater than q. This channel has a bandwidth of 14 bits⁶ per DSA signature. Let m = m₁m₂ · · · m₁₄ be the 14 bits that Alice wants to send to Bob subliminally. To send the message m, Alice repeatedly chooses k in the Digital Signature Algorithm (see Appendix C.2.7) and then calculates the signature value r until the following is satisfied:

Bob can recover m in a straightforward fashion. Bob applies Euler's criterion to r mod p_i and knows that m_i = 1 if and only if L(r/p_i) = 1.

The 14 primes should each be greater than q for the following reason. For simplicity consider the one bit channel that uses p₁ to leak one subliminal bit. If p₁ is large (e.g., 128 bits in length) but is still less than q, then the following situation can occur. It is possible that k will be chosen such that r = (g^k mod p) mod q is evenly divisible by p₁. In this case, r mod p₁ = 0. It follows that r is neither a quadratic residue nor a quadratic non-residue modulo p₁. Hence, certain values for r would never be output by a digital signature device that utilizes this channel. By making p₁ > q this situation cannot occur.

It is important to consider the expected running time of the Legendre channel. Since finding a suitable k for a particular subliminal message is a randomized process, the running time can be estimated by considering the probability of finding a suitable k for a given 14-bit message. This is a tricky point to analyze formally. One would expect that a randomly chosen k in DSA will lead to an r = (g^k mod p) mod q that is a quadratic residue modulo p_i with probability 1/2. This results from the fact that half of the elements in p_i are quadratic residues. Under this assumption, a value k will be able to leak a particular message with probability about 2⁻¹⁴. Another potential issue is the probability distribution over r that is induced by the probability distribution over the message space. For communications to be subliminal, the attacked values for r must be indistinguishable from the values for r that result when k is chosen uniformly at random. For the one bit version of this channel that uses only p₁, the values for r will be indistinguishable from the ones that result from choosing k uniformly at random. This follows from a theorem due to Seysen if the r's are not squares over the Reals [133].

It has been assumed that DSA was designed to be a signature algorithm that is hard to abuse in the sense that it could not be used directly as a public-key system, a key exchange system, or as any system providing for confidential information exchange (see [284]). Therefore, it was surprising that Simmons found a channel in it with a bandwidth of 14 bits. If this subliminal channel were employed in a device used to verify the SALT II treaty, it would be capable of leaking the exact identity of each silo. This observation, therefore, destroys the logic behind letting the Russians choose their own cryptographic algorithm for the device for the purpose of learning more about Russian cryptography.

Simmons showed that if Alice's relationship with her accomplice has not gone south then she can use this channel to give her private key to Bob. After doing so she can utilize a channel much like the one described in Section 10.4 to establish a higher bandwidth channel with Bob. In this method the 160-bit DSA private key x is divided into 16 blocks with each block consisting of 10 bits. Four bits are used to identify each of the 16 different blocks and 10 bits are used to display the contents of a given block. Since the aforementioned channel has a bandwidth of 14 bits, it can be used to leak a block and the index for the block. This can be accomplished by letting m₁, m₂, ..., m₁₀ be the contents of the block and letting m₁₁, m₁₂, m₁₃, m₁₄ be the index. So, at a bare minimum, 16 digital signatures are needed to leak an entire DSA private key.

Some algorithm is needed to choose which block to leak in a given DSA signature. An obvious approach is to choose a block uniformly at random. This approach is ideal when the DSA signing algorithm is implemented in a smart card device that has limited or otherwise restricted non-volatile memory. (This would prevent the device from cycling through the 16 blocks in order.) Given this randomized block selection approach, a natural question to ask is how many signatures on average will be required to convey Alice's private key in its entirety. As it turns out, the number of such signatures is dictated by the first moment of the Coupon Collector's Problem [102].

The Coupon Collector's Problem is as follows. Each time a customer buys groceries, the customer is given a coupon that is selected uniformly at random from all N possible types of coupons. If a customer wants to obtain at least one of each possible type of coupon, how many times must the customer go grocery shopping on average? It turns out that the expected number of times is N log N. So, in the case of leaking the DSA private key x, Alice could expect to have to give Bob 16 log 16 = 64 digital signatures. The applicability of the Coupon Collector's Problem to subliminal channels was noted in a kleptographic attack on black-box symmetric ciphers [340].

The ability to leak private keys as such has extremely important implications for smart card security. It brings into question the wisdom behind implementing cryptography in hardware. If DSA were implemented in a tamper-resistant device and this attack were carried out, then the manufacturer of the device could obtain the DSA private keys of anyone who uses the device. The attack is not robust against reverse engineering, since knowledge of the 14 primes implies knowledge of the private keys. But the attack nonetheless demonstrates the feasibility of creating effective subliminal channels out of thin air.

An approach to foiling this is to prevent Alice from having the luxury of choosing k explicitly. By adding a trusted entity to the signature process, a protocol can be devised that prevents Alice from choosing k explicitly. In the scenario of the Prisoner's Problem, the signer and the warden jointly generate the signature by having each person contribute to the randomness in the signature [276, 279]. A complication in this approach is due to the fact that the prisoner who constructs the signature can simply halt, thereby not computing a signature and converying a single bit [90].

10.4.2 The Oracle Channel

In Subsection 10.4.1, the probability that a random k allows the 14-bit subliminal message to be leaked was argued to be 2⁻¹⁴. This assumption is clearly number theoretic in nature. One of the reasons that this analysis is complicated is as follows. Consider the 1-bit channel that uses p₁. For it to be the case that with probability 1/2 a randomly chosen k leads to an r that is a quadratic residue modulo p₁, it is required that half of the values in be quadratic residues modulo p₁. Now consider the case in which the channel is extended to 14 primes. In this case, the event that r is a quadratic residue modulo p₁ and the event that the same r is a quadratic residue modulo p₂ are not independent.

A further issue to consider is that of computational efficiency. The Legendre symbol of r must be computed modulo each p_i to determine if r leaks the desired subliminal message. Using Euler's Criterion, numerous modular exponentiations must be computed for each signature (r, s) that contains a subliminal message.

Aside from these very minor technicalities, it is natural to ask why the Legendre channel works. This question is perhaps best answered by analyzing it a bit more closely. Let LegendreChannel denote the function that is used to decide if r subliminally leaks m₁, m₂, ..., m₁₄ using the secret primes p₁, p₂, ..., p₁₄ > q. Hence, this function is a boolean predicate that may be computed by running Euler's Criterion 14 times and checking the results.

When LegendreChannel outputs 1 then r leaks the 14-bit subliminal message. The inputs are a publicly displayed value r, a subliminal message, and a secret key in the form of 14 distinct primes. Clearly the space for r and the key space should be large to make the channel secure. This brute-force channel works well for short messages due to the elbowroom in choosing r.

Horster, Michels, and Petersen proposed a narrowband channel that uses a One-time pad [133]. The 14-bit version of this channel will now be described. In this channel, Alice and Bob share a randomly chosen 14-bit string b₁, b₂, ..., b₁₄. The 14-bit subliminal message is XORed with this bit string and the resulting 14-bit Vernam ciphertext is displayed in the 14 least significant bits of r. Hence, k is repeatedly chosen until the 14 least significant bits of r happen to match this Vernam ciphertext. The predicate for this channel, which is named after Horst et al, is given below.

When HMP returns 1, the 14 least significant bits of r is the Vernam ciphertext of the 14-bit subliminal message. The subliminal message is recovered by decrypting the Vernam ciphertext using the One-time pad b₁, b₂, ..., b₁₄. Strictly speaking, this channel is not secure if it is used more than once.

A new channel will now be presented that extends the Simmons and Horster et al narrowband channels. It is based on the observation that a large space for r is required as well as a large key space. The channel is as follows. A random oracle R is chosen randomly and is used in the attack. As in Simmons' original attack, the parameter k is repeatedly chosen until an r is found that leaks the subliminal message. Let S be a randomly chosen secret seed. For concreteness let S be a 160-bit quantity. The value S is analogous to the 14 primes in the Simmons attack. The predicate for the Oracle Channel is as follows.

In the attack, the device repeatedly chooses k, computes r, and then computes the above predicate. The attack ceases when the predicate returns 1. The final values for k and r are the ones used in computing the digital signature that is output. The predicate is instantiated by computing R(S||r) and taking the first 14 output bits of the oracle. If these 14 bits match m₁, m₂, ..., m₁₄ exactly, then the predicate returns 1. Upon obtaining r, the attacker need only take the first 14 output bits of R(S||r) to recover m₁, m₂, ..., m₁₄.

It is instructive to consider the security of this channel. Suppose that the channel is being used in a black-box environment and that the user suspects that the device is using this channel to leak secrets. From the perspective of the device designer, the user is a distinguishing adversary that wants to be able to distinguish honest devices from those that use the subliminal channel. A worst-case scenario is one in which the device always leaks the same 14-bit message, and one in which the adversary supplies the key pair to the device and analyzes the resulting DSA signatures (r, s). Note that given x and (y, g, p) it is straightforward to recover k from (r, s). So, the distinguishing adversary has access to every value for k that the device uses in the signatures that it outputs.

The security parameter in DSA is 160, the number of bits in q. To try to distinguish, the poly-time adversary can obtain a set of signatures that has a cardinality that is polynomial in k. Given the limited number of outputs that are created, the likelihood that the device will generate a given value for k more than once is very small. Hence, the oracle inputs will likely be distinct. This means that the oracle outputs will likely be chosen in an independent fashion. Since there are an exponential in 160 number of values for k that can be used to leak a given 14-bit message, it is not hard to see that the distinguishing adversary cannot distinguish. This approach is applicable to the ElGamal Legendre channel as well as the DSA Legendre channel.

10.4.3 Subliminal Card Marking

Another early result on subliminal leakage of information was a subliminal attack on a cryptographic poker game protocol. Rivest, Shamir, and Adleman suggested the scheme. It utilizes a box-locking primitive based on the RSA algorithm. In the scheme Alice and Bob know the factorization of a large number N. Alice chooses an exponent K randomly mod (N) such that K is relatively prime to (N). She uses K as the RSA exponent to lock cards from a virtual deck of cards in a box (by exponentiation mod N with the exponent K). Let E_K(M) denote the box-locking primitive applied to card M. She can unlock a box using the inverse of K mod (N). As long as she does not give K to Bob, the contents of the box is secured. Note that this primitive constitutes a commutative symmetric cipher. Bob can lock the box received from Alice, and give the result to Alice, which Alice can unlock. However, in this case Alice cannot read the contents of the box without Bob performing the unlocking procedure to reverse his locking computation. This commutative property is necessary to play this version of mental poker (for example, over the phone).

However, in 1980 Richard Lipton observed that if M is a perfect square modulo N, then so is E_K(M). The encryption primitive therefore preserves quadratic residues. In a paper by DeMillo and Merrit it was shown how this primitive can be used to mark cards M [83]. For example, a player who initially encrypts M has an advantage in identifying/ruling out encrypted cards by determining quadratic residuosity modulo N of locked cards in which the player does not know the contents. Though this attack doesn't uniquely identify marked cards, it does give an unfair advantage to those who employ it, and may help a player cheat and win in the long run. It is clear that this attack, in some sense, constitutes a subliminal channel with a bandwidth between 0 bits and 1 bit (knowledge of the factors of N is needed to use this channel).

10.4.4 The Newton Channel

Work on finding new subliminal channels has continued as demonstrated by the discovery of the Newton channel [7]. The following is a description of this channel. Let p = qm + 1 be prime, and let q be prime. Furthermore, assume that m is a smooth integer and that g generates . For security it is assumed that computing discrete logs in the group generated by g^m is hard. Let c be the message that is to be subliminally leaked. To display c in an exponentiation mod p using base g, a value k′ mod (p − 1)/m is chosen randomly, and then k is solved for in k = c+k′m mod p − 1. Hence,

The user then publishes r = g^k mod p in the usual way. For example, this could be the value r in an ElGamal digital signature. The value c can be computed by anyone by solving for z in the following equation.

The value z can be found since the order of the subgroup of generated by g^q is a smooth integer. Let B be the largest prime in m (i.e., its smoothness). Using the Pohlig-Hellman algorithm [224] and Pollard's Rho algorithm [227] this requires time O(B^1/2). It then follows that,

Observe that this is in fact a broadcast channel since everyone is capable of computing c. The Newton channel can be modified to address this issue. This is done by replacing q with two different primes q₁ and q₂, having the sender and receiver a priori secretly share the signing private key mod q₂, and having the sender keep the signing key mod q₁ private [7]. This, however, requires a more specialized form for the factorization of p − 1 and may result in reducing the security of the underlying system.

So what can be done to minimize the threat of malware that exploits the Newton channel? Fortunately, the elimination of this particular channel is not difficult. By basing cryptosystems on a prime order subgroup of , this particular channel can be eliminated. DSA is a perfect example of a cryptosystem that is immune to this threat.

10.4.5 Subliminal Channel in Composites

Yvo Desmedt noted that it is possible to choose half of the bits of the product of two primes explicitly when one is free to choose any two large prime numbers [89]. In Crypto '96 it was shown that this channel can be used by malicious software to compromise RSA key geneartion [333]. Also, a number of recent papers address the generation of RSA moduli with a predetermined portion [145, 172].

One approach to displaying data in the bit representation of the modulus n is as follows. Suppose that n is required to be a W-bit composite that is the product of two W/2-bit primes p and q. Let M be a W/2 bit integer. Hence, M is W/2 bits long and the most significant bit is 1. The goal is to display M in the bit representation of n that is being randomly generated.

DisplayM(M):

input: a W/2-bit subliminal message M

output: two W/2-bit primes p and q

1. set W = 2|M|

2. generate a random W/2-bit string RND

3. set n₁ = M||RND

4. generate a random W/2-bit prime p

5. solve for quotient q and remainder r in n₁ = pq + r

6. if q is not a W/2-bit integer or if q < 2^W/2−1 + 1 then goto step 2

7. if q is composite then goto step 2

8. output (p, q) and halt

The quotient q and remainder r are computed by performing division. In many cases M will appear in unaltered form in the W/2 upper order bits of n = pq = n₁ − r. However, sometimes the subtraction of r will cause a borrow bit to be taken from M in the upper order bits. In this case M − 1 is displayed in the upper order bits. The subliminal message M can easily be recovered in either case. Ideally M should be chosen in a pseudorandom fashion, since fixing it may give rise to a weak composite that might be easily factorable. There are variations on this approach to displaying subliminal information in composites n = pq.

Kilian and Leighton showed how to exploit this channel to subvert a factoring based key escrow system [155]. This applies, for instance, to a PKI that is based on RSA. In such a key escrow system the users are forced to escrow their RSA private keys in order to be registered into the PKI. However, the subliminal channel in composites allows rogue users to subliminally display composites n′ that have unescrowed private keys within composites that have escrowed private keys. More specifically, the public modulus n′ of a rogue user can be displayed within the upper half of the bits in the bit representation of his or her own legitimate public modulus n (see Figure 10.1). The security parameter of n′ is half of the value of the security parameter of n. When such rogue users collude, they can establish an unescrowed PKI that benefits from the certification performed in the legitimate infrastructure, since CA signatures on the legitimate composites are also signatures on the rogue composites.

This form of abuse has been dubbed shadow public key abuse. A shadow public key is a public key that is displayed within the bits of a legitimate public key. Note, however, that if an RSA shadow public key is displayed within a legitimate composite then its security parameter will be half that of the security parameter of the legitimate composite.

Figure 10.1 Shadow public key attack on composites

A coalition of rogue users can always go outside of the system to defeat a key escrow infrastructure. However, one can envision a scenario in which a totalitarian government persecutes all persons that establish rogue certification authorities that certify unescrowed keys. In such a situation the shadow public key attack subverts the totalitarian PKI and uses it to securely distribute shadow public keys.

10.5 The Impact of Subliminal Channels on Key Escrow

The applications of subliminal channels have expanded significantly over the years. Using subliminal channels it was shown how to implement an RSA based key escrow system using smart card devices in a way that is transparent⁷ to the end user [333]. The information needed by the key recovery agent to recover the private key of a user is encoded within the upper order bits of the public key itself and cannot be obfuscated by the user without ruining the public key. In other words, the user cannot publish the public key without publishing the means for the key recovery agent to recover the user's RSA private key. By way of a subliminal channel, the two pieces of information are inseparable. The public key is digitally signed by a device-specific signing private key contained within the device. So, the device outputs three values to the user: a public key, the corresponding private key, and a signature on the public key. The user is registered into the PKI if and only if a public key is given to the CA along with a valid signature on the public key. The signature on the public key proves that the public key was generated by the hardware device. The upper order bits of the public key is an asymmetric ciphertext that when decrypted by the key escrow authorities reveals a prime divisor of the RSA public modulus of the user.

This hardware based key escrow solution seemed so close to being the solution to software key escrow, yet no cigar. The problem is that it requires hardware. The private signing key in the device has to remain private otherwise users can forge unescrowed key pairs. The key element that was missing was a proof that the private key is escrowed.

The software key escrow problem had received a lot of attention [155, 192, 193, 246] and was the subject of a fair amount of controversy. The fair cryptosystem approach of Micali could be implemented completely in software, but requires that each user secretly shares his or her private key in a publicly verifiable fashion among a set of key escrow authorities. So, it is required that the user perform more protocol interaction than in the case of an unescrowed public key infrastructure. It seemed that if the hardware based key escrow system from Crypto '96 could be modified so that the device creates a single non-interactive zero-knowledge proof⁸ that the private key is properly escrowed, then a more efficient protocol for software key escrow could be made.

This, in fact, turned out to be the case. It was shown that by having the user construct such a proof, the problem of software key escrow is solved [328, 337]. The key escrow solution utilizes a technique that is often referred to as verifiable encryption [108, 291]. The public keys of the key recovery authorities are used in constructing the non-interactive proof that in itself constitutes a ciphertext that encrypts the private key of the user. The non-interactive proof shows in zero-knowledge that the plaintext is in fact the private key of the user, and is hence recoverable by the key escrow authorities. This proof has been referred to as a certificate of recoverability.

The basic idea is to make entry into the public key infrastructure contingent upon providing a public key and corresponding proof of escrow to the certification authority (CA). In other words, each user is forced to escrow his or her own private key, otherwise the user will not be issued a digital certificate from the CA. The CA signs the public key if and only if the public key and proof are valid. The key escrow authorities can recover the user's private key from the public key and proof alone. In this respect, the key escrow solution does not require tamper-resistance and maintains transparency with respect to the end user. It is transparent since the certificate of recoverabilty can be sent to the CA along with the public key. The user can obtain the public key of the escrow authorities from the CA, for instance. As a result, the user never has to interact directly with the key escrow authorities.

This approach differs from the fair cryptosystem approach in a critical way: in fair cryptosystems, the user splits his or her private key into shares and gives them to the escrow authorities in a verifiable fashion, whereas in a solution based on certificates of recoverability the escrow authorities generate shares of a private key, compute the corresponding public key, and have the users use the public key to construct certificates of recoverability.⁹

Numerous other verifiable encryption algorithms have been shown that mention certificates of recoverability as a particular application [11, 49, 217, 232, 264, 273]. To date, the notion of certificates of recoverability have caught on in the scientific community but has yet to make its way into the industry. In retrospect, subliminal channels were an essential step in the discovery of a protocol-efficient solution to the software key escrow problem.

Another approach to efficient key escrow has recently been proposed by Franklin and Boneh [36]. The solution is based on the notion of an identity-based cryptosystem [269]. In the Franklin-Boneh system, the public key of a user can be computed by anyone given publicly available information about the user such as name, social security number, date of birth, and so on. A set of trusted authorities computes the private key of the user and sends the private key to the user. The private key is escrowed until these authorities decide to take it out of escrow.

This system is remarkable since it is essentially certificate-free. However, some form of key revocation mechanism is needed if the private key is ever compromised. The solution differs from systems that utilize certificates of recovery since the recovery authorities must actively compute and transmit the private key for each new user. In a scheme based on certificates of recoverability, the key recovery authorities remain off-line until an actual recovery is needed. The Franklin-Boneh scheme is secure against chosen ciphertext attacks in the random oracle model assuming an elliptic curve variant of the computational Diffie-Hellman problem. The system is based on the Weil pairing [144].