Cryptography Engineering: Design Principles and Practical Applications PDF

Cryptography Engineering Cryptography Engineering Design Principles and Practical Applications Niels Ferguson Bruce Schneier Tadayoshi Kohno Wiley Publishing, Inc. Cryptography Engineering: Design Principles and Pract...

Cryptography Engineering Cryptography Engineering Design Principles and Practical Applications Niels Ferguson Bruce Schneier Tadayoshi Kohno Wiley Publishing, Inc. Cryptography Engineering: Design Principles and Practical Applications Published by Wiley Publishing, Inc. 10475 Crosspoint Boulevard Indianapolis, IN 46256 www.wiley.com Copyright © 2010 by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno Published by Wiley Publishing, Inc., Indianapolis, Indiana Published simultaneously in Canada ISBN: 978-0-470-47424-2 Manufactured in the United States of America 10 9 8 7 6 5 4 3 2 1 No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permissions. Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional services. If professional assistance is required, the services of a competent professional person should be sought. Neither the publisher nor the author shall be liable for damages arising herefrom. The fact that an organization or Web site is referred to in this work as a citation and/or a potential source of further information does not mean that the author or the publisher endorses the information the organization or Web site may provide or recommendations it may make. Further, readers should be aware that Internet Web sites listed in this work may have changed or disappeared between when this work was written and when it is read. For general information on our other products and services please contact our Customer Care Department within the United States at (877) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002. Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books. Library of Congress Control Number: 2010920648 Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. All other trademarks are the property of their respective owners. Wiley Publishing, Inc. is not associated with any product or vendor mentioned in this book. To Denise, who has made me truly happy. —Niels Ferguson To Karen; still, after all these years. —Bruce Schneier To Taryn, for making everything possible. —Tadayoshi Kohno  Credits Executive Editor Vice President and Executive Carol Long Publisher Barry Pruett Project Editor Tom Dinse Associate Publisher Jim Minatel Production Editor Daniel Scribner Project Coordinator, Cover Lynsey Stanford Editorial Director Robyn B. Siesky Proofreader Publication Services, Inc. Editorial Manager Mary Beth Wakefield Indexer Robert Swanson Production Manager Tim Tate Cover Image © DSGpro/istockphoto Vice President and Executive Group Publisher Cover Designer Richard Swadley Michael E. Trent vi  About the Authors Niels Ferguson has spent his entire career working as a cryptographic engi- neer. After studying mathematics in Eindhoven, he worked for DigiCash analyzing, designing, and implementing advanced electronic payment sys- tems that protect the privacy of the user. Later he worked as a cryptographic consultant for Counterpane and MacFergus, analyzing hundreds of systems and designing dozens. He was part of the team that designed the Twofish block cipher, performed some of the best initial analysis of AES, and co-designed the encryption system currently used by WiFi. Since 2004 he works at Microsoft where he helped design and implement the BitLocker disk encryption system. He currently works in the Windows cryptography team that is responsi- ble for the cryptographic implementations in Windows and other Microsoft products. Bruce Schneier is an internationally renowned security technologist, referred to by The Economist as a ‘‘security guru.’’ He is the author of eight books—including the best sellers Beyond Fear: Thinking Sensibly about Security in an Uncertain World, Secrets and Lies, and Applied Cryptography—as well as hundreds of articles and essays in national and international publications, and many more academic papers. His influential newsletter Crypto-Gram, and his blog Schneier on Security, are read by over 250,000 people. He is a frequent guest on television and radio, and is regularly quoted in the press on issues surrounding security and privacy. He has testified before Congress on multiple occasions, and has served on several government technical committees. Schneier is the Chief Security Technology Officer of BT. vii viii About the Authors Tadayoshi Kohno (Yoshi) is an assistant professor of computer science and engineering at the University of Washington. His research focuses on improv- ing the security and privacy properties of current and future technologies. He conducted the initial security analysis of the Diebold AccuVote-TS electronic voting machine source code in 2003, and has since turned his attention to securing emerging technologies ranging from wireless implantable pacemak- ers and defibrillators to cloud computing. He is the recipient of a National Science Foundation CAREER Award and an Alfred P. Sloan Research Fellow- ship. In 2007 he was awarded the MIT Technology Review TR-35 Award for his work in applied cryptography, recognizing him as one of the world’s top innovators under the age of 35. He received his PhD in computer science from the University of California at San Diego. Niels, Bruce, and Yoshi are part of the team that designed the Skein hash function, one of the competitors in NIST’s SHA-3 competition.  Acknowledgments for Cryptography Engineering We are deeply indebted to the cryptography and security community at large. This book would not have been possible without all of their efforts in advancing the field. This book also reflects our knowledge and experience as cryptographers, and we are deeply grateful to our peers and mentors for helping shape our understanding of cryptography. We thank Jon Callas, Ben Greenstein, Gordon Goetz, Alex Halderman, John Kelsey, Karl Koscher, Jack Lloyd, Gabriel Maganis, Theresa Portzer, Jesse Walker, Doug Whiting, Zooko Wilcox-O’Hearn, and Hussein Yapit for providing invaluable feedback on earlier versions of this book. Part of this book was developed and refined in an undergraduate com- puter security course at the University of Washington. We thank all those students, teaching assistants, and student mentors for the course. We espe- cially thank Joshua Barr, Jonathan Beall, Iva Dermendjieva, Lisa Glendenning, Steven Myhre, Erik Turnquist, and Heather Underwood for providing specific comments and suggestions on the text. We thank Melody Kadenko and Julie Svendsen for all their administrative support throughout this process. We are indebted to Beth Friedman for all her work copyediting this manuscript. Finally, we thank Carol Long, Tom Dinse, and the entire Wiley team for encouraging us to prepare this book and helping us all along the way. We are also indebted to all the other wonderful people in our lives who worked silently behind the scenes to make this book possible. ix  Acknowledgments for Practical Cryptography (the 1st Edition) This book is based on our collective experience over the many years we have worked in cryptography. We are heavily indebted to all the people we worked with. They made our work fun and helped us reach the insights that fill this book. We would also like to thank our customers, both for providing the funding that enabled us to continue our cryptography research and for providing the real-world experiences necessary to write this book. Certain individuals deserve special mention. Beth Friedman conducted an invaluable copyediting job, and Denise Dick greatly improved our manuscript by proofreading it. John Kelsey provided valuable feedback on the crypto- graphic contents. And the Internet made our collaboration possible. We would also like to thank Carol Long and the rest of the team at Wiley for bringing our ideas to reality. And finally, we would like to thank all of the programmers in the world who continue to write cryptographic code and make it available, free of charge, to the world. x  Contents at a Glance Preface to Cryptography Engineering xxiii Preface to Practical Cryptography (the 1st Edition) xxvii Part I Introduction 1 Chapter 1 The Context of Cryptography 3 Chapter 2 Introduction to Cryptography 23 Part II Message Security 41 Chapter 3 Block Ciphers 43 Chapter 4 Block Cipher Modes 63 Chapter 5 Hash Functions 77 Chapter 6 Message Authentication Codes 89 Chapter 7 The Secure Channel 99 Chapter 8 Implementation Issues (I) 115 Part III Key Negotiation 135 Chapter 9 Generating Randomness 137 Chapter 10 Primes 163 Chapter 11 Diffie-Hellman 181 Chapter 12 RSA 195 xi xii Contents at a Glance Chapter 13 Introduction to Cryptographic Protocols 213 Chapter 14 Key Negotiation 227 Chapter 15 Implementation Issues (II) 243 Part IV Key Management 257 Chapter 16 The Clock 259 Chapter 17 Key Servers 269 Chapter 18 The Dream of PKI 275 Chapter 19 PKI Reality 281 Chapter 20 PKI Practicalities 295 Chapter 21 Storing Secrets 301 Part V Miscellaneous 315 Chapter 22 Standards and Patents 317 Chapter 23 Involving Experts 323 Bibliography 327 Index 339  Contents Preface to Cryptography Engineering xxiii History xxiv Example Syllabi xxiv Additional Information xxvi Preface to Practical Cryptography (the 1st Edition) xxvii How to Read this Book xxix Part I Introduction 1 Chapter 1 The Context of Cryptography 3 1.1 The Role of Cryptography 4 1.2 The Weakest Link Property 5 1.3 The Adversarial Setting 7 1.4 Professional Paranoia 8 1.4.1 Broader Benefits 9 1.4.2 Discussing Attacks 9 1.5 Threat Model 10 1.6 Cryptography Is Not the Solution 12 1.7 Cryptography Is Very Difficult 13 1.8 Cryptography Is the Easy Part 13 1.9 Generic Attacks 14 1.10 Security and Other Design Criteria 14 1.10.1 Security Versus Performance 14 1.10.2 Security Versus Features 17 1.10.3 Security Versus Evolving Systems 17 xiii xiv Contents 1.11 Further Reading 18 1.12 Exercises for Professional Paranoia 18 1.12.1 Current Event Exercises 19 1.12.2 Security Review Exercises 20 1.13 General Exercises 21 Chapter 2 Introduction to Cryptography 23 2.1 Encryption 23 2.1.1 Kerckhoffs’ Principle 24 2.2 Authentication 25 2.3 Public-Key Encryption 27 2.4 Digital Signatures 29 2.5 PKI 29 2.6 Attacks 31 2.6.1 The Ciphertext-Only Model 31 2.6.2 The Known-Plaintext Model 31 2.6.3 The Chosen-Plaintext Model 32 2.6.4 The Chosen-Ciphertext Model 32 2.6.5 The Distinguishing Attack Goal 32 2.6.6 Other Types of Attack 33 2.7 Under the Hood 33 2.7.1 Birthday Attacks 33 2.7.2 Meet-in-the-Middle Attacks 34 2.8 Security Level 36 2.9 Performance 37 2.10 Complexity 37 2.11 Exercises 38 Part II Message Security 41 Chapter 3 Block Ciphers 43 3.1 What Is a Block Cipher? 43 3.2 Types of Attack 44 3.3 The Ideal Block Cipher 46 3.4 Definition of Block Cipher Security 46 3.4.1 Parity of a Permutation 49 3.5 Real Block Ciphers 50 3.5.1 DES 51 3.5.2 AES 54 3.5.3 Serpent 56  Contents xv 3.5.4 Twofish 57 3.5.5 Other AES Finalists 58 3.5.6 Which Block Cipher Should I Choose? 59 3.5.7 What Key Size Should I Use? 60 3.6 Exercises 61 Chapter 4 Block Cipher Modes 63 4.1 Padding 64 4.2 ECB 65 4.3 CBC 65 4.3.1 Fixed IV 66 4.3.2 Counter IV 66 4.3.3 Random IV 66 4.3.4 Nonce-Generated IV 67 4.4 OFB 68 4.5 CTR 70 4.6 Combined Encryption and Authentication 71 4.7 Which Mode Should I Use? 71 4.8 Information Leakage 72 4.8.1 Chances of a Collision 73 4.8.2 How to Deal With Leakage 74 4.8.3 About Our Math 75 4.9 Exercises 75 Chapter 5 Hash Functions 77 5.1 Security of Hash Functions 78 5.2 Real Hash Functions 79 5.2.1 A Simple But Insecure Hash Function 80 5.2.2 MD5 81 5.2.3 SHA-1 82 5.2.4 SHA-224, SHA-256, SHA-384, and SHA-512 82 5.3 Weaknesses of Hash Functions 83 5.3.1 Length Extensions 83 5.3.2 Partial-Message Collision 84 5.4 Fixing the Weaknesses 84 5.4.1 Toward a Short-term Fix 85 5.4.2 A More Efficient Short-term Fix 85 5.4.3 Another Fix 87 5.5 Which Hash Function Should I Choose? 87 5.6 Exercises 87 xvi Contents Chapter 6 Message Authentication Codes 89 6.1 What a MAC Does 89 6.2 The Ideal MAC and MAC Security 90 6.3 CBC-MAC and CMAC 91 6.4 HMAC 93 6.5 GMAC 94 6.6 Which MAC to Choose? 95 6.7 Using a MAC 95 6.8 Exercises 97 Chapter 7 The Secure Channel 99 7.1 Properties of a Secure Channel 99 7.1.1 Roles 99 7.1.2 Key 100 7.1.3 Messages or Stream 100 7.1.4 Security Properties 101 7.2 Order of Authentication and Encryption 102 7.3 Designing a Secure Channel: Overview 104 7.3.1 Message Numbers 105 7.3.2 Authentication 106 7.3.3 Encryption 106 7.3.4 Frame Format 107 7.4 Design Details 107 7.4.1 Initialization 107 7.4.2 Sending a Message 108 7.4.3 Receiving a Message 109 7.4.4 Message Order 111 7.5 Alternatives 112 7.6 Exercises 113 Chapter 8 Implementation Issues (I) 115 8.1 Creating Correct Programs 116 8.1.1 Specifications 117 8.1.2 Test and Fix 118 8.1.3 Lax Attitude 119 8.1.4 So How Do We Proceed? 119 8.2 Creating Secure Software 120 8.3 Keeping Secrets 120 8.3.1 Wiping State 121 8.3.2 Swap File 122  Contents xvii 8.3.3 Caches 124 8.3.4 Data Retention by Memory 125 8.3.5 Access by Others 127 8.3.6 Data Integrity 127 8.3.7 What to Do 128 8.4 Quality of Code 128 8.4.1 Simplicity 129 8.4.2 Modularization 129 8.4.3 Assertions 130 8.4.4 Buffer Overflows 131 8.4.5 Testing 131 8.5 Side-Channel Attacks 132 8.6 Beyond this Chapter 133 8.7 Exercises 133 Part III Key Negotiation 135 Chapter 9 Generating Randomness 137 9.1 Real Random 138 9.1.1 Problems With Using Real Random Data 139 9.1.2 Pseudorandom Data 140 9.1.3 Real Random Data and prngs 140 9.2 Attack Models for a prng 141 9.3 Fortuna 142 9.4 The Generator 143 9.4.1 Initialization 145 9.4.2 Reseed 145 9.4.3 Generate Blocks 146 9.4.4 Generate Random Data 146 9.4.5 Generator Speed 147 9.5 Accumulator 147 9.5.1 Entropy Sources 147 9.5.2 Pools 148 9.5.3 Implementation Considerations 150 9.5.3.1 Distribution of Events Over Pools 150 9.5.3.2 Running Time of Event Passing 151 9.5.4 Initialization 152 9.5.5 Getting Random Data 153 9.5.6 Add an Event 154 9.6 Seed File Management 155 9.6.1 Write Seed File 156 xviii Contents 9.6.2 Update Seed File 156 9.6.3 When to Read and Write the Seed File 157 9.6.4 Backups and Virtual Machines 157 9.6.5 Atomicity of File System Updates 158 9.6.6 First Boot 158 9.7 Choosing Random Elements 159 9.8 Exercises 161 Chapter 10 Primes 163 10.1 Divisibility and Primes 163 10.2 Generating Small Primes 166 10.3 Computations Modulo a Prime 167 10.3.1 Addition and Subtraction 168 10.3.2 Multiplication 169 10.3.3 Groups and Finite Fields 169 10.3.4 The GCD Algorithm 170 10.3.5 The Extended Euclidean Algorithm 171 10.3.6 Working Modulo 2 172 10.4 Large Primes 173 10.4.1 Primality Testing 176 10.4.2 Evaluating Powers 178 10.5 Exercises 179 Chapter 11 Diffie-Hellman 181 11.1 Groups 182 11.2 Basic DH 183 11.3 Man in the Middle 184 11.4 Pitfalls 185 11.5 Safe Primes 186 11.6 Using a Smaller Subgroup 187 11.7 The Size of p 188 11.8 Practical Rules 190 11.9 What Can Go Wrong? 191 11.10 Exercises 193 Chapter 12 RSA 195 12.1 Introduction 195 12.2 The Chinese Remainder Theorem 196 12.2.1 Garner’s Formula 196 12.2.2 Generalizations 197 12.2.3 Uses 198 12.2.4 Conclusion 199 12.3 Multiplication Modulo n 199  Contents xix 12.4 RSA Defined 200 12.4.1 Digital Signatures with RSA 200 12.4.2 Public Exponents 201 12.4.3 The Private Key 202 12.4.4 The Size of n 203 12.4.5 Generating RSA Keys 203 12.5 Pitfalls Using RSA 205 12.6 Encryption 206 12.7 Signatures 209 12.8 Exercises 211 Chapter 13 Introduction to Cryptographic Protocols 213 13.1 Roles 213 13.2 Trust 214 13.2.1 Risk 215 13.3 Incentive 215 13.4 Trust in Cryptographic Protocols 217 13.5 Messages and Steps 218 13.5.1 The Transport Layer 219 13.5.2 Protocol and Message Identity 219 13.5.3 Message Encoding and Parsing 220 13.5.4 Protocol Execution States 221 13.5.5 Errors 221 13.5.6 Replay and Retries 223 13.6 Exercises 225 Chapter 14 Key Negotiation 227 14.1 The Setting 227 14.2 A First Try 228 14.3 Protocols Live Forever 229 14.4 An Authentication Convention 230 14.5 A Second Attempt 231 14.6 A Third Attempt 232 14.7 The Final Protocol 233 14.8 Different Views of the Protocol 235 14.8.1 Alice’s View 235 14.8.2 Bob’s View 236 14.8.3 Attacker’s View 236 14.8.4 Key Compromise 238 14.9 Computational Complexity of the Protocol 238 14.9.1 Optimization Tricks 239 14.10 Protocol Complexity 240 xx Contents 14.11 A Gentle Warning 241 14.12 Key Negotiation from a Password 241 14.13 Exercises 241 Chapter 15 Implementation Issues (II) 243 15.1 Large Integer Arithmetic 243 15.1.1 Wooping 245 15.1.2 Checking DH Computations 248 15.1.3 Checking RSA Encryption 248 15.1.4 Checking RSA Signatures 249 15.1.5 Conclusion 249 15.2 Faster Multiplication 249 15.3 Side-Channel Attacks 250 15.3.1 Countermeasures 251 15.4 Protocols 252 15.4.1 Protocols Over a Secure Channel 253 15.4.2 Receiving a Message 253 15.4.3 Timeouts 255 15.5 Exercises 255 Part IV Key Management 257 Chapter 16 The Clock 259 16.1 Uses for a Clock 259 16.1.1 Expiration 259 16.1.2 Unique Value 260 16.1.3 Monotonicity 260 16.1.4 Real-Time Transactions 260 16.2 Using the Real-Time Clock Chip 261 16.3 Security Dangers 262 16.3.1 Setting the Clock Back 262 16.3.2 Stopping the Clock 262 16.3.3 Setting the Clock Forward 263 16.4 Creating a Reliable Clock 264 16.5 The Same-State Problem 265 16.6 Time 266 16.7 Closing Recommendations 267 16.8 Exercises 267 Chapter 17 Key Servers 269 17.1 Basics 270 17.2 Kerberos 270  Contents xxi 17.3 Simpler Solutions 271 17.3.1 Secure Connection 272 17.3.2 Setting Up a Key 272 17.3.3 Rekeying 272 17.3.4 Other Properties 273 17.4 What to Choose 273 17.5 Exercises 274 Chapter 18 The Dream of PKI 275 18.1 A Very Short PKI Overview 275 18.2 PKI Examples 276 18.2.1 The Universal PKI 276 18.2.2 VPN Access 276 18.2.3 Electronic Banking 276 18.2.4 Refinery Sensors 277 18.2.5 Credit Card Organization 277 18.3 Additional Details 277 18.3.1 Multilevel Certificates 277 18.3.2 Expiration 278 18.3.3 Separate Registration Authority 279 18.4 Summary 280 18.5 Exercises 280 Chapter 19 PKI Reality 281 19.1 Names 281 19.2 Authority 283 19.3 Trust 284 19.4 Indirect Authorization 285 19.5 Direct Authorization 286 19.6 Credential Systems 286 19.7 The Modified Dream 288 19.8 Revocation 289 19.8.1 Revocation List 289 19.8.2 Fast Expiration 290 19.8.3 Online Certificate Verification 291 19.8.4 Revocation Is Required 291 19.9 So What Is a PKI Good For? 292 19.10 What to Choose 293 19.11 Exercises 294 xxii Contents Chapter 20 PKI Practicalities 295 20.1 Certificate Format 295 20.1.1 Permission Language 295 20.1.2 The Root Key 296 20.2 The Life of a Key 297 20.3 Why Keys Wear Out 298 20.4 Going Further 300 20.5 Exercises 300 Chapter 21 Storing Secrets 301 21.1 Disk 301 21.2 Human Memory 302 21.2.1 Salting and Stretching 304 21.3 Portable Storage 306 21.4 Secure Token 306 21.5 Secure UI 307 21.6 Biometrics 308 21.7 Single Sign-On 309 21.8 Risk of Loss 310 21.9 Secret Sharing 310 21.10 Wiping Secrets 311 21.10.1 Paper 311 21.10.2 Magnetic Storage 312 21.10.3 Solid-State Storage 313 21.11 Exercises 313 Part V Miscellaneous 315 Chapter 22 Standards and Patents 317 22.1 Standards 317 22.1.1 The Standards Process 317 22.1.1.1 The Standard 319 22.1.1.2 Functionality 319 22.1.1.3 Security 320 22.1.2 SSL 320 22.1.3 AES: Standardization by Competition 321 22.2 Patents 322 Chapter 23 Involving Experts 323 Bibliography 327 Index 339  Preface to Cryptography Engineering Most books cover what cryptography is—what current cryptographic designs are and how existing cryptographic protocols, like SSL/TLS, work. Bruce Schneier’s earlier book, Applied Cryptography, is like this. Such books serve as invaluable references for anyone working with cryptography. But such books are also one step removed from the needs of cryptography and security engineers in practice. Cryptography and security engineers need to know more than how current cryptographic protocols work; they need to know how to use cryptography. To know how to use cryptography, one must learn to think like a cryp- tographer. This book is designed to help you achieve that goal. We do this through immersion. Rather than broadly discuss all the protocols one might encounter in cryptography, we dive deeply into the design and analysis of specific, concrete protocols. We walk you—hand-in-hand—through how we go about designing cryptographic protocols. We share with you the reasons we make certain design decisions over others, and point out potential pitfalls along the way. By learning how to think like a cryptographer, you will also learn how to be a more intelligent user of cryptography. You will be able to look at existing cryptography toolkits, understand their core functionality, and know how to use them. You will also better understand the challenges involved with cryptography, and how to think about and overcome those challenges. This book also serves as a gateway to learning about computer security. Computer security is, in many ways, a superset of cryptography. Both com- puter security and cryptography are about designing and evaluating objects (systems or algorithms) intended to behave in certain ways even in the presence xxiii xxiv Preface to Cryptography Engineering of an adversary. In this book, you will learn how to think about the adversary in the context of cryptography. Once you know how to think like adversaries, you can apply that mindset to the security of computer systems in general. History This book began with Practical Cryptography by Niels Ferguson and Bruce Schneier, and evolved with the addition of Tadayoshi Kohno—Yoshi—as an author. Yoshi is a professor of computer science and engineering at the University of Washington, and also a past colleague of Niels and Bruce. Yoshi took Practical Cryptography and revised it to be suitable for classroom use and self-study, while staying true to the goals and themes of Niels’s and Bruce’s original book. Example Syllabi There are numerous ways to read this book. You can use it as a self-study guide for applied cryptographic engineering, or you can use it in a course. A quarter- or semester-long course on computer security might use this book as the foundation for a 6-week intensive unit on cryptography. This book could also serve as the foundation for a full quarter- or semester-long course on cryptography, augmented with additional advanced material if time allows. To facilitate classroom use, we present several possible syllabi below. The following syllabus is appropriate for a 6-week intensive unit on cryp- tography. For this 6-week unit, we assume that the contents of Chapter 1 are discussed separately, in the broader context of computer security in general. Week 1: Chapters 2, 3, and 4; Week 2: Chapters 5, 6, and 7; Week 3: Chapters 8, 9, and 10; Week 4: Chapters 11, 12, and 13; Week 5: Chapters 14, 15, 16, and 17; Week 6: Chapters 18, 19, 20, and 21. The following syllabus is for a 10-week quarter on cryptography engineering. Week 1: Chapters 1 and 2; Week 2: Chapters 3 and 4;  Preface to Cryptography Engineering xxv Week 3: Chapters 5 and 6; Week 4: Chapters 7 and 8; Week 5: Chapters 9 and 10; Week 6: Chapters 11 and 12; Week 7: Chapters 13 and 14; Week 8: Chapters 15, 16, and 17; Week 9: Chapters 18, 19, 20; Week 10: Chapter 21. The following syllabus is appropriate for schools with 12-week semesters. It can also be augmented with advanced materials in cryptography or computer security for longer semesters. Week 1: Chapters 1 and 2; Week 2: Chapters 3 and 4; Week 3: Chapters 5 and 6; Week 4: Chapter 7; Week 5: Chapters 8 and 9; Week 6: Chapters 9 (continued) and 10; Week 7: Chapters 11 and 12; Week 8: Chapters 13 and 14; Week 9: Chapters 15 and 16; Week 10: Chapters 17 and 18; Week 11: Chapters 19 and 20; Week 12: Chapter 21. This book has several types of exercises, and we encourage readers to com- plete as many of these exercises as possible. There are traditional exercises designed to test your understanding of the technical properties of cryptog- raphy. However, since our goal is to help you learn how to think about cryptography in real systems, we have also introduced a set of non-traditional exercises (see Section 1.12). Cryptography doesn’t exist in isolation; rather, cryptography is only part of a larger ecosystem consisting of other hardware xxvi Preface to Cryptography Engineering and software systems, people, economics, ethics, cultural differences, politics, law, and so on. Our non-traditional exercises are explicitly designed to force you to think about cryptography in the context of real systems and the sur- rounding ecosystem. These exercises will provide you with an opportunity to directly apply the contents of this book as thought exercises to real systems. Moreover, by weaving these exercises together throughout this book, you will be able to see your knowledge grow as you progress from chapter to chapter. Additional Information While we strove to make this book as error-free as possible, errors have undoubtedly crept in. We maintain an online errata list for this book. The procedure for using this errata list is below. Before reading this book, go to http://www.schneier.com/ce.html and download the current list of corrections. If you find an error in the book, please check to see if it is already on the list. If it is not on the list, please alert us at cryptographyengineering @schneier.com. We will add the error to the list. We wish you a wonderful journey through cryptography engineering. Cryptography is a wonderful and fascinating topic. We hope you learn a great deal from this book, and come to enjoy cryptography engineering as much as we do. October 2009 Niels Ferguson Bruce Schneier Redmond, Washington Minneapolis, Minnesota USA USA [email protected] [email protected] Tadayoshi Kohno Seattle, Washington USA [email protected]  Preface to Practical Cryptography (the 1st Edition) In the past decade, cryptography has done more to damage the security of digital systems than it has to enhance it. Cryptography burst onto the world stage in the early 1990s as the securer of the Internet. Some saw cryptography as a great technological equalizer, a mathematical tool that would put the lowliest privacy-seeking individual on the same footing as the greatest national intelligence agencies. Some saw it as the weapon that would bring about the downfall of nations when governments lost the ability to police people in cyberspace. Others saw it as the perfect and terrifying tool of drug dealers, terrorists, and child pornographers, who would be able to communicate in perfect secrecy. Even those with more realistic attitudes imagined cryptography as a technology that would enable global commerce in this new online world. Ten years later, none of this has come to pass. Despite the prevalence of cryptography, the Internet’s national borders are more apparent than ever. The ability to detect and eavesdrop on criminal communications has more to do with politics and human resources than mathematics. Individuals still don’t stand a chance against powerful and well-funded government agencies. And the rise of global commerce had nothing to do with the prevalence of cryptography. For the most part, cryptography has done little more than give Internet users a false sense of security by promising security but not delivering it. And that’s not good for anyone except the attackers. The reasons for this have less to do with cryptography as a mathematical science, and much more to do with cryptography as an engineering discipline. We have developed, implemented, and fielded cryptographic systems over the xxvii xxviii Preface to Practical Cryptography (the 1st Edition) past decade. What we’ve been less effective at is converting the mathematical promise of cryptographic security into a reality of security. As it turns out, this is the hard part. Too many engineers consider cryptography to be a sort of magic security dust that they can sprinkle over their hardware or software, and which will imbue those products with the mythical property of ‘‘security.’’ Too many consumers read product claims like ‘‘encrypted’’ and believe in that same magic security dust. Reviewers are no better, comparing things like key lengths and on that basis, pronouncing one product to be more secure than another. Security is only as strong as the weakest link, and the mathematics of cryp- tography is almost never the weakest link. The fundamentals of cryptography are important, but far more important is how those fundamentals are imple- mented and used. Arguing about whether a key should be 112 bits or 128 bits long is rather like pounding a huge stake into the ground and hoping the attacker runs right into it. You can argue whether the stake should be a mile or a mile-and-a-half high, but the attacker is simply going to walk around the stake. Security is a broad stockade: it’s the things around the cryptography that make the cryptography effective. The cryptographic books of the last decade have contributed to that aura of magic. Book after book extolled the virtues of, say, 112-bit triple-DES without saying much about how its keys should be generated or used. Book after book presented complicated protocols for this or that without any mention of the business and social constraints within which those protocols would have to work. Book after book explained cryptography as a pure mathematical ideal, unsullied by real-world constraints and realities. But it’s exactly those real- world constraints and realities that mean the difference between the promise of cryptographic magic and the reality of digital security. Practical Cryptography is also a book about cryptography, but it’s a book about sullied cryptography. Our goal is to explicitly describe the real-world constraints and realities of cryptography, and to talk about how to engineer secure cryptographic systems. In some ways, this book is a sequel to Bruce Schneier’s first book, Applied Cryptography, which was first published ten years ago. But while Applied Cryptography gives a broad overview of cryptography and the myriad possibilities cryptography can offer, this book is narrow and focused. We don’t give you dozens of choices; we give you one option and tell you how to implement it correctly. Applied Cryptography displays the wondrous possibilities of cryptography as a mathematical science—what is possible and what is attainable; Practical Cryptography gives concrete advice to people who design and implement cryptographic systems. Practical Cryptography is our attempt to bridge the gap between the promise of cryptography and the reality of cryptography. It’s our attempt to teach engineers how to use cryptography to increase security.  Preface to Practical Cryptography (the 1st Edition) xxix We’re qualified to write this book because we’re both seasoned cryptogra- phers. Bruce is well known from his books Applied Cryptography and Secrets and Lies, and from his newsletter ‘‘Crypto-Gram.’’ Niels Ferguson cut his cryp- tographic teeth building cryptographic payment systems at the CWI (Dutch National Research Institute for Mathematics and Computer Science) in Ams- terdam, and later at a Dutch company called DigiCash. Bruce designed the Blowfish encryption algorithm, and both of us were on the team that designed Twofish. Niels’s research led to the first example of the current generation of efficient anonymous payment protocols. Our combined list of academic papers runs into three digits. More importantly, we both have extensive experience in designing and building cryptographic systems. From 1991 to 1999, Bruce’s consulting com- pany Counterpane Systems provided design and analysis services to some of the largest computer and financial companies in the world. More recently, Counterpane Internet Security, Inc., has provided Managed Security Monitor- ing services to large corporations and government agencies worldwide. Niels also worked at Counterpane before founding his own consulting company, MacFergus. We’ve seen cryptography as it lives and breathes in the real world, as it flounders against the realities of engineering or even worse, against the realities of business. We’re qualified to write this book because we’ve had to write it again and again for our consulting clients. How to Read this Book Practical Cryptography is more a narrative than a reference. It follows the design of a cryptographic system from the specific algorithm choices, out- wards through concentric rings to the infrastructure required to make it work. We discuss a single cryptographic problem—one of establishing a means for two people to communicate securely—that’s at the heart of almost every cryp- tographic application. By focusing on one problem and one design philosophy for solving that problem, it is our belief that we can teach more about the realities of cryptographic engineering. We think cryptography is just about the most fun you can have with mathematics. We’ve tried to imbue this book with that feeling of fun, and we hope you enjoy the results. Thanks for coming along on our ride. Niels Ferguson Bruce Schneier January 2003  Part I Introduction In This Part Chapter 1: The Context of Cryptography Chapter 2: Introduction to Cryptography  CHAPTER 1 The Context of Cryptography Cryptography is the art and science of encryption. At least, that is how it started out. Nowadays it is much broader, covering authentication, digital signatures, and many more elementary security functions. It is still both an art and a science: to build good cryptographic systems requires a scientific background and a healthy dose of the black magic that is a combination of experience and the right mentality for thinking about security problems. This book is designed to help you cultivate these critical ingredients. Cryptography is an extremely varied field. At a cryptography research conference, you can encounter a wide range of topics, including computer security, higher algebra, economics, quantum physics, civil and criminal law, statistics, chip designs, extreme software optimization, politics, user interface design, and everything in between. In some ways, this book concentrates on only a very small part of cryptography: the practical side. We aim to teach you how to implement cryptography in real-world systems. In other ways, this book is much broader, helping you gain experience in security engineering and nurturing your ability to think about cryptography and security issues like a security professional. These broader lessons will help you successfully tackle security challenges, whether directly related to cryptography or not. The variety in this field is what makes cryptography such a fascinating area to work in. It is really a mixture of widely different fields. There is always something new to learn, and new ideas come from all directions. It is also one of the reasons why cryptography is so difficult. It is impossible to understand it all. There is nobody in the world who knows everything about cryptography. There isn’t even anybody who knows most of it. We certainly don’t know 3 4 Part I Introduction everything there is to know about the subject of this book. So here is your first lesson in cryptography: keep a critical mind. Don’t blindly trust anything, even if it is in print. You’ll soon see that having this critical mind is an essential ingredient of what we call ‘‘professional paranoia.’’ 1.1 The Role of Cryptography Cryptography by itself is fairly useless. It has to be part of a much larger system. We like to compare cryptography to locks in the physical world. A lock by itself is a singularly useless thing. It needs to be part of a much larger system. This larger system can be a door on a building, a chain, a safe, or something else. This larger system even extends to the people who are supposed to use the lock: they need to remember to actually lock it and to not leave the key around for anyone to find. The same goes for cryptography: it is just a small part of a much larger security system. Even though cryptography is only a small part of the security system, it is a very critical part. Cryptography is the part that has to provide access to some people but not to others. This is very tricky. Most parts of the security system are like walls and fences in that they are designed to keep everybody out. Cryptography takes on the role of the lock: it has to distinguish between ‘‘good’’ access and ‘‘bad’’ access. This is much more difficult than just keeping everybody out. Therefore, the cryptography and its surrounding elements form a natural point of attack for any security system. This does not imply that cryptography is always the weak point of a system. In some cases, even bad cryptography can be much better than the rest of the security system. You have probably seen the door to a bank vault, at least in the movies. You know, 10-inch-thick, hardened steel, with huge bolts to lock it in place. It certainly looks impressive. We often find the digital equivalent of such a vault door installed in a tent. The people standing around it are arguing over how thick the door should be, rather than spending their time looking at the tent. It is all too easy to spend hours arguing over the exact key length of cryptographic systems, but fail to notice or fix buffer overflow vulnerabilities in a Web application. The result is predictable: the attackers find a buffer overflow and never bother attacking the cryptography. Cryptography is only truly useful if the rest of the system is also sufficiently secure against the attackers. There are, however, reasons why cryptography is important to get right, even in systems that have other weaknesses. Different weaknesses are useful to different attackers in different ways. For example, an attacker who breaks the cryptography has a low chance of being detected. There will be no traces of the attack, since the attacker’s access will look just like a ‘‘good’’ access. This  Chapter 1 The Context of Cryptography 5 is comparable to a real-life break-in. If the burglar uses a crowbar to break in, you will at least see that a break-in has occurred. If the burglar picks the lock, you might never find out that a burglary occurred. Many modes of attack leave traces, or disturb the system in some way. An attack on the cryptography can be fleeting and invisible, allowing the attacker to come back again and again. 1.2 The Weakest Link Property Print the following sentence in a very large font and paste it along the top of your monitor. A security system is only as strong as its weakest link. Look at it every day, and try to understand the implications. The weakest link property is one of the main reasons why security systems are so fiend- ishly hard to get right. Every security system consists of a large number of parts. We must assume that our opponent is smart and that he is going to attack the system at the weakest part. It doesn’t matter how strong the other parts are. Just as in a chain, the weakest link will break first. It doesn’t matter how strong the other links in the chain are. Niels used to work in an office building where all the office doors were locked every night. Sounds very safe, right? The only problem was that the building had a false ceiling. You could lift up the ceiling panels and climb over any door or wall. If you took out the ceiling panels, the whole floor looked like a set of tall cubicles with doors on them. And these doors had locks. Sure, locking the doors made it slightly harder for the burglar, but it also made it harder for the security guard to check the offices during his nightly rounds. It isn’t clear at all whether the overall security was improved or made worse by locking the doors. In this example, the weakest link property prevented the locking of the doors from being very effective. It might have improved the strength of a particular link (the door), but there was another link (the ceiling) that was still weak. The overall effect of locking the doors was at best very small, and its negative side effects could well have exceeded its positive contribution. To improve the security of a system, we must improve the weakest link. But to do that, we need to know what the links are and which ones are weak. This is best done using a hierarchical tree structure. Each part of a system has multiple links, and each link in turn has sublinks. We can organize the links into what we call an attack tree. We give an example in Figure 1.1. Let’s say that we want to break into a bank vault. The first-level links are the walls, the floor, the door, and the ceiling. Breaking through any one of them gets 6 Part I Introduction us into the vault. Let’s look at the door in more detail. The door system has its own links: the connection between the door frame and the walls, the lock, the door itself, the bolts that keep the door in the door frame, and the hinges. We could continue by discussing individual lines of attack on the lock, one of which is to acquire a key, which in turn leads to a whole tree about stealing the key in some way. enter vault through through through through walls floor door ceiling through defeat break disable break connection lock door bolts hinge door-wall Figure 1.1: Example attack tree for a vault We can analyze each link and split it up into other links until we are left with single components. Doing this for a real system can be an enormous amount of work. If we were concerned about an attacker stealing the diamonds stored in the vault, then Figure 1.1 is also just one piece of a larger attack tree; an attacker could trick an employee into removing the diamonds from the vault and steal them once removed. Attack trees provide valuable insight as to possible lines of attack. Trying to secure a system without first doing such an analysis very often leads to useless work. In this book, we work only on limited components—the ones that can be solved with cryptography—and we will not explicitly talk about their attack trees. But you should be certain to understand how to use an attack tree to study a larger system and to assess the role of cryptography in that system. The weakest link property affects our work in many ways. For example, it is tempting to assume that users have proper passwords, but in practice they don’t. They often choose simple short passwords. Users may go to almost any length not to be bothered by security systems. Writing a password on a sticky note and attaching it to their monitor is just one of many things they might do. You can never ignore issues like this because they always affect the end result. If you design a system that gives users a new 12-digit random password every week, you can be sure they will stick it on their monitors. This weakens an already weak link, and is bad for the overall security of the system.  Chapter 1 The Context of Cryptography 7 Strictly speaking, strengthening anything but the weakest link is useless. In practice, things are not so clear-cut. The attacker may not know what the weakest link is and attack a slightly stronger one. The weakest link may be different for different types of attackers. The strength of any link depends on the attacker’s skill and tools and access to the system. The link an attacker might exploit may also depend on the attacker’s goals. So which link is the weakest depends on the situation. It is therefore worthwhile to strengthen any link that could in a particular situation be the weakest. Moreover, it’s worth strengthening multiple links so that if one link does fail, the remaining links can still provide security—a property known as defense in depth. 1.3 The Adversarial Setting One of the biggest differences between security systems and almost any other type of engineering is the adversarial setting. Most engineers have to contend with problems like storms, heat, and wear and tear. All of these factors affect designs, but their effect is fairly predictable to an experienced engineer. Not so in security systems. Our opponents are intelligent, clever, malicious, and devious; they’ll do things nobody had ever thought of before. They don’t play by the rules, and they are completely unpredictable. That is a much harder environment to work in. Many of us remember the film in which the Tacoma Narrows suspension bridge wobbles and twists in a steady wind until it breaks and falls into the water. It is a famous piece of film, and the collapse taught bridge engineers a valuable lesson. Slender suspension bridges can have a resonance mode in which a steady wind can cause the whole structure to oscillate, and finally break. How do they prevent the same thing from happening with newer bridges? Making the bridge significantly stronger to resist the oscillations would be too expensive. The most common technique used is to change the aerodynamics of the bridge. The deck is made thicker, which makes it much harder for the wind to push up and down on the deck. Sometimes railings are used as spoilers to make the bridge deck behave less like a wing that lifts up in the wind. This works because wind is fairly predictable, and does not change its behavior in an active attempt to destroy the bridge. A security engineer has to take a malicious wind into account. What if the wind blows up and down instead of just from the side, and what if it changes directions at the right frequency for the bridge to resonate? Bridge engineers will dismiss this kind of talk out of hand: ‘‘Don’t be silly, the wind doesn’t blow that way.’’ That certainly makes the bridge engineers’ jobs much easier. Cryptographers don’t have that luxury. Security systems are attacked by clever and malicious attackers. We have to consider all types of attack. 8 Part I Introduction The adversarial setting is a very harsh environment to work in. There are no rules in this game, and the deck is stacked against us. We talk about an ‘‘attacker’’ in an abstract sense, but we don’t know who she is, what she knows, what her goal is, when she will attack, or what her resources are. Since the attack may occur long after we design the system, she has the advantage of five or ten years’ more research, and can use technology of the future that is not available to us. And with all those advantages, she only has to find a single weak spot in our system, whereas we have to protect all areas. Still, our mission is to build a system that can withstand it all. This creates a fundamental imbalance between the attacker of a system and the defender. This is also what makes the world of cryptography so exciting. 1.4 Professional Paranoia To work in this field, you have to become devious yourself. You have to think like a malicious attacker to find weaknesses in your own work. This affects the rest of your life as well. Everybody who works on practical cryptographic systems has experienced this. Once you start thinking about how to attack systems, you apply that to everything around you. You suddenly see how you could cheat the people around you, and how they could cheat you. Cryptographers are professional paranoids. It is important to separate your professional paranoia from your real-world life so as to not go completely crazy. Most of us manage to preserve some sanity... we think.1 In fact, we think that this practical paranoia can be a lot of fun. Developing this mindset will help you observe things about systems and your environment that most other people don’t notice. Paranoia is very useful in this work. Suppose you work on an electronic pay- ment system. There are several parties involved in this system: the customer, the merchant, the customer’s bank, and the merchant’s bank. It can be very difficult to figure out what the threats are, so we use the paranoia model. For each participant, we assume that everybody else is part of a big conspiracy to defraud this one participant. And we also assume that the attacker might have any number of other goals, such as compromising the privacy of a participant’s transactions or denying a participant’s access to the system at a critical time. If your cryptographic system can survive the paranoia model, it has at least a fighting chance of surviving in the real world. We will interchangeably refer to professional paranoia and the paranoia model as the security mindset. 1 But remember: the fact that you are not paranoid doesn’t mean they are not out to get you or compromise your system.  Chapter 1 The Context of Cryptography 9 1.4.1 Broader Benefits Once you develop a sense of professional paranoia, you will never look at systems the same way. This mindset will benefit you throughout your career, regardless of whether you become a cryptographer or not. Even if you don’t become a cryptographer, you may someday find yourself working on the design, implementation, or evaluation of new computer software or hardware systems. If you have the security mindset, then you will be constantly thinking about what an attacker might try to do to your system. This will nicely position you to identify potential security problems with these systems early. You may not always be able to fix all of the security problems by yourself, but that’s all right. The most important thing is to realize that a security problem might exist. Once you do that, it becomes a straightforward task to find others to help you fix the problem. But without the security mindset, you might never realize that your system has security problems and, therefore, you obviously can’t protect against those problems in a principled way. Technologies also change very rapidly. This means that some hot security mechanisms of today may be outdated in 10 or 15 years. But if you can learn how to think about security issues and have an appreciation for adversaries, then you can take that security mindset with you for the rest of your life and apply it to new technologies as they evolve. 1.4.2 Discussing Attacks Professional paranoia is an essential tool of the trade. With any new system you encounter, the first thing you think of is how you can break it. The sooner you find a weak spot, the sooner you learn more about the new system. Nothing is worse than working on a system for years, only to have somebody come up and say: ‘‘But how about if I attack it this way... ?’’ You really don’t want to experience that ‘‘Oops’’ moment. In this field, we make a very strict distinction between attacking somebody’s work and attacking somebody personally. Any work is fair game. If somebody proposes something, it is an automatic invitation to attack it. If you break one of our systems, we will applaud the attack and tell everybody about it.2 We constantly look for weaknesses in any system because that is the only way to learn how to make more secure systems. This is one thing you will have to learn: an attack on your work is not an attack on you. Also, when you attack a system, always be sure to criticize the system, not the designers. Personal attacks in cryptography will get you the same negative response as anywhere else. But be aware that this acceptance of attacks may not extend to everyone working on a system—particularly if they are not familiar with the field 2 Depending on the attack, we might kick ourselves for not finding the weakness ourselves, but that is a different issue. 10 Part I Introduction of cryptography and computer security. Without experience in the security community, it is very easy for people to take criticism of their work as a personal attack, with all the resulting problems. It is therefore important to develop a diplomatic approach, even if it makes it initially difficult to get the message across. Being too vague and saying something like ‘‘There might be some issues with the security aspects’’ may not be productive, since it may get a noncommittal response like ‘‘Oh, we’ll fix it,’’ even if the basic design is fundamentally flawed. Experience has shown us that the best way to get the message across technically is to be specific and say something like ‘‘If you do this and this, then an attacker could do this,’’ but such a statement may be felt as harsh by the recipient. Instead, you could begin by asking, ‘‘Have you thought about what might happen if someone did this?’’ You could then ease the designers of the system into a discussion of the attack itself. You might also consider complimenting them on the remaining strengths of their system, observe the challenges to building secure systems, and offer to help them fix their security problems if possible. So the next time someone attacks the security of your system, try not to take it personally. And make sure that when you attack a system, you only focus on the technology, you don’t criticize the people behind it, and you are sensitive to the fact that the designers may not be familiar with the culture of constructive criticism in the security community. 1.5 Threat Model Every system can be attacked. There is no such thing as perfect security. The whole point of a security system is to provide access to some people and not to others. In the end, you will always have to trust some people in some way, and these people may still be able to attack your system. It is very important to know what you are trying to protect, and against whom you wish to protect it. What are the assets of value? What are the threats? These sound like simple questions, but it turns out to be a much harder problem than you’d think. Since there’s really no such thing as perfect security, when we say that a system is ‘‘secure,’’ what we are really saying is that it provides a sufficient level of security for our assets of interest against certain classes of threats. We need to assess the security of a system under the designated threat model. Most companies protect their LAN with a firewall, but many of the really harmful attacks are performed by insiders, and a firewall does not protect against insiders at all. It doesn’t matter how good your firewall is; it won’t protect against a malicious employee. This is a mismatch in the threat model. Another example is SET. SET is a protocol for online shopping with a credit card. One of its features is that it encrypts the credit card number so that  Chapter 1 The Context of Cryptography 11 an eavesdropper cannot copy it. That is a good idea. A second feature—that not even the merchant is shown the customer’s credit-card number—works less well. The second property fails because some merchants use the credit card number to look up customer records or to charge surcharges. Entire commerce systems have been based on the assumption that the merchant has access to the customer’s credit card number. And then SET tries to take this access away. When Niels worked with SET in the past, there was an option for sending the credit card number twice—once encrypted to the bank, and once encrypted to the merchant so that the merchant would get it too. (We have not verified whether this is still the case.) But even with this option, SET doesn’t solve the whole problem. Most credit card numbers that are stolen are not intercepted while in transit between the consumer and the merchant. They are stolen from the merchant’s database. SET only protects the information while it is in transit. SET makes another, more serious, mistake. Several years ago Niels’s bank in the Netherlands offered a SET-enabled credit card. The improved security for online purchases was one of the major selling points. But this turned out to be a bogus argument. It is quite safe to order online with a normal credit card. Your credit card number is not a secret. You give it to every salesperson you buy something from. The real secret is your signature. That is what authorizes the transaction. If a merchant leaks your credit card number, then you might get spurious charges, but as long as there is no handwritten signature (or PIN code) there is no indication of acceptance of the transac- tion, and therefore no legal basis for the charge. In most jurisdictions you simply complain and get your money back. There might be some inconve- nience involved in getting a new credit card with a different number, but that is the extent of the user’s exposure. With SET, the situation is different. SET uses a digital signature (explained in Chapter 12) by the user to autho- rize the transaction. That is obviously more secure than using just a credit card number. But think about it. Now the user is liable for any transaction performed by the SET software on his PC. This opens the user up to huge liabilities. What if a virus infects his PC and subverts the SET software? The software might sign the wrong transaction, and cause the user to lose money. So from the user’s point of view, SET offers worse security than a plain credit card. Plain credit cards are safe for online shopping because the user can always get his money back from a fraudulent transaction. Using SET increases the user’s exposure. So although the overall payment system is better secured, SET transfers the residual risk from the merchant and/or bank to the user. It changes the user’s threat model from ‘‘It will only cost me money if they forge my signature well enough’’ to ‘‘It will only cost me money if they forge my signature well enough, or if a clever virus infects my PC.’’ 12 Part I Introduction Threat models are important. Whenever you start on a cryptographic secu- rity project, sit down and think about what your assets are and against which threats you wish to protect them. A mistake in your threat analysis can ren- der an entire project meaningless. We won’t talk a lot about threat analysis in this book, as we are discussing the limited area of cryptography here, but in any real system you should never forget the threat analysis for each of the participants. 1.6 Cryptography Is Not the Solution Cryptography is not the solution to your security problems. It might be part of the solution, or it might be part of the problem. In some situations, cryptography starts out by making the problem worse, and it isn’t at all clear that using cryptography is an improvement. The correct use of cryptography must therefore be carefully considered. Our previous discussion of SET is an example of this. Suppose you have a secret file on your computer that you don’t want others to read. You could just protect the file system from unauthorized access. Or you could encrypt the file and protect the key. The file is now encrypted, and human nature being what it is, you might not protect the file very well. You might store it on a USB stick and not worry if that USB stick is lost or stolen. But where can you store the key? A good key is too long to remember. Some programs store the key on the disk—the very place the secret file was stored in the first place. But an attack that could recover the secret file in the first situation can now recover the key, which in turn can be used to decrypt the file. Further, we have introduced a new point of attack: if the encryption system is insecure or the amount of randomness in the key is too low, then the attacker could break the encryption system itself. Ultimately, the overall security has been reduced. Therefore, simply encrypting the file is not the entire solution. It might be part of the solution, but by itself it can create additional issues that need to be solved. Cryptography has many uses. It is a crucial part of many good security systems. It can also make systems weaker when used in inappropriate ways. In many situations, it provides only a feeling of security, but no actual security. It is tempting to stop there, since that is what most users want: to feel secure. Using cryptography in this manner can also make a system comply with certain standards and regulations, even if the resulting system isn’t actually secure. In situations like this (which are all too common), any voodoo that the customer believes in would provide the same feeling of security and would work just as well.  Chapter 1 The Context of Cryptography 13 1.7 Cryptography Is Very Difficult Cryptography is fiendishly difficult. Even seasoned experts design systems that are broken a few years later. This is common enough that we are not surprised when it happens. The weakest-link property and the adversarial setting con- spire to make life for a cryptographer—or any security engineer—very hard. Another significant problem is the lack of testing. There is no known way of testing whether a system is secure. In the security and cryptography research community, for example, what we try to do is publish our systems and then get other experts to look at them. Note that the second part is not automatic; there are many published systems that nobody has even glanced at after they were published, and the conference and journal review process alone isn’t sufficient to preemptively identify all potential security issues with a system prior to publication. Even with many seasoned eyes looking at the system, security deficiencies may not be uncovered for years. There are some small areas of cryptography that we as a community understand rather well. This doesn’t mean they are simple; it just means that we have been working on them for a few decades now, and we think we know the critical issues. This book is mostly about those areas. What we have tried to do in this book is to collect the information that we have about designing and building practical cryptographic systems, and bring it all together in one place. For some reason, many people still seem to think that cryptography is easy. It is not. This book will help you understand the challenges to cryptography engineering and help propel you on the road to overcoming those challenges. But don’t go out and build a new cryptographic voting machine or other critical security system right away. Instead, take what you learn here and work with others—especially seasoned cryptography experts—to design and analyze your new system. Even we, despite our years of experience in cryptography and security, ask other cryptography and security experts to review the systems that we design. 1.8 Cryptography Is the Easy Part Even though cryptography itself is difficult, it is still one of the easy parts of a security system. Like a lock, a cryptographic component has fairly well-defined boundaries and requirements. An entire security system is much more difficult to clearly define, since it involves many more aspects. Issues like the organizational procedures used to grant access and the procedures used to check that the other procedures are being followed are much harder to deal 14 Part I Introduction with, as the situation is always changing. Another huge problem in computer security is the quality of much software. Security software cannot be effective if the software on the machine contains numerous bugs that lead to security holes. Cryptography is the easy part, because there are people who know how to do a reasonably good job. There are experts for hire who will design a cryptographic system for you. They are not cheap, and they are often a pain to work with. They insist on changing other parts of the system to achieve the desired security properties. Still, for all practical purposes, cryptography poses problems that we know how to solve, and this book will give you a sense for how to go about solving them. The rest of the security system contains problems we don’t know how to solve. Key management and key storage is crucial to any cryptographic system, but most computers have no secure place to store a key. Poor software quality is another problem. Network security is even harder. And when you add users to the mix, the problem becomes harder still. 1.9 Generic Attacks It is also important to realize that some security problems can’t be solved. There are black box or generic attacks against certain types of systems. A classic example of this is the analog hole for digital rights management (DRM) systems. These DRM systems try to control the copying of digital mate- rials, such as a picture, song, movie, or book. But no technology—cryptography or otherwise—can protect against a generic attack outside the system. For example, an attacker could take a photo of a computer screen to create a copy of the picture, or use a microphone to re-record the song. It is important to identify what the generic attacks against a system are. Otherwise, you might spend a lot of time trying to fix an unfixable problem. Similarly, when someone claims that they’ve secured a system against a generic attack, you know to be skeptical. 1.10 Security and Other Design Criteria Security is never the only design criterion for a system. Instead, security is but one of many criteria. 1.10.1 Security Versus Performance The bridge over the Firth of Forth in Scotland has to be seen to be believed. A 19th-century engineering marvel, it is mind-numbingly large (and there- fore expensive) compared to the trains that cross it. It is so incredibly  Chapter 1 The Context of Cryptography 15 over-engineered it is hard to believe your eyes. Yet the designers did the right thing. They were confronted with a problem they had not solved successfully before: building a large steel bridge. They did an astoundingly good job. They succeeded spectacularly; their bridge is still in use today over a century later. That’s what good engineering looks like. Over the years, bridge designers have learned how to build such bridges much more cheaply and efficiently. But the first priority is always to get a bridge that is safe and that works. Efficiency, in the form of reducing cost, is a secondary issue. We have largely reversed these priorities in the computer industry. The primary design objective all too often includes very strict efficiency demands. The first priority is always speed, even in areas where speed is not important. Here speed might be the speed of the system itself, or it might be the speed with which the system can be brought to market. This leads to security cost- cutting. The result is generally a system that is somewhat efficient, yet is not sufficiently secure. There is another side to the Firth of Forth bridge story. In 1878, Thomas Bouch completed the then-longest bridge in the world across the Firth of Tay at Dundee. Bouch used a new design combining cast iron and wrought iron, and the bridge was considered to be an engineering marvel. On the night of December 28, 1879, less than two years later, the bridge collapsed in a heavy storm as a train with 75 people on board crossed the bridge. All perished. It was the major engineering disaster of the time.3 So when the Firth of Forth bridge was designed a few years later, the designers put in a lot more steel, not only to make the bridge safe but also to make it look safe to the public. We all know that engineers will sometimes get a design wrong, especially when they do something new. And when they get it wrong, bad things can happen. But here is a good lesson from Victorian engineers: if it fails, back off and become more conservative. The computer industry has largely forgotten this lesson. When we have very serious security failures in our computer systems, and we have them all too frequently, it is very easy to just plod along, accepting it as if it were fate. We rarely go back to the drawing board and design something more conservative. We just keep throwing a few patches out and hoping this will solve the problem. By now, it will be quite clear to you that we will choose security over efficiency any time. How much CPU time are we willing to spend on security? Almost all of it. We wouldn’t care if 90% of our CPU cycles were spent on a reliable security system if the alternative was a faster but insecure system. The lack of computer security is a real hindrance to us, and to most users. That is 3 William McGonagall wrote a famous poem about the Tay Bridge disaster, ending with the lines For the stronger we our houses do build/The less chance we have of being killed. This advice is still highly relevant today. 16 Part I Introduction why people still have to send pieces of paper around with signatures, and why they have to worry about viruses and other attacks on our computers. Digital crooks of the future will know much more and be much better equipped, and computer security will become a larger and larger problem. We are still only seeing the beginnings of the digital crime wave. We need to secure our computers much better. There are of course many ways of achieving security. But as Bruce extensively documented in Secrets and Lies, good security is always a mixture of prevention, detection, and response. The role for cryptography is primarily in the prevention part, which has to be very good to ensure that the detection and response parts (which can and should include manual intervention) are not overwhelmed. Cryptography can, however, be used to provide more secure detection mechanisms, such as strong cryptographic audit logs. Cryptography is what this book is about, so we’ll concentrate on that aspect. Yes, yes, we know, 90% still sounds like a lot. But there is some consolation. Remember first that we are willing to spend 90% of our CPU on security if the alternative is an insecure system. Fortunately, in many cases the costs of security can be hidden from the user. We can only type around 10 characters per second—on a good day—and even the slow machines of a decade ago had no trouble keeping up with that. Today’s machines are over a thousand times faster. If we use 90% of the CPU for security, the computer will appear one-tenth as fast. That is about the speed that computers were five years ago. And those computers were more than fast enough for us to get our work done. We may not always have to spend so many cycles on security. But we’re willing to, and that’s the point. There are only a few situations in which we have to wait on the computer. These include waiting for Web pages, printing data, starting certain programs, booting the machine, etc. A good security system would not slow down any of these activities. Modern computers are so fast that it is hard to figure out how to use the cycles in a useful manner. Sure, we can use alpha-blending on screen images, 3D animations, or even voice recognition. But the number-crunching parts of these applications do not perform any security-related actions, so they would not be slowed down by a security system. It is the rest of the system, which is already as fast as it can possibly get on a human time scale, that will have the overhead. And we don’t care if it goes at one-tenth the speed if it increases security. Most of the time, you wouldn’t even notice the overhead. Even in situations where the overhead would be significant, that is just the cost of doing business. It will be clear by now that our priorities are security first, second, and third, and performance somewhere way down the list. Of course, we still want the system to be as efficient as possible, but not at the expense of security. We understand that this design philosophy is not always possible in the real world. Often the realities of the marketplace trump the need for security.  Chapter 1 The Context of Cryptography 17 Systems can rarely be developed from scratch, and often need to be secured incrementally or after deployment. Systems need to be backward-compatible with existing, insecure, systems. The three of us have designed many security systems under these constraints, and we can tell you that it’s practically impossible to build a good security system that way. The design philosophy of this book is security first and security foremost. It’s one we’d like to see adopted more in commercial systems. 1.10.2 Security Versus Features Complexity is the worst enemy of security, and it almost always comes in the form of features or options. Here is the basic argument. Imagine a computer program with 20 different options, each of which can be either on or off. That is more than a million different configurations. To get the program to work, you only need to test the most common combination of options. To make the program secure, you must evaluate each of the million possible configurations that the program can have, and check that each configuration is secure against every possible form of attack. That is impossible to do. And most programs have considerably more than 20 options. The best way to have confidence in building something secure is to keep it simple. A simple system is not necessarily a small system. You can build large systems that are still fairly simple. Complexity is a measure of how many things interact at any one point. If the effect of an option is limited to a small part of the program, then it cannot interact with an option whose effect is limited to another part of the program. To make a large, simple system you have to provide a very clear and simple interface between different parts of the system. Programmers call this modularization. This is all basic software engineering. A good simple interface isolates the rest of the system from the details of a module. And that should include any options or features of the module. One of the things we have tried to do in this book is define simple interfaces for cryptographic primitives. No features, no options, no special cases, no extra things to remember, just the simplest definition we could come up with. Some of these definitions are new; we developed them while writing the book. They have helped us shape our thinking about good security systems, and we hope they will help you, too. 1.10.3 Security Versus Evolving Systems One of the other biggest problems for security is that the full system continues to evolve even after the underlying security mechanisms are put in place. This means that the designer of the security mechanism needs not only to exhibit 18 Part I Introduction professional paranoia and consider a wide range of attackers and attack goals, but also to anticipate and prepare for future uses of the system. This can also create enormous challenges, and is an issue that systems designers need to keep in mind. 1.11 Further Reading Anyone interested in cryptography should read Kahn’s The Codebreakers. This is a history of cryptography, from ancient times to the 20th century. The stories provide many examples of the problems engineers of cryptographic systems face. Another good historical text, and a pleasurable read, is The Code Book. In some ways, the book you’re holding is a sequel to Bruce’s first book, Applied Cryptography. Applied Cryptography covers a much broader range of subjects, and includes the specifications of all the algorithms it discusses. However, it does not go into the engineering details that we talk about in this book. For facts and pre