Serious Cryptography: A Practical Introduction to Modern Encryption

by Jean-Philippe Aumasson
No Starch Press, 2018, 282 pages
reviewed by T. Nelson

kay, this is serious stuff. No jokes today.

In ancient times, certain numbers, such as 7 and 666, were thought to have magical powers. Nowadays we carry on that same tradition, but with much longer numbers like 36567232109354321 and 486662. Clearly our civilization has advanced by a factor of at least 730.7.

The main property of these big magical numbers is that they're hard to factor, so factoring big numbers has become the basis for much of modern crypto­graphy. The strength of this book over classics like Bruce Schneier's classic Applied Cryptography is that Aumasson gives good descriptions of how famous systems, many of which were once thought un­break­able, were broken. That includes RC4 (a stream cipher used in WEP, the old Wi-Fi protocol), A5/1 (used in 2G phones), and DES, the (former) digital encryption standard. All of these are fatally flawed and no longer used, and books on these topics (of which there are many) are no longer worth their paper.

Schneier wrote this about DES in 1994:

Although it [DES] is showing signs of old age, it has held up remarkably well against years of cryptanalysis and is still secure against all but possibly the most powerful of adversaries.

Now, in 2018, Aumasson writes:

Prior to the adoption of AES, the standard cipher in use was DES, with its ridiculous 56-bit security . . . . AES is as secure as a block cipher can be, and will never be broken. [p.65, emphasis added]

How do things like this keep happening? Sometimes the size of the key or the nonce (which is essential in stream ciphers to randomize the key) is too small, but often it is that the specification is so damn compli­cat­ed that almost no one can get it right. The canonical example of this is RSA, about which Aumasson writes:

I sincerely hope you'll never have to implement RSA from scratch. If you're asked to, run as fast as you can and question the sanity of the person who asked you to do so. [p.191]

Encryption standards are constantly changing, with elliptic curve cryptography (ECC) rapidly taking over and quantum computers, which could blow all of them out of the water, on the horizon. Aumasson describes ECC and its advantages, the main one being its use of smaller numbers to provide comparable security, which makes it up to 150 times faster than RSA for verifying signatures. But like RSA, ECC is very complicated, maybe too complicated, which invites coding mistakes. Some implementations of TLS that used it made coding or other mistakes that compro­mised their security.

Of course, there's not nearly enough information here to enable anyone to create a serious encryption system. For that, you'd probably be better off getting a PhD in mathematics and reading the current literature. Aumasson recommends Oded Goldreich's 2001 two-volume Foundations of Cryptography for the math background. The purpose here is to help the reader, who is tasked with using an encryption system or incorporating one into their own software, to understand how to use the existing ones better. The algorithms, including RSA, Diffie-Hellman, AES, Salsa20, SHA-1, -2, and -3, and several others, as well as their potential vulnerabilities, are very nicely described, using toy numbers to show the principle, Sage to show sample big-number calculations, and bits of pseudo­code and Snake Language, i.e. Python, for the rest. For example:

def compare_mac(x, y, n):
   for i in range(n):
      if x[i] != y[i]:
         return False
   while True:
      sssayyaaaah.sassshiiii

(Last two lines added by reviewer)

After reading this book, and with the help of the RPN Calculator app on my cell phone (which can do logic operations in hex mode), I had no trouble following some of the original papers on the topic, though I'm still a little fuzzy about where some of these magical constants come from.

It would have helped if the author had pointed us to programs that handle big integers. wcalc is a Linux program that does, but neither wcalc nor Matlab can handle things like 22071032 % 4127, where ‘%’ means ‘modulo.’ (Update: Using the algorithm in Hoffstein et al. (reviewed at right), the answer turns out to be 1175.)

To give you an idea how serious this book is, the binding on my copy self-destructed, Mission Impossible style, about ten seconds after I finished reading it, giving me a concrete example of a permutation cipher (though not, I should add, an unbreakable one, because the publisher numbered the pages sequentially—a classic mistake).

This is one of the few books that give practical details on what can go wrong, but even so there are many questions left unanswered. Why do people use a counter instead of a random number for their nonce in stream ciphers? When is a FSR (feedback shift register) used instead of a random number generator? What is the best way to convert a password into a key? What software is available to test these algorithms? This book won't answer every question, but it will get you oriented. After that, I suppose it's a matter of reading the RFCs and looking at the source code.

And yes, I lied at the top about not telling jokes, but at least they were bad ones.

jul 25, 2023. updated aug 08, 2023

An Introduction to Mathematical Cryptography 2e

by J. Hoffstein, J. Pipher, J.H. Silverman
Springer, 2008, 2014, 538 pages
reviewed by T. Nelson

