NETWORK SECURITY JUMPSTART
CONTENTS I INTRODUCTION AND CLASSICAL CRYPTOGRAPHY INTRODUCTION CRYPTOGRAPHY AND MODERN CRYPTOGRAPHY THE SETTING OF PRIVATE-KEY ENCRYPTION HISTORICAL CIPHERS AND THEIR CRYPTANALYSIS PRINCIPLES OF MODERN CRYPTOGRAPHY PRINCIPLE 1 – FORMAL DE?NITIONS PRINCIPLE 2 – PRECISE ASSUMPTIONS PRINCIPLE 3 – PROOFS OF SECURITY PROVABLE SECURITY AND REAL-WORLD SECURITY REFERENCES AND ADDITIONAL READING EXERCISES PERFECTLY SECRET ENCRYPTION DE?NITIONS THE ONE-TIME PAD LIMITATIONS OF PERFECT SECRECY *SHANNON’S THEOREM II PRIVATE-KEY (SYMMETRIC) CRYPTOGRAPHY PRIVATE-KEY ENCRYPTION COMPUTATIONAL SECURITY THE CONCRETE APPROACH THE ASYMPTOTIC APPROACH DE?NING COMPUTATIONALLY SECURE ENCRYPTION THE BASIC DE?NITION OF SECURITY (EAV-SECURITY) *SEMANTIC SECURITY CONSTRUCTING AN EAV-SECURE ENCRYPTION SCHEME PSEUDORANDOM GENERATORS PROOFS BY REDUCTION EAV-SECURITY FROM A PSEUDORANDOM GENERATOR STRONGER SECURITY NOTIONS SECURITY FOR MULTIPLE ENCRYPTIONS CHOSEN-PLAINTEXT ATTACKS AND CPA-SECURITY CPA-SECURITY FOR MULTIPLE ENCRYPTIONS CONSTRUCTING A CPA-SECURE ENCRYPTION SCHEME PSEUDORANDOM FUNCTIONS AND PERMUTATIONS CPA-SECURITY FROM A PSEUDORANDOM FUNCTION MODES OF OPERATION AND ENCRYPTION IN PRACTICE STREAM CIPHERS STREAM-CIPHER MODES OF OPERATION BLOCK CIPHERS AND BLOCK-CIPHER MODES OF OPERATION *NONCE-BASED ENCRYPTION MESSAGE AUTHENTICATION CODES MESSAGE INTEGRITY SECRECY VS INTEGRITY ENCRYPTION VS MESSAGE AUTHENTICATION MESSAGE AUTHENTICATION CODES (MACS) – DE?NITIONS CONSTRUCTING SECURE MESSAGE AUTHENTICATION CODES A FIXED-LENGTH MAC DOMAIN EXTENSION FOR MACS CBC-MAC THE BASIC CONSTRUCTION *PROOF OF SECURITY MACS FROM DI?ERENCE-UNIVERSAL FUNCTIONS INSTANTIATIONS *INFORMATION-THEORETIC MACS ONE-TIME MACS FROM STRONGLY UNIVERSAL FUNCTIONS ONE-TIME MACS FROM DI?ERENCE-UNIVERSAL FUNCTIONS LIMITATIONS ON INFORMATION-THEORETIC MACS CCA-SECURITY AND AUTHENTICATED ENCRYPTION CHOSEN-CIPHERTEXT ATTACKS AND CCA-SECURITY PADDING-ORACLE ATTACKS DE?NING CCA-SECURITY AUTHENTICATED ENCRYPTION DE?NING AUTHENTICATED ENCRYPTION CCA SECURITY VS AUTHENTICATED ENCRYPTION AUTHENTICATED ENCRYPTION SCHEMES GENERIC CONSTRUCTIONS STANDARDIZED SCHEMES SECURE COMMUNICATION SESSIONS HASH FUNCTIONS AND APPLICATIONS COLLISION RESISTANCE WEAKER NOTIONS OF SECURITY DOMAIN EXTENSION: THE MERKLE–DAMG?ARD TRANSFORM MESSAGE AUTHENTICATION USING HASH FUNCTIONS HASH-AND-MAC HMAC GENERIC ATTACKS ON HASH FUNCTIONS BIRTHDAY ATTACKS FOR FINDING COLLISIONS SMALL-SPACE BIRTHDAY ATTACKS *TIME/SPACE TRADEO?S FOR INVERTING HASH FUNCTIONS THE RANDOM-ORACLE MODEL THE RANDOM-ORACLE MODEL IN DETAIL IS THE RANDOM-ORACLE METHODOLOGY SOUND? ADDITIONAL APPLICATIONS OF HASH FUNCTIONS FINGERPRINTING AND DEDUPLICATION MERKLE TREES PASSWORD HASHING KEY DERIVATION COMMITMENT SCHEMES PRACTICAL CONSTRUCTIONS OF SYMMETRIC-KEY PRIMITIVES LINEAR-FEEDBACK SHIFT REGISTERS ADDING NONLINEARITY TRIVIUM RC4 CHACHA20 BLOCK CIPHERS SUBSTITUTION-PERMUTATION NETWORKS FEISTEL NETWORKS DES – THE DATA ENCRYPTION STANDARD 3DES: INCREASING THE KEY LENGTH OF A BLOCK CIPHER AES – THE ADVANCED ENCRYPTION STANDARD *DI?ERENTIAL AND LINEAR CRYPTANALYSIS COMPRESSION FUNCTIONS AND HASH FUNCTIONS COMPRESSION FUNCTIONS FROM BLOCK CIPHERS THE SPONGE CONSTRUCTION AND SHA-3 (KECCAK) *THEORETICAL CONSTRUCTIONS OF SYMMETRIC-KEY PRIMITIVES ONE-WAY FUNCTIONS CANDIDATE ONE-WAY FUNCTIONS HARD-CORE PREDICATES FROM ONE-WAY FUNCTIONS TO PSEUDORANDOMNESS HARD-CORE PREDICATES FROM ONE-WAY FUNCTIONS A SIMPLE CASE A MORE INVOLVED CASE THE FULL PROOF CONSTRUCTING PSEUDORANDOM GENERATORS PSEUDORANDOM GENERATORS WITH MINIMAL EXPANSION INCREASING THE EXPANSION FACTOR CONSTRUCTING PSEUDORANDOM FUNCTIONS CONSTRUCTING (STRONG) PSEUDORANDOM PERMUTATIONS ASSUMPTIONS FOR PRIVATE-KEY CRYPTOGRAPHY COMPUTATIONAL INDISTINGUISHABILITY III PUBLIC-KEY (ASYMMETRIC) CRYPTOGRAPHY NUMBER THEORY AND CRYPTOGRAPHIC HARDNESS ASSUMPTIONS PRELIMINARIES AND BASIC GROUP THEORY PRIMES AND DIVISIBILITY MODULAR ARITHMETIC GROUPS THE GROUP Z? N *ISOMORPHISMS AND THE CHINESE REMAINDER THEOREM PRIMES, FACTORING, AND RSA GENERATING RANDOM PRIMES *PRIMALITY TESTING THE FACTORING ASSUMPTION THE RSA ASSUMPTION *RELATING THE FACTORING AND RSA ASSUMPTIONS CRYPTOGRAPHIC ASSUMPTIONS IN CYCLIC GROUPS CYCLIC GROUPS AND GENERATORS THE DISCRETE-LOGARITHM/DI?E–HELLMAN ASSUMPTIONS WORKING IN (SUBGROUPS OF) Z? P ELLIPTIC CURVES *CRYPTOGRAPHIC APPLICATIONS ONE-WAY FUNCTIONS AND PERMUTATIONS COLLISION-RESISTANT HASH FUNCTIONS 10 *ALGORITHMS FOR FACTORING AND COMPUTING DISCRETE LOGA- RITHMS 101 ALGORITHMS FOR FACTORING 1011 POLLARD’S P ?1 ALGORITHM 1012 POLLARD’S RHO ALGORITHM 1013 THE QUADRATIC SIEVE ALGORITHM 102 GENERIC ALGORITHMS FOR COMPUTING DISCRETE LOGARITHMS 1021 THE POHLIG–HELLMAN ALGORITHM 1022 THE BABY-STEP/GIANT-STEP ALGORITHM 1023 DISCRETE LOGARITHMS FROM COLLISIONS 103 INDEX CALCULUS: COMPUTING DISCRETE LOGARITHMS IN Z? P 104 RECOMMENDED KEY LENGTHS 11 KEY MANAGEMENT AND THE PUBLIC-KEY REVOLUTION 111 KEY DISTRIBUTION AND KEY MANAGEMENT 112 A PARTIAL SOLUTION: KEY-DISTRIBUTION CENTERS 113 KEY EXCHANGE AND THE DI?E–HELLMAN PROTOCOL 114 THE PUBLIC-KEY REVOLUTION 12 PUBLIC-KEY ENCRYPTION 121 PUBLIC-KEY ENCRYPTION – AN OVERVIEW 122 DE?NITIONS 1221 SECURITY AGAINST CHOSEN-PLAINTEXT ATTACKS 1222 MULTIPLE ENCRYPTIONS 1223 SECURITY AGAINST CHOSEN-CIPHERTEXT ATTACKS 123 HYBRID ENCRYPTION AND THE KEM/DEM PARADIGM 1231 CPA-SECURITY 1232 CCA-SECURITY 124 CDH/DDH-BASED ENCRYPTION 1241 EL GAMAL ENCRYPTION 1242 DDH-BASED KEY ENCAPSULATION 1243 *A CDH-BASED KEM IN THE RANDOM-ORACLE MODEL 1244 *CHOSEN-CIPHERTEXT SECURITY AND DHIES/ECIES 125 RSA-BASED ENCRYPTION 1251 PLAIN RSA ENCRYPTION 1252 PADDED RSA AND PKCS #1 V15 1253 *CPA-SECURE ENCRYPTION WITHOUT RANDOM ORACLES 1254 OAEP AND PKCS #1 V2 1255 *A CCA-SECURE KEM IN THE RANDOM-ORACLE MODEL 1256 RSA IMPLEMENTATION ISSUES AND PITFALLS 13 DIGITAL SIGNATURE SCHEMES 131 DIGITAL SIGNATURES – AN OVERVIEW 132 DE?NITIONS 133 THE HASH-AND-SIGN PARADIGM 134 RSA-BASED SIGNATURES 1341 PLAIN RSA SIGNATURES 1342 RSA-FDH AND PKCS #1 STANDARDS 135 SIGNATURES FROM THE DISCRETE-LOGARITHM PROBLEM 1351 IDENTI?CATION SCHEMES AND SIGNATURES 1352 THE SCHNORR IDENTI?CATION/SIGNATURE SCHEMES 1353 DSA AND ECDSA 136 CERTI?CATES AND PUBLIC-KEY INFRASTRUCTURES 137 PUTTING IT ALL TOGETHER – TLS 138 *SIGNCRYPTION 14 *POST-QUANTUM CRYPTOGRAPHY 141 POST-QUANTUM SYMMETRIC-KEY CRYPTOGRAPHY 1411 GROVER’S ALGORITHM AND SYMMETRIC-KEY LENGTHS 1412 COLLISION-FINDING ALGORITHMS AND HASH FUNCTIONS 142 SHOR’S ALGORITHM AND ITS IMPACT ON CRYPTOGRAPHY 143 POST-QUANTUM PUBLIC-KEY ENCRYPTION 144 POST-QUANTUM SIGNATURES 1441 LAMPORT’S SIGNATURE SCHEME 1442 CHAIN-BASED SIGNATURES 1443 TREE-BASED SIGNATURES 15 *ADVANCED TOPICS IN PUBLIC-KEY ENCRYPTION 151 PUBLIC-KEY ENCRYPTION FROM TRAPDOOR PERMUTATIONS 1511 TRAPDOOR PERMUTATIONS 1512 PUBLIC-KEY ENCRYPTION FROM TRAPDOOR PERMUTATIONS 152 THE PAILLIER ENCRYPTION SCHEME 1521 THE STRUCTURE OF Z? N 1522 THE PAILLIER ENCRYPTION SCHEME 1523 HOMOMORPHIC ENCRYPTION 153 SECRET SHARING AND THRESHOLD ENCRYPTION 1531 SECRET SHARING 1532 VERI?ABLE SECRET SHARING 1533 THRESHOLD ENCRYPTION AND ELECTRONIC VOTING 154 THE GOLDWASSER–MICALI ENCRYPTION SCHEME 1541 QUADRATIC RESIDUES MODULO A PRIME 1542 QUADRATIC RESIDUES MODULO A COMPOSITE 1543 THE QUADRATIC RESIDUOSITY ASSUMPTION 1544 THE GOLDWASSER–MICALI ENCRYPTION SCHEME 155 THE RABIN ENCRYPTION SCHEME 1551 COMPUTING MODULAR SQUARE ROOTS 1552 A TRAPDOOR PERMUTATION BASED ON FACTORING 1553 THE RABIN ENCRYPTION SCHEME