<<

. 4
( 41 .)



>>

the strength of NSA™s modi¬cation, but ¬fty-six times the strength. The
reduction of the key rate caused a signi¬cant stir among the nascent
group of civilian cryptographers.
In 1975, two cryptographers from Stanford became particularly crit-
ical of the 56-bit key. Whit¬eld Di¬e, one of the two cryptographers,
took the notion of an independent cryptographer to a new level. Not
only was Di¬e free from the restraints of secret government research,
but he also developed his work free of the in¬‚uence of large corpo-
rations. Having graduated from MIT with a degree in mathematics
in 1965 and performed computer security work for several companies
since then, Di¬e found himself becoming recognized as an expert by
his peers even without the help of a powerful support system.
Cryptographic systems long had a serious problem: getting the keys
sent between the sender and recipient of encrypted messages. After all,
if you can safely send a key in secret, why not use the same method
to send the message itself? In practice, this problem was addressed
through procedures, such as having the sender and recipient agree on
a series of keys in person. The ¬rst message would be encrypted with
the ¬rst key, the second with the next key, and so on, until they had
exhausted their supply of keys, at which point they would need again to
exchange a list of keys”whether in person or through a trusted source
like a secured courier.
Being fascinated with the problem of the distribution of crypto-
graphic keys, in particular key distribution over a global Internet, Di¬e
Data Encryption Standard 15

spent a lot of time thinking about this problem. While still forming his
ideas on key distribution, Di¬e visited IBM™s Thomas J. Watson Lab-
oratory to deliver a talk on cryptography, with particular emphasis on
how to manage keys safely.
After his presentation, he learned that Martin Hellman, a professor
of electrical engineering from Stanford had spoken at the same labora-
tory on the same topic not long before. Di¬e took particular interest
in Hellman because most cryptographers at the time were enamored
with the algorithms themselves, leaving few to give the problem of key
distribution any serious consideration.
That evening, Di¬e got into his car and started driving across the
country to meet Hellman. After arriving in Stanford, Di¬e called Hell-
man, who agreed to a meeting. The two were impressed enough with
each other that they looked for a way to work together. Because Hell-
man did not have the funding to hire Di¬e as a researcher, he took
Di¬e on as a graduate student instead. Thus began the partnership of
Di¬e and Hellman at Stanford University.8




After the criticisms Hellman and Di¬e leveled against the 56-bit key
of the developing standard for data encryption throughout 1975 were
ignored by NBS, the Stanford pair authored a letter published in Com-
munications of the ACM. In that letter, they outlined their objections
to the key size and its rami¬cations. Because the Association for Com-
puting Machinery (ACM) is the oldest and largest association of com-
puter scientists and engineers, its Communications is well-read and
highly-regarded, seen by e¬ectively everyone working in computing at
the time.
Hellman and Di¬e knew that the help of this group would be critical
in forcing NBS to address their concerns. Even so, they recognized that
the issue of the algorithm™s security would be so far-reaching that their
concerns would be of interest to the American public. The algorithm
would protect data about the medical histories, ¬nances, and o¬cial
records of Americans from all walks of life.
If the standard could not withstand attack, it would be the Amer-
ican people who would su¬er. Recognizing the di¬culty of bringing
such an obscure (albeit important) matter to the attention of the pub-
16 CHAPTER 3

lic, Hellman and Di¬e wisely enlisted the help of David Kahn, author
of the highly regarded 1967 book The Codebreakers.9 Kahn wrote an
Op-Ed piece for The New York Times that was published on April 3,
1976. In that article, Kahn wrote of the proposed standard, “While
this cipher has been made just strong enough to withstand commer-
cial attempts to break it, it has been left just weak enough to yield to
government cryptanalysis.”
By this time, experts from IBM, Bell Labs, and MIT had also
weighed in on the matter: 56-bit keys were too small, they all declared.
As Kahn noted in his article, “one major New York bank has decided
not to use the proposed cipher” in part because of the criticisms of its
key size.
The uproar was su¬cient to cause the U.S. House of Representa-
tives™ Government Information and Individual Rights Subcommittee
to look into the matter. NBS was forced to recognize that the ¬eld of
cryptanalysis existed beyond the walls of government, that the concerns
are real, and they must be addressed if the e¬ort to standardize the
proposed 56-bit system was to succeed.10 Consequently, NBS decided
to hold two workshops on the cipher proposed as the “data encryption
standard” (DES).
NBS held two workshops in 1976 to deal with the objections raised
by Hellman and Di¬e. These were working meetings where cryptog-
raphers from across the country would be able to discuss the thorny
issues around the proposed data encryption standard face-to-face. As
part of their objections, Hellman and Di¬e proposed the design of a
special-purpose computer that would use a technique called brute-force
to crack DES-encoded keys quickly. The ¬rst NBS workshop was com-
posed of hardware experts who considered the proposed special-purpose
DES cracker.
Some participants argued that the proposed DES cracking ma-
chine would not work because design and control costs would exceed
the cost of the hardware. Hellman and Di¬e countered that crack-
ing DES keys would not be one large job, but many small jobs that
could be performed independently. As such, there was no need for the
microprocessors”the “brains” of the computer”to interact with one
another. Each could be given tasks to perform independent of the oth-
ers. This, Hellman and Di¬e responded, meant that the objection to
the feasibility of a brute-force attack on the basis of design and control
costs did not stand.
Data Encryption Standard 17

