Electronic Review of Computer Books
[ ERCB Home | New | Feature | Brief | DDJ | Letters | Links ]

Applying Cryptanalysis

Review by Al Stevens
Copyright (C) Dr. Dobb's Journal, May, 1994
cryptography (krip-tgra-f) n. The art or process of writing in or deciphering secret code.
A Sherlock Holmes story tells how Professor Moriarty, despite his superior intelligence and mathematical skills, is unable to break a simple code, one that uses a particular edition of a rare book as the key. The story does not reveal the secret of the code until the end. The ciphertext--the encrypted message--consists of page and word numbers. There is no repetition, no underlying formula that Moriarty could derive from the seemingly random numbers in the ciphertext. To decrypt the message, Moriarty has to know the algorithm--the cipher--after which he needs a matching edition of the key codebook, of which only two copies exist, and they are in the possession of the covert correspondents. Unbreakable code, according to the artistic license exercised by Conan Doyle.

Cryptography is nearly as old as the written word. Surreptitious communication has been a requirement of governments and their armies since the beginning of organized society. Some of the first applications for digital computers were computations to assist codebreakers. Programmers take to encryption/decryption algorithms naturally. The subject intrigues us because it involves complex puzzles and their solutions and because the solutions reveal the locked-away secrets of others. We like to use our wits to get into locked places, to outsmart those who contrive the locks, to contrive locks of our own that others cannot pick. To do so requires an understanding of code-making--cryptography--and code-breaking--cryptanalysis.

Applied Cryptography, by Bruce Schneier, is a comprehensive treatment of the subject, describing its concepts and demonstrating its processes. It is the definitive work on cryptography for computer programmers. According to this book, applications for cryptography fall into two camps--those meant to deter the mildly curious and those that must stand up to aggressive and expert assault. The dedicated cryptographer has no use for the former and strives for perfection in the latter. Schneier is a dedicated practitioner. He characterizes the first type of applications as being suitable for defending against your kid sister and the second for standing off the agents of major governments. Apparently there is no middle ground.

Applied Cryptography begins with a discussion of the terms and processes of cryptography. It describes several classical manual encryption processes and some computer algorithms. It even provides an example of a simple XOR algorithm written in C, borrowed and slightly modified from a DDJ "C Programming" column I wrote several years ago. I was pleased to see my code included in this work until I read the part where the author called the algorithm an embarrassment, one that produces code that is trivial to break, good enough only to keep your kid sister from reading your files. I don't have any sisters, so that wasn't my intent. The point of the example, however, is that the simple algorithm is the same one that many respectable commercial applications use for encryption. The message is that if you depend on those applications for security in more than the most benign of environments, you are being short-changed. Although Schneier references the DDJ column and uses its code to make the point, he fails to say that the column pointed out the algorithm's weaknesses, then implemented the much more secure DES algorithm that month and again with some corrections two months later. That omission is my only criticism of the book, and it is a personal one. If you weren't me, you wouldn't notice and it wouldn't matter.

Although Applied Cryptography describes itself as a reference book, it also serves as an advanced wall-to-wall tutorial on cryptography. You cannot turn to a chapter and expect to understand everything without some preparation. For example, you should read Chapter 2, "Protocol Building Blocks" before going further. This chapter defines a cast of characters used throughout the book in scenarios about messages, encryption, decryption, and codebreaking. If you are interested in public-key algorithms, for example, and you jump to Chapter 12, you will find yourself reading about situations involving Bob and Alice, with no explanation of who they are and what roles they play. Chapter 2 is a prerequisite to much of the rest of the book.

Applied Cryptography discusses the degree of security that each algorithm offers. A cryptanalyst can use a computer to decrypt ciphertext with brute-force techniques, but, depending on the algorithm, the time required for a Cray to do it might be measured in multiples of the life of the universe. Decryption of an encrypted message requires three things: the decryption algorithm, the key, and the message itself. We encrypt messages because the carrier is not secure, and we assume that an interloper can eavesdrop. Much of the book's discussion about codebreaking assumes that the intruder knows which encryption algorithm is being used. How they could know this is not always obvious. In a benign environment, it could be as simple as looking at your application and knowing or reverse-engineering the algorithm the application employs. In a more hostile environment, the enemy has to apply other intelligence-gathering techniques to find out how you encrypt your messages. The book assumes rightly that such techniques exist and are effective. If the snoop learns the key as well as the algorithm, then no codebreaking is necessary.

Many encryption algorithms depend on the use of a random-number generator. If my computer and your computer both generate identical random-number sequences given the same seed, then we can build a reasonably secure cryptosystem, or so it would seem. As long as the sequence is truly random with no repeating patterns, there are no patterns for the codebreaker to observe. The book points out the problem with these schemes. Computer random-number generators are effectively only pseudorandom-number generators. Give them enough cycles, and they will repeat themselves. Repetitions produce patterns, on which a cryptanalyst thrives.

