NSA response to key length report

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.]

It sounds like most of their "counter-arguments" are just stalling tactics.

If you are a lawyer for someone you know is guilty, you still would choose
to find every reason in the book to attack the prosecution's case.  Here we
have precisely the same effect with the NSA.  Any tactical manuveur to keep
stalling the impending collapse of ITAR.

(It is human .. er .. rather .. bureaucrat-esque to claim innocence in the
face of overwhelming evidence of guilt.)

> 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.

Perhaps, in their fit of downsizing, Congress should privatize the NSA?

Ern

Ernest Hua <hua@xenon.chromatic.com> writes:
> 
> It sounds like most of their "counter-arguments" are just stalling tactics.
> 
> If you are a lawyer for someone you know is guilty, you still would choose
> to find every reason in the book to attack the prosecution's case.  Here we
> have precisely the same effect with the NSA.  Any tactical manuveur to keep
> stalling the impending collapse of ITAR.
> 
> (It is human .. er .. rather .. bureaucrat-esque to claim innocence in the
> face of overwhelming evidence of guilt.)

Particularly impressive is that our key length report was hardly
above criticism from several angles, but their rebuttal managed 
somehow to avoid them.

What I find most disturbing about this is that their report was
provided secretly to policymakers in the administration and in
Congress, without independent technical review that would have
quickly exposed the fallacy of the arguments.  I never would have
seen it had several of the recipients not faxed it to me.  This is
the first hard evidence I've seen of NSA providing anything less
than the highest quality technical analysis to other parts of the
government.  A non-specialist reader would be easily misled by the
technically dense, but completely irrelevant, "rebuttal".  It smacks 
of either ill-informed sloppiness, or, perhaps worse, self-serving  
disingenuous cynicism.  Either conclusion is scary, and, to me in
fact, quite surprising.

-matt

> What I find most disturbing about this is that their report was
> provided secretly to policymakers in the administration and in
> Congress, without independent technical review that would have
> quickly exposed the fallacy of the arguments.  I never would have
> seen it had several of the recipients not faxed it to me.  This is

Yes.  This is the bureaucratic slime factor.  It pissed me off when
Freeh lobbied behind the scenes for Digital Telephony.  It pissed me
off when government officials use effectively hidden channels
precisely because they know they cannot get away with it in the full
light of public scrutiny.

Another way B.S.F. shows up is exemplified by gross mistatements
like Gore's recent "emerging consensus" claim.  It's the old "it's
technically true but we know damn well we are effectively lying to
the public" trick.

I am actually kind of surprised that there are some on this list
who might have considered giving Gore the benefit of the doubt.

Ern