<<

. 6
( 41 .)



>>


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

<<

. 6
( 41 .)



>>