Another matter of concern was the reliability of the computer”a
more visible concern in the computing technology of the 1970s than
it is today. The reliability of computers is directly tied to the number
of components needed to construct them. Some of the NBS workshop
participants performed calculations for a DES cracker with 1 million
components”parts for handling computer working memory, storage,
central processing, arithmetic logic, and all of the electronics to hold it
all together. Based on the average time it would take electronic equip-
ment of the day to fail, the million-component machine would not be
able to run for more than a single day before failing in some way. Such
a large system, with that level of failure, would be too big and too
complex to operate.
The Di¬e-Hellman design for a DES cracker, however, called for far
fewer components”only 16,000. Furthermore, rather than using a large
number of parts that would be used only a few times in the machine,
the Di¬e-Hellman design called for construction involving fewer types
of parts”allowing any parts that fail to be easily replaced, getting the
system back up and running in under ten minutes. Such a system would
give error-free operation with a relatively small number of spare parts.
Another objection on the million-chip machine was its size: 6000
large cases”known as “racks””that were 6 feet high. Hellman and
Di¬e responded with a proposal for a million chip machine in only 64
racks, suggesting that even were 1 million chips necessary, the size of
the machine was being seriously overestimated.
Still basing assumptions on the large, million-chip, 6000-rack ma-
chine, power requirements were the next objection raised by NBS and
others. Simply providing the electricity for such a machine to run would
exceed any “reasonable budget,” apparently without specifying what
would constitute “reasonable.” Hellman and Di¬e proposed the use
of chips manufactured in a newer and more cost-e¬ective manner that
would bring the operating cost to under $1500 per day, observing that
power costs could be reduced ¬ve times with newer technology.
Looking at the speed with which a message could be encrypted with
DES on readily available (general-purpose) chips, some participants
determined that those chips would be too slow and cost too much when
purchased in the quantity needed to test DES keys quickly. Looking
at available technology, Hellman and Di¬e suggested that complaints
about chip speed and cost could be overcome by using a special chip,
designed for the speci¬c purpose of searching for DES keys. A special-
18 CHAPTER 3

purpose chip would dramatically increase the speed of the operation.
Such chips, they observed, could be produced in quantity for $10 each.
In the course of this dispute, NBS even o¬ered some of its own alter-
natives to increasing the key size. One approach they suggested was to
develop a system that made use of frequent key changes. Rather than
reusing the same key from one message to another, such a system would
give each message a unique key. That way, the illicit discovery of a key
would compromise only one message, rather than every message en-
crypted with that machine. Hellman and Di¬e responded by observing
that rather than cracking the message immediately after it was sent,
some attackers might have the ability to intercept a message and then
to spend the time necessary to break any particular message. (Interest-
ingly, while cryptographers like Hellman and Di¬e had no way to know
it at the time, this is precisely what happened when SIS cryptanalysts
could not keep up with the ¬‚ow of Japanese military communications
in the run-up to the attack on Pearl Harbor. Recall that SIS decrypted
those messages ¬ve years after they were intercepted.) Hellman and
Di¬e went on to observe that medical records needed to remain pri-
vate for ten years”that kind of long-term privacy requirement could
not be met by a system where a single message encrypted with a rela-
tively small key could be broken in a ten-year period.
Looking at the costs that would need to be borne by anyone im-
plementing commercial cryptography, some argued that increasing the
proposed standard™s length of a key to 128 or 256 bits”as Hellman
and Di¬e suggested”would greatly increase the costs. The expense,
in turn, would make the construction and use of such systems less at-
tractive while also decreasing the overall use of encryption. Hellman
and Di¬e countered these assertions by observing that the comput-
ing power needed to perform encryption is much less than needed to
perform brute-force search. (This works much like a scavenger hunt.
Hiding twenty items”akin to encryption”is not signi¬cantly harder
than hiding ten items, though ¬nding those twenty”akin to brute-force
decryption”would take dramatically more time than ¬nding ten.) The
di¬erence in the cost of operation of a 128-bit system and a 56-bit
system was negligible, but the payo¬ in terms of greater security was
signi¬cant.
Finally, NBS argued that there simply was no way to tell for sure
when the right key had been found in a brute-force search, even if
someone took an encrypted message and used that key to turn it into a
Data Encryption Standard 19

