<<

. 9
( 41 .)



>>

national security agencies some ability to monitor transmissions.
Current law does not have such restrictions.
The second issue is whether there should be any restrictions
on the export of encryption technology. Current law regulates
the export of encryption technology in a manner similar to mil-
itary technology.

After hearing from two representatives, the committee heard testi-
mony from William A. Reinsch, undersecretary at the Bureau of Ex-
port Administration in the U.S. Department of Commerce. Reinsch
described the Clinton administration™s policy on cryptography: avail-
Congress Takes Note 51

ability of strong cryptography to protect commercial and personal in-
terests without sacri¬cing the ability to investigate alleged crimes and
to protect national security.
Implementation of the Clinton policy for encryption was centered
around key recovery and key escrow systems. Such systems make it
possible for an authorized agent to decrypt ciphertext to reveal the
original plaintext. While this is what decryption keys normally do, key
recovery systems are designed to allow decryption even if the key is lost
or if the key holder refuses to divulge it. Key escrow systems have a
similar end result, but their mechanism relies on a trusted third party,
one who essentially holds a “master key” that can be applied to decrypt
ciphertext.
As part of the administration™s attempts to implement this policy,
cryptographic products were recategorized. Instead of being considered
a munition and thus regulated by the Department of State, cryptogra-
phy would be recognized as a dual-use technology (one that would be
use in normal commercial activity in addition to government or military
operation), and thus regulated by the Department of Commerce.
In addition, export restrictions were altered, temporarily changing
the export limit from forty bits to ¬fty-six bits. This change explicitly
allowed DES and “equivalent products” to be exported, provided that
the exporting company submit plans to show they were working to de-
velop a “key management infrastructure” (essentially, key recovery or
key escrow). After a two-year transition period, exporters of crypto-
graphic technology would be expected to have their systems support
the sort of key management infrastructure envisioned by the adminis-
tration.
Despite the relaxation of cryptographic product control, the admin-
istration did not want simply to let go of cryptography. Reinsch made
the administration™s view quite clear in the conclusion of his testimony.

I must tell you that legislation such as H.R. 695 would not be
helpful, and the administration cannot support it. The bill has a
number of similarities to what we will shortly submit, but it pro-
poses export liberalization far beyond what the administration
can entertain and which would be contrary to our international
export control obligations. We are sympathetic to some aspects
of H.R. 695, such as penalties for unlawful use of encryption
and access to encrypted information for law enforcement pur-
poses, but the bill does not provide the balanced approach we
52 CHAPTER 7

are seeking and as a result would unnecessarily sacri¬ce our law
enforcement and national security needs. I defer to other wit-
nesses to describe the impact of the bill on law enforcement, but
let me describe a few of its other problems.
The bill appears to decontrol even the strongest encryption
products, thus severely limiting government review of highly
sensitive transactions. The administration has a long-standing
policy that the risks to national security and law enforcement
which could arise from widespread decontrol of encryption jus-
tify continued restrictions on exports.
In addition, whether intended or not, we believe the bill as
drafted would preclude the development of key recovery even
as an option. The administration has repeatedly stated that it
does not support mandatory key recovery, but we most certainly
endorse and encourage development of voluntary key recovery
systems, and we see a strong and growing demand for them that
we do not want to cut o¬.
As I have said on many occasions, Mr. Chairman, encryption
is one of the most di¬cult issues in public policy today, but we
are committed to solving it in cooperation with industry, the
law enforcement community, and the Congress in a way that
reinforces market principles and achieves our diverse goals. We
hope that you will work with us to facilitate that process by
passing the legislation we are proposing.

