Applied Cryptography, Second Edition

Applied Cryptography, Second Edition:
Protocols, Algorthms, and Source Code in C

Chapter 1—Foundations
1.1 Terminology
1.2 Steganography
1.3 Substitution Ciphers and Transposition Ciphers
1.4 Simple XOR
1.5 One-Time Pads
1.6 Computer Algorithms
1.7 Large Numbers

Part I—Cryptographic Protocols

Chapter 2—Protocol Building Blocks
  2.1 Introduction to Protocols
  2.2 Communications Using Symmetric Cryptography
  2.3 One-Way Functions
  2.4 One-Way Hash Functions
  2.5 Communications Using Public-Key Cryptography
  2.6 Digital Signatures
  2.7 Digital Signatures with Encryption
  2.8 Random and Pseudo-Random-Sequence Generation

Chapter 3—Basic Protocols
  3.1 Key Exchange
  3.2 Authentication
  3.3 Authentication and Key Exchange
  3.4 Formal Analysis of Authentication and Key-Exchange Protocols
  3.5 Multiple-Key Public-Key Cryptography
  3.6 Secret Splitting
  3.7 Secret Sharing
  3.8 Cryptographic Protection of Databases

Chapter 4—Intermediate Protocols
  4.1 Timestamping Services
  4.2 Subliminal Channel
  4.3 Undeniable Digital Signatures
  4.4 Designated Confirmer Signatures
  4.5 Proxy Signatures
  4.6 Group Signatures
  4.7 Fail-Stop Digital Signatures
  4.8 Computing with Encrypted Data
  4.9 Bit Commitment
  4.10 Fair Coin Flips
  4.11 Mental Poker
  4.12 One-Way Accumulators
  4.13 All-or-Nothing Disclosure of Secrets
  4.14 Key Escrow

Chapter 5—Advanced Protocols
  5.1 Zero-Knowledge Proofs
  5.2 Zero-Knowledge Proofs of Identity
  5.3 Blind Signatures
  5.4 Identity-Based Public-Key Cryptography
  5.5 Oblivious Transfer
  5.6 Oblivious Signatures
  5.7 Simultaneous Contract Signing
  5.8 Digital Certified Mail
  5.9 Simultaneous Exchange of Secrets

Chapter 6—Esoteric Protocols
  6.1 Secure Elections
  6.2 Secure Multiparty Computation
  6.3 Anonymous Message Broadcast
  6.4 Digital Cash

Part II—Cryptographic Techniques

Chapter 7—Key Length
  7.1 Symmetric Key Length
  7.2 Public-Key Key Length
  7.3 Comparing Symmetric and Public-Key Key Length
  7.4 Birthday Attacks against One-Way Hash Functions
  7.5 How Long Should a Key Be?
  7.6 Caveat Emptor

Chapter 8—Key Management
  8.1 Generating Keys
  8.2 Nonlinear Keyspaces
  8.3 Transferring Keys
  8.4 Verifying Keys
  8.5 Using Keys
  8.6 Updating Keys
  8.7 Storing Keys
  8.8 Backup Keys
  8.9 Compromised Keys
  8.10 Lifetime of Keys
  8.11 Destroying Keys
  8.12 Public-Key Key Management

Chapter 9—Algorithm Types and Modes
  9.1 Electronic Codebook Mode
  9.2 Block Replay
  9.3 Cipher Block Chaining Mode
  9.4 Stream Ciphers
  9.5 Self-Synchronizing Stream Ciphers
  9.6 Cipher-Feedback Mode
  9.7 Synchronous Stream Ciphers
  9.8 Output-Feedback Mode
  9.9 Counter Mode
  9.10 Other Block-Cipher Modes
  9.11 Choosing a Cipher Mode
  9.12 Interleaving
  9.13 Block Ciphers versus Stream Ciphers

Chapter 10—Using Algorithms
  10.1 Choosing an Algorithm
  10.2 Public-Key Cryptography versus Symmetric Cryptography
  10.3 Encrypting Communications Channels
  10.4 Encrypting Data for Storage
  10.5 Hardware Encryption versus Software Encryption
  10.6 Compression, Encoding, and Encryption
  10.7 Detecting Encryption
  10.8 Hiding Ciphertext in Ciphertext
  10.9 Destroying Information

Part III—Cryptographic Algorithms

Chapter 11—Mathematical Background
  11.1 Information Theory
  11.2 Complexity Theory
  11.3 Number Theory
  11.4 Factoring
  11.5 Prime Number Generation
  11.6 Discrete Logarithms in a Finite Field

Chapter 12—Data Encryption Standard (DES)
  12.1 Background
  12.2 Description of DES
  12.3 Security of DES
  12.4 Differential and Linear Cryptanalysis
  12.5 The Real Design Criteria
  12.6 DES Variants
  12.7 How Secure Is DES Today?

Chapter 13—Other Block Ciphers
  13.1 Lucifer
  13.2 Madryga
  13.3 NewDES
  13.4 FEAL
  13.5 REDOC
  13.6 LOKI
  13.7 Khufu and Khafre
  13.8 RC2
  13.9 IDEA
  13.10 MMB
  13.11 CA-1.1
  13.12 Skipjack

