Special-Purpose Cryptanalytic Devices — an annotated taxonomy

To achieve secure cryptographic functionality such as encryption, signature or authentication, one must rely on computational problems that are presumed to be hard for the adversary. Alas, we know of no appropriate problems that are provably hard, and moreover one usually cannot know the all resources and machinations available to his adversaries. Thus, we end up making various assumptions about the power of the adversary and the way he can use this power to attack the computational challenge. One of the ways in which these assumptions may fail in practice (thereby compromising the practical security of the cryptosystem) is when the attacker employs unexpected computational devices tailored for the specific task. Such devices carry a couple of advantages for the attacker: first, they can be significantly more cost-effective than general-purpose computational devices (let alone manual labor!) due to reduced overheads; and second, they may employ more efficient algorithms made possible by the flexibility of their physical construction. Special-purpose devices are not a magic solution that will crack every problem, but often reduce costs by several orders of magnitude compared to more traditional alternatives — which may make the difference between an infeasible problem and one that is well within reach.

Over time various special-purpose cryptanalytic devices have been proposed and constructed, often with devastation results for the security of the cryptosystem being attacked.This page catalogs various such devices that have appeared in the open literature, classified by purpose. The list is not exhaustive, and neither are the references; comments and additions are very welcome.

Integer Factorization

Sieving (modern)

  • TWINKLE ("The Weizmann Institute Key Locating Engine")
    First modern sieving device. Never built. Uses non-conventional electro-optical components for analog summation. Not attractive for large (≥768 bit) integers, due to need for large number of support PCs.
    • Adi Shamir, Factoring large numbers with the TWINKLE device, Cryptographic Hardware and Embedded Systems (CHES) 1999, LNCS 1717, 2-12, Springer, 1999.[SpringerLink](non-free) [pdf]
      Original proposal, in the context of the Quadratic Sieve.
    • Arjen K. Lenstra, Adi Shamir, Analysis and optimization of the TWINKLE factoring Device, proc. Eurocrypt 2000, LNCS 1807, 35--52, Springer, 2000. [SpringerLink](non-free)
      Analysis for the Number Field Sieve with 512-bit and 768-bit composites and lattice sieving. Design optimizations and variants.
  • Mesh-based sieving
    A class of highly-parallel electronic sieving devices based on mesh sorting or routing. Adapt ideas of D. J. Bernstein from the NFS linear algebra (see below) to sieving. Never built. Feasible cost for 1024-bit composites.
    • Willi Geiselmann, Rainer Steinwandt, A dedicated sieving hardware, proc. Public Key Cryptography (PKC) 2003, LNCS 2567, 254-266, Springer, 2003. [SpringerLink](non-free)
      Original proposal. Never built.
    • Willi Geiselmann, Rainer Steinwandt,Yet another sieving device, proc. CT-RSA 2004, LNCS 2964,  278--291, Springer, 2004. [pdf](extended version)
      Extensive optimization and analysis for 768-bit composites. Never built.
  • Pipelined sieving
    A class of highly-parallel electronic sieving devices based on (essentially) unidirectional information flows and processing.
    • TWIRL ("The Weizmann Institute Relation Locator")
      Highly-parallel electronic sieving device. Never built. Uses a pipelined architecture different from mesh-based sieving, with a lower cost. Never built. Feasible cost for 1024-bit composites.
      • Adi Shamir, Eran Tromer, Factoring large numbers with the TWIRL device, proc. Crypto 2003, LNCS 2729, 1-26, Springer, 2003. [pdf]
        Original proposal.
      • Arjen K. Lenstra, Eran Tromer, Adi Shamir, Wil Kortsmit, Bruce Dodson, James Hughes, Paul Leyland, Factoring estimates for a 1024-bit RSA modulus, proc. Asiacrypt 2003, Springer, LNCS 2894, 331--346, Springer, 2003 [pdf]
        Analysis of Number Field Sieve parameters used in original proposal, and of cost with more recent (90nm) chip manufacturing technology.
      • Adi Shamir, Eran Tromer, On the cost of factoring RSA-1024, RSA CryptoBytes, vol. 6 no. 2, 10-19, 2003 [pdf]
        Abridged and more accessible version of the original proposal.
    • Willi Geiselmann, Rainer Steinwandt, Non-Wafer-Scale Sieving Hardware for the NFS: Another Attempt to Cope with 1024-bit, proc. EUROCRYPT 2007, LNCS 4515, 466-481, Springer, 2007. [SpringerLink](non-free) [slides (pdf)]
      Removes the need for full-wafer circuits, in favor of a network of smaller chips (at a silicon cost increase of x2.5-3). Never built.
    • CAIRN 2
      Tetsuya Izu,, Jun Kogure, Takeshi Shimoyama, CAIRN 2: An FPGA Implementation of the Sieving Step in the Number Field Sieve Method , proc. Cryptographic Hardware and Embedded Systems (CHES) 2007, LNCS 4727, 364-377, Springer, 2007. [SpringerLink](non-free)
      FPGA implementation following a similar approach. Built and used to perform the sieving for a 423-bit Special Number Field Sieve instance in 30 days. Claims scalability up to 768-bit composites (in terms of memory requirements), though performance is not analyzed.
  • SHARK
    Highly-parallel electronic sieving device. Differs from TWIRL in its use of a butterfly routing network, use of standard-sized chips, and being tailored for special-q sieving. Cost evaluated for 1024-bit composites. The predicted cost is higher than TWIRL's ($200M vs. $1.1M for 1024-bit composites in 1 year), but the technological challenges differ.
    • Jens Franke, Thorsten Kleinjung, Christof Paar, Jan Pelzl, Christine Priplata, Colin Stahlke, SHARK — a realizable special hardware sieving device for factoring 1024-bit integers, proc. Workshop on Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS) 2005, February 2005. [paper (pdf)] [slides (pdf)]
