|Table of Contents
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.
Heres how Mallory, an unscrupulous implementer of DSA,can have the algorithm leak 10 bits of Alices private key every time she signs a document.
Its 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 Alices 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.
Heres the protocol [1470,1472,1473]:
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 Alices 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 Alices signatures by choosing k" with certain characteristics. When Simmons discovered this, he dubbed it the Cuckoos Channel. Details on how the Cuckoos Channel works, and a three-pass protocol for generating k that prevents it, are discussed in [1471,1473].
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 .
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, gx mod p.
To sign a message, Alice computes z =mx mod p.Thats all she has to do.
Verification is a little more complicated.
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 Bobs and Daves transcripts are identical. She cannot be convinced of the signatures validity unless she goes through the protocol herself.
Of course, if she were watching over Bobs 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 protocolAlice can convince Bob that her signature is validbut 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 .
|Table of Contents