<<

. 5
( 41 .)



>>

tional Standards Organization (ISO) adopted the algorithm, calling it
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

<<

. 5
( 41 .)



>>