Subliminal Channels

17 Dec 2003

      -----BEGIN PGP SIGNED MESSAGE-----

A while ago I sent a post on subliminal channels - I had a chance to work
a larger example.

A subliminal channel is a communication channel that cannot be read by
those for whom it is not intended.  The problem is sometimes phrased as
a prisoner's dilemma: two prisoners are allowed to communicate with each
other by exchanging messages.  They are able to digitally sign the messages
to protect against spoofing.  However, the warden will not allow the
messages to be encrypted - only plaintext and the digital signature will
be passed.  All parties agree to these conditions and communication
begins.

Unknown to the warden, the prisoners are still able to coordinate their
plans by using a subliminal channel to communicate, in full view of the
warden!  Essentially, the prisoners use some piece of shared knowledge to
hide their real communication in the digital signature of an innocuous
message.  The warden sees the innocent message, checks that the signature
is valid, and passes it along.  The prisoner checks the signature to see
if the warden didn't alter the message, and then extracts the real message
from the digital signature.

This topic came up when previously on the list, people were discussing
the fact that encrypted communication over HAM radio is illegal - only
authentication codes may be transmitted.  I mentioned that actually, this
restraint can be sidestepped by embedding encrypted communication a la
subliminal channel style.  YES, I KNOW THIS IS ILLEGAL AND I'M NOT
SUGGESTING ANYBODY DO IT!  I just pointed it out.

What may be more important is that a subliminal channel may lurk in the
digital signature standard (DSS).  In turn, this is important because from
time to time proposals are made concerning national id cards, national
health cards, etc.  If some agency is going to authenticate or otherwise
digitally sign an identification card, they may also embed information
into the signature.  The DSS has been described as "very hospitable to
subliminal channels."  Imagine what records could be kept on you if various
information were embedded in the digital signature of documents you own.

First, a description and example of El Gamal authentication, and then of
the subliminal channel based on El Gamal.

El Gamal authentication:

The sender picks a prime p, primitive element g, and random integer r.
The public information is the triple (K,g,p), where 
K = g^r mod p

To authenticate a message M, the sender picks another random integer r'
such that gcd(r',p-1) = 1, and computes 
X = g^r' mod p

Then, the sender solves for Y in the equation 
M = r X + r' Y mod p-1

The triple (M,X,Y) is the message and the signature - this is what is 
transmitted to the receiver.  r and r' are kept secret.

The receiver computes
A = K^X X^Y mod p

and accepts the message as authentic if
A = g^M mod p

El Gamal Example:

p = 224737, r = 5135, g = 2
K = 2^5135 mod 224737 = 136800
The triple (136800, 2, 224737) is public.

To send the message M = 12345, the sender picks r' = 89321
gcd(89321,224736) = 1 so r' is ok.  Now compute X = 2^89321 mod 224737
                                                  = 87880

Solve for Y in: 12345 = 5135 87880 + 89321 Y mod 224736
          ==>   18433 = 89321 Y mod 224736
          ==>   Y = 207929

The triple (12345, 87880, 207929) is the message and the signature.

The receiver gets (12345, 87880, 207929) and knows (136800, 2, 224737).
A = 136800^87880 87880^207929 mod 224737 = 160740
g^M mod p = 2^12345 mod 224737 = 160740

These are equal and the message is accepted as authentic.

El Gamal Subliminal Channel:

Now the interesting part is the subliminal channel.  The sender and 
receiver must share the knowledge of random number r.

To send the subliminal message M, where gcd(M,p) = 1, using a cryptogram
C, the sender calculates 
X = g^M mod p

and solves for Y in
C = r X + M Y mod p-1

The triple (C,X,Y) is transmitted to the receiver.

The receiver computes 
A = (g^r)^X X^Y mod p 

and accepts the message as authentic if 
A = g^C mod p

To extract the subliminal message, the receiver calculates
M = Y^-1 (C - r X) mod p-1

El Gamal Subliminal Channel Example:

Suppose the sender and receiver share the knowledge r = 5135

The sender wants to send M = 11111 using the innocent message C = 12345.
The sender calculates X = 2^11111 mod 224737 = 20944
and solves for Y in : 12345 = 5135 20944 + 11111 Y mod 224736
               ==>    Y = 194447

The triple sent to the receiver is (12345, 20944, 194447).

The warden can check this if he wants, to very the signature:
A = 136800^20944 20944^194447 mod 224737 = 160740
g^C mod p = 2^12345 mod 224737 = 160740

so the warden verifies the signatures.  Convinced nothing fishy is
going on here, he passes on the message.

The receiver checks authenticity and is successful.  However, now the
subliminal message is extracted:
M = 194447^-1 (12345 - 5135 20944) mod 224736 = 11111

The subliminal message is successfully extraced, and the prisoners have
passed information right by the warden.

Subliminal Channels

Karl Lui Barrus