readable plaintext. Hellman and Di¬e argued that while a formal proof
would be di¬cult, the design of DES was not such that a ciphertext
message would be able to decrypt into lots of di¬erent sensible-looking
plaintext messages. The decryption process would produce either a sen-
sible message or gibberish.
Hellman and Di¬e argued that none of the NBS objections was
valid and that a 56-bit key could not provide adequate security against
a dedicated attacker. They recommended devices that would support
variable key lengths. Allowing users to choose their own key lengths
would allow them to decide for themselves whether the extra security
of the larger keys was worth the extra time needed for the encryption
and decryption processes.
NBS didn™t stop with consideration of DES-cracking computers. The
following month, NBS held a second workshop on DES, focused on the
mathematical foundations for the DES algorithm. Participants in the
second workshop expressed signi¬cant concern that while the design
was available for review, the principles that guided NSA™s changes were
classi¬ed, and therefore available only to government cryptographers
sworn to secrecy. The workshop adjourned without consensus.
Nevertheless, the workshops had three important e¬ects. First, much
concern was voiced over the possible weaknesses of DES, with the key
length being a major issue, as well as the participants™ inability to re-
view the design principles behind NSA™s S-Box changes. If NSA wanted
to implant a secret “shortcut” so that only it could decrypt messages
immediately, that would be the place to do it, and participants might
not have enough understanding of the details to identify it.
Second, few participants were convinced that the Hellman-Di¬e
scheme for breaking DES keys was practical. Costs still seemed too
high, and e¬ort needed still seemed too great to be worthwhile. Given
the technology of 1976 and the next few years, there seemed little like-
lihood that DES would be defeated by brute force.
Third, the arguments put forth by Hellman and Di¬e did convince
participants that the key length provided no safety margin. Essentially,
the Hellman-Di¬e designs for key-cracking computers were possible,
but not presently feasible. Anything that would change that balance,
driving the cost of computing down in an unexpected way would un-
dermine the strength of DES against brute-force attacks.
20 CHAPTER 3

NBS considered the matter as resolved as it would ever be, ulti-
mately ignoring the warnings issued by the outsiders from Stanford
and e¬ectively declaring no need for a safety margin.
Whit¬eld Di¬e and Martin Hellman documented their objections
to the 56-bit key of the DES cryptographic algorithm in an article
published in the June 1977 issue of IEEE Computer. Their article,
“Exhaustive Cryptanalysis of the NBS Data Encryption Standard,”
described a special-purpose machine to crack DES keys by brute force.
Building on top of the debates during the NBS DES standardization
process over the hardware requirements for DES-key-cracking comput-
ers, the published Di¬e and Hellman design was estimated to cost $20
million to build, and would be able to break DES keys in roughly twelve
hours each.




Four and a half years after announcing its intention to create a stan-
dard for data encryption, NBS published its o¬cial standard in the
Federal Information Processing Standard series, a group of regulations
and standards that all of the agencies in the Federal government must
follow. At long last, FIPS 46, titled “Data Encryption Standard,” was
released.11
A private, non-pro¬t industry association, the American National
Standards Institute (ANSI) had (and still has) a committee to handle
the standardization of information technology. Not wanting to duplicate
all of the work that NBS had undertaken in the development of its
standard, ANSI adopted exactly the same algorithm, known inside of
ANSI as the Data Encryption Algorithm (DEA). Apparently the issue
of key size would not seriously emerge again”judgment regarding that
matter was being left to NBS, which had mustered as much expertise
in open cryptography as any organization could.
Other ANSI committees, including the committee on Retail and
Banking and the Financial Institution Wholesale Security Working
Group”saw the adoption of DEA and established their own require-
ments to use the same Data Encryption Standard produced by the NBS
e¬ort.
In view of this activity, the American Bankers Association developed
its own (voluntary) standard around the DES algorithm. The Interna-
Data Encryption Standard 21

<<

. 4
( 41 .)



>>