DEA-1. Australia™s banking standard also was built around DES.

Given the widespread adoption of DES for data encryption, a great

deal was at stake. If DES turned out to be resistant to serious attack,

tremendous amounts of data being locked up in computers would be

safe, even against the most sophisticated attacks. On the other hand,

if anyone found an exploitable weakness or good attack against DES,

tremendous loss would be possible.

Ruth M. Davis of NBS published an article in the November 1978

issue of IEEE Communications Society about the process of forming

the Data Encryption Standard.12 In it, she wrote that the workshops

determined that DES was satisfactory as a cryptographic standard for

the next ten to ¬fteen years. Interestingly, she speci¬cally observed

that, “the risks to data encrypted by the DES will come from sources

other than brute-force attacks.”

After DES was adopted as a standard, it would be subjected to many

types of attacks, and its properties would be studied exhaustively. After

years of cryptanalysis, consensus would emerge that DES was indeed

a strong algorithm, remarkably resistant to a wide variety of attacks.

Still, one criticism of the algorithm just could not be shaken. The key

length, at ¬fty-six bits, was proclaimed insu¬cient to protect against

attackers very far into the future.

Academic and industrial cryptologic research increased signi¬cantly

in the years following the standardization of DES, including signi¬-

cant work done in the growing community of cryptographers outside of

government intelligence agencies. Products would continue to be devel-

oped, with increasingly sophisticated systems becoming available and

put into use. While not opening its vault of cryptologic secrets, the

U.S. government did watch the ever-increasing size and sophistication

of this community with great interest. The government™s concern was

not just with the independent domestic development of powerful new

encryption products, but with the export of those products into the

international markets.

As with other technologies that could raise national security con-

cerns, the export of cryptographic products was subject to the Inter-

22 CHAPTER 3

national Tari¬s in Arms Regulations (“ITAR”), administered by the

O¬ce of Defense Trade Controls at the Department of State. A li-

cense would be required for any U.S. companies or persons to export

such items, and that license would be subject to approval of the State

Department, which would presumably follow the recommendation of

NSA.

The purpose of ITAR was to prevent the export not just of arma-

ments but of implementations of cryptographic techniques. Working

cryptosystems could only be exported outside of the U.S. and Canada

with a key of forty bits or smaller, which would essentially mean that

only systems that could be broken easily were allowed to be exported.

There was no restriction on key length for domestic use, and by 1996

systems with keys of 128 bits and more were widely available. Even so,

DES, which was already well-established as the de facto international

benchmark, remained the standard for commercial usage.

4

Key Length

In any cryptosystem where a key allows the intended recipient to read

the message, there is always a chance that an attacker will ¬gure out

which key will decrypt message. Longer keys are one of the simplest

and most e¬ective mechanisms to lower the risk: a machine that could

¬nd a ¬fty-six bit key every second would take 150 trillion years to

¬nd a 128 bit key. This is why Hellman and Di¬e argued for longer

keys; ¬nding keys by trial and error would be simply ridiculous even to

contemplate.

Cryptosystems are divided into two categories: symmetric (also

called “secret key” or “conventional”) and asymmetric (also called

“public key”). In both categories, the concepts of key and the key length

are of the greatest importance.

Symmetric cryptosystems use the same key for encryption and de-

cryption. Physical locks are often symmetric.

A familiar example of a symmetric lock was mentioned on page 12: a

bicycle chain with a combination lock that holds the two ends together

until the numbers are rotated to display the proper combination. The

key in this case is not a physical piece of metal, but the combination

that the user can enter, which will cause the internal mechanisms of

the lock to align so that the end pieces can be put together and pulled

apart. If you know the combination, you can use the lock; if not, you

can™t.

All of these locks are vulnerable to an exhaustive key search, known

as a brute-force attack. Attackers simply try every single possible com-

bination until ¬nding the one that works. Imagine a bicycle combination

lock with one tumbler, with ten positions numbered from 0 to 9. The

brute-force attack against this lock is to set the tumbler to position 0

23

24 CHAPTER 4

and to pull on the lock to see if it opens. If not, move the tumbler to

position 1 and pull on the lock to see if it opens. If not, systematically

