The Subliminal Channel and Digital Signatures

In a paper entitled “The Prisoners’ Problem and the Subliminal Channel” [1], the present author showed that a message authentication without secrecy channel providing m bits of overt communication and r bits of message authentication could be perverted to allow an l < r bit covert channel between the transmitter and a designated receiver at the expense of reducing the message authentication capability to r-l bits, without affecting the overt channel. It was also shown that under quite reasonable conditions the detection of even the existence of this covert channel could be made as difficult as the underlying cryptoalgorithm was difficult to “break.” In view of this open -- but indetectable -- existence, the covert channel was called the “subliminal” channel. The examples constructed in [1], although adequate to prove the existence of such channels, did not appear to be feasible to extend to interesting communications systems. Fortunately, two digital signature schemes have been proposed since Crypto 83 -- one by Ong-Schnorr-Shamir [2] based on the difficulty of factoring sufficiently large composite numbers and one by Gamal [3] based on the difficulty of taking discrete logarithms with respect to a primitive element in a finite field -- that provide ideal bases for implementing practical subliminal channels. This paper reviews briefly the essential features of the subliminal channel and then discusses implementations in both the Ong-Schnorr-Shamir and Gamal digital signature channels.