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)

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. 

Linear Algebra Step of the Number Field Sieve

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: Proposed special-purpose ECM devices: 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

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:

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.

— Eran Tromer