The Law Enforcement Access Field

In 1992 AT&T announced a device called the TSD-3600D. It was a box that sat between an ordinary telephone base and its handset, and when it called another one it digitised the conversation at 4,800 bits per second and encrypted it with DES. The two boxes agreed a key between themselves and each displayed a four character hash of it on a small screen, so the two people on the call could read the characters out to each other and know that nobody was sitting in the middle.

It was expensive and it worked. Then the American government found out about it.

The swap

The concern in Washington was that criminals would buy these things and stop being wiretappable. The National Security Agency drew up an alternative encryption scheme in a hurry, and AT&T was persuaded to take the DES out of its product and put the new scheme in.

The new one was the Clipper chip, and its distinguishing feature was that the government could read the traffic. AT&T's cooperation was bought: the government agreed to purchase a large quantity of the new Clipper version, which sold for over a thousand dollars a unit. The original unescrowed models were recalled and disappeared from the market.

This was announced on 16 April 1993, in the standard language. Encryption protects business secrets and personal information, said the White House, and "it also can be used by terrorists, drug dealers, and other criminals". A state of the art microcircuit had been developed by government engineers. A key escrow system would be established "to ensure that the Clipper Chip is used to protect the privacy of law-abiding Americans", with two keys for each device deposited separately in two databases run by the Attorney General. To demonstrate the technology, the statement added, the Attorney General would shortly buy several thousand of the devices.

How it worked

Every Clipper chip carried a cipher called Skipjack, designed by the NSA, using an 80 bit key. Skipjack was classified. It could only ever exist inside tamper-resistant hardware supplied by approved vendors, never in software, and it was reviewed by a small panel of civilian experts under secrecy rather than by the field at large.

Before two chips would talk to each other they exchanged something called the Law Enforcement Access Field. The LEAF carried the chip's serial number and a copy of the session key for that call, encrypted under a unit key unique to that chip and assigned when it was manufactured, along with a sixteen bit checksum, the whole thing then encrypted again under a family key common to all the chips.

So an agency with a warrant did not need to break Skipjack. It intercepted the traffic, pulled the LEAF out of it, collected the two halves of that chip's unit key from the two escrow databases, and decrypted the session key. The design was clean and the argument was coherent: strong encryption for everyone, readable by the state on production of a warrant.

The standard was explicit about the split. FIPS 185 required that the device unique key be composed of two components, each at least eighty bits long, and that each component be independently generated and stored by a separate escrow agent. No single office would hold a whole key. That was the safeguard, and it is a real one as far as it goes: it means the two databases have to be compromised, or subpoenaed, together.

FIPS 185, the Escrowed Encryption Standard, was issued by the Department of Commerce on 9 February 1994 and took effect on 11 March. Use of it was voluntary, which was the answer to the first and most obvious objection and also the reason the scheme could never do what it was for. A criminal buying a telephone was under no obligation to buy that one.

The sixteen bits

The objections arrived immediately, and most of them were about incentives rather than mathematics. Why would a criminal choose a system whose designer has announced in advance that it can read the output? How do you secure a national database of every key ever issued? Why would industry buy expensive hardware encryption at exactly the moment software encryption was becoming cheap? Why trust a cipher nobody outside a secret panel has examined?

Then Matt Blaze, a young researcher at AT&T Bell Laboratories, obtained a prototype card containing the chip and started poking at the protocol rather than the cipher. He circulated the result on 20 August 1994.

The whole scheme depended on the receiving chip refusing to talk unless it was handed a valid LEAF, and the check it performed was the sixteen bit checksum. Sixteen bits is 65,536 possibilities. Blaze found that a rogue device could simply search for a bogus LEAF value that happened to produce the right checksum, in about that many operations, and send it. The receiving chip would accept the call and encrypt it under Skipjack as normal. The government, holding a captured LEAF that decrypted to nothing useful, would be left with strongly encrypted traffic it could not read.

He was careful about the limits. The search took long enough that it was not practical for setting up a live voice call, so the attack did not defeat the system for telephones. For data and store-and-forward traffic, where a delay does not matter, it worked.

The point was not that the escrow could always be evaded. It was that a system built to guarantee government access, designed in secret by the agency with the deepest cryptographic expertise on the planet, had a protocol flaw in it that an outside researcher found within months of getting his hands on a sample. Everything the government was asking the public to accept rested on the claim that this would be done competently.

What was left

Clipper did not survive. The one full product ever built on it was the AT&T telephone, which is to say the only thing the escrowed standard ever shipped inside was a device that had previously worked without it.

In 1998, with the programme abandoned, the NSA declassified and published Skipjack. The cipher that could never be released, that could only exist inside tamper-resistant hardware, that no software could be trusted to implement, went out as a document. It turned out to be a decent cipher. It had never been the problem.

Sources

• The White House, "Statement by the Press Secretary on the Clipper Chip encryption initiative, 16 April 1993" (the announcement of the initiative; the passage on encryption being usable by terrorists, drug dealers and other criminals; the description of the Clipper Chip as a state of the art microcircuit developed by government engineers; the key escrow system with two keys per device deposited in two databases established by the Attorney General; and the undertaking that the Attorney General would purchase several thousand devices).
• National Institute of Standards and Technology, "FIPS PUB 185, Escrowed Encryption Standard" (the standard itself, issued 9 February 1994 by the Department of Commerce, effective 11 March 1994, and voluntary for unclassified government applications).
• Matt Blaze, AT&T Bell Laboratories, "Protocol Failure in the Escrowed Encryption Standard", 20 August 1994 (the structure of the Law Enforcement Access Field containing the chip serial number, the session key encrypted under the unit key and a sixteen bit checksum; the confirmation from experiment that the checksum is sixteen bits and that a brute force search requires about 65,536 operations; the classified status of Skipjack and its restriction to tamper-resistant hardware supplied by approved vendors; and the finding that rogue devices can communicate without transmitting a valid LEAF).
• Matt Blaze, "Key Escrow from a Safe Distance: Looking Back at the Clipper Chip", 2011 (the AT&T TSD-3600D of 1992 with DES, 4,800 bit per second digitised voice, Diffie-Hellman key exchange and the four character hash displayed for detecting a man in the middle; the government's concern and the NSA's hurried design; AT&T being persuaded to replace DES with Clipper and the government agreeing to buy quantities of the replacement at over a thousand dollars each; the recall and disappearance of the unescrowed models; Skipjack's 80 bit key and the Mykotronx manufacture; the objections raised at the time; and the declassification and publication of Skipjack in 1998 after Clipper was abandoned).
• Clinton Presidential Materials Project, "Press release on the Clipper Chip encryption initiative" (the archived White House copy of the same announcement).
• Electronic Privacy Information Center, "The Clipper Chip" (the contemporary documentary archive of the initiative, including the White House statements of April 1993 and February 1994).