Chapter 14—Still Other Block Ciphers
  14.1 GOST
  14.2 CAST
  14.3 Blowfish
  14.4 SAFER
  14.5 3-Way
  14.6 Crab
  14.7 SXAL8/MBAL
  14.8 RC5
  14.9 Other Block Algorithms
  14.10 Theory of Block Cipher Design
  14.11 Using one-Way Hash Functions
  14.12 Choosing a Block Algorithm

Chapter 15—Combining Block Ciphers
  15.1 Double Encryption
  15.2 Triple Encryption
  15.3 Doubling the Block Length
  15.4 Other Multiple Encryption Schemes
  15.5 CDMF Key Shortening
  15.6 Whitening
  15.7 Cascading Multiple Block Algorithms
  15.8 Combining Multiple Block Algorithms

Chapter 16—Pseudo-Random-Sequence Generators and Stream Ciphers
  16.1 Linear Congruential Generators
  16.2 Linear Feedback Shift Registers
  16.3 Design and Analysis of Stream Ciphers
  16.4 Stream Ciphers Using LFSRs
  16.5 A5
  16.6 Hughes XPD/KPD
  16.7 Nanoteq
  16.8 Rambutan
  16.9 Additive Generators
  16.10 Gifford
  16.11 Algorithm M
  16.12 PKZIP

Chapter 17—Other Stream Ciphers and Real Random-Sequence Generators
  17.1 RC4
  17.2 SEAL
  17.3 WAKE
  17.4 Feedback with Carry Shift Registers
  17.5 Stream Ciphers Using FCSRs
  17.6 Nonlinear-Feedback Shift Registers
  17.7 Other Stream Ciphers
  17.8 System-Theoretic Approach to Stream-Cipher Design
  17.9 Complexity-Theoretic Approach to Stream-Cipher Design
  17.10 Other Approaches to Stream-Cipher Design
  17.11 Cascading Multiple Stream Ciphers
  17.12 Choosing a Stream Cipher
  17.13 Generating Multiple Streams from a Single Pseudo-Random-Sequence Generator
  17.14 Real Random-Sequence Generators

Chapter 18—One-Way Hash Functions
  18.1 Background
  18.2 Snefru
  18.3 N- Hash
  18.4 MD4
  18.5 MD5
  18.6 MD2
  18.7 Secure Hash Algorithm (SHA)
  18.8 RIPE-MD
  18.9 HAVAL
  18.10 Other One-Way Hash Functions
  18.11 One-Way Hash Functions Using Symmetric Block Algorithms
  18.12 Using Public-Key Algorithms
  18.13 Choosing a One-Way Hash Function
  18.14 Message Authentication Codes

Chapter 19—Public-Key Algorithms
  19.1 Background
  19.2 Knapsack Algorithms
  19.3 RSA
  19.4 Pohlig-Hellman
  19.5 Rabin
  9.6 ElGamal
  19.7 McEliece
  19.8 Elliptic Curve Cryptosystems
  19.9 LUC
  19.10 Finite Automaton Public-Key Cryptosystems

Chapter 20—Public-Key Digital Signature Algorithms
  20.1 Digital Signature Algorithm (DSA)
  20.2 DSA Variants
  20.3 Gost Digital Signature Algorithm
  20.4 Discrete Logarithm Signature Schemes
  20.5 Ong-Schnorr-Shamir
  20.6 ESIGN
  20.7 Cellular Automata
  20.8 Other Public-Key Algorithms

Chapter 21—Identification Schemes
  21.1 Feige-Fiat-Shamir
  21.2 Guillou-Quisquater
  21.3 Schnorr
  21.4 Converting Identification Schemes to Signature Schemes

Chapter 22—Key-Exchange Algorithms
  22.1 Diffie-Hellman
  22.2 Station-to-Station Protocol
  22.3 Shamir’s Three-Pass Protocol
  22.4 COMSET
  22.5 Encrypted Key Exchange
  22.6 Fortified Key Negotiation
  22.7 Conference Key Distribution and Secret Broadcasting

Chapter 23—Special Algorithms for Protocols
  23.1 Multiple-Key Public-Key Cryptography
  23.2 Secret-Sharing Algorithms
  23.3 Subliminal Channel
  23.4 Undeniable Digital Signatures
  23.5 Designated Confirmer Signatures
  23.6 Computing with Encrypted Data
  23.7 Fair Coin Flips
  23.8 One-Way Accumulators
  23.9 All-or-Nothing Disclosure of Secrets
  23.10 Fair and Failsafe Cryptosystems
  23.11 Zero-Knowledge Proofs of Knowledge
  23.12 Blind Signatures
  23.13 Oblivious Transfer
  23.14 Secure Multiparty Computation
  23.15 Probabilistic Encryption
  23.16 Quantum Cryptography

Part IV—The Real World

