# Introduction to cryptography

I teach Introduction to cryptography [NDMI100] in the winter semester of 2023/2024. The lecture will cover the basics of both theoretical and practical cryptography, focusing on protocols currently used on the Internet.

Lectures will be on Thursdays from 12:20 in S4.

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

22. 2. | Cryptographic primitives: symmetric and asymmetric ciphers, hash functions, random generators. Protocols and roles. Kerckhoffs principle. Simple protocols: multi-party communication, signatures (symmetric and asymmetric) hybrid ciphers, challenge-response authentication. Designing an auction protocol: padding, nonces, sequence numbers, signatures, session IDs. | video |

29. 2. |
Basic types of cryptographic attacks. Security level. Know your enemy.
Different kinds of "Birthday attacks".
One-time pad and Vernam's cipher.
Perfect security and its limits.
Secret sharing and threshold schemes (construction with polynomials).
Exercise: How to toss a coin over a phone call?
| video |

7. 3. |
Introduction to symmetric ciphers.
Block ciphers: trivial examples, an attempt to define security. General constructions: iterated ciphers, substitution-permutation networks, Feistel networks.
DES: history, structure, critique, work-arounds (3-DES).
AES a.k.a. Rijndael: history, structure, critique.
Exercise: Why is the security level of 2-DES only 57 bits?
Further reading::
EFF DES cracker,
details of AES.
| video |

14. 3. |
How to (mis)use a block cipher: padding, modes ECB, CBC, CTR.
Information leaks in CBC and CTR modes.
Padding oracle attacks on CTR and CBC.
Stream cipher sketches: LFSR-based constructions, eSTREAM project, Trivium.
Further reading: Trivium,
ChaCha20,
ciphertext stealing.
Illustrations: Block cipher modes
(plaintext,
ECB,
CBC),
visual secret sharing
(layer 1,
layer 2,
both layers put together),
| video |

21. 3. |
There will be no lecture.
| |

28. 3. | More stream ciphers: RC4, ChaCha20. Hash functions: requirements, Merkle-Damgård construction by iterating compression function, length extension attacks. Birthday attacks on hash functions: the tortoise, the hare, and the turtle. How to obtain a compression function: Davies-Meyer construction from a block cipher. Practical hash functions: MD5 (broken), SHA1 (broken), SHA2, and SHA3 (sketch). | video |

4. 4. |
Sponge hashes: analysis for random permutations, Keccak, SHA3-n, SHAKE-n.
Parallel hashing: Merkle trees and 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.
Practical polynomial MACs: GCM mode, Poly1305 (sketch).
| video |

11. 4. | 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. 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). | video |

18. 4. | More number theory: 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, note on Agarwal's deterministic test. Generating large primes. Multiplicative group is cyclic, discrete logarithms, how to find a generator. Discrete square roots, Euler's criterion. | video |

25. 4. | RSA cipher: Definition, correctness, acceleration tricks. Properties of RSA: swapping roles of keys, 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, same message and multiple keys, effects of computation errors. Semantic security: RSA preserves Jacobi symbol, but determining the lowest-significant bit or the half of the interval is hard. RSA padding and a note on Bleichenbacher attack. RSA versus factoring. | video |

2. 5. |
Diffie-Hellman key exchange, signing the result/transcript,
quadratic residues, problems with subgroups, DH in general groups.
ElGamal cryptosystem and its derivation from DH.
Elliptic curves over reals and over finite fields (sketch only).
Asymmetric signatures: attack types, signatures using RSA, hashing is essential.
ElGamal signatures, notes on EC(DSA), consequences of weak random numbers, and
deterministic DSA.
Further reading on elliptic curves:
blog post series
by Andrea Corbellini,
the SafeCurves project.
| video |

9. 5. | Putting bits together: secure channel protocol, forward security. Implementation issues: how to not develop software, real-world attacks, various kinds of side channels, storing and destroying secrets. Lessons from physical security. | video |

16. 5. | Real-world cryptography. Handling passwords: hashing, rainbow tables, salting, key derivation functions (PBKDF2). Interactive authentication: challenge-response, the SCRAM protocol. DNSSEC (secure domain name system). Verifying identity: directory services, certification authorities, trust on first use, web of trust. Double ratchet protocol for protecting two-party messaging. | video |

23. 5. | Real-world cryptography continued: TLS 1.3 (and its predecessors) – record protocol, handshake protocol, alert protocol, key exchange and authentication, pre-shared keys and session resume, 0-RTT handshake, interesting extensions. The Internet PKI: X.509, certification authorities and their behavior, revoking certificates (CRL, OCSP, stapling), transparency logs. | video |

## Exams

Exam dates are listed in SIS, please sign up there. 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

- Previous runs of the lecture: 2023 (with video recordings), 2020 (partial recordings), 2019 (with Czech video recordings).
- My notes (in Czech), also for Double Ratchet and TLS.
- Study text (in Czech, very much work in progress)
- 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, 2nd edition, 2021.
- Moxie Marlinspike, Trevor Perrin: The Double Ratchet Algorithm