his one explains the mathematics behind the topics in Aumasson's book and seems to be a good match for it. It's reasonably well written, but its biggest strength is its step-by-step explanation of the algorithms using specific examples. For example, the Fast Powering Algorithm, used in RSA and Diffie-Hellman, is a clever way to calculate powers of extremely large numbers with only a few steps without exceeding the range of ordinary 64-bit integers. The results take some getting used to, as it seems weird to see things like 3218 = 489 (mod 1000). There are also some quirks, like showing moduli as negative numbers. But the examples are worked through in detail to make sure the reader understands the math propo­si­tions and theorems before giving a formal definition and proof.

The fast powering algorithm, along with many others, can also be found in the more advanced book Algor­ithm­ic Crypt­analysis by Antoine Joux, where it's presented as pseudocode, but Joux's book has no worked examples or test data. Algor­ithm­ic Crypt­analysis is a good source for studying how weaknesses can be found. The drawback is that the discussion is quite formal and abstract, with few clues about why the algorithms work or how effective they are. Joux assumes you know how to apply the algorithms to the problem at hand. This creates challenges in the chapters on Fourier transforms and index calculus. While providing the algorithms for FFT and Hadamard transforms is great, I'm still a little unclear about how they help to crack DES.

Hoffstein et al.'s book is a lot easier to follow, especially if you reproduce the algorithms on a computer rather than just accepting the answers. It seems to me that this is an ideal way to study mathematical topics. A practical application like cryptography makes it clear that these aren't just interesting abstractions. That's because of the Rule of Pedagog­ical Dependency: if you teach A, B, C, and D, where each topic depends on using what they learned in the previous one, they'll quickly forget D but will remember much of C, most of B, and all of A.

One disadvantage is its extended discussion of basic probability and statistics and of the Vigenère cipher, invented in 1553, for which the hardest step in cryptanalyzing it is spelling its name right. Another minor gripe is the use, starting on page 193, of Samantha and Victor [for signer and verifier] instead of the usual names, which were probably a pun of that dreadful movie Bob and Carol and Ted and Alice, which is about permutations. (We don't hear much about Ted these days; perhaps he's in Leavenworth.) The goal was to liven up the text, but Sigmund and Veronica would have been easier to remember.

In the other chapters you'll get some education on number theory, elliptic curves, and lattices. Lattices are a new ‘hard problem’ designed to be resistant to quantum algorithms. On the topic of quantum computing, the authors write:

Tempting though it is, we will not use this opportunity to give a serious introduction to quantum mechanics.

As for the rest of it, it helps if you can remember the stuff they taught you back in analysis class (which for me was a long, long way back). The book mainly discusses public key and signature schemes. The authors' own lattice-based public key cryptosystem, called NTRU (Nth degree Truncated Polynomial Ring Units), which they call NTRUEncrypt, gets particular attention. There's very little on specific block crypto­graphic systems like AES, which gets a single paragraph on the last page of the book, and next to nothing on how those myster­ious S-boxes are made.

Be sure to check the errata list.

aug 10, 2023

Cryptography Engineering

by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno
Wiley, 2010, 353 pages
reviewed by T. Nelson

ot all cryptographic software is written for the Internet. Much of it is designed for commercial communications such as between banks and POS [point-of-sale] devices. This book draws on Ferguson's experience with an electronic Smart Card system to give general advice to programmers planning to develop a secure communications protocol.

Working with credit card chips must have been a harrowing experience because it made the authors paranoid about everything: don't use Java, they say, and you can't trust C or C++ either. Be sure to encrypt your memory and erase the keys from memory. Delete all program state every so often, so when the memory gets swapped to disk or the CPU gets rebooted, a bad guy can't get any information by examining your hard drive and RAM chips. And watch out for RF emissions.

The authors say they want you to become paranoid as well. Or at least that's what they want you to think. But it makes sense: in some OSs, like Linux, you can't count on anything continuing to exist a year from now. In others, somebody can attach a debugger to an already running process. In Unix, a superuser can read anything in memory or trigger a core dump. Don't trust your compiler to actually erase things from memory when you tell it to. Don't trust your big number library, but don't create your own, either. It sounds impossible, but as in all engineering tasks, everything is a compromise.

The advice is fairly vague, but the text is readable. Issues are discussed from three distinct viewpoints, as if the contributions from each of the three authors were written independently and then concatenated. Some sections discuss specific communication security items and key negotiation protocols, like D-H, RSA, X.509 certificates, and PKI. These sections are mostly out of date, but the general principles of good programming will be useful for a long time, or until ChatGPT achieves sentience and exterminates all the remaining humans, whichever comes first.

aug 14, 2023