Cryptography Reference
In-Depth Information
the questions, there would be no need for evolutionary
scientists. Nor would there be any need for the program
officers at the National Science Foundation who give out
money to evolutionary scientists. There is a well-defined
synergy at work here.
7.2 Using Grammar for Mimicry
Chapter 6 showed how to hide data and turn it into something that
mimicked the statistical patterns of a file. If you want a piece of text
to sound like the
New York Times
, for instance, you could feed in a
largeamountofsourcematerialfromthepaperandgatherstatistical
patterns that make it possible to mimic its output. Ideally, such a
function would be a strong technique for hiding information from
automatic scanning programs that might use statistical patterns to
identify data.
The output of these Huffman-based methods could certainly fool
any machine examining data for suspicious patterns. The letters
would conform to the expected distribution: “e”s would be com-
mon, “z”s would be uncommon. If either second- or third-order text
was used, then “u”s would follow “q”s and everything would seem to
make sense to a computer that was merely checking statistics.
These statistical mimic functions wouldn't fool anyone looking
at the grammar. First- or second-order mimicry like that found on
page 91 looks incomprehensible. Words start to appear in third-
or fourth-order text, but they rarely fall into the basic grammatical
structure. Even a wayward grammar checker could flag these a mile
away.
This chapter describes how to create mimicry that will be gram-
matically correct andmake perfect sense to a human. The algorithms
are based on some of the foundational work done in linguistics that
now buttresses much of computer science. The net result is some-
thing that reads quite well and can be very, very difficult to break.
7.2.1 Context-Free Grammars
The basic abstraction used in this chapter is
context-free grammar
,a
Earlier editions of this
topic included code for
generating
grammar-based
mimicry. It's now
available directly from
the author.
notion developed by NoamChomsky [CM58] to explain roughly how
languages work. The structure is something like a more mathemati-
cal form of sentence diagramming. This model was adopted by com-
puter scientists who both explored its theoretical limits and used it
as a basis for programming languages like C or Pascal.
A context-free grammar consists of three different parts:
