-----BEGIN PGP SIGNED MESSAGE----- Eric Hughes just told me some extremely interesting information concerning subliminal channels and the DSS. Apparently, the DSS is very hospitable towards subliminal channels. (I won't summarize further since Eric may have posted to the list). Again: a subliminal channel is a channel in which an external observer is unaware of communication. For example, two prisoners want to communicate. The warden agrees if the messages are plaintext. The prisoners agree if they can authenticate (digitally sign) the messages - - after all, the warden may try to spoof them. The warden agrees to this arrangement (for instance, after reading up on digital signatures in Denning's book, which doesn't cover subliminal channels!), allowing the prisoners to embed their true communication in the digital signature of their plaintext messages. Before showing an example El Gamal subliminal channel, I'll briefly describe El Gamal's authentication scheme (since most people are familiar with or have heard of the RSA method only). In El Gamal's scheme (from Seberry and Pieprzyk's "Cryptography: an Introduction to Computer Security"): 1) Alice chooses p a prime, g a primitive element of GF(p), r a random integer. Loosely, g (being primitive) can be used to generate the rest of the field GF(p) by exponentiation. 2) Alice calculates K = g^r mod p Alice publishes (K,g,p) as the public key 3) a message M is authenticated by first choosing a second random integer r' such that r' and p-1 are relatively prime Alice computes X = g^r' mod p Alice solves M = rX + r'Y mod p-1 for Y Alice sends (M,X,Y) to B and keeps (r,r') secret 4) Bob can verify the message M by calculating A = K^X X^Y mod p and only accepts the message as authentic if and only if A = g^M mod p The example in the book is (I'm not sitting at a NeXT at the moment, the only place it's convenient for me to use Mathematica, or I'd use some larger numbers): Alice chooses p = 11, g = 2, r = 8 Alice computes K = g^r mod p = 2^8 mod 11 = 3 Thus (K,g,p) = (3,2,11) Say the message is M = 5 Alice chooses r' = 9. GCD(r',p-1) = 1, so they are relatively prime Alice computes X = g^r' mod p = 2^9 mod 11 = 6 Alice solves M = rX + r'Y mod p-1 for Y 5 = 8*6 + 9*Y mod 10; yeilding Y = 3 Alice sends out the triple (M,X,Y) = (5,6,3) to Bob. Note: M can be read. Bob now has (M,X,Y) = (5,6,3) and the public key (K,g,p) = (3,2,11) Bob calculates A = K^X X^Y mod p = 3^6 6^3 mod 11 = 10 Bob calculates g^M mod p = 2^5 mod 11 = 10 So, since A = 10 and g^M mod p = 10, the message is valid. Again, when I have a chance I'll plug in much larger numbers so you don't think it all works out by coincidence. In the El Gamal subliminal channel, somehow the random integer r is known by both parties. So Alice and Bob agree on a random r before they ever find themselves in the position of using a subliminal channel. 1) Alice chooses p, g as before. She chooses the r that she and Bob share. She calculates K as before. 2) Alice calculates the subliminal message m, using a plaintext message M, by calculating X = g^m and solving the following equation for Y: M = rX + mY mod (p-1) 3) Alice send (M,X,Y) to Bob. 4) Bob receives (M,X,Y) and knows (p,g) which are public and the secret r he shares with Alice. 5) Bob calculates A = (g^r)^X X^Y mod p and accepts the message M as authentic if A = g^M mod p (as before in El Gamal authentication). 6) Now Bob extracts the subliminal message by computing m = Y^-1 (M - rX) mod (p-1) As before, (K,g,p) = (3,2,11) is public. r = 8 is the shared secret. Alice wants to send m = 9, using the plaintext message M = 5 Alice computes X = g^m mod p = 2^9 mod 11 = 6 Alice solves 5 = 8*6 9Y mod 10 for Y; Y = 3 Alice sends (M,X,Y) = (5,6,3) to Bob. Bob computes A = (2^8)^6 6^3 mod 11 = 10 Bob computes g^M mod p = 2^5 mod 11 = 10 These are equal, so Bob accepts the message. Now, he extracts the subliminal message: m = Y^-1 (M - rX) mod (p-1) = 3^-1 (5 - 8*6) mod 10 = 9. So, it is possible to communicate information with subliminal channels. A real life example where this could occur is with ham radio operators. Encrypted messages are illegal, but checksum message can be transmitted, so the checksum can be modified to include a subliminal message. I'm just pointing this out for theoretical interest - I know it's illegal! Now, back to subliminal messages and the DSS. Suppose the government decides to authenticate the information on your driver's license with DSS. All sorts of information can be included subliminally, such as an arrest record, number of speeding tickets, if the person in question is suspicious, etc... -----BEGIN PGP SIGNATURE----- Version: 2.3 iQCVAgUBLEyIroOA7OpLWtYzAQE95gQAmrCoIB0lWTbBUOcayev0HvKUoAyz2dT4 FSbqi65oytE+EA2RhY9BHOFeRuA8yF97Dm+tTunOUYlA3CTlGRvmfxdA98TuGD7X otmr0qVPJlAFsW7xqm8sJq09mozM+NMONwQJTOObaEr9UzPsgGeyGs4RVz3h29Qp nvxCopYQy6A= =4kzu -----END PGP SIGNATURE-----