Modern Cryptography and Networked Systems Security

Instructors

Prof. Dr.-Ing. Volker Roth

Description

This course gives a modern introduction to cryptography and cryptographic key management, followed by an introduction to cryptographic protocols and their applications in distributed systems security. Mathematical background is developed to the degree reasonable in an introductory class. In addition to the mathematical underpinnings of cryptographic primitives the course also touches on the importance of implementation for a secure system.

Time and Location

Lectures:

• Tuesdays, 16h - 18h, T9/005
• Thursdays, 12h - 14h, T9/005

Recitations (Tutorien):

• Mondays, 16h - 18h, T9/051

Note: The recitations commence in the second week of the semester.

Grading

The grade will be computed as a weighted sum as shown below. Passing the exam is necessary to pass the course.

• 80% exam
• 20% project

Students will be admitted to the exam if they pass the mid-term exam or they earn at least 50% of the points in n-2 home work assignments (where n is the overall number of assignments).

Homework

Below are the homework assignments. Each assignment is given on a Monday, and is due on the Monday two weeks later. You can turn in your assignments at the recitation or at Fabeckstraße 15 before the recitation.

• Homework 1 is due on November 15, 2010
• Homework 2 is due on November 29, 2010
• Homework 3 is due on December 13, 2010
• Homework 4 is due on December 17, 2010

Lectures

No lecture on Tuesday October 19, we begin on Thursday

Lecture 1, Thursday October 21

Topics:

• Welcome and administrativa
• Private key encryption
• Historic ciphers and their cryptanalysis
• Principles of modern cryptography

Read: sect. 7.3 of [1]

Lecture 2, Tuesday October 26

Topics:

• Perfectly-secret encryption
• Adversarial indistinguishability
• Vernam cipher
• Limitations of perfectly secure encryption

Read: chap. 2 of [2]

Lecture 3, Thursday October 28

Topics:

• Shannon's Theorem and its proof
• Introduction to computational security

Read: chap. 2 of [2]

Lecture 4, Tuesday November 02

Topic:

• Relaxations of perfect secrecy
• Efficient computation and negligible success probability
• Proofs by reduction
• Pseudorandomness and pseudorandom generators
• Indistinguishable encryptions in the presence of an eavesdropper
• Handling variable-length messages

Read: chap. 3 of [2], the anecdote in [3]

Lecture 5, Thursday November 04

Topics:

• Indistinguishable multiple encryptions in the presence of an eavesdropper
• Probabilistic encryption
• Chosen plaintext attacks
• Psedurorandom functions
• Indistinguishable encryptions under a chosen plaintext attack

Read: chap. 3 of [2], [4]

Lecture 6, Tuesday November 09

Topics:

• Pseudorandom permutations
• Block ciphers and operation modes

Read: chap. 3 of [2]

Lecture 7, Thursday November 11

Topics:

• Counter mode
• Chosen cipher text attacks and non-malleability

Read: chap. 3 of [2]

Lecture 8, Tuesday November 16

Topics:

• Encryption versus message authentication
• Message authentication codes
• Existential unforgeability under adaptive-chosen message attacks
• Replay attacks
• Constructions of fixed-length MAC
• Constructions of variable-length MAC

Read: chap. 4 of [2]

Lecture 9, Thursday November 18

Topics:

• CBC-MAC for fixed-length and variable-length messages
• Collision resistant hash functions
• Birthday attacks
• Merkle-Damgard transform

Read: chap. 4 of [2]

Lecture 10, Tuesday November 23

Topics:

• Encryption secure against chosen ciphertext attacks

Read: chap. 4 of [2]

Lecture 11, Thursday November 25

Topics:

• Practical constructions of pseudorandom permutations
• Substitution permutation networks
• Feistel networks
• DES and AES
• 2-DES, meet-in-the-middle attacks, 3-DES

Read: chap. 5 of [2]

Lecture 12, Tuesday November 30

Topics:

• Introduction to number theory
• Primes and divisibility
• Bezou's Lemma and the extended Euclidean algorithm
• Modular arithmetic
• Cyclic groups

Read: chap. 7 of [2], [5]

Lecture 13, Thursday December 02

Topics:

• The factoring assumption
• The RSA assumption
• The discrete logarithm assumption
• The DH assumptions
• Factoring and one-way functions
• Discrete logarithms and collision resistant hash functions

Read: chap. 7 of [2]

Lecture 14, Tuesday December 07

Topics:

• From private key management to public key cryptography
• Diffie-Hellman key exchange

Read: chap. 9 of [2]

