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