ABCDEFGHIJKLMNOPQRSTUVWXYZ

QWERTYABCDFGHIJKLMNOPSUVXZ

and

ATTACK AT DAWN

would become

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

message,

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

incomprehensible.

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

at T.

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

e¬orts.

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-

tan Project.

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

¬le.

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,

ASPSDFAQQPJF

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:

CRYPTOGRAPHY

ATTACKATDAWN

BISCUITMAKER

THISISSECRET

HANDKERCHIEF

LEXICOGRAPHY.

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

Cipher.)

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

the key.

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

for privacy.

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

August 1993

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.”