Cryptology I

Lecture spring 2017

Instructor Dominique Unruh <<surname> at ut dot ee>
Teaching assistant
Tore Vincent Carstens <<firstname dot thirdname at gmx dot de>
Lecture Period February 8, 2017 - May 24, 2017
Lectures Wednesdays, 12:15-13:45, room 218 (Paabel) (Unruh; may sometimes be switched with tutorial)
Practice sessions
Wednesdays, 16:15-17:45, room 220 (Paabel) (Unruh/Fauzi)
Course Material Lecture notes, blackboard photos (of practice), and exam study guide.
Language English
Mailing list ut-crypto1@googlegroups.com
Contact Dominique Unruh <<surname> at ut dot ee>


Topics covered

2017-02-15 (lecture)Classical ciphers.[video]
2017-02-15b (lecture)Perfect secrecy. One-time pad. Security and limitations of OTP. Streamciphers (basic construction). LFSR.[video]
2017-02-22 (lecture)Stream ciphers (ctd.). IND-OT-CPA security. Pseudo-random generators (PRG). Security proof for stream ciphers.[video]
2017-02-22 (practice)Breaking a substitution cipher. Malleability of one-time-pad (bank transfer). Attacking the linear congruence randomness generator.
2017-03-01 (lecture)Block ciphers. AES (construction). Feistel networks. Provable security vs. best effort.[video]
2017-03-01 (practice)Security proof: If G is PRG, then H(x,y):=G(x)||y is PRG. Insecurity of 3-round-Feistel.
2017-03-08 (lecture)Security notions of block ciphers: strong PRP. Provable security & "best-effort security". Security of encryption: IND-CPA. Modes of operation: ECB, CBC. Insecurity of ECB. IND-CPA security of CBC (only claim).[video]
2017-03-08 (practice)Security of AES with missing AddRoundKey/SubBytes/MixColumns/ShiftRows
2017-03-15 (lecture)Public key encryption. Textbook RSA. RSA-assumption. Weaknesses of textbook RSA.[video]
2017-03-15 (practice)Malleability of CBC mode, "Crypto competition": Authenticated encryption
2017-03-22 (lecture)ElGamal. Decisional Diffie-Hellman (DDH) assumption. IND-CPA (public-key). Security of ElGamal.[video]
2017-03-22 (practice)Breaking 3RSA for small messages. RSA with N=pqr
2017-03-29 (lecture)Malleability of ElGamal. Definition IND-CCA. Hybrid Encryption. Message authentication codes (MACs). Hash functions. Collision-resistance.[video]
2017-03-29 (practice)Repetition: ElGamal
2017-04-05 (lecture)Iterated hash. Merkle-Damgård construction. Insecurity of Merkle-Damgård as a MAC. HMAC.[video]
2017-04-05 (practice)Insecurity of ElGamal mod p. Quadratic residues.
2017-04-12 (lecture)EF-CMA definition. MAC from block cipher/PRF. Extending message space of MACs. CBC-MAC, DMAC, and their security. Davies-Meyer. Miyaguchi-Preneel. Birthday attacks for hashes.[video]
2017-04-12 (practice)Breaking Iterated Hash / Merkle-Damgård with various compression functions.
2017-04-19 (lecture)Signatures. EF-CMA. One-way functions. One-time signature construction.[video]
2017-04-19 (practice)Two variants of EF-CMA. Constructing bad MACs secure under these variants.
2017-04-26 (lecture)Tree-based signatures (how to get signatures from one-time signatures). Full-domain hash (FDH).[video]
2017-04-26 (practice)Constructing a secure protocol for movie download using PKE and signatures.
2017-05-03 (lecture)Random oracle model/heuristic. EF-CMA in random oracle model. Security proof of FDH.[video]
2017-05-03 (practice)Constructiong and security proof: One-way functions in the random oracle model. Unsoundness of random oracle heuristic. Insecurity of Lamport's one-time signature in twice-sign-scenario.
2017-05-10 (lecture)Symbolic cryptography. Needham-Schröder-(Lowe) protocols (NSL). Modeling security of NSL symbolically.[video]
2017-05-10 (practice)Repetition: PRFs, MACs and Random Oracle Heuristic.
2017-05-17 (lecture)Proving symbolic security of NSL.[video]
2017-05-17 (practice)Merkle-Puzzles.
2017-05-24 (lecture)Quantum cryptography (short overview).[video]
2017-05-24 (practice)Symbolic crypto analysis of "movie download" protocol

Homework

Your current amount of points in the homework can be accessed here.
Out Due Homework Solution
2017-02-172017-03-03Homework 1Solution 1, otp-xor.py
2017-03-032017-03-17Homework 2, ind-ot-cpa.py, prg.pySolution 2, ind-ot-cpa-solution.py, ind-cpa-solution.py
2017-03-212017-04-01Homework 3, ecb-distinguish.py, ecb-distinguish-2.txt, ecb-distinguish-1.txt, 3rsa-aes.pySolution 3, 3rsa-aes-adv.py, ecb-distinguish-sol.py
2017-04-042017-04-17Homework 4, hybrid.pySolution 4, hybrid-solution.py
2017-04-212017-05-05Homework 5, owf.pySolution 5, owf-solution.py
2017-05-082017-05-19Homework 6Solution 6
2017-05-222017-06-05Homework 7, sym-crypto-parts.pySolution 7, sym-crypto.py

Description

The course "Cryptology I" introduces the basics of cryptography. After discussing historic ciphers and their weaknesses, we introduce modern cryptographic primitives such as encryption and signature schemes, hash functions, one-way functions etc. We explain how the security of cryptographic schemes is defined and proven. We study advanced cryptographic schemes such as zero-knowledge proofs and secure function evaluation.

Requirements

"Elements of Discrete Mathematics" or some comparable mathematical foundations.

Reading

The following reading supplements this lecture (optional!)

Lindell and Katz, Introduction to Modern Cryptography, Chapman & Hall, 2007.
Materials from the course "Topics of Mathematics in Cryptology" (especially the chapter on probability and the one on modular arithmetic).