Exercises are due 2 weeks after the lecture, and can be submitted in the course mailbox

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

- 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 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?

- 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 2: Generalize the approximate analysis of entropy rate to the case of a source which emit symbols 1,2,3,...,k with probabilities p

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?

- Elad Barkan, Eli Biham, Adi Shamir, Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs, 2006 [paper] [slides]

- Alex Biryukov, Adi Shamir, Structural Cryptanalysis of SASAS, Eurocrypt 2001, pp. 394-405 [paper] [slides]

- 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 2: Consider any 5-round Feistel structure with invertible F

- 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 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 S

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.

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

- 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

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

- Joux's multicollision attack and extensions
- Examples of hash functiosn: MD4, SHA-0/1
- Differential attacks on hash functions

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