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)