Introduction to cryptography
I teach Introduction to cryptography [NDMI100] in the winter semester of 2020/2021. The lecture will cover the basics of both theoretical and practical cryptography, focusing on protocols currently used on the Internet.
The lectures will be held online on Wednesdays from 12:20. You should have received a Zoom link by e-mail.
If you want to consult anything, please write an e-mail to mares+kry@kam.mff.cuni.cz and we will discuss possibilities.
date | topics | recording |
---|---|---|
7. 10. | Cryptographic primitives: symmetric and asymmetric ciphers, hash functions, random generators. Protocols and roles. Kerckhoffs principle. Simple protocols: multi-party communication, signatures, hybrid ciphers, challenge-response authentication. Puzzle: How to toss a coin over a phone call? How to build an auction protocol? | video board |
14. 10. | Commitment using hash functions. Designing an auction protocol: padding, nonces, sequence numbers, signatures, session IDs. Know your enemy. Basic types of cryptographic attacks. Security level. Different kinds of "Birthday attacks". One-time pad and Vernam's cipher. | video board |
21. 10. | Perfect security and its limits. Secret sharing and threshold schemes (construction with polynomials). Introduction to symmetric ciphers. Block ciphers: trivial examples, an attempt to define security, ideal block ciphers. General constructions: iterated ciphers, substitution-permutation networks, Feistel networks. DES: history, structure. | video board |
28. 10. | No lecture today, choose your own holiday :) | |
4. 11. | DES: key schedule, critique, work-arounds (3-DES). AES a.k.a. Rijndael: history, structure, critique. Further AES finalists: Serpent and Twofish. How to (mis)use a block cipher: padding, modes ECB, CBC, CTR, and OFB; ciphertext stealing. Puzzle: Why is the security level of 2-DES only 57 bits? | video board |
11. 11. | Information leaks in CBC and CTR modes. Padding oracle attacks on CBC. Stream ciphers (briefly): LFSR-based constructions, eSTREAM project, Trivium, RC4, ChaCha20. Hash functions: requirements. | video board |
18. 11. | Hash functions: Merkle-Damgård construction by iterating compression function. How to obtain a compression function: Davies-Meyer construction from a block cipher. Birthday attacks on hash functions. Examples: MD5, SHA-1, SHA-2. Sponge functions: principle and analysis for random permutations. | video board |
25. 11. | Hash functions: Keccak, SHA-3, SHAKE-n and others. Parallel hashing: Merkle trees, Sakura. Symmetric signatures (MACs): construction from hash functions (KMAC and HMAC), different ways of combining a MAC with a cipher. CBC-MAC. Information-theoretic MAC from 2-independent linear functions or from polynomials. | video board |
2. 12. | Practical polynomial MACs: GCM mode, Poly1305 (sketch). Generating random bits: pseudo-random generators from symmetric ciphers, physical randomness (LavaRand, circular oscillators, …), combining both – Fortuna, RDRAND, /dev/random. Putting all symmetric cryptography together: a secure channel. Basics of algorithmic number theory: Complexity of arithmetics. | video board |
9. 12. | Basics of algorithmic number theory: Euclid's algorithm and Bézout's coefficients. Multiplicative group modulo N. Little Fermat's and Euler's theorem. Lagrange's theorem on subgroups (without proof). Chinese remainder theorem and its constructive version. Computing Euler's function. Factoring vs. primality testing. Fermat and Rabin-Miller tests (R-M without proof), Carmichael numbers, mention of Agarwal's deterministic test. Generating large primes. Multiplicative group is cyclic, discrete logarithms, how to find a generator. | video board |
16. 12. | More number theory: Discrete square roots, Legendre symbol. RSA cipher: Definition, acceleration tricks. Properties of RSA: commutativity, homomorphism with respect to multiplication (application: blind signatures). Attacks: short messages, small secret exponent, meet in the middle, similar primes, similar messages, multiple keys with the same modulus. A brief note on semantic security. RSA padding and mention of Bleichenbacher attack. Diffie-Hellman key exchange, signing the result/protocol, quadratic residues and (non)uniformity, problems with subgroups, DH in general groups. ElGamal cryptosystem and its derivation from DH. | video board |
6. 1. | Implementation issues: how to not develop software, real-world attacks, various kinds of side channels, storing and destroying secrets, keeping state. Lessons from physical security. | video board |
25. 1. | An optional lecture on practical protocols: Handling passwords: hashing, salting, key derivation functions (PBKDF2). Interactive authentication: the SCRAM protocol. DNSSEC (secure domain name system). Kerberos. | video board |
Plan: An optional lecture on practical protocols: Verifying identity: directory services, certification authorities, trust on first use, web of trust. The SSL/TLS protocol: cipher suites, record protocol, handshake protocol, alert protocol, types of key exchange, session resume, re-negotiation, and a collection of attacks. The Internet PKI: X.509, certification authorities and their behavior. |
Exams
Exam dates are listed in SIS, please sign up there. I prefer examining in person, but it is hard for you to get to Prague, there are also distance exams listed. If no date suits you, let me know and we can arrange another one. If you want to consult anything before the exam, feel free to ask.
You are expected to know the theory presented at the lecture (constructions, theorems, and proofs) and use it to analyse (i.e., break) simple protocols.
Sources
- Web page of the previous run of this lecture
- Web page of the first run of this lecture (in Czech, includes video recordings).
- My notes (in Czech)
- Niels Ferguson, Bruce Schneier: Practical Cryptography. Wiley Publishing, 2003.
- Jonathan Katz, Yehuda Lindell: Introduction to Modern Cryptography, 2nd Edition. CRC Press, 2015.
- Douglas Stinson, Maura Paterson: Cryptography – Theory and Practice. CRC Press, 2018.
- Dan Boneh, Victor Shoup: A Graduate Course in Applied Cryptography.
- Mike Rosulek: The Joy of Cryptography.
- Ross Anderson: Security Engineering, Wiley Publishing, 2008.
- Martin Mareš: Algoritmy okolo teorie čísel (in Czech).
- Ivan Ristić: Bulletproof SSL and TLS, Feisty Duck Publishing, 2017.