Cryptography Reference
In-Depth Information
[Kom95]. I also wrote an introductory topic on compression
last millenium. [Way99]
Subliminal Channels
This idea is not covered in the topic, but it
may be of interest to many readers. Much of the work in the
area was done by Gus Simmons, who discovered that many dig-
ital signature algorithms had a secret channel that could be ex-
ploited to send an extra message. [Sim84, Sim85, Sim86, Sim93,
Sim94] This is pretty easy to understand in the abstract. Many
of the algorithms, like the Elgamal signature scheme [ElG85]
or the Digital Signature Algorithm [NCS93] create a new digi-
tal signature at random. Many valid signatures exist and the
algorithm simply picks one at random. It is still virtually im-
possible for someone without the secret key to generate one,
but the algorithms were intended to offer authentication with-
out secrecy.
Imagine that you want to send a one bit message to someone.
The only encryption software you can use is a DSA signature
designed not to hide secrets. You could simply send along a
happy message and keep recomputing the digital signature of
thismessage until the last bit is the bit of your message. Eventu-
ally, you should find one because the algorithm chooses among
signatures at random.
This abstract technique only shows how to send one bit. There
are many extra bits available for use and the papers describe
how to do the mathematics and exploit this channel.
The algorithms form an important basis for political discus-
sions about cryptography. The U.S. Government would like
to allow people to use authentication, but they would like to
restrict the use of secrecy-preserving encryption. Algorithms
like the DSA appear to be perfect compromises. The existence
of subliminal channels, however, shows how the current algo-
rithms are not a perfect compromise.
1
Covert Channels
This is, in many ways, just an older term for the
same techniques used in this topic. The classic example comes
from operating system design: Imagine that you run a com-
puter system that has an operating system that is supposed to
be secure. That means the OS can keep information from trav-
eling between two users. Obviously, you can implement such
an OS by shutting down services like file copying or electronic
1
They may be a perfectly adequate practical compromise because implementing
the software to use this additional channel is time consuming.
