SUBLIMINAL CHANNELS - PAST AND PRESENT

Subliminal channels were devised by Simmons in 1978 to demonstrate a f undamental flaw in a protocol the U.S. was considering using to allow the U.S.S.R. to verify U.S. compliance with the terms of the SALT II t reaty. The examples given of such channels were more in the nature of existence proofs than feasible communication channels until 1984 when it was shown that most digital signature schemes could be caused to ho st subliminal communications hidden in the digital signatures. Almost all of these subliminal channels, however, had several shortcomings. I n order for the subliminal receiver to be able to recover a subliminal message, it was apparently necessary for him to know the transmitter' s (the signer's) secret key. This meant that the subliminal receiver h ad to be given the capability to utter undetectable forgeries of the t ransmitter's signature. Also, only a subset of the natural message set could be communicated subliminally and some of those that could be tr ansmitted were computationally infeasible for the subliminal receiver to recover. A digital signature standard (DSS) has recently been adopt ed by the U.S. government (May, 1994) which like most other digital si gnature schemes also permits subliminal communications to be concealed in signatures. Remarkably though, the subliminal channels in the DSS avoid all of the shortcomings that limit the usefulness of these chann els in other digital signature schemes. This paper briefly describes t he setting for the discovery of subliminal channels and then in some d etail, the nature and shortcomings of the subliminal channels in the E l Gamal digital signature scheme - to which the DSS is closely related . Finally, to make clear what a remarkable coincidence it is that the apparently inherent shortcomings present in subliminal channels realiz ed in the El Gamal scheme can all be overcome in channels realized in the DSS, each of the channels is analyzed in detail in both schemes. T he inescapable conclusion, though, is that the DSS provides the most h ospitable setting for subliminal communications discovered to date.