|Previous||Table of Contents||Next|
Simmonss second subliminal channel , described in [1407,1473], is based on the ElGamal signature scheme (see Section 19.6).
Key generation is the same as the basic ElGamal signature scheme. First choose a prime, p, and two random numbers, g and r, such that both g and r are less than p. Then calculate
The public key is K, g, and p. The private key is r. Besides Alice, Bob also knows r; it is the key that is used to send and read the subliminal message in addition to being the key used to sign the innocuous message.
To send a subliminal message M using the innocuous message M', M and p must be all relatively prime to each other, and M and p -1 must be relatively prime. Alice calculates
and solves the following equation for Y (using the extended Euclidean algorithm):
As in the basic ElGamal scheme, the signature is the pair: X and Y.
Walter can verify the ElGamal signature. He confirms that
Bob can recover the subliminal message. First he confirms that
If it does, he accepts the message as genuine (not from Walter).
Then, to recover M, he computes
For example, let p =11 and g =2. The private key, r, is chosen to be 8. This means the public key, which Walter can use to verify the signature, is gr mod p =28 mod 11 =3.
To send the subliminal message M =9, using innocuous message M'= 5, Alice confirms that 9 and 11 are relatively prime and that 5 and 11 are relatively prime. She also confirms that 9 and 11 -1 =10 are relatively prime. They are, so she calculates
Then, she solves the following equation for Y:
Y = 3, so the signature is the pair, X and Y: 6 and 3.
Bob confirms that
It does (do the math yourself if you dont trust me), so he then recovers the subliminal message by calculating
A subliminal channel can be added to ESIGN  (see Section 20.6).
In ESIGN, the secret key is a pair of large prime numbers, p and q, and the public key is n =p2q . With a subliminal channel, the private key is three primes, p, q, and r, and the public key is n, such that
The variable, r, is the extra piece of information that Bob needs to read the subliminal message.
To sign a normal message, Alice first picks a random number, x, such that x is less than pqr and computes:
H(m) is the hash of the message; k is a security parameter. The value s is the signature.
To verify the signature, Bob computes sk mod n. He also computes a, which is the least integer larger than the number of bits of n divided by 3. If H(m) is less than or equal to sk mod n, and if sk mod n is less than H(m) +2a , then the signature is considered valid.
To send a subliminal message, M, using the innocuous message, M', Alice calculates s using M in place of H(m). This means that the message must be smaller than p2qr. She then chooses a random value, u, and calculates
Then, use this x' value as the random number x to sign M'. This second s value is sent as a signature.
Walter can verify that s (the second s) is a valid signature of M'.
Bob can also authenticate the message in the same way. But, since he also knows r, he can calculate
This implementation of a subliminal channel is far better than the previous two. In the Ong-Schnorr-Shamir and ElGamal implementations, Bob has Alices private key. Besides being able to read subliminal messages from Alice, Bob can impersonate Alice and sign normal documents. Alice can do nothing about this; she must trust Bob to set up this subliminal channel.
The ESIGN scheme doesnt suffer from this problem. Alices private key is the set of three primes: p, q, and r. Bobs secret key is just r. He knows n =p2qr, but to recover p and q he has to factor that number. If the primes are large enough, Bob has just as much trouble impersonating Alice as would Walter or anyone else.
There is also a subliminal channel in DSA (see Section 20.1) [1468,1469,1473]. In fact, there are several. The simplest subliminal channel involves the choice of k. It is supposed to be a 160-bit random number. However, if Alice chooses a particular k, then Bob, who also knows Alices private key, can recover it. Alice can send Bob a 160-bit subliminal message in each DSA signature; everyone else simply verifies Alices signature. Another complication: Since k should be random, Alice and Bob need to share a one-time pad and encrypt the subliminal message with the one-time pad to generate a k.
DSA has subliminal channels that do not require Bob to know Alices private key. These also involve choosing particular values of k, but cannot be used to send 160 bits of information. This scheme, presented in [1468,1469], allows Alice and Bob to exchange one bit of subliminal information per signed message.
|Previous||Table of Contents||Next|