Introduction to Cryptography and the Clipper Chip Controversy

Next week John Perry Barlow and Stewart Baker will be debating the future of cyberspace. It's hard to guess exactly what they will be talking about, but from past lectures and essays, I'm guessing that there will be some discussion of privacy and cryptography. And even if they don't discuss it, it's an interesting topic that you should all be aware of.

I am going to try to present to you facts about cryptography and a summary of the controversial issues surrounding its use in as non-biased a manner as possible. This may be difficult because I have strong opinions about some of these issues. But I would like you to think about these issues yourself and draw your own conclusions.

Much of the information in this presentation is taken from:

Codes, Keys and Conflicts: Issues in U.S. Crypto Policy. Report of a Special Panel of the ACM U.S. Public Policy Committee (USACM) June 1994.

• http://Info.acm.org/reports/acm_crypto_study.html
• ftp://Info.acm.org/reports/acm_crypto_study/
• gopher://gopher.acm.org/11 (the_files.reports.acm_crypto_study)

Parts of this presentation were inspired by a tutorial at the March 1994 Computers, Freedom and Privacy Conference: "Everything you need to know about cryptography in just 60 easy minutes" by Matt Blaze. Blaze is the AT&T Bell Labs researcher who discovered a famous flow in the escrowed encryption standard in May 1994.

For additional information on encryption, check out the EP/CS142 encryption archive.

Who needs privacy?

Who needs privacy and why?

• countries that wish to protect their military strategies
• companies that wish to protect their business strategies
• criminals that don't want to get caught
• ordinary people who don't want others to know about their feelings, beliefs, acquaintances, credit card numbers, purchasing history, etc. and who value the "right to be left alone"

Can't the U.S. government be trusted to respect my privacy?

Although the U.S. government is generally known for respecting the privacy rights of American citizens, there are a number of documented instances where government officials have violated these rights:

• during WWII, census data was used to locate 112,000 people of Japanese ancestry and place them in internment camps
• in the 1960s the FBI regularly taped Martin Luther King's conversations
• between 1947 and 1975 the National Security Agency had international cable companies forward to them millions of cables sent by American citizens

Why is privacy more of a problem now than ever before

Online computer databases make it much easier than ever before for someone to piece together a composite profile of any American citizen. Twenty years ago you could collect information about someone by digging through public records scattered about the counties where they have lived or by hiring a private investigator; now you can obtain much of the same information in a matter of hours (or minutes if you know what you are doing) without leaving your home. Direct marketers are taking advantage of this to better identify potential customers.

Face-to-face communications can generally be made private, but telephone, cellular phone, postal mail, email, and radio are easily interceptable. This becomes more of a problem as virtual meetings, electronically transmitted and signed contracts, and electronic payments become the norm.

• misuse of private information (medical history, buying habits, whom you communicate with)
• abuse of technology by dishonest people (fraud, invasion of privacy, terrorism)

What is cryptography?

"Cryptography is the science of secret writing." -- Matt Blaze

Cryptography can provide:

• confidentiality - prevents messages from being comprehended by anyone other than the intended recipient
• integrity - can be used to detect when messages have been altered
• authenticity - can provide some assurance as to the origin of a message

Secret (or Private) Key Cryptography

The simplest form of private key cryptography can be found in cereal box "secret decoder rings."

All the parties who want to correspond secretly must have a copy of the secret key. This means that they must arrange to exchange the secret key in advance over a secure channel.

"In a well designed system:

• the bad guy must try all possible keys to read or forge messages - no "shortcut."
• trying all the keys takes almost forever
• if a message decrypts properly, Bob knows it must have come from Alice"

The most popular implementation of private key cryptography is the Data Encryption Standard (DES).

• DES was proposed in 1975 and adopted in 1977.
• It was designed by IBM for use by Federal agencies for the protection of sensitive but unclassified data.
• Despite tight export restrictions there are at least 152 DES products being developed and distributed in at least 33 countries.
• Keys are 56 bits long: 2^56 = 7*10^16 = 70,000,000,000,000,000 keys to pick from -- this is a huge number, but a $1,000,000 special-purpose computer can try all of them in 7 hours.
• As computers are becoming faster and cheaper it is becoming easier to crack DES -- therefore it is predicted that it will soon be of little use.

