ATTACK AT DAWN
QOOQEF QO RQUI.
A big problem with simple substitution ciphers is that they are
vulnerable to a simple attack known as frequency analysis. The attacker
counts how often each letter appears and compares that to how often
each letter should appear in a message of a particular language. For
example, in English, the most frequent letter is E, followed by T, so a
cryptanalyst will begin by trying to replace the most frequently used
letter in the encrypted message with the letter E.
That does not always work, as our sample message shows. In this
case, the most frequent letter is Q, which stands for A. The second most
frequent letter, however, does match the expected distribution. O is the
second most common letter in the message, which corresponds to T,
which is the second most common letter in English. Additional analysis
will ´¬ünd other clues like letters appearing in double, certain letters that
appear together, and the likely position of vowels and consonants.
The strength of a substitution cipher can be increased dramatically
by replacing the substitution alphabet with a character stream invul-
nerable to frequency analysis.
The Vernam Cipher is precisely such a system. Rather than map-
ping one character to another using the same twenty-six characters, the
Vernam Cipher relies on a key that is as long as the message that is
being encrypted. So, if the message being encrypted is
Key Length 29
ATTACK AT DAWN
the system will require fourteen random characters for the key. Those
characters might be
YDRJCN MX FHMU.
Now the substitution can be made. To perform the substitution,
we look to see how far into the alphabet each letter of the key is. For
example, Y is the twenty-´¬üfth character of the English alphabet, so we
need to advance twenty-four positions into the alphabet to reach it. So
we use the value twenty-four to perform the substitution.
Our plaintext for this digit is A, the ´¬ürst character in the English al-
phabet. Adding twenty-four to one gives us twenty-´¬üve, so the resulting
ciphertext for that position is Y.
For the second digit, our key is D, the fourth character in the English
alphabet, so we need to advance the next plaintext character three
positions. Thus, our plaintext T becomes W.
In the third digit, our key is R, the eighteenth character in the al-
phabet, so we need to advance the next plaintext character seventeen
positions. This T becomes L.
This process is continued until we arrive at the ciphertext of our
YWLJEY MO IHIG.
Decryption of the message requires the recipient have exactly the
same one-time pad (the same key) and that the keys remain in per-
fect synchronization; if the sender starts to encrypt the next message
with the thirteenth digit of the pad and the recipient starts to decrypt
the message with the fourteenth digit of the pad, the result will be
The correspondents in our example have been careful, so they are
using the same pad and theyÔÇ™re correctly synchronized. The recipient
will take our ciphertext and the one-time pad, performing the same
process as the sender, but in reverse.
Seeing that the letter Y in the ciphertext is zero digits o´¬Ç from the
letter Y in the key is an interesting case. The recipient will look at the
plaintext English alphabet, advancing zero digits before picking the
letter. Zero digits, no advancement, gives the letter A.
Seeing that the di´¬Çerence between our ciphertext W (the twenty-
third letter of the alphabet) and the keyÔÇ™s D (the fourth character of the
30 CHAPTER 4
alphabet), weÔÇ™ll see there is a di´¬Çerence of nineteen. Reaching nineteen
characters into the regular alphabet, we arrive at the letter T.
After examining the third character, we see that L in our ciphertext
is the twelfth character of the alphabet. The corresponding digit in the
key is R, the eighteenth character of the alphabet. Subtracting eighteen
from twelve gives us negative six, which means we have to repeat the
plain alphabet so we can move into that repeating series. (Of course,
we can simply subtract six from twenty-sixÔÇ”the total number of char-
acters in the English alphabet, giving us twentyÔÇ”we will need to move
nineteen positions into the alphabet to reach the twentieth character.)
Advancing nineteen positions into our plain alphabet, we again arrive
For the fourth character, we see that the di´¬Çerence between our
ciphertext J and the key J is zero, so we advance zero digits into the
plain alphabet, again yielding A.
Again, the process is repeated for each digit until we arrive back at
the original message plaintext, ATTACK AT DAWN.
The safety of the Vernam Cipher depends on the key being perfectly
random and used only once. Any reuse of the pad would open the way
for attacks against the key (and therefore all messages ever encrypted
with the pad), as was shown by NSAÔÇ™s VENONA project.
VENONA was a project started by the U.S. ArmyÔÇ™s Signals Intel-
ligence ServiceÔÇ”NSAÔÇ™s forerunnerÔÇ”in 1943 to monitor Soviet diplo-
matic communications. A brilliant success of American intelligence,
VENONA gave the U.S. political leadership important insights into
the intentions of the Soviet Union, as well as details of its espionage
VENONA is now best known for decrypting intercepted Soviet com-
munications that showed Julius and Ethel RosenbergÔÇ™s involvement in
the Soviet spy ring. The project also showed how the Soviet Union
gained information on U.S. atomic research, particularly the Manhat-
Over the course of VENONAÔÇ™s lifetime, some 3000 intercepted mes-
sages encrypted by the Soviets with a Vernam Cipher were broken
because the system was not used properly.13
Despite the restriction on the perfect randomness of the key and the
di´¬âculty in managing the key, the system really does have perfect se-
curity. Because the substitution happens against a randomly generated
pad, a cryptanalyst cannot tell when the right sequence of decrypted
Key Length 31
characters is ATT or THE, because any digit has an equal probability
of mapping to any other digit. Recall that frequency analysis requires
a one-to-one mapping of a plaintext letter to a ciphertext letter, such
that we can count how often a ciphertext letter appears and then to
try reading the message by making the most frequent letter E, the next
most frequent T, and so on.
Consider that when we attack a message using brute force in most
systems, we can simply tell whether we found the right key because the
result of the decryption process gives us something sensible, like plain
English text, or something in a known data format like a JPEG image
The beauty of the Vernam Cipher is that when we ´¬ünd the keyÔÇ”
which we will, if we perform an exhaustive key search of all possibilitiesÔÇ”
weÔÇ™ll have no way of knowing that itÔÇ™s the same key that was used by
the users of the system. Consider the following example.
Given the ciphertext,
all of the plaintexts listed below are equally plausible solutions, because
they have the same number of digits, and each digit in the key has an
equal probability of being any given letter, as a result of being selected
randomly. (A mathematical property of a randomly-chosen character
is that it has equal probability of being any particular element of the
set. Returning to our example with the die, a fair die roll will mean
that there is no di´¬Çerence in the odds of a 1 coming up and the odds
of a 4 coming up.)
Consequently, a cryptanalyst who decrypts our ciphertext cannot
tell whether our original plaintext message was any one of the following,
or some other combination of letters equal in length:
32 CHAPTER 4
Despite the tremendous security o´¬Çered by the Vernam Cipher, the
key length requirement prevents it from being used more widely. It is
only manageable for communications that are brief and infrequent. (Ru-
mor has it that a hotline established between Washington and Moscow
after the Cuban Missile Crisis of 1962 was encrypted with a Vernam
With key management in symmetric cryptosystems, we have reason
to be happy for the availability of asymmetric systems. In recent years,
these have become popular, largely because the Internet has enabled
many people who have never physically met or communicated through
another means to exchange data, in the form of e-mail and through
the Web. The basic idea behind asymmetric systems is that instead of
one key, users have key pairs. One key in each pair is private, while the
other is public, published as widely as possible.
If Alice wishes to send a message to Bob, sheÔÇ™ll encrypt the message
with BobÔÇ™s public key. The only key that can decrypt a message en-
crypted with BobÔÇ™s public key is BobÔÇ™s private key. An interesting side
e´¬Çect of encrypting with BobÔÇ™s public key is that Alice cannot decrypt
a message that she herself wrote and encrypted.
Asymmetric systems tend to be more complicated, mathematically
speaking, than symmetric systems. Symmetric systems are heavily de-
pendent on jumbling messages through processes like transposition
(where the data are rearranged) and substitution (where one datum
is replaced for another). Asymmetric systems are generally based on
mathematical functions that are easy to calculate one way, but ex-
tremely di´¬âcult to reverse.
A good example of a function easy to perform only one way is squar-
ing. Taking any number, and squaring it is easy: simply multiply it by
itself. Going backwardÔÇ”determining square rootÔÇ”isnÔÇ™t so easy. Con-
sider 37, 636, that is, what number, multiplied by itself is 37, 636?
YouÔÇ™ll need to take a guess and see if it works out to be too high or too
low, then keep adjusting it until you ´¬ünd the right number. This takes
a lot of time.
Compare the time spent in calculating square roots with what it
takes, say, to compute 1942 . The di´¬Çerence in time for going forward
(squaring) compared with going backward (taking square root) is what
makes for a one-way function and demonstrates why an attacker has to
spend so much more time and e´¬Çort than users of a system who have
Key Length 33
By 1993, cryptography was becoming a more visible part of the emerg-
ing ÔÇťInternet culture.ÔÇŁ As more people came online, concerns over
privacy of electronic communication grew dramatically. Numerous at-
tempts were made to ´¬ünd ways to secure Internet-based electronic mail.
One group in particular was not about to wait for someone else to bring
privacy to the worldÔÇ™s electronic networks.
The second issue of a magazine called WIRED ran a black and white
photograph of three masked men, holding up an American ´¬‚ag on its
cover. The white masks bore numbersÔÇ”one appearing as a bar code,
the other two in hexadecimal: one across the top, and another across
the eyes. Those numbers were the public key IDs of the faceless persons
on the cover.
Over the photograph was the text, ÔÇťRebels with a Cause (Your
Privacy).ÔÇŁ Without explanation, the bottom-right corner carried the
text ÔÇťPODKL QAITES !ÔÇŁ (Russian for, ÔÇťBe wired!ÔÇŁ)
In the corresponding article, the masked rebels were identi´¬üed as
the founders of a group known as Cypherpunks. Fiercely independentÔÇ”
taking marching orders from neither governments nor corporationsÔÇ”
and strong believers in the power of cryptography, the Cypherpunks
began to look at how to address the problem of protecting information
from prying eyes.
Eric Hughes, a self-employed programmer in California and a co-
founder of the Cypherpunks described the mission succinctly in his
1993 missive, ÔÇťA CypherpunkÔÇ™s Manifesto.ÔÇŁ He wrote,
Cypherpunks write code. They know that someone has to write
code to defend their privacy, and since itÔÇ™s their privacy theyÔÇ™re
going to write it. . . Cypherpunks will make the networks safe
Cypherpunks was never a group with any kind of o´¬âcial member-
ship. People simply called themselves cypherpunks and would show up
at occasional physical meetings, while the bulk of their collaboration
took place electronicallyÔÇ”using the technology of the Internet to build
systems designed to secure their communications. The mailing list be-
came the virtual gathering place to discuss the politics and technology
of cryptography, which is to say protecting liberty in the digital world.
34 CHAPTER 4
CRYPTO ÔÇ™93 Conference, Santa Barbara, California
Canadian cryptographer Michael Wiener shocked his colleagues with
his presentation showing his designs for DES-cracking hardware. His
scienti´¬üc paper included detailed designs, as well as cost estimates for
building various con´¬ügurations of his DES cracker. A $1 million version
of his machine would be able to break DES keys by brute force in three
and a half hours. A $10 million version of his machine would be able
to do the job in twenty minutes. A $100 million version would break
DES keys in two minutes.
While Wiener had not actually built the machine, he did report that
his chip was fully designed and could be fabricated for $10.50 each in
quantity. Were someone willing to come up with the money, his machine
could be built and deployed.
Inspired by WienerÔÇ™s paper, Phil Zimmermann, the author of the
free encryption system called PGP (Pretty Good Privacy) publicly
speculated that large government intelligence agencies, particularly
NSA, had budgets that would support $100 million computers. DES
encryption was useless against the government.
Zimmermann knew that DES was not strong against a determined
attacker years before WienerÔÇ™s paper. PGP, developed over a period
of some ´¬üve years before its release in mid-1991 did not use DES. In-
stead, PGP used a 128-bit symmetric cipher known as IDEAÔÇ”roughly
seventy-two times more resistant to brute-force attacks than DES.
With WienerÔÇ™s paper helping to quantify just how much money
would be needed to build a computer that would render DES useless,
Zimmermann wrote, ÔÇťDES is dead, dead, dead.ÔÇŁ