[Datenschleuder] [55]    Kryptisches...

Kryptisches... To: cypherpunks@toad.com 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 dokument 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 nummer 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 otter 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 ist 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 Ditfie 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 KeySearch." Presented at Crypto-93, Santa Barbara, CA. August 1993, slion.

[Datenschleuder] [55]    Kryptisches...