Applied Cryptography: Protocols, Algorithms and Source Code in C / Edition 1

Applied Cryptography: Protocols, Algorithms and Source Code in C / Edition 1

by Bruce Schneier
ISBN-10:
1119096723
ISBN-13:
9781119096726
Pub. Date:
03/30/2015
Publisher:
Wiley

Hardcover

View All Available Formats & Editions
Current price is , Original price is $70.0. You
Select a Purchase Option (20th Anniversary Edition)
  • purchase options
    $49.00 $70.00 Save 30% Current price is $49, Original price is $70. You Save 30%.
  • purchase options

Overview

Applied Cryptography: Protocols, Algorithms and Source Code in C / Edition 1

From the world's most renowned security technologist, Bruce Schneier, this 20th Anniversary Edition is the most definitive reference on cryptography ever published and is the seminal work on cryptography. Cryptographic techniques have applications far beyond the obvious uses of encoding and decoding information. For developers who need to know about capabilities, such as digital signatures, that depend on cryptographic techniques, there's no better overview than Applied Cryptography, the definitive book on the subject. Bruce Schneier covers general classes of cryptographic protocols and then specific techniques, detailing the inner workings of real-world cryptographic algorithms including the Data Encryption Standard and RSA public-key cryptosystems. The book includes source-code listings and extensive advice on the practical aspects of cryptography implementation, such as the importance of generating truly random numbers and of keeping keys secure.

". . .the best introduction to cryptography I've ever seen. . . .The book the National Security Agency wanted never to be published. . . ." -Wired Magazine

". . .monumental . . . fascinating . . . comprehensive . . . the definitive work on cryptography for computer programmers . . ." -Dr. Dobb's Journal

". . .easily ranks as one of the most authoritative in its field." -PC Magazine

The book details how programmers and electronic communications professionals can use cryptography-the technique of enciphering and deciphering messages-to maintain the privacy of computer data. It describes dozens of cryptography algorithms, gives practical advice on how to implement them into cryptographic software, and shows how they can be used to solve security problems. The book shows programmers who design computer applications, networks, and storage systems how they can build security into their software and systems.

With a new Introduction by the author, this premium edition will be a keepsake for all those committed to computer and cyber security.

Product Details

ISBN-13: 9781119096726
Publisher: Wiley
Publication date: 03/30/2015
Edition description: 20th Anniversary Edition
Pages: 784
Sales rank: 635,639
Product dimensions: 7.40(w) x 9.30(h) x 1.90(d)

About the Author

Bruce Schneier is an internationally renowned security technologist, called a "security guru" by The Economist. He is the author of twelve books—including his seminal work, Applied Cryptography: Protocols, Algorithms, and Source Code in C, and Secrets & Lies: Digital Security in a Networked World as well as hundreds of articles, essays, and academic papers. His influential newsletter "Crypto-Gram" and blog "Schneier on Security" are read by over 250,000 people. Schneier is a fellow at the Berkman Center for Internet and Society at Harvard Law School, a program fellow at the New America Foundation's Open Technology Institute, a board member of the Electronic Frontier Foundation, and an Advisory Board member of the Electronic Privacy Information Center. He is also the Chief Technology Officer of Resilient Systems, Inc. You can read his blog, essays, andacademic papers at www.schneier.com. He tweets at @schneierblog.

Read an Excerpt


Chapter 8: Key Management

8.4 Verifying Keys

When Bob receives a key, how does he know it came from Alice and not from someone pretending to be Alice? If Alice gives it to him when they are face-to-face, it's easy. If Alice sends her key via a trusted courier, then Bob has to trust the courier. if the key is encrypted with a key-encryption key, then Bob has to trust the fact that only Alice has that key. if Alice uses a digital signature protocol to sign the key, Bob has to trust the public-key database when he verifies that signature. (He also has to trust that Alice has kept her key secure.) If a Key Distribution Center (KDC) signs Alice's public key, Bob has to trust that his copy of the KDC's public key has not been tampered with.

In the end, someone who controls the entire network around Bob can make him think whatever he likes. Mallory could send an encrypted and signed message purporting to be from Alice. When Bob tried to access the public-key database to verify Alice's signature, Mallory could substitute his own public key. Mallory could invent his own false KDC and exchange the real KDC's public key for his own creation. Bob wouldn't be the wiser.

