The Final Word on Cryptography
SunWorld readers say this book makes the incomprehensible clear
Though two years old, Bruce Schneier’s Applied Cryptography, Second Edition still stands as the definitive work on its subject. It attempts to explain why cryptography has to be so complex and mystifying, and bring clarity to this complex topic, even for the nontechnical reader. (2,200 words)
Two months ago, I made the assertion that there is no book on cryptography that is both readable and nontrivial. I even offered a prize to the reader who could convince me otherwise. The responses I got were a bit embarrassing, because I was clearly unaware of a work that an overwhelming number of SunWorld readers consider to be the definitive work on this subject: Bruce Schneier’s Applied Cryptography, published in its second edition at the end of 1995.
This 700-plus-page magnum opus is one of the finest technical books I have ever read, easily satisfying my requirements of readability, accessibility, and depth. Although many readers recommended this book to me, the SunWorld Mini Maglite goes to the respondent with the earliest timestamp on his e-mail: Laurence Michaels. Congratulations to Laurence, and thanks to all of you who responded.
Bruce Schneier has long been a well-known consultant on cryptography. Recently he became chief scientist at an e-commerce startup company called Transactor Networks. Transactor builds technology for selling intellectual property in digital form over the Internet; its primary target market is online gaming and entertainment. Maybe he’s decided that consulting fees and book royalties aren’t much compared to the potential of an Internet startup going public. But no matter how much success Transactor has, Schneier’s lasting contribution to the world will surely be this book.
Applied Cryptography will appeal to any reasonably sophisticated reader who is interested in learning about its subject. It will also be appreciated by programmers who need to understand and implement real-world systems. There are plenty of algorithm descriptions and source code in C, but the book is structured so that the non-programmer and non-mathematician doesn’t have to wade through that level of detail. Schneier develops much of his material with nontechnical prose and technical notations in parallel, which means that you can follow whichever explanations are most comfortable. He has the tech-writer’s skill of being able to describe complex things in a crystal-clear way without losing precision, and he leavens his material with welcome humor and opinion.
Parts I and II, roughly the first third of the book, are easily accessible to anyone who invests the effort to read carefully. (No matter how good the writing is, you cannot skim this material if you hope to learn it.) These first two parts of the book develop the need for certain important types of cryptographic protocols and explain the protocols in lay terms. But beyond explaining particular protocols, these sections answer far more interesting questions about why cryptography is necessary — beyond the obvious point about protecting secrets — and why it has to be so complicated.
Many of us feel that cryptography ought to be much simpler than it is. It should be possible to find some cryptographic scheme that’s sufficiently unbreakable and reasonably efficient; then someone should implement it as a black box that requires little or no user intervention, and that technique should be standardized. Period. The end.
But there are two basic problems with this assertion. First of all, the functionality of the black box must vary widely according to what you’re trying to do. Second, computing power is increasing so rapidly that a crypto-scheme thought to be secure today may well not be a few years from now. And third, it is almost always impossible to prove a crypto-scheme secure. There is often some aura of doubt about the security of real-world implementations.
Actually, if all you’re doing is exchanging sensitive information with someone over an electronic connection, then simple, black box security is possible, as AT&T and others demonstrated 10 years ago with the STU-III secure telephone device. But if you want to do anything more sophisticated, cryptography gets very complicated very quickly.
The goal of cryptography: Stopping the shenanigans
In fact, cryptography is not so much about protecting secrets as it’s about emulating traditional human behavior towards information in the online digital domain. The problem with online digital information is that it’s easier for people to access, copy, analyze, and manipulate than physical analog information. Cryptography is a set of techniques that restrict access, analysis, and manipulation so that digital information resembles the old-fashioned types of information exchange that people expect.
Two particular examples of protocols in Applied Cryptography illustrate this point very well. One is digital cash. In electronic commerce, it’s necessary to protect against unscrupulous behavior, like eavesdroppers who want to steal credit card and other identifying numbers. Beyond simply encrypting credit card numbers, financial companies have to take certain steps at every point in a transaction to prevent such shenanigans.
Digital cash adds anonymity to the list of requirements. Preserving anonymity while protecting against fraud and eavesdropping turns out to be quite difficult; a lot has to happen behind the scenes in digital cash algorithms to implement them properly. Schneier starts by describing a relatively simple algorithm, explains what’s wrong with it, and then describes progressively complex algorithms until he finally reaches a successful digital cash implementation.
But even in his first attempt at a digital cash algorithm, a lot of funny things happen. In it, we assume that someone wants her bank to sign a digital cash instrument (a smart card, say) for $1000 so that she can use it to make purchases. She brings 100 of the instruments to the bank. The bank looks at 99 of them, chosen at random, and verifies that they are for $1000. Then it signs the remaining one without looking at it, using the electronic equivalent of carbon paper inside a sealed envelope, and gives it to her. The bank isn’t able to tell whom the instrument it signs is from, and it assumes that, like the other 99, it is for $1000. The user could try to cheat by making one of the 100 money orders out for more than $1000, but the odds are only 1 in 100 that she would get away with it, and the penalties for getting caught can be made severe enough to deter cheating.
Sound like a lot of trouble to go through, simply to replicate the idea of cash in the digital domain? It does, even when you realize that such a protocol can be implemented behind the scenes so that the user is not aware of any of the seemingly bizarre details.
Many people have thought about digital cash, and there are currently a few fairly successful implementations, such as ECash and CyberCash. My other favorite example of the difficulties of replicating real-world situations online is a type of application that far fewer people have thought about and that absolutely no one is likely to implement in the forseeable future: secure digital elections.
What are the necessary attributes of an election? Schneier lists six requirements:
- You have to be authorized (i.e., registered) to vote
- You can’t vote more than once
- No one should be able to find out whom you voted for
- You shouldn’t be able to copy anyone else’s vote
- You can’t change anyone else’s vote
- You should be able to verify that your vote has been counted in the results
Schneier considers how to implement secure digital elections by using what he calls a central tabulating facility (CTF). He goes through no less than five protocols until he presents one that actually works. He starts by stating the obvious simple protocol — each voter encrypts his vote using the CTF’s public key, sends the vote to the CTF, and the CTF tabulates the results — and then showing how utterly inadequate it is. Before he is done, he’s added several elements including, among other things, blind signatures, and another step that’s similar to the 100-smart-cards step in digital cash. He also discusses what to do to ensure that the CTF is not doing nasty things like changing people’s votes. The most secure voting protocol he presents is one that does completely without the CTF by sharing trust among all voters. This protocol is so inefficient as to be unimplementable for more than a handful of voters.
Can you imagine any government (in the United States, at least) implementing some kind of secure digital election scheme? I can’t. Too many objections would be raised about the longevity of the encryption schemes, the trustworthiness of the firms hired to implement it, and even the trustworthiness of the government agency that runs it. It’s not unlike the sort of problems that many have with the government’s controversial key-escrow schemes, in which one or more agencies act as repositories for people’s encryption keys. Schneier discusses these and many related issues in the last chapter of the book, which is called “Politics.”
Much of this last chapter is devoted to the National Security Agency (NSA) and its effects on U.S. cryptography policy. Unfortunately, there’s not much one can definitively say about the NSA, because virtually everything about it is classified, including such basic facts as how many people it employs. It is widely believed to be the largest buyer of computer equipment as well as hosting the highest concentration of mathematical talent in the world. As Schneier puts it, the NSA has been responsible for many heavy-handed attempts to foist cryptography technology on the public that gives power to the government to use people’s private keys, wiretap digital phone systems, and limit the strength of cryptosystems (e.g., lengths of keys) to the point where the NSA can use its (suspected) arsenal of supercomputers to crack them. We saw lots more about this in Whitfield Diffie and Susan Landau’s Privacy on the Line (recently reviewed in Bill’s Bookshelf).
The chapter mentions such Libertarian-minded organizations as the Electronic Frontier Foundation and the Cypherpunks, the band of super-programmers dedicated to implementing privacy technology. It also goes into some detail about U.S. export controls on cryptography. The government treats cryptosystems above a certain level of power as weapons technology, and it’s considered a crime even to lecture on powerful cryptosystems outside of the United States.
The law is murky. Here’s an example of its ambiguity: I have a laptop computer with the U.S. version of Netscape Communicator installed. This version uses unexportable 128-bit encryption. I am currently in Europe and using my laptop for e-mail and Web access. Am I breaking any laws?
The middle of Applied Cryptography contains technical descriptions of many different encryption algorithms, starting with an exhaustive discussion of DES (Data Encryption Standard), for many years the NSA’s standard algorithm. The section starts with a primer on various mathematical prerequisites like NP-completeness, information theory, and modular arithmetic. These are fairly lucid, if brief, explanations for the nontechnical reader, but they aren’t necessary. Non-technical readers are unlikely to need to understand the technical details of the algorithms presented in the chapter, while the technical people who do need to know them should already be familiar with most of the relevant mathematics.
There is also a chapter on real-world implementations of cryptography, including Phil Zimmermann’s well-known Pretty Good Privacy e-mail program and the (virtually useless) encryption in the PKZIP data compression utility. If any part of the book needs updating, it’s this. Surely a lot could be said about encryption and security on the Web, such as SSL and HTTPS, but the Web isn’t covered at all.
Yet the fact that anyone has written a book on this complex subject that is of significant value to both technical and nontechnical readers is little short of amazing. When I first picked up Applied Cryptography, I expected a programmer’s manual, and indeed it fulfills that function. I hadn’t written a C program in years, and I didn’t intend to start up again just to review this book. Nevertheless, I found myself eagerly devouring most of the book’s 600-plus pages (not counting appendices crammed full of source code and over 1,600 bibliographic references) and becoming fascinated with a topic that should concern every citizen of the industrialized world, whether we like it or not.
Because we are unable to cast off millennia worth of experiences in handling information, we are forced to use cryptography to replicate our known protocols in the online digital domain. Applied Cryptography goes a long way toward justifying and making bearable the inherent complexity of the topic. It is a masterpiece.