This posting discusses an "undocumented feature" of the Digital
Signature Algorithm, a fairly recent public key system sometimes known
as the Digital Signature Standard (DSS).

First, a little background.  Today I received in the mail an anonymous
letter with an accompanying photocopy of a 20-page paper by Gustavus
J.  Simmons.  The unsigned letter read, in its entirety:  "This needs
to be made very public.  Simmons resigned from Sandia over writing
it."  (I don't think I've received such a mysterious note since that
Valentine in third grade!)

The paper is entitled "The Subliminal Channels in the U. S. Digital
Signature Algorithm (DSA)".  Subsequent investigation turned up word
that the paper has already been published in Italy.  From the photocopy
I cannot tell in what journal.

I do not know the copyright status of the paper, so I will not
reproduce it here.  What follows are selected quotes and paraphrasing
from the introduction and abstract:

"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 decryption of the
cipher.  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 receivers must have private information
not known to public receivers--and as we shall see, the nature of this
private information provides a natural classification for subliminal
channels."

Simmons starts by describing a hypothetical simple example in which
each plaintext can generate two distinct ciphertexts, which can be
clearly identified as "odd" or "even".  In this case, the choice of an
"odd" vs. "even" ciphertext, which both decrypt to the same plaintext,
would provide a subliminal way of communicating a separate, additional
one-bit message.

"One of the first reactions to the announcement of the possibility of
establishing subliminal channels was that no one in their right mind
would accept (or use) a crypto channel with the properties needed for a
subliminal channel to be possible.  As Simmons subsequently showed,
though, virtually all digital signature schemes are of this form."

[...] "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-1) messages instead of p-1) and some
of those that could be transmitted were computationally infeasible for
the subliminal receiver to recover."

The DSA has an El Gamal-like channel which, however, allows the
conveying of fairly lengthy arbitrary messages.  The size of these
subliminal messages can be log2(|X|) bits, where X is the set of
session keys, all of which are easily recovered by the subliminal
receiver.

Furthermore, the DSA has "two other narrowband subliminal channels ...
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."

[...] "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 proves the most hospitable setting for
subliminal communications discovered to date."

[19 pages omitted.]

The author provides the following references:

1.  El Gamal, T., "A Public Key Cryptosystem and a Signature Scheme
Based on Discrete Logarithms,", IEEE Trans. on Info. Theory, Vol.
IT-31, No. 4, July 1985, pp. 469-72.

2.  NIST, "A Proposed Federal Information Processing Standard for
Digital Signal Standard (DSS)," Fed. Register, Vol. 56, No. 169, Aug.,
1991, pp. 42980-2.

3.  NIST, "Specifications for a Digital Signature Standard (DSS),"
Federal Information Processing Standards Pub. xx (Draft), Aug. 19,
1991, 12 pps.

4.  Seysen, M., "A Probabilistic Factorization Algorithm with Quadratic
Forms of Negative Discriminant," Math. Comp., Vol 48, 178, [sic] April
1987, pps. 757-80.

5.  Simmons, G. J., "The Prisoner's Problem and the Subliminal
Channel," Crypto '83, Santa Barbara, CA, Aug. 21-14, [sic] 1983,
Advances in Cryptology, Ed. by D. Chaum, Plenum Press, New York, 1984,
pp. 51-67.

6.  Simmons, G. J., "The Subliminal Channel and Digital Signatures,"
Eurocrypt '84, Paris France, April 9-11, 1984, Advances in
Cryptography, Ed. by T. Beth et al., Springer Verlag, Berlin, 1985,
pp.  364-378.

7.  Simmons, G. J., "A Secure Subliminal Channel (?)," Crypto '85,
Santa Barbara, CA, August 18-22, 1985, Advances in Cryptology, Ed. by
H. C. Williams, Springer-Verlag, Berlin, 1986, pp. 33-41.

8.  Simmons, G. J., and D. Holdridge, "Forward Search as a
Cryptanalytic Tool Against a Public Key Privacy Channel," Proc. of the
IEEE Computer Soc. 1982 Symp. on Security and Privacy, Oakland, CA,
April 26-28, 1982, pp. 117-128.

---------------

Comments:  I do not think that this is the blockbuster that my
anonymous correspondant evidently does.  However, it is a very
interesting result.

I might note, for completeness' sake, that some critics of DSS have a
proprietary interest in RSA, a competing system.  But I don't think
that's what's going on here.

Mark R.   mrr@ripem.msu.edu