Sending multiple bits via this method involves making r either a quadratic residue or a quadratic nonresidue modulo a variety of parameters. See [1468,1469] for details.

This scheme can be easily extended to send multiple subliminal bits per signature. If Alice and Bob agree on two random primes, P and Q, Alice can send two bits by choosing a random k such that r is either a quadratic residue mod P or a quadratic nonresidue mod P, and either a quadratic residue mod Q or a quadratic nonresidue mod Q. A random value of k has a 25 percent chance of producing an r of the correct form.

Here’s how Mallory, an unscrupulous implementer of DSA,can have the algorithm leak 10 bits of Alice’s private key every time she signs a document.

(1)  Mallory puts his implementation of DSA in a tamperproof VLSI chip, so that no one can examine its inner workings. He creates a 14-bit subliminal channel in his implementation of DSA. That is, he chooses 14 random primes, and has the chip choose a value of k such that r is either a quadratic residue or a quadratic nonresidue modulo each of those 14 primes, depending on the subliminal message.

(2)  Mallory distributes the chips to Alice, Bob, and everyone else who wants them.

(3)  Alice signs a message normally, using her 160-bit private key, x.

(4)  The chip randomly chooses a 10-bit block of x: the first 10 bits, the second 10 bits, and so on. Since there are 16 possible 10-bit blocks, a 4-bit number can identify which block it is. This 4-bit identifier, plus the 10 bits of the key, is the 14-bit subliminal message.

(5)  The chip tries random values of k until it finds one that has the correct quadratic residue properties to send the subliminal message. The odds of a random k being of the correct form are 1 in 16,384. Assuming the chip can test 10,000 values of k per second, it will find one in less than two seconds. This computation does not involve the message and can be performed off-line, before Alice wants to sign a message.

(6)  The chip signs the message normally, using the value of k chosen in step (5).

(7)  Alice sends the digital signature to Bob, or publishes it on the network, or whatever.

(8)  Mallory recovers r and, because he knows the 14 primes, decrypts the subliminal message.

It’s scary that even if Alice knows what is happening, she cannot prove it. As long as those 14 secret primes stay secret, Mallory is safe.

Foiling the DSA Subliminal Channel

The subliminal channel relies on the fact that Alice can choose k to transmit subliminal information. To foil the subliminal channel, Alice cannot be allowed to choose k. However, neither can anyone else; if someone else were allowed to choose k, it would allow that person to forge Alice’s signature. The only solution is for Alice to jointly generate k with another party, call him Bob, in such a way that Alice cannot control a single bit of k and Bob cannot know a single bit of k. At the end of the protocol, Bob should be able to verify that Alice used the k that they jointly generated.

Here’s the protocol [1470,1472,1473]:

(1)  Alice chooses k' and sends Bob

u = g^k' mod p

(2)  Bob chooses k" and sends it to Alice.

(3)  Alice calculates k = k'^k" mod (p - 1). She uses k to sign her message, M, with the DSA and sends Bob the signature: r and s.

(4)  Bob verifies that

((u^k" mod p) mod q) = r

If it does, he knows that k was used to sign M.

After step (4), Bob knows that no subliminal information can be embedded in r. If he is a trusted party, he can certify that Alice’s signature is subliminal-free. Others will have to trust his certification; Bob cannot prove this fact to a third party with a transcript of the protocol.

A surprising result is that if Bob wants to, he can use this protocol to create his own subliminal channel. Bob can embed a subliminal message in one of Alice’s signatures by choosing k" with certain characteristics. When Simmons discovered this, he dubbed it the “Cuckoo’s Channel.” Details on how the Cuckoo’s Channel works, and a three-pass protocol for generating k that prevents it, are discussed in [1471,1473].

Other Schemes

Any signature scheme can be converted into a subliminal channel [1458,1460,1406]. A protocol for embedding a subliminal channel in the Fiat-Shamir and Feige-Fiat-Shamir protocols, as well as possible abuses of the subliminal channel, can be found in [485].

23.4 Undeniable Digital Signatures

This undeniable signature algorithm (see Section 4.3) is by David Chaum [343,327]. First, a large prime, p, and a primitive element, g, are made public, and used by a group of signers. Alice has a private key, x, and a public key, g^x mod p.

To sign a message, Alice computes z =m^x mod p.That’s all she has to do.

Verification is a little more complicated.

(1)  Bob chooses two random numbers, a and b, both less than p, and sends Alice:

c = z^a(g^x)^b mod p

(2)  Alice computes t=x^–1 mod (p - 1), and sends Bob:

d = c^t mod p

(3)  Bob confirms that

d ≡ m^ag^b (mod p)

If it is, he accepts the signature as genuine.

Imagine that Alice and Bob went through this protocol, and Bob is now convinced that Alice signed the message. Bob wants to convince Carol, so he shows her a transcript of the protocol. Dave, however, wants to convince Carol that some other person signed the document. He creates a fake transcript of the protocol. First he generates the message in step (1). Then in step (3) he generates d and the fake transmission from this other person in step (2). Finally, he creates the message in step (2). To Carol, both Bob’s and Dave’s transcripts are identical. She cannot be convinced of the signature’s validity unless she goes through the protocol herself.

Of course, if she were watching over Bob’s shoulder as he completed the protocol, she would be convinced. Carol has to see the steps done in order, just as Bob does.

There may be a problem with this signature scheme, but I know of no details. Please pay attention to the literature before you use it.

Another protocol not only has a confirmation protocol—Alice can convince Bob that her signature is valid—but it also has a disavowal protocol; Alice can use a zero-knowledge interactive protocol to convince him that the signature is not valid, if it is not [329].