Novice cryptographers might assume that their security lies in the secrecy of the algorithm itself. You might reason that a codebreaker can have the ciphertext message and even the key and still not be able to decrypt the message because the algorithm itself is unknown. For example, a file compressed with a Huffman tree appears to be a random pattern of bytes, not even the same length as the original plaintext. Strip the character-frequency array and use it as a key, and an essential piece of the decryption (decompression) is missing from the ciphertext. What is left for a codebreaker to work with? It looks pretty secure to the casual observer.

There are flaws in this logic. First, the mission of espionage is to uncover that which is supposed to be kept secret. Spies have ways of learning your algorithm. Remember that, before you can send an encrypted message, you and your correspondent have to agree on a secure mode of communication, including the algorithm and the key. That agreement itself is a communication, carried out before a secure mode is established, and subject to interception by a potential codebreaker. Second, if you are intent on maintaining the strictest security, you will select an algorithm known among cryptographers as being secure. The enemy knows what those algorithms are, too, and often knows how to determine the algorithm by analyzing patterns in the ciphertext. To quote the book, "trusting_algorithms is like trusting snake oil." In the example of the Huffman pseudo-encryption, the ciphertext turns out to be a simple substitution algorithm, except that the substitution tokens are variable-length bit streams rather than characters. Substitution algorithms are among the easiest to break, the book teaches us.

Rather than rely on the security of the algorithm itself, most cryptographers use well-known algorithms that resist attack. Chapter 7, "Keys," tells us that a truly strong algorithm resists all but a brute-force attack, in which the attacker tries every possible key value. Depending on the key length, this process can take from milliseconds for a 1-byte key to 1025 years for a 16-byte key, which should be long enough. The best algorithms resist all but brute-force attacks, but even they might not always be secure enough. Given the rapid growth of computational speed, the advances in parallel processing, and the willingness of governments to commit unlimited resources to the gathering of intelligence, the day might come when brute-force computer attacks are more productive than applied cryptanalysis.

Applied Cryptography says that cryptography involves protocols, each of which involves two or more people who understand and agree on the protocol. A codebreaker is an outsider who attacks the protocol. I had a problem with the requirement for two or more people, which assumes that all encrypted information is passed to another person. It does not provide for private encryption of private information to be secure from the prying eyes of kid sisters and other interlopers. This is only a matter of interpretation, however. Ignore it, and the book loses no information.

The book teaches about private keys, session keys, public keys, digital signatures, and numerous cryptography protocols. Each protocol includes a scenario where the cast of characters exchange messages in ways that explain the protocol. These discussions are invaluable to someone who is evaluating encryption methods to select one that best matches a particular set of requirements.

The association between public-key encryption and digital signatures is interesting. Each user of a public-key cryptosystem publishes a public key. Correspondents use the public key to encrypt messages to the user. An associated private key, known only to the user, decrypts the message. Everyone can send encrypted messages but only the intended receiver can decrypt them. Inversely, a message encrypted with the private key can be decrypted only with the associated public key. Receivers know that a broadcast message originated with a particular user because only that user's public key successfully decrypts the message. The encryption becomes, in effect, a digital signature. Schneier's book describes most popular encryption algorithms with C-language source-code examples to implement some of them. The companion diskette set, which you must order directly from the author, includes implementations of most algorithms, including DES, RSA, Diffie-Hellman, and PEM. A text file on the diskette explains how to get PGP.

There is a two-page treatment of Clipper, the NSA chip with the backdoor that only the government can open. The discussion touches on the privacy issues associated with such an insidious scheme.

Chapter 18 is about politics. It describes the missions of various government agencies and private organizations with respect to cryptography. It discusses and identifies several software patents that apply. It warns you about exporting cryptographic technology under threat of federal arms-trafficking laws.

Applied Cryptography represents a monumental body of knowledge, particularly to the programmer. I do not know of another work that encapsulates as much information about cryptography and then supplies the computer code to implement the algorithms that it describes. Even a programmer who is only mildly interested in cryptography will find this book fascinating. If you plan to put encryption logic into an application, get the companion diskette, which contains many more source-code examples than are printed in the book and is a virtual grab bag of encryption algorithms. At the same time, educate yourself on the legal implications of using whichever algorithms you choose. They might be patented or you might need a license to export them.

No matter how you use this book, though, Applied Cryptography is an interesting and comprehensive explanation of an enigmatic subject, and well worth the time you will spend with it.

Applied Cryptography: Protocols, Algorithms, and Source Code in C
Bruce Schneier
John Wiley & Sons, 1994, 618 pp. $44.95
ISBN 0-471-59756-2

Electronic Review of Computer Books
Created 5/1/96 / Last modified 6/4/96 / webmaster@ercb.com