STEG: subliminal messages

[Karl Barrus <elee9sf@Menudo.UH.EDU>]

[I'm forwarding mail from Eric which was meant for the list as well]

From: Eric Hughes <hughes@soda.berkeley.edu>
To: elee9sf@Menudo.UH.EDU

>An interesting related topic is subliminal channels and messages.  A
>subliminal channel is one in which communication takes place without
>an external observer realizing it.

[summary deleted]

Gus Simmons has recently written a paper on subliminal channels in the
DSA (the one PKP is about to license).  The paper as of yet is not
officially published, but likely will be at Crypto '93 next month.
I've seen a copy of the paper, but don't have a copy.  

I do, however, remember this one line. "The DSA provides the most
hospitable environment for subliminal channels in any system yet
seen." (Almost verbatim, but not quite.)  

Assume this is true.  (I believe Simmons, myself.)  What might this
mean?  Suppose some agency of the government makes digital signatures
on some certificate for individuals.  To take a concrete example, take
driver's licenses.  The subliminal channel in the signature might be
used to encode, say, the following:

  1. number of drunk driving convictions
  2. number of drunk driving arrests
  3. insurance rating
  4. whether this person is suspected of habitually
    a. merchandising narcotics
    b. carrying large amounts of cash
    c. looking at child pornography
    d. wanting to kill police officers
    e. carrying concealed messages

Since the signature itself contains this information, and since the
channel is subliminal, the only way to know whether the channel
carries data is to see the software.

For this reason the DSA should not be used by government agencies to
make certificates for individuals.  It should be scrapped for this
purpose and some other algorithm designed which has a provable upper
bound on the subliminal channel of less than one bit.

Eric