I decided to post this in spite of an excess on IP of crypto postings over the past few days (additi

[David Farber <>]

From: WHMurray () DOCKMASTER NCSC MIL


The Five Great Inventions of Twentieth Century Cryptography


William Hugh Murray


Preface


[This talk was presented as the keynote address at the 1994 RSA Security
Conference, Redwood City, CA] Foreword


Two years ago I opened the first of these conferences.


Jim Bidzos invited me to "kick it off;" nothing so formal as a "keynote."
While I wore this same suit, I just sort of got up here to shoot the
breeze with a few of my friends and colleagues. No notes, just sort of
"off-the-cuff." He did not even tell me how long I could talk. As far as I
know there were no reporters present; nothing that I said got me in
trouble.


After the morning session was over, Jim hosted a lunch for some of the
speakers and panelists. Whit Diffie sat beside me, with his notes, and
began to quiz me on my sources and authorities for my comments. He even
told me that some of my best stories were apocryphal (though he conceded
me the points that I made with them).


Well, I see the same friends, but there are far more colleagues. The
program is more formal, Diffie still has his pad and pencil, the press is
here, my remarks are styled as a "keynote," they are sufficiently arguable
that I need to choose my words very carefully, and I have a fixed time to
end. Prudence suggests that I use notes.


Introduction


Cryptography, the art of secret communication, is almost as old as
writing. Indeed, it has been suggested that, at least for a while, writing
itself was a relative secret. Certainly it was esoteric and its use was
reserved to an initiated elite.


Cryptography and recording and communicating technologies have played leap
frog through the pages of history. It is my thesis that both have changed
so radically during the nineteenth and twentieth centuries as to
constitute a new era.


On the recording and communicating side we have photography, telegraphy,
telephony, radio, phonography, cinema, television, and
telecommunications.hy, telephony, radio, cinema, television, and the
computer. Collectively, and even individually, these technologies
constitute a dramatic change in our ability to make a mark across time and
space.


We have seen a similar advance in our ability to conceal those records and
messages from all but a chosen few.


Modern cryptography has its origins between the two great wars of the
twentieth century. .It was driven as much by the use of radio on the
battlefield as by any other single influence, but there are an infinite
number of important recording and communicating applications that simply
cannot be done in clear text.


While more sparingly used and less well known, the advances in
cryptography have been no less dramatic than those in recording and
communications.


I propose to consider five inventions of the twentieth century that have
defined modern cryptography and that set it apart from ancient or
traditional cryptography.


The impact of these technologies has been to simplify the use of codes,
reduce their cost, and increase by orders of magnitude the cost to a
cryptanalyst of recovering information protected by the codes.


What constitutes an invention or sets it apart from other inventions is
somewhat arbitrary. Some of the inventions that I propose to discuss could
be considered as a group of other inventions; the members of the group
might or might not be significant by themselves.


I have limited myself to a discussion of inventions rather than
accomplishments, and to cryptography rather than to cryptanalysis.


Many of the accomplishments of the century have been in cryptanalysis and
may have been greater than the inventions in cryptography. However,
greatness is in the eye of the beholder. Certainly all the inventions have
not been limited to cryptography.


For example, if cryptanalysts did not invent the modern computer, they
certainly gave it a major boost. They have lived to see the advantage that
it provides shift, with its scale, from them to the cryptographer.


Automated Encoding and Decoding


Modern cryptography begins in 1917 with the invention by Gilbert S.
Vernam, an employee of the American Telephone & Telegraph Company, of the
Vernam System.


Vernam used two paper tape readers, one for the message and the other for
the key. He added the two (bit-wise and modulo 2) to produce the
ciphertext.


Moreover, he used the standard information technology of his day to
automate the encoding and decoding of information.


Modern cryptography is automatic. Translation from plaintext to ciphertext
and back again is performed automatically, that is by a machine or
automaton.


While there may be a separate step, the conversion from one code to the
other is done by a machine rather than by a person.


Today that conversion can be done by almost any single user computer. With
appropriate controls and for some applications it can be done in a
multi-user computer.


Before computers, this encoding was done in special purpose machines. The
Enigma and Purple machines were both early and famous examples of such
machines.


The requirement to manually convert from natural language to secret codes
has always been a limitation. It tended to limit both the amount of
traffic encrypted and the complexity of the encoding schemes used.


Therefore, encryption machines of any kind increase the complexity and
effectiveness of the codes available.


At one level, the modern computer can be viewed as a general purpose code
conversion machine. That is, it converts information called input into a
new representation called output.


The relationship between the input and the output can be simple or
complex, obvious or obscure, public or secret, and reversible or
irreversible.


If the conversion is complex, obscure, secret, and reversible, then the
computer can be viewed as an encryption machine.


But for want of a small amount of readily available software, all of the
hundred million general purpose computers in the world are encryption
engines of immense power.


At some price in performance, the relationship between input and output
can be arbitrarily complex and obscure and thus arbitrarily effective in
concealing the meaning of the output.


The cost of computer performance has been falling steadily and rapidly for
fifty years. It has now become so cheap that most capacity is not used for
the convenience of having it ready when it is wanted. The result is that
the use of secret codes can be viewed as almost free.


So cheap is automatic coding and encoding that some applications do it by
default and globally, concealing it completely from the user. Since the
difference in cost between public codes and secret codes is vanishing and
can be paid in a currency, computer cycles, that might otherwise be
wasted, secret codes can be used by default.


Independent Long Key Variable


The major weakness of Vernam's system was that it required so much key
material. This was compensated for by Lyman Morehouse who used two key
tapes of 1000 and 999 characters, about eight feet each in length, in
combination to produce an effective key tape of 999,000 characters,
effectively 8000 feet in length. Morehouse had used a long key.


Modern cryptography is tailored to a particular use by a key variable, or
simply a key. The key is a large integer that tailors the behavior of the
standard algorithm and makes it generate a cipher that is specific to that
number.


The requirement for secrecy is limited to this number. The problem of
protecting the data reduces to the simpler one of protecting the key.


Access to the cleartext requires access to the combination of the
ciphertext, the base mechanism, usually a computer and a program, and the
key.


Since the rest are readily available, the efficiency of any use depends
upon the fact that it is more expensive or difficult to obtain the key
than to obtain the protected data by other means.


All other things being equal, the longer the key, the more secure the
mechanism. Key length is a trade off against the complexity and the
secrecy of the algorithm.


The longer the key, the simpler and more obvious can be the mechanism or
algorithm.


If the key is as long as the message, statistically random in appearance,
and used only once (one-time pad), then such a simple and obvious
mechanism as modulo addition will still provide effective security.


For practical reasons, short keys and more complex mechanisms are
preferred.


Complexity Based Cryptography (The Data Encryption Standard)


In May 1973 the US National Bureau of Standards advertised in the Federal
Register for a proposal for an encryption mechanism to be employed as a
standard mechanism for all of the needs of the civilian sectors of the
government.


The ad stated that the successful proposal would be for a mechanism that
would be secure for at least five years in spite of the fact that the
mechanism would be public and published.


The resulting Data Encryption Standard was proposed by the IBM
Corporation. It was invented by a team led by Walter Tuchman and was based
upon a concept originated by Horst Feistel of IBM's Yorktown Research
Laboratory.


This mechanism, which can be implemented on a chip and completely
described in a few 8.5"X11'' pages, changed the nature of cryptography
forever.


The security of modern encryption mechanisms like the DES is rooted in
their complexity rather than in their secrecy.


While traditional encryption relied upon the secrecy of the mechanism to
conceal the meaning of the message, these modern mechanisms employ
standard and public algorithms.


These mechanisms are standard in the sense that they are of known strength
or have a known cost of attack. However, the trade-off is that their
effectiveness can not, must not, depend upon their secrecy.


Rather, it relies upon the complexity of the mechanism. The complexity of
modern ciphers is such that they can be effective even though most of
their mechanism is public.


The most well known, trusted, and widely used of all modern ciphers is the
Data Encryption Standard. Because of the intended breadth and duration of
the use of this cipher, the sponsors specified that it should be assumed
to be public.


Its effectiveness should rely upon the secrecy only of the key (see the
next section). It has been public for more than fifteen years, but its
effectiveness is such that trying all possible keys with known plain and
cipher text is still the cheapest practical attack.


[The DES belongs to a class of ciphers known as Feistel ciphers. These
ciphers are also known as block product ciphers. They are called block
ciphers because they operate on a fixed length block of bits or
characters. They are called product ciphers because they employ both
substitution and transposition.]




Automatic Key Management


The same key must exist at both ends of the communication. Historically,
keys were distributed by a separate channel or path than the one by which
the encrypted traffic passed.


The initial distribution and installation of the keys must be done in such
a way as not to disclose them to the adversary.


When this is done manually, it represents a significant opportunity for
the compromise of the system.


Because they were attempting to combine cryptography and computing in a
novel manner, Tuchman and his team understood this problem very well.


The products that they based upon the DES algorithm addressed it, in part,
by automating the generation, distribution, installation, storage,
control, and timely changing of the keys.


Their elegant system is described in two papers published in the IBM
Systems Journal Vol. 17(2) pp. 106-125 (1978) and covered by a number of
fundamental patents based upon it. [While NSA had automated some key
management operations, and while Rosenblum was awarded a patent for a "key
distribution center," these were ad hoc. This work is the first that
describes and implements a complete and integrated automatic system.]


The impact of this concept on the effectiveness, efficiency, and ease of
application of modern cryptography is immense. However, it may also the
the least understood and appreciated.


For example, much of the analysis of the strength of the DES is made in
the context of the primitive DES. However, the DES rarely appears as a
primitive. Instead it appears in implementations which use it in such a
way as to compensate for its inherent limitations.


For example, automatic generation of the keys avoids the use of weak or
trivial keys. (the DES has four known weak keys and four semiweak keys.)