Subject: THE CLIPPER CHIP: A TECHNICAL SUMMARY

From: [email-masked]
Date: 19 Apr 93 18:23:27 -0400

The following document summarizes the Clipper Chip, how it is used,
how programming of the chip is coupled to key generation and the
escrow process, and how law enforcement decrypts communications.
Since there has been some speculation on this news group about my
own involvement in this project, I'd like to add that I was not in
any way involved.  I found out about it when the FBI briefed me on
Thursday evening, April 15.  Since then I have spent considerable
time talking with the NSA and FBI to learn more about this, and I
attended the NIST briefing at the Department of Commerce on April 16.  
The document below is the result of that effort. 

Dorothy Denning
---------------

                     THE CLIPPER CHIP: A TECHNICAL SUMMARY

                               Dorothy Denning

                                April 19, 1993

INTRODUCTION

On April 16, the President announced a new initiative that will bring
together the Federal Government and industry in a voluntary program
to provide secure communications while meeting the legitimate needs of
law enforcement.  At the heart of the plan is a new tamper-proof encryption
chip called the "Clipper Chip" together with a split-key approach to
escrowing keys.  Two escrow agencies are used, and the key parts from
both are needed to reconstruct a key.

CHIP STRUCTURE

The Clipper Chip contains a classified 64-bit block encryption
algorithm called "Skipjack."  The algorithm uses 80 bit keys (compared
with 56 for the DES) and has 32 rounds of scrambling (compared with 16
for the DES).  It supports all 4 DES modes of operation.  Throughput is
16 Mbits a second.

Each chip includes the following components:

   the Skipjack encryption algorithm
   F, an 80-bit family key that is common to all chips
   N, a 30-bit serial number
   U, an 80-bit secret key that unlocks all messages encrypted with the chip

ENCRYPTING WITH THE CHIP

To see how the chip is used, imagine that it is embedded in the AT&T
telephone security device (as it will be).  Suppose I call someone and
we both have such a device.  After pushing a button to start a secure
conversation, my security device will negotiate a session key K with
the device at the other end (in general, any method of key exchange can
be used).  The key K and message stream M (i.e., digitized voice) are then
fed into the Clipper Chip to produce two values:

   E[M; K], the encrypted message stream, and 
   E[E[K; U] + N; F], a law enforcement block.  

The law enforcement block thus contains the session key K encrypted
under the unit key U concatenated with the serial number N, all
encrypted under the family key F.

CHIP PROGRAMMING AND ESCROW

All Clipper Chips are programmed inside a SCIF (secure computer
information facility), which is essentially a vault.  The SCIF contains
a laptop computer and equipment to program the chips.  About 300 chips
are programmed during a single session.  The SCIF is located at
Mikotronx.

At the beginning of a session, a trusted agent from each of the two key
escrow agencies enters the vault.  Agent 1 enters an 80-bit value S1
into the laptop and agent 2 enters an 80-bit value S2. These values
serve as seeds to generate keys for a sequence of serial numbers.

To generate the unit key for a serial number N, the 30-bit value N is
first padded with a fixed 34-bit block to produce a 64-bit block N1.
S1 and S2 are then used as keys to triple-encrypt N1, producing a
64-bit block R1:

        R1 = E[D[E[N1; S1]; S2]; S1] .

Similarly, N is padded with two other 34-bit blocks to produce N2 and
N3, and two additional 64-bit blocks R2 and R3 are computed:  

        R2 = E[D[E[N2; S1]; S2]; S1] 
        R3 = E[D[E[N3; S1]; S2]; S1] .

R1, R2, and R3 are then concatenated together, giving 192 bits. The
first 80 bits are assigned to U1 and the second 80 bits to U2.  The
rest are discarded.  The unit key U is the XOR of U1 and U2.  U1 and U2
are the key parts that are separately escrowed with the two escrow
agencies.

As a sequence of values for U1, U2, and U are generated, they are
written onto three separate floppy disks.  The first disk contains a
file for each serial number that contains the corresponding key part
U1.  The second disk is similar but contains the U2 values.  The third
disk contains the unit keys U.  Agent 1 takes the first disk and agent
2 takes the second disk.  The third disk is used to program the chips.
After the chips are programmed, all information is discarded from the
vault and the agents leave.  The laptop may be destroyed for additional
assurance that no information is left behind.
 