A relatively new secret key system, IDEA, was developed three years ago by a Swiss graduate student and has a 128 bit key.

Public Key Cryptography

Proposed in the 1970s by Stanford researchers Diffie and Helman and realized by Rivest, Shamir, and Adelman as RSA.

Any message encrypted with a private key must be decrypted with the corresponding public key, and vice versa....so users publish one key and keep the other key secret.

RSA is "based on the idea that factoring really large numbers seems to be a hard problem." -- Matt Blaze

RSA is about 1000 times slower than DES, and is therefore usually combined with DES, IDEA, or another private key cryptosystem.

Implementations

• secure telephones ($1000+ each)
• secure email (PGP)
• secure computer files
• secure networks
• smart cards
• digital signatures

A Hypothetical Example: BlackNet

Your name has come to our attention. We have reason to believe
you may be interested in the products and services our new
organization, BlackNet, has to offer.

BlackNet is in the business of buying, selling, trading, and otherwise
dealing with *information* in all its many forms.

We buy and sell information using public key cryptosystems with
essentially perfect security for our customers. Unless you tell us who
you are (please don't!) or inadvertently reveal information which
provides clues, we have no way of identifying you, nor you us.

Our location in physical space is unimportant. Our location in
cyberspace is all that matters. Our primary address is the PGP key
location: "BlackNet" and we can be contacted
(preferably through a chain of anonymous remailers) by encrypting a
message to our public key (contained below) and depositing this
message in one of the several locations in cyberspace we monitor....

BlackNet is nominally nondideological, but considers nation-states,
export laws, patent laws, national security considerations and the
like to be relics of the pre-cyberspace era. Export and patent laws
are often used to explicity project national power and imperialist,
colonialist state fascism. BlackNet believes it is solely the
responsibility of a secret holder to keep that secret--not the
responsibilty of the State, or of us, or of anyone else who may come
into possession of that secret. If a secret's worth having, it's worth
protecting.

....

BlackNet can make anonymous deposits to the bank account of your
choice, where local banking laws permit, can mail cash directly (you
assume the risk of theft or seizure), or can credit you in
"CryptoCredits," the internal currency of BlackNet (which you then
might use to buy _other_ information and have it encrypted to your
special public key and posted in public place).

....

Join us in this revolutionary--and profitable--venture.

Cryptography and law enforcement

The Fourth Amendment provides safeguards for the security of our "persons, houses, papers and effects" against intrusion by the government.

Prior to 1968, the legality of wiretapping was questioned many times in the courts. In 1968 Congress decided to make the legality of wiretapping unambiguous by including wire tap provisions in the Omnibus Crime Control and Safe Streets Act:

• wiretaps permitted only for certain types of criminal investigations
• wiretaps must be approved by a Federal District Court Judge

The law enforcement community views wiretaps as essential:

• provides otherwise unobtainable information
• provides more reliable information than can be obtained otherwise
• in cases of government corruption, can be the only way to uncover extent of the crime and identify participants
• useful for preventing terrorism

There is no way to know whether evidence obtained through a wire tap is really what ultimately led to a conviction.

In 1993, the average cost of installing and monitoring a wire tap was $57,256.

There are an average of about 900 wire taps annually. About two-thirds are for drug cases.

Cryptography prevents law enforcement from listening in on criminals' communications -- even with a court order!

Cryptography and national security

The public availability of strong cryptography allows foreign governments and terrorists to send communications that U.S. intelligence agencies cannot decipher.

Countries are somewhat successful at controlling the flow of people and tangible items across their borders. However, they are not as successful at controlling the flow of information across their borders, especially when that information is encrypted.

In order to protect all American communications, strong encryption must be widely available in the U.S. However, it is nearly impossible to make strong encryption widely available in the U.S. without making it available abroad as well. For example, despite efforts to prevent the export of DES, it is widely available around the world.

Export control

1. to limit foreign availability of cryptographic systems of strategic capability, namely, those capable of resisting concerted cryptanalytic attack;
2. to limit foreign availability of cryptographic systems of sufficient strength to present a serious barrier to traffic selection or the development of standards that interfere with traffic selection by making the messages in broad classes of traffic (fax, for example) difficult to distinguish; and
3. to use the export-control process as a mechanism for keeping track of commercially produced cryptosystems, whether U.S. or foreign that NSA may at some time be called upon to break."

Export controls make it difficult or impossible for American software developers to market their encryption products abroad.

Private use of encryption technology is prohibited or restricted in several countries including France, Korea, Taiwan, and China. Thus, there is little or no market for U.S. encryption products in some foreign countries.

Products containing digital signatures but no cryptographic algorithms that conceal the content of communications are generally exportable.

Key escrow encryption

Key Escrow: An encryption system in which one or more "escrow agents" hold copies of all encryption keys.

In April 1993 President Clinton announced the Escrowed Encryption Initiative, "a voluntary program to improve security and privacy of telephone communications while meeting the legitimate needs of law enforcement."

• designed by the NSA
• includes a classified encryption algorithm -- SKIPJACK
• voice encryption chip (for phones) -- Clipper
• clipper plus digital signatures (for computer communications) -- Capstone
• key-escrow system -- key is split -- half of key held by NIST, half of key held by Treasury Department

Clipper Chips are manufactured by one company -- Mykotronx. They are used in AT&T secure telephones.

Public response was overwhelmingly negative.

• people don't trust law enforcement to obtain court orders to decrypt
• people don't trust a classified encryption algorithm that has not been subjected to public scrutiny (Note, most encryption systems do not rely on the secrecy if their algorithms for security; they rely only on the secrecy of their keys. However, cryptographers have learned a lot by studying published cryptographic algorithms. The NSA does not want to release the algorithm for fear of aiding foreign cryptographers. However, release of the algorithm should theoretically not compromise its security.)
• people are worried that the secret algorithm might have a "back door"
• companies don't expect a big international market for encryption devices with keys held by the U.S. government
• people who communicate with people over seas are worried that EES won't interoperate with foreign encryption devices
• people are worried that the government may eventually outlaw other forms of encryption in order to force adoption of this voluntary standard
• people don't like the fact that EES is implemented in hardware -- this adds about $60 to any product with EES capabilities and reduces flexibility
• people don't like the idea of trap doors being built into civilian communications infrastructure
• people don't think criminals will use EES

The Clipper Chip breaks messages up into chunks, encrypts each chuck, and adds a Law Enforcement Access Field (LEAF), before transmitting the message. Each encrypted and packaged chunk looks something like this (summarized from Denning's technical report):

F = Family key (common to all Clipper Chips) - 80 bits
N = serial Number of chip - 30 bits
U = secret key for chip - 80 bits
K = Key specific to particular conversation - 80 bits
M = the Message

Law enforcement officers who have a court order permitting them to intercept a phone conversation can decrypt the conversation using the following procedure:

• use F to decrypt outer layer of LEAF revealing N and K encrypted by U
• obtain escrowed key halves for chip with serial number N
• put key halves together (with XOR) to reveal U
• use U to decrypt K
• use K to decrypt M (the message)

In May 1994 Matt Blaze announced that he had found a flaw in EES. Blaze said he discovered a way to replace the LEAF with a bogus LEAF containing a different serial number. Although his technique is not fast enough to be useful for voice communication, it seems to succeed in defeating law enforcement access for other types of communications.

Although EES is a voluntary government standard, the NSA is hoping that everyone will buy Clipper products voluntarily because they will be less expensive than other encryption products. In addition, if an agency such as the IRS were to adopt EES, then anyone who wanted to file their taxes electronically would have to use it.

On July 20, 1994 Vice President Al Gore announced that the administration was backing down on SKIPJACK and its applications. He said they would still pursue the use of Clipper for voice and low speed data communications but would investigate other solutions for high speed data communications. There is still a lot of uncertainty as to what other solutions will be proposed.

Summary of major issues

• Is wiretapping essential for fighting crime and maintaining national security?
• Will criminals and terrorists use EES?

Are there other solutions to this problem?

• Are private escrow agencies a good solution?

• Are people likely to use encryption products?
• Are escrow and auditing procedures sufficient to prevent abuse?
• Should the civilian communications infrastructure rely on a system designed by the military?
• Do we believe in an absolute right to communication privacy?

Is EES likely to reduce foreign markets for American hardware and software products?

Can we afford to live with EES?

Can we afford to live without EES?