Chapter 24—Example Implementations
  24.1 IBM Secret-Key Management Protocol
  24.2 MITRENET
  24.3 ISDN
  24.4 STU-III
  24.5 Kerberos
  24.6 KryptoKnight
  24.7 SESAME
  24.8 IBM Common Cryptographic Architecture
  24.9 ISO Authentication Framework
  24.10 Privacy-Enhanced Mail (PEM)
  24.11 Message Security Protocol (MSP)
  24.12 Pretty Good Privacy (PGP)
  24.13 Smart Cards
  24.14 Public-Key Cryptography Standards (PKCS)
  24.15 Universal Electronic Payment System (UEPS)
  24.16 Clipper
  24.17 Capstone
  24.18 AT&T Model 3600 Telephone Security Device (TSD)

Chapter 25—Politics
  25.1 National Security Agency (NSA)
  25.2 National Computer Security Center (NCSC)
  25.3 National Institute of Standards and Technology (NIST)
  25.4 RSA Data Security, Inc.
  25.5 Public Key Partners
  25.6 International Association for Cryptologic Research (IACR)
  25.7 RACE Integrity Primitives Evaluation (RIPE)
  25.8 Conditional Access for Europe (CAFE)
  25.9 ISO/IEC 9979
  25.10 Professional, Civil Liberties, and Industry Groups
  25.11 Sci.crypt
  25.12 Cypherpunks
  25.13 Patents
  25.14 U.S. Export Rules
  25.15 Foreign Import and Export of Cryptography
  25.16 Legal Issues
  Afterword by Matt Blaze

Part V—Source Code

I wrote Applied Cryptography to be both a lively introduction to the field of cryptography and a comprehensive reference. I have tried to keep the text readable without sacrificing accuracy. This book is not intended to be a mathematical text. Although I have not deliberately given any false information, I do play fast and loose with theory. For those interested in formalism, there are copious references to the academic literature.

Chapter 1 introduces cryptography, defines many terms, and briefly discusses precomputer cryptography.

Chapters 2 through 6 (Part I) describe cryptographic protocols: what people can do with cryptography. The protocols range from the simple (sending encrypted messages from one person to another) to the complex (flipping a coin over the telephone) to the esoteric (secure and anonymous digital money exchange). Some of these protocols are obvious; others are almost amazing. Cryptography can solve a lot of problems that most people never realized it could.

Chapters 7 through 10 (Part II) discuss cryptographic techniques. All four chapters in this section are important for even the most basic uses of cryptography. Chapters 7 and 8 are about keys: how long a key should be in order to be secure, how to generate keys, how to store keys, how to dispose of keys, and so on. Key management is the hardest part of cryptography and often the Achilles’ heel of an otherwise secure system. Chapter 9 discusses different ways of using cryptographic algorithms, and Chapter 10 gives the odds and ends of algorithms: how to choose, implement, and use algorithms.

Chapters 11 through 23 (Part III) list algorithms. Chapter 11 provides the mathematical background. This chapter is only required if you are interested in public–key algorithms. If you just want to implement DES (or something similar), you can skip ahead. Chapter 12 discusses DES: the algorithm, its history, its security, and some variants. Chapters 13, 14, and 15 discuss other block algorithms; if you want something more secure than DES, skip to the section on IDEA and triple–DES. If you want to read about a bunch of algorithms, some of which may be more secure than DES, read the whole chapter. Chapters 16 and 17 discuss stream algorithms. Chapter 18 focuses on one–way hash functions; MD5 and SHA are the most common, although I discuss many more. Chapter 19 discusses public–key encryption algorithms, Chapter 20 discusses public–key digital signature algorithms, Chapter 21 discusses public–key identification algorithms, and Chapter 22 discusses public–key key exchange algorithms. The important algorithms are RSA, DSA, Fiat–Shamir, and Diffie–Hellman, respectively. Chapter 23 has more esoteric public–key algorithms and protocols; the math in this chapter is quite complicated, so wear your seat belt.

Chapters 24 and 25 (Part IV) turn to the real world of cryptography. Chapter 24 discusses some of the current implementations of these algorithms and protocols, while Chapter 25 touches on some of the political issues surrounding cryptography. These chapters are by no means intended to be comprehensive.

Also included are source code listings for 10 algorithms discussed in Part III. I was unable to include all the code I wanted to due to space limitations, and cryptographic source code cannot otherwise be exported. (Amazingly enough, the State Department allowed export of the first edition of this book with source code, but denied export for a computer disk with the exact same source code on it. Go figure.) An associated source code disk set includes much more source code than I could fit in this book; it is probably the largest collection of cryptographic source code outside a military institution. I can only send source code disks to U.S. and Canadian citizens living in the U.S. and Canada, but hopefully that will change someday. If you are interested in implementing or playing with the cryptographic algorithms in this book, get the disk. See the last page of the book for details.

One criticism of this book is that its encyclopedic nature takes away from its readability. This is true, but I wanted to provide a single reference for those who might come across an algorithm in the academic literature or in a product. For those who are more interested in a tutorial, I apologize. A lot is being done in the field; this is the first time so much of it has been gathered between two covers. Even so, space considerations forced me to leave many things out. I covered topics that I felt were important, practical, or interesting. If I couldn’t cover a topic in depth, I gave references to articles and papers that did.