The protocol may be changed slightly so that four people are in the
room instead of two.  The first two would provide the seeds S1 and S2,
and the second two (the escrow agents) would take the disks back to
the escrow agencies.

The escrow agencies have as yet to be determined, but they will not
be the NSA, CIA, FBI, or any other law enforcement agency.  One or
both may be independent from the government.

LAW ENFORCEMENT USE

When law enforcement has been authorized to tap an encrypted line, they
will first take the warrant to the service provider in order to get
access to the communications line.  Let us assume that the tap is in
place and that they have determined that the line is encrypted with
Clipper.  They will first decrypt the law enforcement block with the
family key F.  This gives them E[K; U] + N.  They will then take a
warrant identifying the chip serial number N to each of the key escrow
agents and get back U1 and U2.  U1 and U2 are XORed together to produce
the unit key U, and E[K; U] is decrypted to get the session key K.
Finally the message stream is decrypted.  All this will be accomplished
through a special black box decoder operated by the FBI.

ACKNOWLEDGMENT AND DISTRIBUTION NOTICE.  All information is based on
information provided by NSA, NIST, and the FBI.  Permission to
distribute this document is granted.

---

From: [email-masked] (Perry E. Metzger)
Date: Tue, 20 Apr 1993 11:54:02 GMT

[email-masked] (Vidkun Abraham Lauritz Quisling) writes:

Hmmm. A thirty bit serial number. And, we are told, the unit key U is
derived deterministically from this serial number. That means that
there are only one billion possible unit keys.

Hmmm. We must assume that generating the unit key U from the serial
number N rather than generating it from a randomly selected U1 and U2
is an intentional way of assuring a "fail safe" for the government --
U is completedly determined given S1, S2 and N. If S1 and S2 do not
change they constitute effective "master keys" (along with F), the
theft of which (or the possession of which by various authorities)
completely obviates the security of the system. However, more
interestingly, we know, for a fact that if S1 and S2 are fixed no
matter what the keyspace for U is no more than 2^30. Why not pick U1
and U2 at random? Why this interesting restriction of they key space
if it NOT to provide an additional back door?

I find it disturbing that at the very best my security is dependant on
approximately 30 bytes worth of information that could be written on
the back of a napkin.

Even if S1 and S2 change periodically, the rationale behind this
restriction in the size of the keyspace seems strange if one is
assuming that the goal is security -- and makes perfect sense if the
goal is an illusion of security.

If S1 and S2 do not change, even if they remain secret I wonder if
they can somehow be back-derived given enough unit key/serial number
pairs. We are assured that this cannot happen -- but no one
understands how Skipjack works outside of government officials and,
soon, foreign intelligence services that gain the information via
espionage. Presumably we will eventually have the information as well
-- reverse engineering gets more and more advanced every year -- but
by the time we know it may be too late.

None of this makes me feel the least bit secure. The silly notion of
"destroying the laptop" appears to be yet another bizarre distraction.
We all know that you can't read data from DRAM that has been turned
off for more than a few moments. On the other hand, what we don't know
is why there is a need to generate the unit keys from S1 and S2 in the
first place other than to weaken the system. We don't know if the
agents in question would resist a million in cash a piece for their
information -- its probably worth hundreds of million, so you can make
the bribe arbitrarily hard to resist. And to tell you the truth, doing
this in a "vault" rather than in Joe Random Tempest-shielded Room
with a laptop computer seems like melodrama designed to make
high-school dropouts from Peoria impressed -- but it does very little
for most of the rest of us.

What would this provide? Lets say the escrow agencies are the ACLU and
the NRA and their agents personally take back the disks and are always
honest. Who cares? The NSA must be laughing out loud, because they
have the algorithm to regenerate U given N and likely don't need to
steal they keys as they effectively already have them.

--
Perry Metzger		[email-masked]
--
Laissez faire, laissez passer. Le monde va de lui meme.