Message-ID: <2.2.32.19960718184201.0070667c@linc.cis.upenn.edu> Date: Thu, 18 Jul 1996 12:04:27 -0400 From: 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.]