Cryptography Engineering

Niels Ferguson is a cryptographer for Microsoft who has designed and implemented cryptographic algorithms, protocols, and large-scale security infrastructures. Bruce Schneier is an internationally renowned security technologist whose advice is sought by business, government, and the media. He is the author of Applied Cryptography, Secrets and Lies, and Schneier on Security.Tadayoshi Kohno is a professor at the University of Washington. He is known for his research and for developing innovative new approaches to cryptography and computer security education.

• Preface to Cryptography Engineering xxiiiHistory xxivExample Syllabi xxivAdditional Information xxviPreface to Practical Cryptography (the 1st Edition) xxviiHow to Read this Book xxixPart I Introduction 1Chapter 1 The Context of Cryptography 31.1 The Role of Cryptography 41.2 The Weakest Link Property 51.3 The Adversarial Setting 71.4 Professional Paranoia 81.4.1 Broader Benefits 91.4.2 Discussing Attacks 91.5 Threat Model 101.6 Cryptography Is Not the Solution 121.7 Cryptography Is Very Difficult 131.8 Cryptography Is the Easy Part 131.9 Generic Attacks 141.10 Security and Other Design Criteria 141.10.1 Security Versus Performance 141.10.2 Security Versus Features 171.10.3 Security Versus Evolving Systems 171.11 Further Reading 181.12 Exercises for Professional Paranoia 181.12.1 Current Event Exercises 191.12.2 Security Review Exercises 201.13 General Exercises 21Chapter 2 Introduction to Cryptography 232.1 Encryption 232.1.1 Kerckhoffs’ Principle 242.2 Authentication 252.3 Public-Key Encryption 272.4 Digital Signatures 292.5 PKI 292.6 Attacks 312.6.1 The Ciphertext-Only Model 312.6.2 The Known-Plaintext Model 312.6.3 The Chosen-Plaintext Model 322.6.4 The Chosen-Ciphertext Model 322.6.5 The Distinguishing Attack Goal 322.6.6 Other Types of Attack 332.7 Under the Hood 332.7.1 Birthday Attacks 332.7.2 Meet-in-the-Middle Attacks 342.8 Security Level 362.9 Performance 372.10 Complexity 372.11 Exercises 38Part II Message Security 41Chapter 3 Block Ciphers 433.1 What Is a Block Cipher? 433.2 Types of Attack 443.3 The Ideal Block Cipher 463.4 Definition of Block Cipher Security 463.4.1 Parity of a Permutation 493.5 Real Block Ciphers 503.5.1 DES 513.5.2 AES 543.5.3 Serpent 563.5.4 Twofish 573.5.5 Other AES Finalists 583.5.6 Which Block Cipher Should I Choose? 593.5.7 What Key Size Should I Use? 603.6 Exercises 61Chapter 4 Block Cipher Modes 634.1 Padding 644.2 ECB 654.3 CBC 654.3.1 Fixed IV 664.3.2 Counter IV 664.3.3 Random IV 664.3.4 Nonce-Generated IV 674.4 OFB 684.5 CTR 704.6 Combined Encryption and Authentication 714.7 Which Mode Should I Use? 714.8 Information Leakage 724.8.1 Chances of a Collision 734.8.2 How to Deal With Leakage 744.8.3 About Our Math 754.9 Exercises 75Chapter 5 Hash Functions 775.1 Security of Hash Functions 785.2 Real Hash Functions 795.2.1 A Simple But Insecure Hash Function 805.2.2 MD5 815.2.3 SHA-1 825.2.4 SHA-224, SHA-256, SHA-384, and SHA-512 825.3 Weaknesses of Hash Functions 835.3.1 Length Extensions 835.3.2 Partial-Message Collision 845.4 Fixing the Weaknesses 845.4.1 Toward a Short-term Fix 855.4.2 A More Efficient Short-term Fix 855.4.3 Another Fix 875.5 Which Hash Function Should I Choose? 875.6 Exercises 87Chapter 6 Message Authentication Codes 896.1 What a MAC Does 896.2 The Ideal MAC and MAC Security 906.3 CBC-MAC and CMAC 916.4 HMAC 936.5 GMAC 946.6 Which MAC to Choose? 956.7 Using a MAC 956.8 Exercises 97Chapter 7 The Secure Channel 997.1 Properties of a Secure Channel 997.1.1 Roles 997.1.2 Key 1007.1.3 Messages or Stream 1007.1.4 Security Properties 1017.2 Order of Authentication and Encryption 1027.3 Designing a Secure Channel: Overview 1047.3.1 Message Numbers 1057.3.2 Authentication 1067.3.3 Encryption 1067.3.4 Frame Format 1077.4 Design Details 1077.4.1 Initialization 1077.4.2 Sending a Message 1087.4.3 Receiving a Message 1097.4.4 Message Order 1117.5 Alternatives 1127.6 Exercises 113Chapter 8 Implementation Issues (I) 1158.1 Creating Correct Programs 1168.1.1 Specifications 1178.1.2 Test and Fix 1188.1.3 Lax Attitude 1198.1.4 So How Do We Proceed? 1198.2 Creating Secure Software 1208.3 Keeping Secrets 1208.3.1 Wiping State 1218.3.2 Swap File 1228.3.3 Caches 1248.3.4 Data Retention by Memory 1258.3.5 Access by Others 1278.3.6 Data Integrity 1278.3.7 What to Do 1288.4 Quality of Code 1288.4.1 Simplicity 1298.4.2 Modularization 1298.4.3 Assertions 1308.4.4 Buffer Overflows 1318.4.5 Testing 1318.5 Side-Channel Attacks 1328.6 Beyond this Chapter 1338.7 Exercises 133Part III Key Negotiation 135Chapter 9 Generating Randomness 1379.1 Real Random 1389.1.1 Problems With Using Real Random Data 1399.1.2 Pseudorandom Data 1409.1.3 Real Random Data and PRNGS 1409.2 Attack Models for a PRNG 1419.3 Fortuna 1429.4 The Generator 1439.4.1 Initialization 1459.4.2 Reseed 1459.4.3 Generate Blocks 1469.4.4 Generate Random Data 1469.4.5 Generator Speed 1479.5 Accumulator 1479.5.1 Entropy Sources 1479.5.2 Pools 1489.5.3 Implementation Considerations 1509.5.3.1 Distribution of Events Over Pools 1509.5.3.2 Running Time of Event Passing 1519.5.4 Initialization 1529.5.5 Getting Random Data 1539.5.6 Add an Event 1549.6 Seed File Management 1559.6.1 Write Seed File 1569.6.2 Update Seed File 1569.6.3 When to Read and Write the Seed File 1579.6.4 Backups and Virtual Machines 1579.6.5 Atomicity of File System Updates 1589.6.6 First Boot 1589.7 Choosing Random Elements 1599.8 Exercises 161Chapter 10 Primes 16310.1 Divisibility and Primes 16310.2 Generating Small Primes 16610.3 Computations Modulo a Prime 16710.3.1 Addition and Subtraction 16810.3.2 Multiplication 16910.3.3 Groups and Finite Fields 16910.3.4 The GCD Algorithm 17010.3.5 The Extended Euclidean Algorithm 17110.3.6 Working Modulo 2 17210.4 Large Primes 17310.4.1 Primality Testing 17610.4.2 Evaluating Powers 17810.5 Exercises 179Chapter 11 Diffie-Hellman 18111.1 Groups 18211.2 Basic DH 18311.3 Man in the Middle 18411.4 Pitfalls 18511.5 Safe Primes 18611.6 Using a Smaller Subgroup 18711.7 The Size of p 18811.8 Practical Rules 19011.9 What Can Go Wrong? 19111.10 Exercises 193Chapter 12 RSA 19512.1 Introduction 19512.2 The Chinese Remainder Theorem 19612.2.1 Garner’s Formula 19612.2.2 Generalizations 19712.2.3 Uses 19812.2.4 Conclusion 19912.3 Multiplication Modulo n 19912.4 RSA Defined 20012.4.1 Digital Signatures with RSA 20012.4.2 Public Exponents 20112.4.3 The Private Key 20212.4.4 The Size of n 20312.4.5 Generating RSA Keys 20312.5 Pitfalls Using RSA 20512.6 Encryption 20612.7 Signatures 20912.8 Exercises 211Chapter 13 Introduction to Cryptographic Protocols 21313.1 Roles 21313.2 Trust 21413.2.1 Risk 21513.3 Incentive 21513.4 Trust in Cryptographic Protocols 21713.5 Messages and Steps 21813.5.1 The Transport Layer 21913.5.2 Protocol and Message Identity 21913.5.3 Message Encoding and Parsing 22013.5.4 Protocol Execution States 22113.5.5 Errors 22113.5.6 Replay and Retries 22313.6 Exercises 225Chapter 14 Key Negotiation 22714.1 The Setting 22714.2 A First Try 22814.3 Protocols Live Forever 22914.4 An Authentication Convention 23014.5 A Second Attempt 23114.6 A Third Attempt 23214.7 The Final Protocol 23314.8 Different Views of the Protocol 23514.8.1 Alice’s View 23514.8.2 Bob’s View 23614.8.3 Attacker’s View 23614.8.4 Key Compromise 23814.9 Computational Complexity of the Protocol 23814.9.1 Optimization Tricks 23914.10 Protocol Complexity 24014.11 A Gentle Warning 24114.12 Key Negotiation from a Password 24114.13 Exercises 241Chapter 15 Implementation Issues (II) 24315.1 Large Integer Arithmetic 24315.1.1 Wooping 24515.1.2 Checking DH Computations 24815.1.3 Checking RSA Encryption 24815.1.4 Checking RSA Signatures 24915.1.5 Conclusion 24915.2 Faster Multiplication 24915.3 Side-Channel Attacks 25015.3.1 Countermeasures 25115.4 Protocols 25215.4.1 Protocols Over a Secure Channel 25315.4.2 Receiving a Message 25315.4.3 Timeouts 25515.5 Exercises 255Part IV Key Management 257Chapter 16 The Clock 25916.1 Uses for a Clock 25916.1.1 Expiration 25916.1.2 Unique Value 26016.1.3 Monotonicity 26016.1.4 Real-Time Transactions 26016.2 Using the Real-Time Clock Chip 26116.3 Security Dangers 26216.3.1 Setting the Clock Back 26216.3.2 Stopping the Clock 26216.3.3 Setting the Clock Forward 26316.4 Creating a Reliable Clock 26416.5 The Same-State Problem 26516.6 Time 26616.7 Closing Recommendations 26716.8 Exercises 267Chapter 17 Key Servers 26917.1 Basics 27017.2 Kerberos 27017.3 Simpler Solutions 27117.3.1 Secure Connection 27217.3.2 Setting Up a Key 27217.3.3 Rekeying 27217.3.4 Other Properties 27317.4 What to Choose 27317.5 Exercises 274Chapter 18 The Dream of PKI 27518.1 A Very Short PKI Overview 27518.2 PKI Examples 27618.2.1 The Universal PKI 27618.2.2 VPN Access 27618.2.3 Electronic Banking 27618.2.4 Refinery Sensors 27718.2.5 Credit Card Organization 27718.3 Additional Details 27718.3.1 Multilevel Certificates 27718.3.2 Expiration 27818.3.3 Separate Registration Authority 27918.4 Summary 28018.5 Exercises 280Chapter 19 PKI Reality 28119.1 Names 28119.2 Authority 28319.3 Trust 28419.4 Indirect Authorization 28519.5 Direct Authorization 28619.6 Credential Systems 28619.7 The Modified Dream 28819.8 Revocation 28919.8.1 Revocation List 28919.8.2 Fast Expiration 29019.8.3 Online Certificate Verification 29119.8.4 Revocation Is Required 29119.9 So What Is a PKI Good For? 29219.10 What to Choose 29319.11 Exercises 294Chapter 20 PKI Practicalities 29520.1 Certificate Format 29520.1.1 Permission Language 29520.1.2 The Root Key 29620.2 The Life of a Key 29720.3 Why Keys Wear Out 29820.4 Going Further 30020.5 Exercises 300Chapter 21 Storing Secrets 30121.1 Disk 30121.2 Human Memory 30221.2.1 Salting and Stretching 30421.3 Portable Storage 30621.4 Secure Token 30621.5 Secure UI 30721.6 Biometrics 30821.7 Single Sign-On 30921.8 Risk of Loss 31021.9 Secret Sharing 31021.10 Wiping Secrets 31121.10.1 Paper 31121.10.2 Magnetic Storage 31221.10.3 Solid-State Storage 31321.11 Exercises 313Part V Miscellaneous 315Chapter 22 Standards and Patents 31722.1 Standards 31722.1.1 The Standards Process 31722.1.1.1 The Standard 31922.1.1.2 Functionality 31922.1.1.3 Security 32022.1.2 SSL 32022.1.3 AES: Standardization by Competition 32122.2 Patents 322Chapter 23 Involving Experts 323Bibliography 327Index 339