Applied Cryptography

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.

• CONTENTSINTRODUCTION XIIIFOREWORD BY WHITFIELD DIFFIE XVIIPREFACE XXIHOW TO READ THIS BOOK XXIIACKNOWLEDGMENTS XXIVABOUT THE AUTHOR XXV1 FOUNDATIONS 71.1 TERMINOLOGY 11 .2 STEGANOGRAPHY 91.3 SUBSTITUTION CIPHERS AND TRANSPOSITION CIPHERS 101.4 SIMPLE XOR 131.5 ONE-TIME PADS 151.6 COMPUTER ALGORITHMS 171.7 LARGE NUMBERS 17PART I CRYPTOGRAPHIC PROTOCOLS2 PROTOCOL BUILDING BLOCKS 272.1 INTRODUCTION TO PROTOCOLS 212.2 COMMUNICATIONS USING SYMMETRIC CRYPTOGRAPHY 282.3 ONE-WAY FUNCTIONS 292.4 ONE-WAY HASH FUNCTIONS 302.5 COMMUNICATIONS USING PUBLIC-KEY CRYPTOGRAPHY 312.6 DIGITAL SIGNATURES 342.7 DIGITAL SIGNATURES WITH ENCRYPTION 472.8 RANDOM AND PSEUDO-RANDOM SEQUENCE GENERATION 443 BASIC PROTOCOLS 473.1 KEY EXCHANGE 473.2 AUTHENTICATION 523.3 AUTHENTICATION AND KEY EXCHANGE 563.4 FORMAL ANALYSIS OF AUTHENTICATION AND KEY-EXCHANGE PROTOCOLS 653.5 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY 683.6 SECRET SPLITTING 703.7 SECRET SHARING 713.8 CRYPTOGRAPHIC PROTECTION OF DATABASES 734 INTERMEDIATE PROTOCOLS 754.1 TIMESTAMPING SERVICES 754.2 SUBLIMINAL CHANNEL 794.3 UNDENIABLE DIGITAL SIGNATURES 814.4 DESIGNATED CONFIRMER SIGNATURES 824.5 PROXY SIGNATURES 834.6 GROUP SIGNATURES 844.7 FAIL-STOP DIGITAL SIGNATURES 854.8 COMPUTING WITH ENCRYPTED DATA 854.9 BIT COMMITMENT 864.10 FAIR COIN FLIPS 894.11 MENTAL POKER 924.12 ONE-WAY ACCUMULATORS 954.13 ALL-OR-NOTHING DISCLOSURE OF SECRETS 964.14 KEY ESCROW 975 ADVANCED PROTOCOLS 1015.1 ZERO-KNOWLEDGE PROOFS 1015.2 ZERO-KNOWLEDGE PROOFS OF IDENTITY 1095.3 BLIND SIGNATURES 1125.4 IDENTITY-BASED PUBLIC-KEY CRYPTOGRAPHY 1155.5 OBLIVIOUS TRANSFER 2265.6 OBLIVIOUS SIGNATURES 2275.7 SIMULTANEOUS CONTRACT SIGNING 2285.8 DIGITAL CERTIFIED MAIL 1225.9 SIMULTANEOUS EXCHANGE OF SECRETS 1236 ESOTERIC PROTOCOLS 1256.1 SECURE ELECTIONS 1256.2 SECURE MULTIPARTY COMPUTATION 2346.3 ANONYMOUS MESSAGE BROADCAST 2376.4 DIGITAL CASH 239PART II CRYPTOGRAPHIC TECHNIQUES7 KEY LENGTH 1517.1 SYMMETRIC KEY LENGTH 1517.2 PUBLIC-KEY KEY LENGTH 1587.3 COMPARING SYMMETRIC AND PUBLIC-KEY KEY LENGTH 1657.4 BIRTHDAY ATTACKS AGAINST ONE-WAY HASH FUNCTIONS 1657.5 HOW LONG SHOULD A KEY BE? 1667.6 CAVEAT EMETOR 1688 KEY MANAGEMENT 1698.1 GENERATING KEYS 1708.2 NONLINEAR KEYSPACES 1758.3 TRANSFERRING KEYS 1768.4 VERIFYING KEYS 1788.5 USING KEYS 1798.6 UPDATING KEYS 1808.7 STORING KEYS 1808.8 BACKUP KEYS 1818.9 COMPROMISED KEYS 1828.10 LIFETIME OF KEYS 1838.11 DESTROYING KEYS 1818.12 PUBLIC-KEY KEY MANAGEMENT 1859 ALGORITHM TYPES AND MODES 1899.1 ELECTRONIC CODEBOOK MODE 1899.2 BLOCK REPLAY 1919.3 CIPHER BLOCK CHAINING MODE 1939.4 STREAM CIPHERS 1979.5 SELF-SYNCHRONIZING STREAM CIPHERS 1989.6 CIPHER-FEEDBACK MODE 2009.7 SYNCHRONOUS STREAM CIPHERS 2029.8 OUTPUT-FEEDBACK MODE 2039.9 COUNTER MODE 2059.10 OTHER BLOCK-CIPHER MODES 2069.11 CHOOSING A CIPHER MODE 2089.12 INTERLEAVING 2109.13 BLOCK CIPHERS VERSUS STREAM CIPHERS 21010 USING ALGORITHMS 21310.1 CHOOSING AN ALGORITHM 21410.2 PUBLIC-KEY CRYPTOGRAPHY VERSUS SYMMETRIC CRYPTOGRAPHY 21610.3 ENCRYPTING COMMUNICATIONS CHANNELS 21610.4 ENCRYPTING DATA FOR STORAGE 22010.5 HARDWARE ENCRYPTION VERSUS SOFTWARE ENCRYPTION 22310.6 COMPRESSION, ENCODING, AND ENCRYPTION 22610.7 DETECTING ENCRYPTION 22610.8 HIDING CIPHERTEXT IN CIPHERTEXT 22710.9 DESTROYING INFORMATION 228PART III CRYPTOGRAPHIC ALGORITHMS11 MATHEMATICAL BACKGROUND 23311.1 INFORMATION THEORY 23311.2 COMPLEXITY THEORY 23711.3 NUMBER THEORY 24211.4 FACTORING 25511.5 PRIME NUMBER GENERATION 25811.6 DISCRETE LOGARITHMS IN A FINITE FIELD 26212 DATA ENCRYPTION STANDARD (DES) 26512.1 BACKGROUND 26512.2 DESCRIPTION OF DES 27012.3 SECURITY OF DES 27812.4 DIFFERENTIAL AND LINEAR CRYPTANALYSIS 28512.5 THE REAL DESIGN CRITERIA 29312.6 DES VARIANTS 20412.7 HOW SECURE IS DES TODAY? 30013 OTHER BLOCK CIPHERS 30313.1 LUCIFER 30313.2 MADRYGA 30413.3 NEWDES 30613.4 FEAL 30813.5 REDOC 31113.6 LOKI 31413.7 KHUFU AND KHAFRE 31613.8 RC2 32813.9 IDEA 31913.10 MMB 32513.11 CA-1.1 32713.12 SKIPJACK 32814 STILL OTHER BLOCK CIPHERS 33214.1 GOST 33214.2 CAST 33414.3 BLOWFISH 33614.4 SAFER 33914.5 3-WAY 34114.6 CRAB 34214.7 SXAL8/MBAL 34414.8 RC5 34414.9 OTHER BLOCK ALGORITHMS 34614.10 THEORY OF BLOCK CIPHER DESIGN 34614.11 USING ONE-WAY HASH FUNCTIONS 35114.12 CHOOSING A BLOCK ALGORITHM 35415 COMBINING BLOCK CIPHERS 35715.1 DOUBLE ENCRYPTION 35715.2 TRIPLE ENCRYPTION 35815.3 DOUBLING THE BLOCK LENGTH 36315.4 OTHER MULTIPLE ENCRYPTION SCHEMES 36315.5 CDME KEY SHORTENING 36615.6 WHITENING 36615.7 CASCADING MULTIPLE BLOCK ALGORITHMS 36715.8 COMBINING MULTIPLE BLOCK ALGORITHMS 36816 PSEUDO-KANDOM-SEQUENCE GENERATORS AND STREAM CIPHERS 36916.1 LINEAR CONGRUENTIAL GENERATORS 36916.2 LINEAR FEEDBACK SHIFT REGISTERS 37216.3 DESIGN AND ANALYSIS OF STREAM CIPHERS 37916.4 STREAM CIPHERS USING LFSRS 38116.5 A5 38916.6 HUGHES XPD/KPD 38916.7 NANOTEO 39016.8 RAMBUTAN 39016.9 ADDITIVE GENERATORS 39016.10 GIFFORD 39216.11 ALGORITHM M 39316.12 PKZ1P 39417 OTHER STREAM CIPHERS AND REAL RANDOM-SEQUENCE GENERATORS 39717.1 RC4 39717.2 SEAL 39817.3 WAKE 40017.4 FEEDBACK WITH CARRY SHIFT REGISTERS 40217.5 STREAM CIPHERS USING FCSRS 40517.6 NONLINEAR-FEEDBACK SHIFT REGISTERS 41217.7 OTHER STREAM CIPHERS 41317.8 SYSTEM-THEORETIC APPROACH TO STREAM-CIPHER DESIGN 41517.9 COMPLEXITY-THEMATIC APPROACH TO STREAM-CIPHER DESIGN 41617.10 OTHER APPROACHES TO STREAM-CIPHER DESIGN 41817.11 CASCADING MULTIPLE STREAM CIPHERS 41917.12 CHOOSING A STREAM CIPHER 42017.13 GENERATING MULTIPLE STREAMS FROM A SINGLE PSEUDO-RANDOM-SEQUENCE GENERATOR 42017.14 REAL RANDOM-SEQUENCE GENERATORS 42118 ONE-WAY HASH FUNCTIONS 42918.1 BACKGROUND 42918.2 SNEFRU 43118.3 N-HASH 43218.4 MD4 43518.5 MD5 43618.6 MD2 44118.7 SECURE HASH ALGORITHM (SHA) 44118.8 RIPE-MD 44518.9 HAVAL 44518.10 OTHER ONE-WAY HASH FUNCTIONS 44618.11 ONE-WAY HASH FUNCTIONS USING SYMMETRIC BLOCK ALGORITHMS 44618.12 USING PUBLIC-KEY ALGORITHMS 45518.13 CHOOSING A ONE-WAY HASH FUNCTION 45518.14 MESSAGE AUTHENTICATION CODES 45519 PUBLIC-KEY ALGORITHMS 46119.1 BACKGROUND 46119.2 KNAPSACK ALGORITHMS 46219.3 RSA 46619.4 POHLIG-HELLMAN 47419.5 RABIN 47519.6 ELGAMAL 47619.7 MCELIECE 47919.8 ELLIPTIC CURVE CRYPTOSYSTEMS 48019.9 LUC 48119.10 FINITE AUTOMATON PUBLIC-KEY CRYPTOSYSTEMS 48220 PUBLIC-KEY DIGITAL SIGNATURE ALGORITHMS 48320.1 DIGITAL SIGNATURE ALGORITHM [DSA] 48320.2 DSA VARIANTS 49420.3 GOST DIGITAL SIGNATURE ALGORITHM 49520.4 DISCRETE LOGARITHM SIGNATURE SCHEMES 49620.5 ONG-SCHNORR-SHAMIR 49820.6 ESIGN 49920.7 CELLULAR AUTOMATA 50020.8 OTHER PUBLIC-KEY ALGORITHMS 50021 IDENTIFICATION SCHEMES 50321.1 FEIGE-FIAT-SHAMIR 50321.2 GUTLLOU-QUISQUATER 50821.3 SCHNORR 51021.4 CONVERTING IDENTIFICATION SCHEMES TO SIGNATURE SCHEMES 51222 KEY-EXCHANGE ALGORITHMS 51322.1 DIFFIE-HELLMAN 51322.2 STATION-TO-STATION PROTOCOL 51622.3 SHAMIR'S THREE-PASS PROTOCOL 51622.4 COMSET 57722.5 ENCRYPTED KEY EXCHANGE 51822.6 FORTIFIED KEY NEGOTIATION 52222.7 CONFERENCE KEY DISTRIBUTION AND SECRET BROADCASTING 52323 SPECIAL ALGORITHMS FOR PROTOCOLS 52723.1 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY 52723.2 SECRET-SHARING ALGORITHMS 52823.3 SUBLIMINAL CHANNEL 53123.4 UNDENIABLE DIGITAL SIGNATURES 53623.5 DESIGNATED CONFIRMER SIGNATURES 53923.6 COMPUTING WITH ENCRYPTED DATA 54023.7 FAIR COIN FLIPS 54123.8 ONE-WAY ACCUMULATORS 54323.9 ALL-OR-NOTHING DISCLOSURE OR SECRETS 54323.10 FAIR AND FAILSAFE CRYPTOSYSTEMS 54623.11 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE 54823.12 BLIND SIGNATURES 54923.13 OBLIVIOUS TRANSFER 55023.14 SECURE MULTIPARTY COMPUTATION 55223.15 PROBABILISTIC ENCRYPTION 55223.16 QUANTUM CRYPTOGRAPHY 554PART IV THE REAL WORLD24 EXAMPLE IMPLEMENTATIONS 56124.1 IBM SECRET-KEY MANAGEMENT PROTOCOL 56124.2 MITRENET 56224.3 ISDN 56324.4 STU-III 56524.5 KERBEROS 56624.6 KRYPTOKNIGHT 57224.7 SESAME 57224.8 IBM COMMON CRYPTOGRAPHIC ARCHITECTURE 57324.9 ISO AUTHENTICATION FRAMEWORK 57424.10 PRIVACY-ENHANCED MAIL (PEM) 57724.11 MESSAGE SECURITY PROTOCOL (MSP) 58424.12 PRETTY GOOD PRIVACY (PGP) 58424.13 SMART CARDS 58724.14 PUBLIC-KEY CRYPTOGRAPHY STANDARDS (PKCS) 58824.15 UNIVERSAL ELECTRONIC PAYMENT SYSTEM (UEPS) 58924.16 CLIPPER 59124.17 CAPSTONE 59324.18 AT&T MODEL 3600 TELEPHONE SECURITY DEVICE (TSD) 59425 POLITICS 59725.1 NATIONAL SECURITY AGENCY (NSA) 59725.2 NATIONAL COMPUTER SECURITY CENTER (NCSC) 59925.3 NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY (NIST) 60025.4 RSA DATA SECURITY, INC. 60325.5 PUBLIC KEY PARTNERS 60425.6 INTERNATIONAL ASSOCIATION FOR CRYPTOGRAPHIC RESEARCH (IACR) 60525.7 RACE INTEGRITY PRIMITIVES EVALUATION (RIPE) 60525.8 CONDITIONAL ACCESS FOR EUROPE (CAFE) 60625.9 ISO/IEC 9979 60725.10 PROFESSIONAL, CIVIL LIBERTIES, AND INDUSTRY GROUPS 60825.11 SCICRYPT 60825.12 CYPHERPUNKS 60925.13 PATENTS 60925.14 U.S. EXPORT RULES 61025.15 FOREIGN IMPORT AND EXPORT OF CRYPTOGRAPHY 61725.16 LEGAL ISSUES 618Afterword by Matt Blaze 619PART V SOURCE CODESource Code 623References 675