Idea Transcript
Secret Key Cryptography (Spring 2006) course Instructor: Adi Shamir Teaching assistant: Eran Tromer
Exercises are due 2 weeks after the lecture, and can be submitted in the course mailbox
Lecture outlines and resources Most resources are available [online]. The links denoted by require a subscription to some web service, but can be accessed through the Weizmann Institute web proxy. The links denoted by require the username and password given in class. For some papers there is a reserved copy at [library]
Lecture 1: Introduction Types of cryptosystems Secret key cryptography Public key cryptography W.Diffie and M.E.Hellman, New directions in cryptography, IEEE Transactions on Information Theory, IT-22, 6, pp.644-654, 1976, [paper] Identity-based encryption A. Shamir, Identity-based cryptosystems and signature schemes, proc. CRYPTO 84, 47--53. Springer, 1985 D. Boneh, M. K. Franklin, Identity-Based Encryption from the Weil Pairing, proc. CRYPTO 01, 213--229, Springer, 2001 Modes of attack Black-box analysis: known ciphertext, known plaintext, chosen plaintext, related key Side-channels: timing attacks, power analysis, fault analysis, cache analysis Foundations of cryptography Oded Goldreich, Foundations of Cryptography - Basic Tools, Cambridge Unviersity Press, 2001 Oded Goldreich, Foundations of Cryptography - Basic Applications, Cambridge Unviersity Press, 2004 Fragments of the above books: [drafts] Classical (historial) ciphers Caesar's cipher, exhaustive search Vigenere cipher,Wlliam Friedman's "Index of Coincidence" Monoalphabetic substitution cipher The book method Autokey (key = secret prefix + shifted plaintext) Exercise 1: Solve the cryptograms handout. Exercise 2: Show how to break the autokey method (by method better than the generic observation that the sum of two English text hased bias statistics).
Lecture 2: Enigma History Reverse-engineering using permutation groups Discovering the message key using cillies Appendix: Rejewski's method for recovering the Enigma message password [online] Discovering the ring settings using perforated sheets Deducing plugboard position using known plaintext "cribs" (brief sketch ) Resources: Józef Garliński, Intercept - The Enigma War, J.M. Dent & Sons Ltd., 1979 [excerpt (6MB)] Andrew Hodges, Alan Turing: The Enigma, Walker & Co., 2000 [excerpt: (9MB)] Diagrams and pictures of the Enigma [website] Marian Rejewski, An Application of the Theory of Permutations in Breaking the Enigma Cipher, Applicationes mathematicae, 16(4), 1980 [online] Turing's Treatise on the Enigma [scans (8MB)] [retyped and edited] Wikipedia entries: Enigma, Enigma rotor details, Cryptanalysis of the Enigma, Marian Rejewski Tony Sale,Virtual Bletchley Park, The Breaking of Enigma by the Polish Mathematicians [web page] Exercise 1: Prove that for a permutation C=PQ, where each of P and Q transposed all elements in pairs, every cycle size appears an even number of times in C. Exercise 2: Given a 1000-character Enigma ciphertext, how long does a known plaintext fragment have to be in order to be uniquely placeable via the exclusion property?
Lecture 3: Permutations, Shannon's theory Solving systens of equations in permutation groups U. Feige, A. Fiat, A. Shamir, I. Shimshoni, G. Tardos, Planning and Learning in Permutation Groups, Proceedings of the 30-th Symposium on Foundations of Computer Science, Durham, NC, October 1989, 274--279 [paper] [slides] Basic information theory Rate and redundancy C. Shannon, Communication Theory of Secrecy Systems [paper] Shannon's information-theoretical approach for cipher strength analysis Shannon's random cipher model, unicity distance C. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July and October, 1948. [paper] Exercise 1: Implement the above algorithm for solving equations in permutation groups, and test experimentally for n=1 (number of states), k=2 (permutations alphabet size), r=13 (word length). What is the critical number of equations t0 needed for a random system to be solved with probability half? Exercise 2: Generalize the approximate analysis of entropy rate to the case of a source which emit symbols 1,2,3,...,k with probabilities p1 ,p2 ,p3 ,...pk (whose sum is 1). Exercise 3: Suppose an English plaintext is encrypted by addition with t different English text keys. What is the minimal t for this to be secure, in Shannon's model?
Lecture 4: Time/memory tradeoffs Elad Barkan, Eli Biham, Adi Shamir, Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs, 2006 [paper] [slides]
Lecture 5 Alex Biryukov, Adi Shamir, Structural Cryptanalysis of SASAS, Eurocrypt 2001, pp. 394-405 [paper] [slides]
Lecture 6: Cryptanalysis of DES Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993 Eli Biham, Adi Shamir, Differential cryptanalysis of DES-like cryptosystems, Technical report CS90-16, Weizmann Institute of Science, [paper] C. de Canniere, A. Biryukov, B. Preneel, An introduction to block cipher cryptanalysis, Proceedings of the IEEE vol. 94 issue 2, Feb. 2006, 346--356 [paper] For broader suveys, see the relevant chapters of: Orr Dunkelman, Techniques for Cryptanalysis of Block Ciphers, Ph.D. thesis [paper] Elad Barkan, Cryptanalysis of Ciphers and Protocols, Ph.D. thesis [paper] Exercise 1: Show how to attack DES with incomplete avalanche (reduced rounds) via a meet-in-the-middle-attack. Exercise 2: Consider any 5-round Feistel structure with invertible Fi's. Prove that the differential pattern (0,A)->(0,A) never happens.
Lecture 7: Differential cryptanalysis of DES (cont.) Arithmetic differentials (plus instead of XOR) Modifications of DES Changing or eliminating P or E Changing the S-boxes Independent keys DES-X Characteristic vs. differential Proving resistance against differential attacks (upper bounding characteristics' probability) Design of linear mapping and relation to error-correcting codes Fault attacks (single-bit faults in last rounds) Impossible differential attacks Find by exhaistive enumeration of reduced variant (smaller, random S-boxes) Exercise 1: Check the effect of changing the P permutation on the iterative property of DES (prob. 1/234). Exercise 2: Find the maximum differential property in a random S-box of 6->4 bits Exercise 3: Experimentally find the best differential probability of an S-box layer followed by a bit permutation layer, with input width 128 bits, where every Si is chosen as a random 4->4 bit function and P is a random 128->128 bit permutation. What are the implications on attacking iterated SPSPSP..SP systems -- how many layers can you attack? Exercise 4: Show the stages for an attack of DES when it is known that a single-bit fault has occured on the input of a single S-box on the 15th or 16th round. Cover all cases for the location of the faults.
Lecture 8: Linear cryptanalysis Eli Biham, On Matsui's linear cryptanalysis, proc. Eurocrypt 1994, LNCS 950, 341--355, 1995 [paper] Mitsuru Matsui, Linear cryptanalysis method for DES cipher, proc. Eurocrypt '93, LNCS 765,386--397. Springer, 1993 [paper] Piling-up lemma [Wikipedia entry]
Lecture 9: More on cryptanalysis and cipher design Differential-linear cryptanalysis Boomerang attacks General constructions of block ciphers: SP networks, Feistel networks, IDEA AES: Magenta, RC6, Serpent, Rijndael Algebraic attacks on Rijndael Bitslicing Modes of operation: ECB, CBC, CFB, OFB, for multiple encryptions
Lecture 10: Hash functions Security requirements: preimage resistance, 2nd preimage resistance, collision resistance Applications Constructions: Matyas-Meyer-Oseas, Davies-Meyer, Miyaguchi-Preneel Concatenated constructions, Joux's attack Antoine Joux, Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions, proc. CRYPTO 2004, LNCS 3152, pp 306-31, Springer, 2004 [paper] Jonathan J. Hoch, Adi Shamir, Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions, proc. FSE 2006 [paper] [PowerPoint slides]
Lecture 11: Hash functions (cont.) Joux's multicollision attack and extensions Examples of hash functiosn: MD4, SHA-0/1 Differential attacks on hash functions
Lecture 12: Side-channel and fault attacks Power analysis (simple, differential) Paul Kocher, Joshua Jaffe, Benjamin Jun, Differential power analysis, proc. CRYPTO '99, LNCS 1666, pp. 388--397, 1999 [paper] Timing attacks Cache attacks Dag Arne Osvik, Adi Shamir, Eran Tromer, Cache attacks and countermeasures: the case of AES, proc. RSA Conference Cryptographers Track (CT-RSA) 2006, LNCS 3860, 1--20, Springer, 2006 [extended version] [rump session PowerPoint slides] [detailed PowerPoint slides] Power analysis of RFID tags Yossi Oren, Adi Shamir, Power Analysis of RFID Tags, 2006 [web site]]