## 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]
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