Private Key Cryptography (Spring 2008) Course

Instructor: Adi Shamir

Teaching assistant: Ya'akov Hoch

Administrative

  • Exercises should be submitted in class two weeks after receiving them. Please submit printed exercises (preferably using LaTeX).

Resources

Most resources are available [online]. The links denoted by (password required)  require a username and password (given in class). 
If none of the above is given and you obtain the paper by other means, please e-mail a copy to the TA, so the TA will prepare additional copies for the library.

General

  • Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. [online]
  • Shafi Goldwasser and Mihir Bellare, Lecture Notes on Cryptography. [online]
  • Bruce Schneier, Applied Cryptography, 2nd edition,  John Wiley & Sons, 1996
  • Many recent crypto papers can be found in IACR ePrint.
  • A CD containing the proceedings of Crypto, Eurocrypt and Asiacrypt is available from the library.

Exercises

Ex1 (due March 3rd)

Question 1: Solve the two cryptograms distributed in class.
Question 2: Show how to break the autokey system in time considerably shorter than guessing the keyword. Explain what happens when you guess an incorrect length of keyword in your approach.

Ex2 (due March 10th) – Questions 4' and 4'' replace question 4

Question 1-3: Solve the problems on the page distributed in class.
Question 4: Propose functions f of the state of a shift register which will make the expected cycle length O(N) instead of O(√N).

Question 4': Characterize cases in which the Galois form of feedback is expected to produce O(N) states before repeating.

Question 4'': Consider a SR with r=3, having 8 possible feedback polynomials. Compare the state transitions for regular LFSRs and the Galois form.

 

Ex3 (due March 17th)

Question 1: Show how to attack a plain LFSR cryptographic scheme when the feedback polynomial and the initial state are unknown.

Question 2: Given the infinite sequence of bits generated by a LFSR, its bits satisfy the original recurrence. Which other recurrence relations are satisfied by the sequence.

 
 

Ex4 (due March 24th)

Question 1: Describe how to compute the k'th bit produced by a given LFSR of n bits, in time logarithmic in k and polynomial in n.

 

Question 2: (Counter Assisted Modes): Show that the diversity of any subsequence on length k is at least O(\sqrt k) based on the observation that if

x(i)=x(j) then x(i ± 1) ≠ x(j ± 1)

 

Question 3: (LFSR where the output bit is generated by an 8 -> 1 table): Try to attack this scheme when there are fewer input bits to the table and\or

when the taps are consecutive, when the LFSR and the table are know.

 

Ex5 (due March 31st)

Question 1: Analyze the expected length of ciphertext that can be generated without overlaps when using an LFSR with different IVs.

Question 2: Analyze Crypto-1 when the change in the initial state can be chosen by the attacker.

Question 3: Find a better attack on Crypto-1 when n is large, k=20 and f does not have a special structure (so the statistical attack is harder). Preprocessing is free but the resultant table should not be too large.

 

Ex6(due April 7th)

Question 1: Optimize the algorithm for finding the actual cycle entry point in the k-stack algorithm.

Question 2: Find as many non-random properties in the various flavors of f, with respect to f itself.

Question 3: Analyze the exact region of M,T for which the relation M^2*T=N^2 can be realized.

Question 4 (given last week): Study the details of Trivium and Grain and find some simplifications that will make one of them easy to break.

 

Ex9(due May 5th)

Question 1: Show that the Time/Memory tradeoff obtained by stopping each table prematurely and using the same #tables is inferior (consider also the case of huge #data points so we need <1 table).

Question 2: What is the most uniform realizable point on the triple tradeoff curve?

Question 3: In general Hellman tradeoff, what happens when the input of f is larger or smaller than  the natural output ?

Question 4: In stream ciphers we can also consider a mapping from key to output prefix.

(i)                  Can you still get the benefit from the Time/Memory/Data tradeoff ?

(ii)                How should you take advantage of the fact that in the pair (Key,IV) IV is known ? (Possibilities: use IV simply as a longer key or prepare tables for a subset of the IVs and wait until they happen)

 

 

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, [paper] (password required)
      • D. Boneh, M. K. Franklin, Identity-Based Encryption from the Weil Pairing, proc. CRYPTO 01, 213--229, Springer, 2001, [paper]
  • Modes of attack
    • Known ciphertext
    • Known plaintext
    • Chosen plaintext
    • Etc.
  • 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)

Lecture 2:  Shannon's Theory

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

 

Lecture 3:  Stream Ciphers

  • General shift registers
  • T-functions
  • Linear feedback shift registers

 

Lecture 5:  Mifare, Trivium and Grain

 

 

 

Lecture 6: Time/memory tradeoffs

  • Martin E Hellman, A cryptanalytic Time-Memory Trade-Off, 1980 [paper]
  • Phillipe Oechslin, Making a Faster Cryptanalytic Time-Memory Trade-Off, 2003 [paper]
  • Elad Barkan, Eli Biham, Adi Shamir, Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs, 2006 [paper] [slides]
  • Slides from class [slides]

 

Lecture 7: Time/memory tradeoffs continued and A5/1

Lecture 8: Fault Analysis of Stream Ciphers

 

Lecture ??: DES and Differential Cryptanalysis

 

 

Special thanks to Eran Tromer for part of the material on this page