keep changing the tumbler position until you ¬nd the right one.

Such a system has a work factor of ten operations in the attacker™s

worst case scenario, meaning there is a one in ten chance of guessing

correctly on the ¬rst try. On average, an attacker would be able to ¬nd

the combination in ¬ve tries, assuming that the keys are distributed

randomly.

One way to demonstrate random distribution, and the fact that on

average we need to try only half of the keys to ¬nd the right one, is with

a plain old six-sided die, the sides numbered 1 through 6. If we roll the

die, each number has a one in six chance of coming up. Imagine that

the die is being used to ¬nd the key for a tumbler with six positions,

labeled 1 through 6, we™ll be able to make the connection. Roll the

die a large number of times”say, 100 times”recording which number

comes up on each roll.

Now, if we set the one-tumbler, six-position lock to what comes up

on the die, we have set the “key” for the system randomly, which is

the best possible way to choose a key. If you then give the system to

a group of attackers to unlock the system, they will probably set the

lock to 1, pull it, moving on to 2 if it doesn™t work, and so on, until

they unlock it. The group can also try them all at random if they like.

Even if the group employs both strategies, the result will be the same

in the long run. If we record the number of attempts that it takes for

the attackers to unlock it, we™ll see that they have a one in six chance

of guessing correctly on the ¬rst try. They have a six in six chance

of guessing correctly through the sixth try. They have a three in six

chance of guessing correctly through the third try.

If we assume that it takes one second to set the tumbler and to see

whether the lock has disengaged, our ten-position, single-tumbler lock

would be secure only against an attacker in a very big hurry.

If we want to increase the attackers™ work factor, we can either

increase the number of settings on the tumbler or we can add another

tumbler. If we add another setting on the tumbler, we™ll increase the

attacker™s worst case work factor to eleven seconds. If we add another

ten-setting tumbler to the lock instead, we have increased the attacker™s

worst case work factor to 100 seconds.

Key Length 25

Thus, increasing the number of tumblers is much more e¬ective than

increasing the number of settings on the tumbler. Figure 2 shows the

possible settings on our lock with two tumblers numbered 0 through 9.

x0 x1 x2 x3 x4 x5 x6 x7 x8 x9

0x 00 01 02 03 04 05 06 07 08 09

1x 10 11 12 13 14 15 16 17 18 19

2x 20 21 22 23 24 25 26 27 28 29

3x 30 31 32 33 34 35 36 37 38 39

4x 40 41 42 43 44 45 46 47 48 49

5x 50 51 52 53 54 55 56 57 58 59

6x 60 61 62 63 64 65 66 67 68 69

7x 70 71 72 73 74 75 76 77 78 79

8x 80 81 82 83 84 85 86 87 88 89

9x 90 91 92 93 94 95 96 97 98 99

Fig. 2. Possible Combinations For A Two-Tumbler Lock

Thus, by adding a new tumbler to the lock, the strength of the

system is increased exponentially, whereas the strength of the system

where a new position is added to the tumbler increases only linearly.

Mathematicians express this concept with simple notation like xy ,

where x is the base and y is the exponent. A ten-tumbler system has a

base of 10 and an exponent of the number of tumblers, in this case ten.

Our ¬rst example, the single-tumbler lock has 101 = 10 possible com-

binations. Our second example has 102 = 100 possible combinations.

A typical bicycle tumbler lock might have four tumblers, in which case

there are 104 = 10, 000 possible combinations.

Still assuming that it takes one second to test each combination, it

would take 10,000 seconds (nearly three hours!) to try every possibility

on a four-tumbler lock. Once again, in practice, an attacker will only

need to try approximately half of the keys on average to ¬nd the right

one. So our system will be able to resist brute-force attacks for an

average of just under an hour and a half.

Finding a cryptographic key is no di¬erent. In a brute-force attack

against a cryptosystem, the attacker simply starts trying keys until one

works. Since modern computers are binary, our cryptosystems are like

tumbler locks with only two settings: 0 and 1. Instead of saying how

many “tumblers” we have in computer-based cryptosystems, we say

how many “bits” we use to represent the key. A one-bit cryptosystem