The following survey paper covers some of the above (namely TWINKLE, mesh-based sieving and TWIRL), and provides context and comparative analysis.

Sieving (historical)

The sieving task used in number-theoretical algorithms (ranging from Eratosthenes's algorithm to finding prime to the Number Field Sieve) has a very regular structure, which can be exploited by automated mechanical or electronic means. During the last century, various such devices and been devised and built. These first such devices were used for factorization using Fermat's method, where the goal of sieving is to identify squares in an arithmetic progression by testing quadratic residuosity modulo various small primes. Later, similar sieving tasks arose in newer factoring algorithms such Continued Fraction and the Quadratic Sieve. These devices all predate the Number Field Sieve, but in principle they could be applied to it as well. In the following, we briefly survey various documented special-purpose sieving devices which are of historical interest. 
  • Employing mechanical devices for the sieving task was apparently first proposed by Frederick William Lawrence in 1896.
    • Frederick William Lawrence, Factorisation of numbers, Quarterly Journal of Pure and Applied Mathematics, vol. 28, 285--311, 1896
  • In 1912, following the publication of a French translation of the above, three prototype devices were independently built by André Gérardi (the translator), Maurice Kraitchik, and by Pierre and Eugène Olivier Carissan. These three devices were rough prototypes that relied on a human observer and suffered from mechanical difficulties.
    • Jeffrey Shallit, Hugh C. Williams, François Morain, Discovery of a lost factoring machine, The Mathematical Intelligencer, vol. 17 no. 3, 41-47, 1995. [web page] [slides (ps)]
  • Machine á Congruences
    This device, built by Eugène Olivier Carissan in 1919 as an improvement upon his brother's earlier design, is the first known sieving machine that operated successfully. It consists of 14 concentric brass rings, and employs electrical switches to identify events corresponding to (likely) squares in the Fermat method. It presently resides at the Conservatoire Nationale des Arts Métiers, Paris.
    • Jeffrey Shallit, Hugh C. Williams, François Morain, Discovery of a lost factoring machine, The Mathematical Intelligencer, vol. 17 no. 3, 41-47, 1995. [web page] [slides (ps)]
  • Lehmer's mechanical sieves
    In the 1920's and 1930's, D. N. Lehmer and D. H. Lehmer built several mechanical sieving devices, employing various approaches: bicycle chains (1926, replica at the Computer History Museum), gears and photoelectric detectors (1932, presently at the Computer History Museum) and movie films (1936). In the 1970's, D. H. Lehmer also built electronic sieving devices using delay lines and shift registers (1970's).
    • D. N. Lehmer, Hunting big game in the theory of numbers, Scripta Mathematica I, 229-235, September 1932. [html]
    • D. H. Lehmer, A photo-electric number sieve, American Mathematical Monthly, vol. 40, 401-406, 1933
    • D. H. Lehmer, The mechanical combination of linear forms, The American Mathematical Monthly, vol. 35, 114--121, 1928. [html]
    • Michael R. Williams, Lehmer Sieves, in Ed Thelen, Facts and stories about Antique (lonesome) Computers. [html]
    • Ed Thelen, Lehmer Factoring Machines, in Ed Thelen, Facts and stories about Antique (lonesome) Computers. [web site]
  • Extended Precision Operand Computer, AKA "Georgia Cracker"
    This is a 128-bit, highly parallel special-purpose computer for factoring using the Continued Fraction method, built by Jeffrey Smith and Samuel Wagstaff in 1982-3 (presently held by Jeffrey Smith).
    • Jeffrey W. Smith, Samuel S. Wagstaff, Jr., An extended precision operand computer, proc. 21st Southeast Region. ACM Conference, 209-216, 1983
    • Carl Pomerance, Jeffrey W. Smith, Samuel S. Wagstaff, Jr., New ideas for factoring large integers, proc. CRYPTO'83, Plenum Press,  81--85, 1984
  • "A High Performance Factoring Machine"
    This is a 256-bit general-purpose computer designed by W. Rudd, D. A. Buell and D. M. Chiarull. It was to perform factorization 10 times faster than existing general-purpose computers, with a low construction cost.
    • W. G. Rudd, Duncan A. Buell, Donald M. Chiarulli, A high performance factoring machine, proc. 11th International Conference on Computer Architecture, 297-300, ACM, 1983.
  • Quasimodo ("quadratic sieve motor")
    This device, designed by C. Pomerance, J. W. Smith and R. Tuler, was built but never functioned properly and was superceded by the arrival of efficient general-purpose computers. It has been dismantled and its current whereabouts are unknown.
    • Carl Pomerance, Jeffrey W. Smith, Randy Tuler, A pipeline architecture for factoring large integers with the quadratic sieve algorithm, SIAM Journal on Computing, vol. 17, 387-403, 1988. [pdf](non-free)
    • Carl Pomerance, A Tale of Two Sieves, Notices of the AMS, 1473-1485, 1996 [pdf]