Next to testify was Robert S. Litt, a deputy assistant attorney gen-
eral in the Criminal Division of the Department of Justice. After weigh-
ing in with the Department of Justice™s view on the proposed legisla-
tion, Litt also o¬ered his thoughts on the strength of cryptographic
keys. Litt™s remarks were focused on the systems already in use, rather
than the sorts of key escrow systems that other administration o¬cials
were discussing.
Litt began with a high-level description of the argument put forth
by some citizens. That argument held that the fears of U.S. law en-
forcement and intelligence agencies were “overstated,” and that the
government simply did not want its own citizens communicating in a
way that would keep them safe from governmental eavesdropping. In
e¬ect, the government would oppose any cryptography that it could not
easily break. (Cryptosystems for general export were limited to 40-bit
keys. As William Reinsch had pointed out earlier, companies willing
Congress Takes Note 53

to show how they were going to implement key recovery or key escrow
systems would be allowed to export cryptosystems with up to 56-bit
keys.)
As evidence for the argument that only weak cryptography would
be allowed, many advocates pointed to Ian Goldberg™s victory in RSA™s
40-bit key cracking contest. If Goldberg could break messages protected
with 40-bit cryptography in three and a half hours, the argument went,
the government must have the ability to break those messages as if they
were not encrypted at all.
“This argument does not withstand scrutiny,” said Litt. Pointing
out that the computational power needed to decrypt a message by
brute force rises exponentially as the key size increases, Litt attempted
to show how brute force attacks simply were not an option for law
enforcement.
“According to the National Security Agency™s estimates, the average
time needed to decrypt a single message by means of a brute force
cryptoanalytic attack on 56-bit DES”a strength whose export we are
now allowing”would be approximately one year and eighty-seven days
using a $30 million supercomputer.”
The law enforcement message to the U.S. Congress was unambigu-
ous: brute force attacks against DES were infeasible.
The day™s estimates would not stop there. William P. Crowell,
deputy director of National Security Agency was next to testify. Crow-
ell began, “I appreciate the opportunity to comment on the pending
. . . legislation and to discuss with you NSA™s involvement with the
development of the administration™s encryption policy. Since NSA has
both an information security and a foreign signals intelligence mission,
encryption touches us directly.” He went on to describe how NSA was
acting as a technical advisor on cryptography to the administration.
In his testimony, Crowell said that the use of cryptography can
be of signi¬cant bene¬t to the nation. From there, he outlined key
management infrastructures and how public-key cryptography works,
the need for an infrastructure to support public key cryptography, and
how such infrastructures can support key recovery.
Finally focusing on the most vocal part of the cryptography de-
bate, Crowell said, “I would like to help clarify some of the frequently-
repeated factual errors regarding encryption so we all can stand on ¬rm
ground during the formation of the nation™s encryption policies.”
54 CHAPTER 7

Crowell argued that basing long-term cryptographic policy on key
size and brute-force attacks is shortsighted. Addressing this matter
directly, he said,

You may have heard news accounts of a University of Califor-
nia, Berkeley student who recently decrypted a message that
was encrypted with a 40-bit key using 250 workstations as part
of a contest from RSA Inc. This so-called “challenge” is often
cited as evidence that the government needs only to conduct
“brute force” attacks on messages when they are doing a crimi-
nal investigation. In reality, law enforcement does not have the
luxury to rely on headline-making brute force attacks on en-
crypted criminal communications. I think you will ¬nd it useful
to see for yourselves how increased key sizes can make encryp-
tion virtually unbreakable. Ironically, the RSA challenge proves
this point.
If that Berkeley student was faced with an RSA-supplied
task of brute forcing a single PGP based (128-bit key) encrypted
message with 250 workstations, it would take him an estimated
9 trillion times the age of the universe to decrypt a single mes-
sage. Of course, if the Berkeley student didn™t already know
the contents of part of the message RSA provided some of the
unencrypted message content to assist those who accepted the
challenge it would take even longer.15
For that matter, even if every one of the 29,634 students
enrolled at UC Berkeley in 1997 each had 250 workstations at
their disposal 7,408,500 computers (cost: $15 billion) it would
still take an estimated 100 billion times the age of the universe,
that is over 1 sextillion years (1 followed by 21 zeros), to break
a single message.
If all the personal computers in the world, 260 million com-
puters were put to work on a single PGP-encrypted message,
it would still take an estimated 12 million times the age of the
universe, on average, to break a single message (assuming that
each of those workstations had processing power similar to each
of the Berkeley student™s workstations).
Clearly, encryption technology can be made intractable against
sheer compute power, and long-term policies cannot be based on
bit lengths. Brute force attacks cannot be the primary solution
for law enforcement decryption needs. This line of argument is
Congress Takes Note 55

a distraction from the real issues at hand, and I encourage you
to help put this debate behind us.

