NSA response to key length report

[Matt Blaze <mab@research.att.com>]

July 18, 1996

There is currently being circulated, to members of Congress and
possibly elsewhere, a four page document entitled ``Brute-Force
Cryptanalytic Attacks'' that calls into question some of the
conclusions of the ``Minimum Key Lengths for Symmetric Ciphers'' white
paper [1].  The document bears no author or organization attribution,
but we are told that it originated from NSA.

The NSA document argues that ``physical realities'' make parallel key
search much more expensive and time consuming than our white paper
estimated.  However, the NSA document appears to have been written
from the perspective of general parallel processing or cryptanalysis
rather than exhaustive key search per se.  It ignores several
elementary principles of parallel processing that apply specifically
to exhaustive key search machines of the type that our white paper
considered.

In particular, NSA argues that interconnections, heat dissipation,
input/output bandwidth, and interprocessor communication make it
difficult to ``scale up'' a key search machine by dividing the task
among a large number of small components.  While these factors do
limit the scalability of more general purpose multiprocessor computers
(such as those made by Cray), they do not apply at all to specialized
exhaustive key search machines.  The NSA argument ignores the most
fundamental feature of brute-force key search: the processors
performing the search have no need to communicate with other
components of the system while they perform their share of the search,
and therefore the system has no need for any of the global
interconnections that limit scaling.  Indeed, there is no reason that
all the components of a parallel search machine must be located even
within the same city, let alone the same computer housing.  We note
that one of our co-authors (Eric Thompson, of Access Data, Inc.)
designs and builds medium-scale FPGA-based key search machines with
exactly this loosely-coupled structure, and regularly uses them to
recover keys for clients that include the FBI.

The NSA document also calls into question our cost estimates for ASIC
components, suggesting that ASIC chips of this type cost NSA
approximately $1000.00 each.  However, our $10.00 per chip estimate is
based on an actual price quote from a commercial chip fabrication
vendor for a moderate-size order for an exhaustive search ASIC
designed in 1993 by Michael Wiener [2].  Perhaps NSA could reduce its
own costs by changing vendors.

Finally, the NSA report offers estimates of the time required to
perform exhaustive search using a Cray model T3D supercomputer.  This
is a curious choice, for as our report notes, general-purpose
supercomputers of this type make poor (and uneconomical) key search
engines.  However, even the artificially low performance results for
this machine should give little comfort to the users of 56 bit keys.
According to NSA, 56 bit keys can be searched on such a machine in
less than 453 days.  ``Moore's law'' predicts that it will not be long
before relatively inexpensive general-purpose computers offer similar
computational capability.

/s/  Matt Blaze
     Whitfield Diffie

References:

[1] Blaze, M., Diffie, W., Rivest, R., Schneier, B., Shimomura, T.,
    Thompson, E., and Wiener, M.  ``Minimum Key Lengths for Symmetric
    Key Ciphers for Commercial Security.''  January 1996.  Available
    from ftp://ftp.research.att.com/dist/mab/keylength.txt

[2] Wiener, M.  ``Exhaustive DES Key Search.''  Presented at
    Crypto-93, Santa Barbara, CA.  August 1993.

=========================================================================
[Transcription of document circulated to various members of congress
and others in June, 1996, apparently by NSA]

BRUTE-FORCE CRYPTANALYTIC ATTACKS

Two published theoretical estimates of cost versus time to perform
brute-force hardware attacks on selected cryptography key lengths
differ between themselves and differ significantly from what we find
when we buy or build computers to carry out such attacks.

The differences lie in assumptions made in the theoretical estimates,
which are not fully spelled out by the authors, and in scaling up
hypothesized small machines to ever larger ones without accounting for
physical realities.

The factors not accounted for are:

  o R&D costs for the first machine, typically on the order of $10
    million.

  o As more and more chips are added to a machine, two effects occur:

      o Interconnections increase and increase running time;
      o Heat from the chips eventually limit [sic] the size of a
        machine.

  o Memory costs are not included.

  o When get [sic] to the very fast processing speed estimates,
    machines can become Input/Output bound; so [sic] it cannot achieve
    the estimated speed.

  o Assuming every algorithm can be tested in same amount of time and
    key length is the only difference.

Table 1 are [sic] the average time estimates made for a given cost
done by Michael Wiener of Bell Norther Research in 1995.  These are
published in Bruce Schneier's Applied Cryptography book.

Note that these are average times, one-half of the total exhaust time.

Table 2 are [sic] the estimates for total exhaust times using Field
Programmmable Gate Arrays (FPGA) and Application Specific ICs (ASICs)
done for the Business Software Alliance by Blaze, Diffie, Rivest,
Schneier, Shimomura, Thompson, and Wiener in 1996.  In addition to the
above factors not accounted for they have assumed ASICs cost as low as
$10.  We find ASICs more typically cost $1000 and their capabilities
can vary considerably depending upon the specific task.

Table 3 are out estimates based on our experience with a Cray T3D
supercomputer with 1024 nodes.  This machine costs $30 million.

[Tables 1, 2, and 3 not transcribed here.]