has two possible keys: 0 and 1; mathematically, this is 21 = 2. A two-bit

26 CHAPTER 4

cryptosystem has four possible keys: 00, 01, 10, and 11; mathematically,

22 = 4. A three-bit cryptosystem has eight possible combinations (23 =

8).

What™s interesting about breaking a cryptosystem, though, is that

the equivalent of pulling on the lock to see if it opens involves running

the encrypted message, trying a key that might unlock the message

through the decryption process and then examining its output. The

encrypted message will look like gibberish. Running the wrong key

through the decryption process with the message will give us more

gibberish. Running the right key through the decryption process will

give us something that looks sensible, like English text.

For example, given ciphertext of QmFzZTY0PyBQbGVhc2Uh and the

key 1101 as input, the decryption function would produce something

like UW1GelpUWTBQeUJRYkdWaGMyVWg if the key is wrong. If the key is

correct, the output would look like ATTACK AT DAWN.

This entire process can be automated with software. Consider a

brute-force attack against messages encrypted with a three-bit cryp-

tosystem. The software will need to recognize many popular data

formats, for example, standard plain text, a JPEG graphics ¬le, an

MP3 sound ¬le, and so on. To determine the key needed to unlock

an encrypted message, the software would run the encrypted message

through the decryption process with the ¬rst key, 000. If the output

seems to match one of the known formats, the software will report 000

as a possible match. If not, it can go to the next key, 001 and repeat

the process. Obviously, it won™t take a computer long to work through

eight possible combinations to ¬nd the right key.

The more strength we put into a system, the more it will cost us, so

a balance must be struck between our own convenience”we can™t make

it too di¬cult for ourselves”and the attacker™s. A lock that withstands

attacks for an hour and a half is “secure” if it needs to protect something

for an hour. A lock that withstands attacks for a year is “insecure” if

it needs to protect something for a decade.

Team sports like American football provide a good illustration of

the importance of timing in security matters. Football teams have play-

books, which are e¬ectively code books. The quarterback calls the play,

and his own team knows what to do next. The opposing team, on the

other hand, should not be able to anticipate what the next play will

be. If someone had the time before the play starts to analyze the quar-

terback™s calls, their contexts (the down, how well the o¬ense has been

Key Length 27

performing in its passing and running), and some history of the team™s

behavior, it™s quite likely that he could ¬gure out the play before it

starts. But the code employed is secure because no one has time to

perform all of that analysis. The message is secret for only a few mo-

ments, but it is enough time to serve its purpose.

There is one type of symmetric system that does not have the same

weakness to brute-force attacks. This is the Vernam Cipher, developed

by Gilbert Vernam of AT&T in 1918. Some”notably, Vernam him-

self was not one of them”have suggested that the Vernam Cipher is

unbreakable, a claim which is worth considering.

The Vernam Cipher is actually a simple substitution cipher, one

of the old manual systems (as opposed to modern computer-based sys-

tems) that used scratch paper and nothing else. Before we consider how

the Vernam Cipher in particular works, we should be clear on simple

substitution ciphers in general.

Julius Caesar is known for his use of a primitive encryption system

that now bears his name. The Caesar Cipher is a simple mechanism of

substituting one letter for another, following a regular pattern. To see

how this works, write the alphabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Write the alphabet again, just below it, starting with N (shifting

thirteen characters to the left).

NOPQRSTUVWXYZABCDEFGHIJKLM

The shifted-thirteen-places version of the alphabet is the key in the

cipher. To encrypt a message with this system, simply choose the letter

you want from the top alphabet, ¬nd the corresponding letter in the

bottom alphabet, and write that down.

Thus,

ATTACK AT DAWN

becomes

NGGNPX NG QNJA.

28 CHAPTER 4

Decryption works the same way; the intended recipient knows how

to construct the bottom alphabet. When reading the message, he™ll ¬nd

the letter in message in the second alphabet and match it up to a letter

in the ¬rst alphabet, revealing the original message.

Variations have been proposed, where instead of simply shifting the

alphabet some number of spaces, the letters of a word like QWERTY are

used to start the substitution alphabet. In such a case, the key would

become