Crowell™s argument was an interesting one. While he intended it
to be taken as evidence that brute force attacks against commonly-
available cryptosystems were simply not feasible, those who argued for
freedom in cryptography would interpret Crowell™s words much dif-
ferently. To them, NSA™s position suggested that the government was
reluctant to allow its citizens to engage in free speech and virtual as-
sociation via global networks without the prying eyes of even the most
powerful government agencies.
Crowell™s argument was also interesting from a technical point of
view. While he used a recently-publicized event to provide estimates
on how long it would take to crack a key by brute force, he used the
speed of Goldberg™s 40-bit challenge solution, rather than Germano
Caronni™s 48-bit challenge solution”even though Caronni™s was con-
siderably faster.
Another critical element of Crowell™s argument was that it assumed
that available computing power would remain constant”ignoring
Moore™s Law, which essentially says that computing power doubles ev-
ery eighteen months. Thus, a computation that might take two months
in early 1997 with “current technology” would take one month in mid
1998, and be down to two weeks at the beginning of 2000.
To many private cryptographers, it would appear that, just as it had
twenty-¬ve years earlier, the government was overstating the di¬culty
of brute force attacks.
8
Supercomputer




Testimony before the House Judiciary Subcommittee on Courts and In-
tellectual Property was compelling across the board. Everyone seemed
to agree that the stakes were high and that breaking encrypted mes-
sages by brute force was a hard, time-consuming problem, even for
well-funded government agencies.
The Justice Department™s Robert S. Litt provided some of the day™s
most interesting testimony, not only providing estimates on the di¬-
culty of cracking a cryptosystem by brute force, but speci¬cally pro-
viding an estimate for cracking DES keys. Litt even cited the source of
his estimate”NSA, the very same intelligence agency responsible for
the brilliant cryptanalysis that uncovered Soviet spies operating in the
United States after World War II. If anyone understood cryptography,
it would be NSA.
NSA™s estimate, he said, was that even with a $30 million su-
percomputer it would take a year and several months to decrypt a
DES-encrypted message by brute force. Litt™s argument was especially
strong, drawing on the common knowledge that supercomputers were
the fastest and most powerful computers available. Indeed, supercom-
puters were very good at dealing with very complex problems, tracking
huge amounts of data, and working with gargantuan numbers.
But ¬nding cryptographic keys in a brute-force attack isn™t a large,
complex problem. A search wouldn™t need many data and the numbers
involved weren™t very big, at least as far as computers were concerned.
Finding a key by trying every single one until the right key is discovered
was really a large number of very small problems. The security of the
system relies in the sheer number of keys that must be tested to ¬nd
the one that unlocks the message.


57
58 CHAPTER 8

You might think about a test that would require you to solve arith-
metic problems like 1 + 3 and 9 + 4. Those problems aren™t di¬cult at
all, but if you must ¬nish the test in an hour and there are one million
problems, you might not be up to the challenge.
There are several ways that you can increase your chances of success.
You could have all of your friends work on the test with you, giving
each person a separate sheet of paper with some of the arithmetic prob-
lems on it. Perhaps your friends might recruit their friends, and you
could increase the number of people helping you on your test further
still. Having a mathematician join the project isn™t going to help you
much, though. While a mathematician can perform much more compli-
cated operations and can work with much larger numbers, a ¬fth grade
student could solve simple arithmetic just as quickly as the greatest
mathematician in the world.
Using supercomputers to ¬nd DES keys would be just as expen-
sive and ine¬cient as using mathematicians to solve a large number
of trivial arithmetic problems. Just as an army of ¬fth graders would
be cheaper and more e¬ective in ¬nishing a million-problem test of
arithmetic, a large number of regular computers would be much more
e¬ective than a single supercomputer in ¬nding a cryptographic key.
The fundamental issue here is how easily the problem can be
“parallelized””broken into steps that can be performed simultaneously
by di¬erent computers, instead of all in order, one at a time. Engineers
often illustrate this problem by pointing out that bringing a new person
into the world is not something that can be parallelized. One woman
is pregnant for nine months before we have a new person. We cannot
expect a baby at the end of a month by impregnating nine women.

<<

. 9
( 41 .)



>>