Some people have used this argument to claim that public-key cryptography is useless. Since the only way for Alice and Bob to ensure that their keys have not been tampered with is to meet face-to-face, public-key cryptography doesn't enhance security at all.

This view is naive. It is theoretically true, but reality is far more complicated. Public-key cryptography, used with digital signatures and trusted KDCs, makes it much more difficult to substitute one key for another. Bob can never be absolutely certain that Mallory isn't controlling his entire reality, but Bob can be confident that doing so requires more resources than most real-world Mallorys have access to.

Bob could also verify Alice's key over the telephone, where he can hear her voice. Voice recognition is a really good authentication scheme. If it's a public key, he can safely recite it in public. If it's a secret key, he can use a one-way hash function to verify the key. Both PGP (see Section 24.12) and the AT&T TSD (see Section 24.18) use this kind of key verification.

Sometimes, it may not even be important to verify exactly whom a public key belongs to. it may be necessary to verify that it belongs to the same person to whom it belonged last year. If someone sends a signed withdrawal message to a bank, the bank does not have to be concerned with who withdraws the money, only whether it is the same person who deposited the money in the first place.

Error Detection during Key Transmission

Sometimes keys get garbled in transmission. Since a garbled key can mean megabytes of undecryptable ciphertext, this is a problem. All keys should be transmitted with some kind of error detection and correction bits. This way errors in transmission can be easily detected and, if required, the key can be resent.

One of the most widely used methods is to encrypt a constant value with the key, and to send the first 2 to 4 bytes of that ciphertext along with the key. At the receiving end, do the same thing. If the encrypted constants match, then the key has been transmitted without error. The chance of an undetected error ranges from one in 2(16) to one in 2(32).

Key-error Detection during Decryption

Sometimes the receiver wants to check if a particular key he has is the correct symmetric decryption key. If the plaintext message is something like ASCII, he can try to decrypt and read the message. If the plaintext is random, there are other tricks.

The naive approach is to attach a verification block: a known header to the plaintext message before encryption. At the receiving end, Bob decrypts the header and verifies that it is correct. This works, but it gives Eve a known plaintext to help cryptanalyze the system. It also makes attacks against short-key ciphers like DES and all exportable ciphers easy. Precalculate the checksum once for each key, then use that checksum to determine the key in any message you intercept after that. This is a feature of any key checksum that doesn't include random or at least different data in each checksum. It's very similar in concept to using salt when generating keys from passphrases.

Here's a better way to do this [821]:

(1) Generate an IV (not the one used for the message).
(2) Use that IV to generate a large block of bits: say, 512.
(3) Hash the result.
(4) Use the same fixed bits of the hash, say 32, for the key checksum.

This gives Eve some information, but very little. If she tries to use the low 32 bits of the final hash value to mount a brute-force attack, she has to do multiple encryptions plus a hash per candidate key; brute-force on the key itself would be quicker.

She also gets no known-plaintext values to try out, and even if she manages to choose our random value for us, she never gets a chosen-plaintext out of us, since it goes through the hash function before she sees it.

8.5 USING KEYS

Software encryption is scary. Gone are the days of simple microcomputers under the control of single programs. Now there's Macintosh System 7, Windows NT, and UNIX. You can't tell when the operating system will suspend the encryption application in progress, write everything to -disk, and take care of some pressing task. When the operating system finally gets back to encrypting whatever is being encrypted, everything will look just fine. No one will ever realize that the operating system wrote the encryption application to disk, and that it wrote the key along with it. The key will sit on the disk, unencrypted, until the computer writes over that area of memory again. It could be minutes or it could be months. It could even be never; the key could still be sitting there when an adversary goes over the hard drive with a fine-tooth comb. In a preemptive, multitasking environment, you can set your encryption operation to a high enough priority so it will not be interrupted. This would mitigate the risk. Even so, the whole thing is dicey at best.

Some communications applications, such as telephone encryptors, can use session keys. A session key is a key that is just used for one communications sessiona single telephone conversation-and then discarded. There is no reason to store the key after it has been used. And if you use some key-exchange protocol to transfer the key from one conversant to the other, the key doesn't have to be stored before it is used either. This makes it far less likely that the key might be compromised.

