Subliminal Channels in the Digital Signature Algorithm (DSA)

[tcmay@netcom.com (Timothy C. May)]

The recent discussion of possible subliminal channels (which some call
covert channels) in the DSA reminds me of a preprint of a paper I received
several months back with a rather mysterious note attached to it. There was
no return address on the envelope. Apparently a number of Cypherpunks and
folks active in the sci.crypt community also received it, as it came up on
sci.crypt and we talked about it at a physical Cypherpunks meeting.

The note read:

"This needs to be made very public. Simmons resigned from Sandia over
writing it."

Some caveats:

* this allegation that Gus Simmons left Sandia was denied by several folks
on sci.crypt who actually _know_ Simmons. I don't know him, so I haven't
checked directly.

* some say this paper is hardly earth-shaking, though the possibility of
subliminal channels should be taken seriously, especially in light of the
cross-licensing of DSA/DSS with Public Key Partners (RSA Data, etc.).

* I don't even know where this paper is being published--the preprint gave
no clues. The timing of my getting it, several months back, suggests this
year's Crypto Conference. The advance program ought to have it (I can't
find my copy).

I've OCRed the first page or so, including the Abstract. Too many OCR
errors and too many equations with Greek symbols for me to scan-in the
entire 20-page paper.

The implications for Clipper, Capstone, Skipjack, etc. I'll leave for now.


Here it is:



The Subliminal Channels in the U.S. Digital Signature Algorithm (DSA)

    Gustavus J. Simmons
Sandia Park. NM 87047. USA

Abstract

    Since the DSA is derivative from El Gamal's digital signature
scheme--which Simmons showed in 1985 permitted a subliminal channel--it
should come as no surprise that the DSA also permits a similar channel. The
subliminal channel in the El Gamal scheme, however, had several
shortcomings. In order for the subliminal receiver to be able to recover
the subliminal message, it was necessary for him to know the transmitter's
secret key.  This meant that the subliminal receiver had the capability to
utter undetectable forgeries of the transmitter's signature.  Also, only a
subset of the desired message set could be communicated subliminally (phi
(p-l) messages instead of p-1) and some of those that could be transmitted
were computationally infeasible for the subliminal receiver to recover.

    The subliminal channels in the DSA avoid all of these difficulties! In
fairness, it should be mentioned that not all are avoided at the same time.
The channel in the DSA analogous to the one Simmons demonstrated in the El
Gamal scheme can communicate messages conveying the full log-base-2  |X|
bits, where  X is the set of session keys; all of which are easily
recovered by the subliminal receiver.  However, this broadband channel
still requires the subliminal receiver to know the transmitter's secret
key. There are two other narrowband (<< 1og-base-2  |X|) subliminal
channels in the DSA that do not give the subliminal receiver any better
chance of forging the transmitter's signature than an outsider has. The
price one pays for this integrity for the transmitter's signature is a
reduced bandwidth for the subliminal channel and a difficult but feasible
(dependent on the bandwidth actually used) amount of computation needed to
use the channel. Two quite different such channels have been devised:  one
places the computational load almost entirely on the transmitter, the other
almost entirely on the subliminal receiver.  Since the total computation is
essentially the same in either case, the choice of a particular channel
would be based on which end is best equipped to do the necessary
computation.

    To make clear what a remarkable coincidence it is that the apparently
inherent shortcomings of subliminal channels using the El Gamal scheme can
all be overcome in the DSA, we will analyze each of the channels
implemented in both schemes. The inescapable conclusion, though, is that
the DSA provides-the most hospitable setting for subliminal communications
discovered to date.

Introduction

    In  1983  Simmons  introduced   the  notion  of  a  subliminal  channel
 existing  in an  encrypted  communication  channel  by  pointing  out  
that  if  for  each  plaintext there  existed  two  or  more  corresponding
 cipher  texts,  the  identity  of  the  cipher used   to  communicate  a 
plaintext  could  convey  information  additional  to   that revealed  by 
the  decryptlon  of   the  cipher  [5].   In  particular,  in  a 
public-key based  authentication  scheme  in  which  the  decryption  key  
must  be  public  information  in  order  for  public  receivers  to  be 
able  to  decrypt  cipher  texts  and  verify the   authenticity   of   the
  encrypted  plaintext,   this   raised   the   possibility   of there 
also  being  subliminal  receivers  who  could  recover  information 
hidden  from the public receivers: hence the name of a subliminal channel.
Clearly subliminal channel receivers must have private information not
known to public receivers--and as we will see, the nature of this private
information provides a natural classification for subliminal channels.



(rest of paper not OCRed...too many errors (blurred fonts), too many equations)