Lecture 15, Thursday December 09

Topics:

• Public key encryption
• Public key encryption and indistinguishable encryptions

Read: chap. 10 of [2]

Lecture 16, Tuesday December 14

Topics:

• Hybrid encryptions secure against chosen plaintext atacks

Read: chap. 10 of [2]

Lecture 17, Thursday December 16

Topics:

• Attacks on text book RSA
• Implementation issues
• ElGamal encryption
• Chosen ciphertext attacks against RSA and ElGamal

Read: chap. 10 of [2]

No lecture on Tuesday December 21

No lecture on Thursday December 23

No lecture on Tuesday December 28

No lecture on Thursday December 30

Lecture 18, Tuesday January 04

Topics:

• Digital signature schemes
• The hash and sign paradigm

Read: chap. 12 of [2]

Lecture 19, Thursday January 06

Topics:

• Security in the random oracle model

Read: chap. 13 of [2], [6]

Lecture 20, Tuesday January 11

Topics:

• Homomorphic encryption
• The Paillier encryption scheme

Read: sect. 11.3 of [2], [7], [8]

Lecture 21, Thursday January 13

Topics:

• Key management
• Key distribution centers
• Public key directories
• Public Key Infrastructure
• Web of Trust
• Identity

Read: [9], [10]

Lecture 22, Tuesday January 18

Topics:

• Introduction to cryptographic protocols
• Needham Schroeder
• Kerberos

Read: [11]

Lecture 23, Thursday January 20

Topics:

• Secure Sockets Layer
• Secure Shell
• Short authenticated strings

Read: [12], [13], [14], [15], [16]

Lecture 24, Tuesday January 25

Topics:

• Wide area routing security
• Secure BGP
• Onion routing

Lecture 25, Thursday January 27

Topics:

• Bit committment
• Flipping coins over the telephone

Lecture 26, Tuesday February 01

Topics:

• Oblivious transfer
• Playing poker over the telephone

Lecture 27, Thursday February 03

Guest speaker: TBD

No lecture on Tuesday February 08, This lecture is given on February 7th, instead of the recitation.

Topics:

• Dining cryptographers
• Secret sharing

Lecture 28, Thursday February 10

Guest speaker: Dr. Kim Nguyen, Bundesdruckerei GmbH

Topic:

• Introduction to elliptic curves
• Groups based on elliptic curves
• Elliptic curve cryptography
• Applications

Lecture 29, Tuesday February 15

Class project presentations

Lecture 30, Thursday February 17

Final exam

Literature

1. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 2001.
2. Jonathan Katz, Yehuda Lindell. Introduction to Modern Cryptography. Chapman & Hall/CRC, 2008.
3. R. Morris and K. Thompson. Password security: a case history. Commun. ACM 22, 11 (Nov. 1979), 594-597.
4. Hongjun Wu, The Misuse of RC4 in Microsoft Word and Excel. IACR e-print number 007, 2005.
5. Victor Shoup. A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2008.
6. Mihir Bellare and Phillip Rogaway. Random Oracles are practical: a paradigm for designing efficient protocols. Proc. ACM Computer and Communications Security, November 1993.
7. Caroline Fontaine and Fabien Galand. A Survey of Homomorphic Encryption for Nonspecialists. EURASIP Journal on Information Security, October 2007.
8. Castelluccia, C., Chan, A. C., Mykletun, E., and Tsudik, G. 2009. Efficient and provably secure aggregation of encrypted data in wireless sensor networks. ACM Trans. Sen. Netw. 5, 3 (May. 2009), 1-36.
9. Loren M. Kohnfelder. Towards a practical public-key cryptosystem. B.Sc. thesis, MIT, May 1978.
10. Carl M. Ellison. Establishing Identity Without Certification Authorities. In Proc. USENIX Security Symposium, July 1996.
11. Martin Abadi and Roger Needham. Prudent Engineering Practice for Cryptographic Protocols. Digital Equipment Corporation, November 1995.
12. D. Brumley and D. Boneh. Remote timing attacks are practical. In Proc. 12th Usenix Security Symposium, 2003.
13. Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Proc. CRYPTO (1996). Lecture Notes In Computer Science, vol. 1109. Springer-Verlag, London, 104-113.
14. T. Dierks and C. Allen. The TLS Protocol Version 1.0. Internet Engineering Task Force Request for Comments 2246, January 1999.
15. Moxie Marlinspike. Null Prefix Attacks against SSL/TLS Certificates. Published online.
16. Moxie Marlinspike. Defeating OCSP With the Character '3'. Published online.