Controlling Key Usage

In some applications it may be desirable to control how a session key is used. Some users may need session keys only for encryption or only for decryption. Session keys might only be authorized for use on a certain machine or at a certain time. One scheme to handle these sorts of restrictions attaches a Control Vector (CV) to the key; the control vector specifies the uses and restrictions for that key (see Section 24.1) [1025,1026]. This CV is hashed and XORed with a master key; the result is used as an encryption key to encrypt the session key. The resultant encrypted session key is then stored with the CV. To recover the session key, hash the CV and XOR it with the master key, and use the result to decrypt the encrypted session key.

The advantages of this scheme are that the CV can be of arbitrary length and that it is always stored in the clear with the encrypted key. This scheme assumes quite a bit about tamperproof hardware and the inability of users to get at the keys directly. This system is discussed further in Sections 24.1 and 24.8.

8.6 Updating Keys

Imagine an encrypted data link where you want to change keys daily. Sometimes it's a pain to distribute a new key every day. An easier solution is to generate a new key from the old key; this is sometimes called key updating.

All it takes is a one-way function. if Alice and Bob share the same key and they both operate on it using the same one-way function, they will get the same result. Then they can take the bits they need from the results to create the new key.

Key updating works, but remember that the new key is only as secure as the old key was. If Eve managed to get her hands on the old key, she can perform the key updating function herself. However, if Eve doesn't have the old key and is trying a ciphertext-only attack on the encrypted traffic, this is a good way for Alice and Bob to protect themselves.

8.7 Storing Keys

The least complex key storage problem is that of a single user, Alice, encrypting files for later use. Since she is the only person involved, she is the only person responsible for the key. Some systems take the easy approach: The key is stored in Alice's brain and never on the system. Alice is responsible for remembering the key and entering it every time she needs a file encrypted or decrypted....

Table of Contents

CONTENTS

INTRODUCTION XIII

FOREWORD BY WHITFIELD DIFFIE XVII

PREFACE XXI

HOW TO READ THIS BOOK XXII

ACKNOWLEDGMENTS XXIV

ABOUT THE AUTHOR XXV

1 FOUNDATIONS 7

1.1 TERMINOLOGY 1

1 .2 STEGANOGRAPHY 9

1.3 SUBSTITUTION CIPHERS AND TRANSPOSITION CIPHERS 10

1.4 SIMPLE XOR 13

1.5 ONE-TIME PADS 15

1.6 COMPUTER ALGORITHMS 17

1.7 LARGE NUMBERS 17

PART I CRYPTOGRAPHIC PROTOCOLS

2 PROTOCOL BUILDING BLOCKS 27

2.1 INTRODUCTION TO PROTOCOLS 21

2.2 COMMUNICATIONS USING SYMMETRIC CRYPTOGRAPHY 28

2.3 ONE-WAY FUNCTIONS 29

2.4 ONE-WAY HASH FUNCTIONS 30

2.5 COMMUNICATIONS USING PUBLIC-KEY CRYPTOGRAPHY 31

2.6 DIGITAL SIGNATURES 34

2.7 DIGITAL SIGNATURES WITH ENCRYPTION 47

2.8 RANDOM AND PSEUDO-RANDOM SEQUENCE GENERATION 44

3 BASIC PROTOCOLS 47

3.1 KEY EXCHANGE 47

3.2 AUTHENTICATION 52

3.3 AUTHENTICATION AND KEY EXCHANGE 56

3.4 FORMAL ANALYSIS OF AUTHENTICATION AND KEY-EXCHANGE PROTOCOLS 65

3.5 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY 68

3.6 SECRET SPLITTING 70

3.7 SECRET SHARING 71

3.8 CRYPTOGRAPHIC PROTECTION OF DATABASES 73

4 INTERMEDIATE PROTOCOLS 75

4.1 TIMESTAMPING SERVICES 75

4.2 SUBLIMINAL CHANNEL 79

4.3 UNDENIABLE DIGITAL SIGNATURES 81

4.4 DESIGNATED CONFIRMER SIGNATURES 82

4.5 PROXY SIGNATURES 83

4.6 GROUP SIGNATURES 84

4.7 FAIL-STOP DIGITAL SIGNATURES 85

4.8 COMPUTING WITH ENCRYPTED DATA 85

4.9 BIT COMMITMENT 86

4.10 FAIR COIN FLIPS 89

4.11 MENTAL POKER 92

4.12 ONE-WAY ACCUMULATORS 95

4.13 ALL-OR-NOTHING DISCLOSURE OF SECRETS 96

4.14 KEY ESCROW 97

5 ADVANCED PROTOCOLS 101

5.1 ZERO-KNOWLEDGE PROOFS 101

5.2 ZERO-KNOWLEDGE PROOFS OF IDENTITY 109

5.3 BLIND SIGNATURES 112

5.4 IDENTITY-BASED PUBLIC-KEY CRYPTOGRAPHY 115

5.5 OBLIVIOUS TRANSFER 226

5.6 OBLIVIOUS SIGNATURES 227

5.7 SIMULTANEOUS CONTRACT SIGNING 228

5.8 DIGITAL CERTIFIED MAIL 122

5.9 SIMULTANEOUS EXCHANGE OF SECRETS 123

6 ESOTERIC PROTOCOLS 125

6.1 SECURE ELECTIONS 125

6.2 SECURE MULTIPARTY COMPUTATION 234

6.3 ANONYMOUS MESSAGE BROADCAST 237

6.4 DIGITAL CASH 239

PART II CRYPTOGRAPHIC TECHNIQUES

7 KEY LENGTH 151

7.1 SYMMETRIC KEY LENGTH 151

7.2 PUBLIC-KEY KEY LENGTH 158

7.3 COMPARING SYMMETRIC AND PUBLIC-KEY KEY LENGTH 165

7.4 BIRTHDAY ATTACKS AGAINST ONE-WAY HASH FUNCTIONS 165

7.5 HOW LONG SHOULD A KEY BE? 166

7.6 CAVEAT EMETOR 168

8 KEY MANAGEMENT 169

8.1 GENERATING KEYS 170

8.2 NONLINEAR KEYSPACES 175

8.3 TRANSFERRING KEYS 176

8.4 VERIFYING KEYS 178

8.5 USING KEYS 179

8.6 UPDATING KEYS 180

8.7 STORING KEYS 180

8.8 BACKUP KEYS 181

8.9 COMPROMISED KEYS 182

8.10 LIFETIME OF KEYS 183

8.11 DESTROYING KEYS 181

8.12 PUBLIC-KEY KEY MANAGEMENT 185

9 ALGORITHM TYPES AND MODES 189

9.1 ELECTRONIC CODEBOOK MODE 189

9.2 BLOCK REPLAY 191

9.3 CIPHER BLOCK CHAINING MODE 193

9.4 STREAM CIPHERS 197

9.5 SELF-SYNCHRONIZING STREAM CIPHERS 198

9.6 CIPHER-FEEDBACK MODE 200

9.7 SYNCHRONOUS STREAM CIPHERS 202

9.8 OUTPUT-FEEDBACK MODE 203

9.9 COUNTER MODE 205

9.10 OTHER BLOCK-CIPHER MODES 206

9.11 CHOOSING A CIPHER MODE 208

9.12 INTERLEAVING 210

9.13 BLOCK CIPHERS VERSUS STREAM CIPHERS 210

10 USING ALGORITHMS 213

10.1 CHOOSING AN ALGORITHM 214

10.2 PUBLIC-KEY CRYPTOGRAPHY VERSUS SYMMETRIC CRYPTOGRAPHY 216

10.3 ENCRYPTING COMMUNICATIONS CHANNELS 216

10.4 ENCRYPTING DATA FOR STORAGE 220

10.5 HARDWARE ENCRYPTION VERSUS SOFTWARE ENCRYPTION 223

10.6 COMPRESSION, ENCODING, AND ENCRYPTION 226

10.7 DETECTING ENCRYPTION 226

10.8 HIDING CIPHERTEXT IN CIPHERTEXT 227

10.9 DESTROYING INFORMATION 228

PART III CRYPTOGRAPHIC ALGORITHMS

11 MATHEMATICAL BACKGROUND 233

11.1 INFORMATION THEORY 233

11.2 COMPLEXITY THEORY 237

11.3 NUMBER THEORY 242

11.4 FACTORING 255

11.5 PRIME NUMBER GENERATION 258

11.6 DISCRETE LOGARITHMS IN A FINITE FIELD 262

12 DATA ENCRYPTION STANDARD (DES) 265

12.1 BACKGROUND 265

12.2 DESCRIPTION OF DES 270

12.3 SECURITY OF DES 278

12.4 DIFFERENTIAL AND LINEAR CRYPTANALYSIS 285

12.5 THE REAL DESIGN CRITERIA 293

12.6 DES VARIANTS 204

12.7 HOW SECURE IS DES TODAY? 300

13 OTHER BLOCK CIPHERS 303

13.1 LUCIFER 303

13.2 MADRYGA 304

13.3 NEWDES 306

13.4 FEAL 308

13.5 REDOC 311

13.6 LOKI 314

13.7 KHUFU AND KHAFRE 316

13.8 RC2 328

13.9 IDEA 319

13.10 MMB 325

13.11 CA-1.1 327

13.12 SKIPJACK 328

14 STILL OTHER BLOCK CIPHERS 332

14.1 GOST 332

14.2 CAST 334

14.3 BLOWFISH 336

14.4 SAFER 339

14.5 3-WAY 341

14.6 CRAB 342

14.7 SXAL8/MBAL 344

14.8 RC5 344

14.9 OTHER BLOCK ALGORITHMS 346

14.10 THEORY OF BLOCK CIPHER DESIGN 346

14.11 USING ONE-WAY HASH FUNCTIONS 351

14.12 CHOOSING A BLOCK ALGORITHM 354

15 COMBINING BLOCK CIPHERS 357

15.1 DOUBLE ENCRYPTION 357

15.2 TRIPLE ENCRYPTION 358

15.3 DOUBLING THE BLOCK LENGTH 363

15.4 OTHER MULTIPLE ENCRYPTION SCHEMES 363

15.5 CDME KEY SHORTENING 366

15.6 WHITENING 366

15.7 CASCADING MULTIPLE BLOCK ALGORITHMS 367

15.8 COMBINING MULTIPLE BLOCK ALGORITHMS 368

16 PSEUDO-KANDOM-SEQUENCE GENERATORS AND STREAM CIPHERS 369

16.1 LINEAR CONGRUENTIAL GENERATORS 369

16.2 LINEAR FEEDBACK SHIFT REGISTERS 372

16.3 DESIGN AND ANALYSIS OF STREAM CIPHERS 379

16.4 STREAM CIPHERS USING LFSRS 381

16.5 A5 389

16.6 HUGHES XPD/KPD 389

16.7 NANOTEO 390

16.8 RAMBUTAN 390

16.9 ADDITIVE GENERATORS 390

16.10 GIFFORD 392

16.11 ALGORITHM M 393

16.12 PKZ1P 394

17 OTHER STREAM CIPHERS AND REAL RANDOM-SEQUENCE GENERATORS 397

17.1 RC4 397

17.2 SEAL 398

17.3 WAKE 400

17.4 FEEDBACK WITH CARRY SHIFT REGISTERS 402

17.5 STREAM CIPHERS USING FCSRS 405

17.6 NONLINEAR-FEEDBACK SHIFT REGISTERS 412

17.7 OTHER STREAM CIPHERS 413

17.8 SYSTEM-THEORETIC APPROACH TO STREAM-CIPHER DESIGN 415

17.9 COMPLEXITY-THEMATIC APPROACH TO STREAM-CIPHER DESIGN 416

17.10 OTHER APPROACHES TO STREAM-CIPHER DESIGN 418

17.11 CASCADING MULTIPLE STREAM CIPHERS 419

17.12 CHOOSING A STREAM CIPHER 420

17.13 GENERATING MULTIPLE STREAMS FROM A SINGLE PSEUDO-RANDOM-SEQUENCE GENERATOR 420

17.14 REAL RANDOM-SEQUENCE GENERATORS 421

18 ONE-WAY HASH FUNCTIONS 429

18.1 BACKGROUND 429

18.2 SNEFRU 431

18.3 N-HASH 432

18.4 MD4 435

18.5 MD5 436

18.6 MD2 441

18.7 SECURE HASH ALGORITHM (SHA) 441

18.8 RIPE-MD 445

18.9 HAVAL 445

18.10 OTHER ONE-WAY HASH FUNCTIONS 446

18.11 ONE-WAY HASH FUNCTIONS USING SYMMETRIC BLOCK ALGORITHMS 446

18.12 USING PUBLIC-KEY ALGORITHMS 455

18.13 CHOOSING A ONE-WAY HASH FUNCTION 455

18.14 MESSAGE AUTHENTICATION CODES 455

19 PUBLIC-KEY ALGORITHMS 461

19.1 BACKGROUND 461

19.2 KNAPSACK ALGORITHMS 462

19.3 RSA 466

19.4 POHLIG-HELLMAN 474

19.5 RABIN 475

19.6 ELGAMAL 476

19.7 MCELIECE 479

19.8 ELLIPTIC CURVE CRYPTOSYSTEMS 480

19.9 LUC 481

19.10 FINITE AUTOMATON PUBLIC-KEY CRYPTOSYSTEMS 482

20 PUBLIC-KEY DIGITAL SIGNATURE ALGORITHMS 483

20.1 DIGITAL SIGNATURE ALGORITHM [DSA] 483

20.2 DSA VARIANTS 494

20.3 GOST DIGITAL SIGNATURE ALGORITHM 495

20.4 DISCRETE LOGARITHM SIGNATURE SCHEMES 496

20.5 ONG-SCHNORR-SHAMIR 498

20.6 ESIGN 499

20.7 CELLULAR AUTOMATA 500

20.8 OTHER PUBLIC-KEY ALGORITHMS 500

21 IDENTIFICATION SCHEMES 503

21.1 FEIGE-FIAT-SHAMIR 503

21.2 GUTLLOU-QUISQUATER 508

21.3 SCHNORR 510

21.4 CONVERTING IDENTIFICATION SCHEMES TO SIGNATURE SCHEMES 512

22 KEY-EXCHANGE ALGORITHMS 513

22.1 DIFFIE-HELLMAN 513

22.2 STATION-TO-STATION PROTOCOL 516

22.3 SHAMIR'S THREE-PASS PROTOCOL 516

22.4 COMSET 577

22.5 ENCRYPTED KEY EXCHANGE 518

22.6 FORTIFIED KEY NEGOTIATION 522

22.7 CONFERENCE KEY DISTRIBUTION AND SECRET BROADCASTING 523

23 SPECIAL ALGORITHMS FOR PROTOCOLS 527

23.1 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY 527

23.2 SECRET-SHARING ALGORITHMS 528

23.3 SUBLIMINAL CHANNEL 531

23.4 UNDENIABLE DIGITAL SIGNATURES 536

23.5 DESIGNATED CONFIRMER SIGNATURES 539

23.6 COMPUTING WITH ENCRYPTED DATA 540

23.7 FAIR COIN FLIPS 541

23.8 ONE-WAY ACCUMULATORS 543

23.9 ALL-OR-NOTHING DISCLOSURE OR SECRETS 543

23.10 FAIR AND FAILSAFE CRYPTOSYSTEMS 546

23.11 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE 548

23.12 BLIND SIGNATURES 549

23.13 OBLIVIOUS TRANSFER 550

23.14 SECURE MULTIPARTY COMPUTATION 552

23.15 PROBABILISTIC ENCRYPTION 552

23.16 QUANTUM CRYPTOGRAPHY 554

PART IV THE REAL WORLD

24 EXAMPLE IMPLEMENTATIONS 561

24.1 IBM SECRET-KEY MANAGEMENT PROTOCOL 561

24.2 MITRENET 562

24.3 ISDN 563

24.4 STU-III 565

24.5 KERBEROS 566

24.6 KRYPTOKNIGHT 572

24.7 SESAME 572

24.8 IBM COMMON CRYPTOGRAPHIC ARCHITECTURE 573

24.9 ISO AUTHENTICATION FRAMEWORK 574

24.10 PRIVACY-ENHANCED MAIL (PEM) 577

24.11 MESSAGE SECURITY PROTOCOL (MSP) 584

24.12 PRETTY GOOD PRIVACY (PGP) 584

24.13 SMART CARDS 587

24.14 PUBLIC-KEY CRYPTOGRAPHY STANDARDS (PKCS) 588

24.15 UNIVERSAL ELECTRONIC PAYMENT SYSTEM (UEPS) 589

24.16 CLIPPER 591

24.17 CAPSTONE 593

24.18 AT&T MODEL 3600 TELEPHONE SECURITY DEVICE (TSD) 594

25 POLITICS 597

25.1 NATIONAL SECURITY AGENCY (NSA) 597

25.2 NATIONAL COMPUTER SECURITY CENTER (NCSC) 599

25.3 NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY (NIST) 600

25.4 RSA DATA SECURITY, INC. 603

25.5 PUBLIC KEY PARTNERS 604

25.6 INTERNATIONAL ASSOCIATION FOR CRYPTOGRAPHIC RESEARCH (IACR) 605

25.7 RACE INTEGRITY PRIMITIVES EVALUATION (RIPE) 605

25.8 CONDITIONAL ACCESS FOR EUROPE (CAFE) 606

25.9 ISO/IEC 9979 607

25.10 PROFESSIONAL, CIVIL LIBERTIES, AND INDUSTRY GROUPS 608

25.11 SCICRYPT 608

25.12 CYPHERPUNKS 609

25.13 PATENTS 609

25.14 U.S. EXPORT RULES 610

25.15 FOREIGN IMPORT AND EXPORT OF CRYPTOGRAPHY 617

25.16 LEGAL ISSUES 618

Afterword by Matt Blaze 619

PART V SOURCE CODE

Source Code 623

References 675

Preface

There are two kinds of cryptography in this world: cryptography that will stop your kid sister from reading your files, and cryptography that will stop major governments from reading your files. This book is about the latter.

If I take a letter, lock it in a safe, hide the safe somewhere in New York, and then tell you to read the letter, that's not security. That's obscurity. On the other hand, if I take a letter and lock it in a safe, and then give you the safe along with the design specifications of the safe and a hundred identical safes with their combinations so that you and the world's best safecrackers can study the locking mechanism--and you still can't open the safe and read the letter, that's security.

For many years, this sort of cryptography was the exclusive domain of the military. The United States' National Security Agency (NSA), and their counterparts in the former Soviet Union, England, France, Israel, and elsewhere, have spent billions of dollars in the very serious game of securing their own communications while trying to break everyone else's. Private individuals, with far less expertise and budget, have been powerless to protect their own privacy against these governments.

During the last 20 years, public academic research in cryptography has exploded. While classical cryptography has been long used by ordinary citizens, since World War II computer cryptography was the exclusive domain of the world's militaries. Today, state-of-the-art computer cryptography is practiced outside the secured walls of the military agencies. The layperson can now employ security practices that can protect against the most powerful ofadversaries--security that may protect against military agencies for years to come.

Do average people really need this kind of security? Yes. They may be planning a political campaign, discussing taxes, or having an illicit affair. They may be designing a new product, discussing a marketing strategy, or planning a hostile business takeover. Or they may be living in a country that does not respect the rights of privacy of its citizens. They may be doing something that they feel shouldn't be illegal, but is. For whatever reason, the data and communications are personal, private, and no one else's business.

This book is being published in a tumultuous time. In 1994, the Clinton administration approved the Escrowed Encryption Standard (including the Clipper chip) and signed the Digital Telephony bill into law. Both of these initiatives try to ensure the government's ability to conduct electronic surveillance.

Some dangerously Orwellian assumptions are at work here: that the government has right to listen to private communications, and that there is something wrong with a private citizen trying to keep a secret from the government. Law enforcement has always been able to conduct court authorized surveillance if possible, but this is the first time that the people have been forced to take active measures to make themselves available for surveillance. These initiatives are not simply government proposals in some obscure area; they are preemptive and unilateral attempts to usurp powers that previously belonged to the people.

Clipper and Digital Telephony do not protect privacy; they force individuals to unconditionally trust that the government will respect their privacy. The same law enforcement authorities who illegally tapped Martin Luther King Jr.'s phones can easily tap a phone protected with Clipper. In the recent past, local police authorities have either been charged criminally or sued civilly in numerous jurisdictions--Maryland, Connecticut, Vermont, Georgia, Missouri, and Nevada--for conducting illegal wiretaps. It's a poor idea to deploy a technology that could some day facilitate a police state.

The lesson here is that it is insufficient to protect ourselves with laws; we need to protect ourselves with mathematics. Encryption is too important to be left solely to governments. This book gives you the tools you need to protect your own privacy; cryptography products may be declared illegal, but the information will never be.

How to Read This Book

I wrote Applied Cryptography to be a both a lively introduction to the field of cryptography and a comprehensive reference work. 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 nomeans intended to be comprehensive.

Also included are source code listings for ten algorithms discussed in Part III. I was unable to include all the code I wanted to due to space imitations, 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.

I have done my best to hunt down and eradicate all errors in this book, but many have assured me that it is an impossible task. Certainly, the second edition has far fewer errors than the first. An errata listing is available from me and will be periodically posted to the Usenet newsgroup sci.crypt. If any reader finds an error, please let me know. I'll send the first person to find each error in the book will get a free copy of the source code disk.

Acknowledgments

The list of people who had a hand in this book may seem unending, but all are worthy of mention. I would like to thank Don Alvarez, Ross Anderson, Dave Balenson, Karl Barrus, Steve Bellovin, Dan Bernstein, Eli Biham, Joan Boyar, Karen Cooper, Whit Diffie, Joan Feigenbaum, Phil Karn, Neal Koblitz, Xuejia Lai, Tom Leranth, Mike Markowitz, Ralph Merkle, Bill Patton, Peter Pearson, Charles Pfleeger, Ken Pizzini, Bart Preneel, Mark Riordan, Joachim Schurman, and Marc Schwartz for reading and editing all or parts of the first edition; Marc Vauclair for translating the first edition into French; Abe Abraham, Ross Anderson, Steve Bellovin, Eli Biham, Matt Bishop, Matt Blaze, Gary Carter, Jan Comenisch, Claude Cr=E9peau, Joan Daemen, Jorge Davila, Ed Dawson, Whit Diffie, Carl Ellison, Joan Feigenbaum, Niels Ferguson, Matt Franklin, Rosario Gennaro, Dieter Gollmann, Mark Goresky, Richard Graveman, Stuart Haber, Jingman He, Bob Hogue, Kenneth Iversen, Markus Jakobsson, Burt Kaliski, Phil Karn, John Kelsey, John Kennedy, Lars Knudsen, Paul Kocher, John Ladwig, Xuejia Lai, Arjen Lenstra, Paul Leyland, Mike Markowitz, Jim Massey, Bruce McNair, William Hugh Murray, Roger Needham, Clif Neuman, Kaisa Nyberg, Luke O'Connor, Peter Pearson, Ren=E9 Peralta, Yisrael Radai, Michael Roe, Phil Rogaway, Avi Rubin, Paul Rubin, Selwyn Russell, Kazue Sako, Mahmoud Salmasizadeh, Markus Stadler, Dmitry Titov, Jimmy Upton, Marc Vauclair, Serge Vaudenay, Gideon Yuval, and Glen Zorn for reading and editing all or parts of the second-edition; Lawrie Brown, Leisa Condie, Joan Daemen, Peter Gutmann, Alan Insley, Chris Johnston, John Kelsey, Xuejia Lai, Bill Leininger, Mike Markowitz, Richard Outerbridge, Peter Pearson, Ken Pizzini, Colin Plumb, RSA Data Security, Inc., Michael Roe, Michael Wood, and Phil Zimmermann for providing source code; Paul MacNerland for creating the figures for the first edition; Karen Cooper for copyediting the second edition; Beth Friedman for proofreading the second edition; Carol Kennedy for indexing the second edition; the readers of sci.crypt and the Cypherpunks mailing list for commenting on ideas, answering questions, and finding errors in the first edition; Randy Seuss for providing Internet access; Jeff Duntemann and Jon Erickson for helping me get started; assorted random Insleys for the impetus, encouragement, support, conversations, friendship, and dinners; and AT&T Bell Labs for firing me and making this all possible. All these people helped to create a far better book than I could have created alone.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews