Subject: NIST Response to Blaze Attack on Clipper

From: [email-masked]
Date: Thu, 16 Jun 1994 17:29:40 -0400 (EDT)

Note: The following material was released by NIST in response to recent
articles regarding AT&T/Matt Blaze and the key escrow chip.  A second more
technical response follows.

                    -------------------------
June 2, 1994
Contact:  Anne Enright Shepherd
(301) 975-4858

The draft paper by Matt Blaze* describes several techniques aimed at
circumventing law enforcement access to key escrowed encryption products based
on government-developed technologies.

As Blaze himself points out, these techniques deal only with the
law-enforcement feature, and in no way reduce the key escrow chips' inherent
security and data privacy.

     --   "None of the methods given here permit an attacker to
          discover the contents of encrypted traffic or
          compromise the integrity of signed messages.  Nothing
          here affects the strength of the system from the point
          of view of the communicating parties...." p. 7.

Furthermore, Blaze notes that the techniques he is suggesting are
of limited use in real-world voice applications.

     --   "28 minutes obviously adds too much latency to the
          setup time for real-time applications such as secure
          telephone calls." p. 7.

     --   "The techniques used to implement them do carry enough
          of a performance penalty, however, to limit their
          usefulness in real-time voice telephony, which is
          perhaps the government's richest source of wiretap-
          based intelligence." p. 8.

Anyone interested in circumventing law enforcement access would most likely
choose simpler alternatives (e.g., use other nonescrowed devices, or super
encryption by a second device).  More difficult and time-consuming efforts,
like those discussed in the Blaze paper, merit continued government review --
but they are very unlikely to be employed in actual communications.

All sound cryptographic designs and products consider trade-offs among design
complexity, costs, time and risks.  Voluntary key escrow technology is no
exception.  Government researchers recognized and accepted that the law
enforcement access feature could be nullified, but only if the user was
willing to invest substantial time and trouble, as the Blaze report points
out.  Clearly, the government's basic design objective for key escrow
technology was met: to provide users with very secure communications that will
still enable law enforcement agencies to benefit from lawfully authorized
wiretaps.  It is still the only such technology available today.

Today, most Americans using telephones, fax machines, and cellular phones have
minimal privacy protection.  The key escrow technology -- which is available
on a strictly voluntary basis to the private sector -- will provide the
security and privacy that Americans want and need.

*    Statements from "Protocol Failure in the Escrowed Encryption
     Standard," May 20 draft report by Matt Blaze, AT&T Bell
     Laboratories
                              -----

Note: The following provides additional technical material in response to
questions regarding a recent paper by Matt Blaze on key escrow encryption.

        --------------------------------------
                              
Technical Fact Sheet on Blaze Report and Key Escrow Encryption

     Several recent newspaper articles have brought attention to a report
prepared by Dr. Matthew Blaze, a researcher at AT&T's Bell Labs. These
articles characterize a particular finding in Blaze's report as a ~flaw~ in
the U.S. government's key escrow encryption technology. None of the findings
in Dr. Blaze's paper in any way undermines the security and privacy provided
by the escrow encryption devices.

     The finding which has received the most publicity could allow a
non-compliant or ~rogue~ application to send messages to compliant or
~non-rogue~ users which will not be accessible by law enforcement officials
through the escrowed encryption standard field called the Law Enforcement
Access Field (LEAF).

     Dr. Blaze's approach uses the openly disclosed fact that the LEAF
contains 16-bit checkword to prevent rogue users from modifying the law
enforcement access mechanism. This 16-bit checkword is part of the 128-bit
LEAF, which also includes the enciphered traffic key and the unique chip
identifier.
 
     Dr. Blaze's method is to randomly generate different 128-bit LEAFs until
he gets one that passes the checkword. It will take on average 216, or 65,536
tries.  This is not a formidable task; it could be done in less than an hour.
Dr. Blaze questions the adequacy of a 16-bit checkword and suggests using a
larger one, to ensure that the exhaustion attack would be so time consuming as
to be impractical.
 
     The chip designers recognized the strengths and limitations of a 16-bit
checkword. Following are the reasons why they chose to use a checkword of only
16 bits:

* There were four fundamental considerations that the designers considered in
choosing the LEAF parameters.

These were:

(1) ease of access by authorized law enforcement agencies, 

(2) impact on communications, 

(3) a sufficiently large identifier field which would not constrain
manufacturers, and

(4) the difficulty required to invalidate the LEAF mechanism by techniques
such as those described by Dr. Blaze.

* The purpose of the LEAF is to preserve law enforcement's ability to access
communications in real-time. The encrypted traffic key, which enables them to
do this, is 80 bits long. In addition to this 80-bit field, the LEAF must
contain the unique identification number of the key escrow encryption chip
doing the encryption.

* The size of the identifier field was the subject of considerable
deliberation.  In the earliest considerations it was only 25 bits long. The
chip designers recognized that 25 bits did not offer enough flexibility to
provide for multiple manufacturers of key escrow devices. Different chip
manufacturers would need manufacturer identifiers as well as their own chip
identifiers to ensure that identifiers are unique. Eventually, the designers
agreed that 32 bits would adequately meet this requirement.

* In many environments, error-free delivery of data is not guaranteed, and
there is considerable concern by communication engineers that requiring
error-free transmission of a fixed field (the LEAF) could make the encryption
device difficult to use. In early discussions with industry, they were opposed
to any checkword.  In the end, they agreed it would be acceptable if the size
of the LEAF was restricted to 128 bits. This left 16 bits for a checkword to
inhibit bypassing the LEAF. While recognizing the possibility of exhausting
these 16 bits, the designers concluded that 16 bits are adequate for the first
intended application. Security enhancements are being made for other
applications, such as the TESSERA card.

Note that computations are required to search for a matching checkword, which
then has to be properly substituted into the communications protocol. The
performance and cost penalties of the search operation are significant for
telephone, radio, and other such applications, thus providing adequate
protection against this technique for bypassing the LEAF.

In summary:

* Although this technique would allow one to bypass the LEAF, the security
provided by the escrow encryption devices would not be altered. Users'
information would still be protected by the full strength of the encryption
algorithm.

* Dr. Blaze was accurate in noting that these attacks are of limited
effectiveness in real-time telephony.

* When designing the key escrow chip, NSA emphasized sound security and
privacy, along with user friendliness. The attacks described by Dr. Blaze were
fully understood at the time of initial chip design. The use of 16 bits for
the checkword was an appropriate choice in view of the constraints of a
128-bit LEAF.  It provides excellent security for real-time telephone
applications with high assurance that law enforcement's interests are
protected.

* Dr. Blaze's research was done using prototype TESSERA cards.  As part of the
family of planned releases/upgrades, NSA already has incorporated additional
security safeguards into the production TESSERA cards to protect against the
kinds of attacks described by Dr. Blaze.