Linear Algebra Step of the Number Field Sieve

  • Mesh-based
    • Daniel J. Bernstein, Circuits for Integer Factorization: a Proposal, manuscript, 2001. [pdf]
      Observed that the NFS linear algebra step has a huge input that is accessed repeatedly. When implemented on traditional computers, very few (often one) processors are accessing that huge input, which is inherently inefficient -- at any moment, most of the storage is idle. Also makes related observations on the NFS sieving step (see above). Proposed an implementation using mesh sorting, which reduces the asymptotic cost. Design given on a abstract level; subsequent analysis (see below) shows that a naive implementation would have prohibitive cost for 1024-bit composites.
    • Arjen K. Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer, Analysis of Bernstein's factorization circuit, proc. Asiacrypt 2002, LNCS 2501, 1-26, Springer, 2002. [pdf]
      Analyzed the above paper by Bernstein, asymptotically and concretely. Proposed an alternative concrete design that improves efficiency by various algorithmic and technological means. High-level parallel, wafer-scale electronic device consisting of an array of cells, executing mesh routing. Feasible cost, but technologically challenging, for 1024-bit composites. A variant prototyped on FPGA (see below).
    • Willi Geiselmann, Rainer Steinwandt, Hardware to solve sparse systems of linear equations over GF(2), Cryptographic Hardware and Embedded Systems (CHES) 2003, LNCS 2779, 51--61, Springer, 2003. [SpringerLink]
      Improves the above by adding splitting into smaller and semi-independent chips. This variant was prototyped on FPGA:
      • Sashisu Bajracharya, Deapesh Misra, Kris Gaj, Tarek El-Ghazawi, Reconfigurable hardware implementation of mesh routing in number field sieve factorization Field Programmable Technology (FPT) 2004, December 2004. [pdf]
      • Sashisu Bajracharya, Deapesh Misra, Kris Gaj, Tarek El-Ghazawi, Reconfigurable hardware implementation of mesh routing in number field sieve factorization Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS) 2005, February 2005. [extended abstract (pdf)] [slides (pdf)]
        (Revision of the earlier paper above.)
    • Willi Geiselmann, Hubert Köpfer, Rainer Steinwandt, Eran Tromer, Improved routing-based linear algebra for the Number Field Sieve, proc. International Conference on Information Technology (ITCC) 2005, to appear. [pdf] 
      Points out, and resolve heuristically, pathological cases in the routing algorithm used by the two devices above. Suggest some improvements. Never built, but similar to the above FPGA prototype.
  • Pipelined
    • Willi Geiselmann, Adi Shamir, Rainer Steinwandt, Eran Tromer, Scalable Hardware for Sparse Systems of Linear Equations, with Applications to Integer Factorization, preliminary version, March 2005. [pdf]
      Highly-parallel electronic device, based on a pipelined architecture (reminiscent of the TWIRL sieving device). More efficient than the above mesh-based devices, and more technologically feasible due to smaller chips and better scalability. Feasible cost for 1024-bit composites. Never built.

Elliptic Curve Method

The ECM factoring algorithm can be used as a stand-alone factoring algorithm, but for factoring large RSA composites it is of interest mainly as a component in the relation collection step of the Number Field Sieve. In the latter, there is a trade-off between the amount of sieving (discussed above) and the amount of subseqent ECM-based smoothness testing; most past proposals chose parameters that make the cost of the smoothness testing negligible compared to that of the sieving, but this is suboptimal asymptotically and probably also concretely (if special-purpose hardware are used for both). The latter point is argued in the following:
  • Dan Bernstein, Factorization myths, talk at Algorithmic Number Theory Symposium (ANTS) VI, June 2004. [slides and transcript]
Proposed special-purpose ECM devices:
  • Richard P. Brent, Factorization of the tenth and eleventh Fermat numbers, Report TR-CS-96-02, Computer Sciences Laboratory, Australian National University, Canberra, 1996. [paper (dvi.gz)]
    This is mostly a conventional PC-based implementation of the Number Field Sieve, but uses the Dubner Cruncher digital signal processing accelerator (an ISA card) for fast large integer multiplication.
  • Jens Franke, Thorsten Kleinjung, Christof Paar, Jan Pelzl, Christine Priplata, Martin Šimka, Colin Stahlke, An efficient hardware architecture for factoring integers with the Elliptic Curve Method, proc.  Workshop on Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS) 2005, February 2005. [paper (pdf)] [slides (pdf)]
    A compact hardware design for the ECM algorithm, allowing highly parallel implementations. Implemented on FPGA+microcontroller, and cost of an ASIC implementationis estimated. Application to Number Field Sieve (and specifically, the SHARK device above) is discussed.
  • Giacomo de Meulenaer, François Gosset, Guerric Meurice de Dormale, Jean-Jacques Quisquater, Integer Factorization Based on Elliptic Curve Method: Towards Better Exploitation of Reconfigurable Hardware, IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM07), 197--207, IEEE Computer Society Press, 2007 [IEEExplore](non-free)
Beyond these direct works, there is also extensive literature about efficient hardware implementation of elliptic curve arithematic, and much of it is applicable also in the cryptanalytic context of factoring via ECM.

Exhaustive Key Search

  • Hypothetical DES cracking via custom ASICs
    • Michael J. Wiener, Efficient DES Key Search, presented at the rump session of Crypto '93, reprinted in Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, pp. 31-79, 1996 [on-line]
    • Michael J. Wiener, Efficient DES Key Search — an update, CryptoBytes, vol. 3 no. 2, 6-8, RSA Laboratories [on-line]
    A design for US$1M machine that would break a DES key in 3.5 hours (as of 1993) or 35 minutes (as of 1997) on average.
  • M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson, M. Weiner, Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security — A Report by an Ad Hoc Group of Cryptographers and Computer Scientists, 1996 [on-line]
    Cost estimate exhaustive search for custom ASIC-based devices, FPGA-based devices, and distributed computing.
  • DES Cracker
    Electronic Frontier Foundation, Cracking DES, O'Reilly, 1998 [on-line] [web site] [sourcecode]
    Broke 56-bit DES keys in a few days by exhaustive search using 36,864 custom-produced ASIC chips. Built by the Electronic Frontier Foundation in 1998 for under US$ 250K.

World War II Ciphers

Today special-purpose cryptanalytic devices are an exotic and often-ignored possibility, but in the dawn of computing, computational resources were so limited that special-purpose devices were the only feasible way to carry out useful tasks. One may even say that these devices were the dawn of computing, in the sense of providing motivation and experience for the subsequent construction of general-purpose computers. Several such devices were built and fruitfully employed by the Allies during the 2nd World War:
  • Bomba
    [Wikipedia]
    Electro-mechanical computers for breaking the German cipher Enigma. Built by Polish General Staff's Cipher Bureau in 1938 and successfully broke encryptions employing the basic variant of Enigma.
  • Bombe
    Donald Davies, The Bombe — a Remarkable Logic Machine, Cryptologia, vol. 23 no. 2, 108-138, April 1999 [online]
    [Wikipedia] [Jerry Proc]
    Electro-mechanical computers for breaking advanced variants of the German cipher Enigma. Built by the British Government Codes & Ciphers School at Bletchley Park (via British Tabulating Machine Company) during 1940-1945. Over Over 200 such machines were built and and operated with great success.
  • Heath Robinson and Colossus
    Tony Sale, Lorenz ciphers and the Colossus [web site]
    [Wikipedia]
    Electro-mechanical computers for breaking the German cipher Lorenz. Built by the British Government Codes & Ciphers School at Bletchley Park (via the British Post Office's research center) circa 1943. Overall 10 such machines were built and operated with great success. Rebuilt from 1994 by Tony Sale and the Colossus Team.

This list is not exhaustive, and neither are the references; comments and additions are very welcome.
Acknowledgments. In the description of the historical sieving devices, I have made extensive use of material composed by Arjen K. Lenstra and Jeffrey Shallit. All errors are, of course, my own.