High-speed cryptography

Fall 2006 course at the Fields Institute

I'm writing a book called ``High-speed cryptography.'' I'm also teaching a block course on the topic at the Fields Institute in Toronto in Fall 2006.

Why is high-speed cryptography important?

Anyone with access to the Internet can intercept mail messages and web pages and other packets of data to see what they say. He can also send fake messages that look like real messages.

Cryptography protects messages sent through the Internet. Cryptography scrambles and unscrambles packets to protect against forgery and against espionage. An attacker who forges a message won't be able to scramble it in the right way, so when we unscramble it we'll see that it's a forgery and that we should throw it away. An attacker who intercepts a scrambled credit-card number won't be able to figure out the original number.

High-speed cryptography is important for busy network servers. For example, here's a quote from Cricket Liu, author of several books on the Internet's Domain Name System: ``Verifying signed resource records [i.e., performing cryptographic operations] is computationally intensive [i.e., is painfully slow]. This has slowed deployment of DNS security.'' As a practical matter, DNS security still doesn't exist; attackers can seize control over incoming mail and outgoing web pages by forging DNS records. The users need faster software to scramble DNS records.

What does this book cover?

The book focuses on the four fundamental tasks in cryptography:

using a long shared secret to protect a long series of private messages;
expanding a short shared secret into a long shared secret;
sharing a secret through a public conversation; and
using a sender secret, with no shared secrets, to protect a long series of public messages.

For each task, the book explains a state-of-the-art function solving the task, explains what is known and what is believed about the security of the function, explains state-of-the-art methods to compute the function on several common computer architectures, and surveys the alternative functions discussed in the literature.

The book takes the attitude of the practical cryptographer. Security is essential, so unnecessarily risky cryptographic functions are rejected. Speed is often essential, so unnecessarily slow cryptographic functions are rejected. There are many books surveying a broad spectrum of potential cryptographic solutions to the fundamental cryptographic problems; this book highlights the best solutions available, minimizing risk while maximizing speed.

What do readers need to know before reading this book?

Readers are expected to have some experience with algorithm analysis (figuring out why a computer hasn't finished a computation yet) and algorithm improvement (making the computer finish the computation more quickly). A typical reader will have studied some chapters of a textbook by Cormen, Leiserson, Rivest, and Stein; will have heard that heapsort ``takes time n log n times, um, some constant''; and will have seen many algorithm improvements incorrectly described as ``optimizations.''

The most obvious difference in flavor between this book and a typical algorithms book is that this book pays attention to constants. For example, this book explains how a state-of-the-art function takes half a millisecond on my laptop to compute a high-security shared secret from a public conversation. Ignoring constant factors would remove all content from this statement.

Of course, these constants depend on the choice of computer. Sometimes one computer takes 10 clock cycles for an operation while another computer takes just 1 clock cycle; this affects the time for any algorithm built on top of that operation. Readers might have seen some computer-dependent algorithm analysis and algorithm improvement in books on architecture, assembly language, ``optimizing'' compilers, supercomputing, etc. None of those topics are prerequisites; this book includes a detailed introduction to the speed of real computers.

Many higher-level speedups are also constant-factor speedups. In fact, most of the speedups in the algorithms literature are constant-factor speedups. However, readers are not presumed to have any previous experience handling constant factors in algorithm analysis.

The other obvious difference in flavor between this book and typical books is the choice of functions being computed. A typical book spends time on sorting, for example, and on various graph operations such as shortest paths. This book instead focuses on a few critical cryptographic operations. Those operations rely on some mathematics that readers might have seen in other books on algebra, number theory, or cryptography. None of those are prerequisites; this book includes an introduction to the relevant mathematics.

In more detail, what does the book cover?

From a cryptographer's perspective, here are the main topics of the book (linked here to more than 200 pages already available in the form of papers):

Using a long shared secret to protect a long series of private messages: Wegman-Carter authentication, specifically univariate polynomial-evaluation MACs, specifically Poly1305, combined with additive stream encryption. More broadly, includes a structural framework for MAC constructions and a complete security proof from the permutation/function switching perspective.
Expanding a short shared secret into a long shared secret: parallelized stream generation, specifically block hashing by constant-time operations, specifically Salsa20, with additional material on Bolero20. Includes extensive discussion of massively parallel multiple-target brute-force attacks, cache-timing attacks on AES, and what went wrong with MD5 and SHA-1.
Sharing a secret through a public conversation: the Diffie-Hellman system, specifically elliptic-curve Diffie-Hellman, specifically Curve25519. Includes extensive discussion of Pippenger's exponentiation algorithm, Montgomery's exponentiation algorithms, square-root computation, etc.
Using a sender secret, with no shared secrets, to protect a long series of public messages: public-key signatures, specifically RSA-Rabin-Williams public-key signatures, specifically Square2048. Includes verification speedups, the latest signature-compression and key-compression techniques, a complete security proof against generic attacks, and discussion of the difficulty of integer factorization.

At a lower level, the book contains extensive coverage of computer architecture and microarchitecture, new programming tools aimed at high-speed computations, and many specific speedups, with special attention paid to floating-point arithmetic. This material is of interest outside cryptography in applications ranging from video games to weather simulation.

Are any similar books already available?

I like Practical Cryptography, by Ferguson and Schneier. This book does a great job of explaining how to select low-risk cryptographic functions. But it doesn't pay much attention to speed; it doesn't explain how careful design and implementation of cryptographic functions can improve performance by a factor of ten or more.