MAD 6478 Cryptanalysis - Course Information

The course will provide an introduction to some fundamental cryptanalytic techniques and tools. In particular, the following topics are to be discussed:

Algorithms for computing discrete logarithms (e.g., Shanks' baby-step-giant-step method and index calculus techniques)
Algorithms for factoring large integers (e.g., using elliptic curves and sieving techniques)
Analysis of block ciphers (e.g., differential and linear cryptanalysis)
Protocol level attacks (e.g., based on concurrent protocol execution)
Side channel attacks (e.g., using timing information or power analysis)
Theoretical attack models and provable security (e.g., for asymmetric encryption and signature schemes)

The course assumes familiarity with elementary algebra like computing with congruences and the Euclidean algorithm. Some background in cryptology is certainly helpful, but not required.
Parts of the course material will be taken from the book Cryptanalysis of number theoretic ciphers (Samuel S. Wagstaff, Chapman & Hall/CRC, 2003 [Wags03]). Also the Handbook of Applied Cryptography (A. Menezes, P. van Oorschot, S. Vanstone) [MvOV96] will be used, and for some topics I plan to make use of original conference articles. More information on the course can be found in the syllabus. So far the following topics have been addressed

Aug 23, 2005: Quick survey of different types of cryptographic schemes; recall of textbook RSA encryption and security problems related to it (like handling of small message spaces or Hastad's attack on small encryption exponents).
Literature: [Wags03; Ch. 1, 17.1, 24.3]
Aug 25, 2005: +++ lecture canceled due to Tropical Storm Katrina +++
Aug 30, 2005: Informal discussion of the problem of malleability using encryption with textbook RSA, ElGamal and the one-time pad as examples.
Literature: [Wags03; 17.4, 17.5]; [MvOV96, Ch. 8.2, Ch. 8.4]
Sep 1, 2005: Some criteria for and different types of cyclic groups used in cryptography: (prime order subgroups of the) multiplicative group of finite fields, elliptic curves.
Literature: [Wags03; Ch. 9.5, Ch. 12.1]
Sep 6, 2005: Shanks' baby-step-giant-step algorithm for computing discrete logarithms.
Literature: [Wags03; Ch. 9.3]
If you have no background in computer science, you may like to take a quick look at the Big O notation and the basic idea of Quicksort.
Sep 8, 2005: Quiz #1; brief introduction to Magma.
Sep 13, 2005: Complexity of Shanks' baby-step-giant-step algorithm; the index calculus method for computing discrete logarithms.
Literature: [Wags03; Ch. 14.3]; [MvOV96, Ch. 3.6.5]
Sep 15, 2005: Applying index calculus in the multiplicative group of finite prime and non-prime fields; the concept of subexponential running time; brief survey of Pollard's p-1 method.
Literature: [Wags03; Ch. 10.3]; [MvOV96, Ch 2.3.3., Ch. 3.2.3, Ch. 3.6.5]
Sep 20, 2005: Pollard's Rho Method for computing discrete logarithms.
Literature: [Wags03; Ch. 14.2.1]; [MvOV96, Ch. 3.6.3]
Sep 22, 2005: Fundamental properties of quadratic residues; definition and evaluation of the Legendre and Jacobi symbol.
Literature: [Wags03; Ch. 7.1-7.3]
Sep 27, 2005: Pollard's p-1 method; basic idea of factoring with elliptic curves.
Literature: [Wags03; Ch. 10.3, Ch. 12.2]; [MvOV96, Ch. 3.2.3, Ch. 3.2.4]
Sep 29, 2005: Quiz #2; ECM factoring
Literature: [Wags03; Ch. 12.2]; [MvOV96, Ch. 3.2.4]
Oct 4, 2005: Dixon's algorithm and the quadratic sieve for factoring integers.
Literature: [Wags03; Ch 13.2]; [MvOV96, Ch. 3.2.5, Ch 3.2.6]
Oct 6, 2005: Exam #1
Oct 11, 2005: Fault attacks; introduction to side channels; Simple Power Analysis (SPA).
Literature: [Wags03, Ch 24.5]; P. Kocher, J. Jaffe, B. Jun: Differential Power Analysis
Oct 13, 2005: Differential Power Analysis (DPA); introduction to timing attacks.
Literature: P. Kocher, J. Jaffe, B. Jun: Differential Power Analysis
Oct 18, 2005: Short introduction to block ciphers; substitution-permutation networks; DES; AES.
Literature: Ch. 3.1-3.2 of D. Stinson: Cryptography---Theory and Practice; 2nd edition; FIPS PUB 46-3: Data Encryption Standard (DES); FIPS PUB 197-3: Advanced Encryption Standard (AES)
You may also like to take a look at the Wikipedia pages on DES and AES.
Oct 20, 2005: Timing attacks; countermeasures against side-chanel attacks.
Literature: [Wags03, Ch. 23.4], P. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems
Oct 25, 2005: +++ lecture (incl. Quiz #3) canceled due to Hurricane Wilma +++
Oct 27, 2005: +++ lecture canceled due to Pi Mu Epsilon Day/Hurricane Wilma+++
Nov 1, 2005: +++ lecture canceled due to Hurricane Wilma +++
Nov 3, 2005: Introduction to provable security; formalizing public key encryption; IND-CPA and IND-CCA2
Literature: [Bellare et al.: Relations Among Notions of Security for Public-Key Encryption Schemes]
Nov 8, 2005: IND-CPA and IND-CCA2; RSAES-OAEP
Literature: [Bellare et al.: Relations Among Notions of Security for Public-Key Encryption Schemes], [PKCS #1 v2.1: RSA Cryptography Standard]
Nov 10, 2005: Formalizing malleability; NM-CCA and IND-CCA
Literature: [Bellare et al.: Relations Among Notions of Security for Public-Key Encryption Schemes]
Nov 15, 2005: Introduction to digital signatures; signing with ElGamal.
Literature: [MvOV96, Ch. 11]
Nov 17, 2005: Introduction to zero-knowledge; Fiat-Shamir identification protocol.
Literature: [MvOV96, Ch. 10.4]
Nov 22. 20005: Desmedt-Odlyzko selective forgery attack; security notions for signatures schemes; EF-CMA; key substitution.
Literature: [A. Menezes: Evaluation of Security Level of Cryptography: RSA Signature Schemes (PKCS#1 v.1.5, ANSI X9.31, ISO 9796), Sec. 3]; [A. Menezes and N. Smart: Security of Signature Schemes in a Multi-User Setting (Designs, Codes and Cryptography 33, 261-274, 2004)]; [J.-M. Bohli et al.: Key substitution attacks revisited: Taking into account malicious signers (Int. J. Inf. Secur. (2005)]
Nov 29, 2005: Short introduction to linear and differential analysis of block ciphers.
Literature: H. M. Heys: A Tutorial on Linear and Differential Cryptanalysis
Dec 1, 2005: Security requirements for (password-authenticated) two-party key establishment; Lowe's attack on the Needham-Schroeder public-key protocol.
Literature: D. P. Jablon: Strong Password-Only Authenticated Key Exchange; G. Lowe: Breaking and Fixing the Needham-Schroeder Public-Key Protocol using FDR
Dec 6, 2005: Homework #3: Presentations by the course participants
Dec 8, 2005: Exam #2

I would like to thank all course participants for their great commitment and continuous support of the course!

For questions or comments, please feel free to contact me anytime (see my homepage for email, phone number, etc.).

Dec 8, 2005