Cryptography Reference
In-Depth Information
See Section 2.2 on page
22 for details.
random. What is completely random? In practice, it means that
the attacker can't build a machine that will predict the pattern of the
bits. This is substantially easier to achieve for one-time pads than
it is for reversible Turing machines. There are numerous sources of
completely random information and noise that can be used as the
basis for a one-time pad. The random snow from a noisy section of
the radio spectrum can make the good beginning for such a pad.
The rest of this chapter will concentrate on actually constructing
a reversible Turing machine that could be used to create hiddenmes-
sages in text. It will be based, in part, on the grammar approach from
Chapter 7 because text is a good end product for the process. There is
no reason why the work couldn't be adapted to produce other mim-
icry.
8.3 Building a Reversible Machine
If every Turing machine can be reconstructed in a reversible manner,
Some reversible
machines are inherently
error limiting and
self-resynchronizing in
both directions, as
shown by Peter
Neumann[Neu64] for
David Huffman's
information-lossless
sequential machines.
[Huf59]
then every possible machine is a candidate for being turned into a
vehicle for hidden information. Obviously, though, some machines
are more interesting than others. For instance, loan companies use
computer programs to evaluate the credit of applicants and these
programs respond with either “qualified” or “unqualified”. That's
just one bit of information and it seems unlikely that anyone will
be able to hide much of anything in that bit. On the other hand,
programs that produce complex worlds for games like Doom spit
out billions of bits. There is ample room in the noise. Imagine if
somesecretinformationwasencodedinthedanceofanattacking
droid. You might get your signal by joining an internet group game
of Doom. The information would come across the wire disguised
as instructions for where to draw the attacker on the screen. Your
version of Doom could extract this.
This chapter will show how to build two different reversible ma-
chines. The first, a simple reversible Turing machine, is provided as a
warm-up. It is based on the work of Charles Bennett and it shows
how to take the standard features of a Turing machine and tweak
them so that there is only one possible state that could lead to an-
other. This makes it possible to rewind the behavior.
The second machine is an extension of the grammar-based mim-
icry from Chapter 7. That system used only context-free grammars.
This one lets you simulate any arbitrary computation to add realism
to the text that it produces. The data hidden by the system won't be
recovered by parsing. It will come by running the machine in reverse.
