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 (non-free) require a subscription to some web service, but can be accessed through the Weizmann Institute web proxy. The links denoted by (password required)  require the username and password given in class. For some papers there is a reserved copy at [library]

Lecture 1: Introduction

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

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

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

Lecture 5

Lecture 6: Cryptanalysis of DES

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.)

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

Lecture 9: More on cryptanalysis and cipher design

Lecture 10: Hash functions

Lecture 11: Hash functions (cont.)

Lecture 12: Side-channel and fault attacks