CSE 207B, Fall 2024
Applied Cryptography

Instructor:
  Nadia Heninger
  Office hours: Thursdays 3:30-4:30pm EBU3B 3138 or outside CSE depending on weather; on Zoom following class for Zoom lectures

TA:
  Adam Suhl OH Friday 3:30-4:30pm EBU3B B270A (CSE Basement) or outside CSE depending on weather

Lectures:
  Tuesday/Thursday 2pm-3:20pm WLH 2112
  Lectures are over Zoom where noted on the schedule and in person otherwise.

Class Resources:
  Gradebook on Canvas
  Q&A on Piazza

Grading:

There will be no final exam.

Your grade will be your average homework score.

Course Overview

This is a course on applied cryptography, with a significant focus on cryptanalysis. Topics to be covered include

Prerequisites

If you are a CSE graduate student, you should take CSE 202 and do well in it before taking this class. If you are a math grad student, you probably want to have taken a proof-based CS algorithms class, and you will need to be able to program in Python. If you are an undergraduate, you should have taken CSE 107 and gotten an A.

This course is independent of CSE 207A, modern cryptography. Some of the material will overlap, but neither is a prerequisite for the other.

Enrollment and waitlist

The waitlist is being processed by the department according to department rules. If you want to take this class and are still on the waitlist, you should attend the first week of lectures and turn in the first homework. If you are on the waitlist, you will have access to Canvas/Piazza/Gradescope.

Schedule

Topic References Assignments
9/26 Introduction, one-time pad
Lecture via Zoom

Lecture slides 		Boneh & Shoup Ch. 2.1

Further reading:
Communication theory of secrecy systems Shannon 1949
Cryptanalysis of the Lorenz cipher (video)
Did a broken random number generator in Cuba help expose a Russian espionage network? by Matt Blaze 2020
A History of US Communications Security by David Boak 1973

 Homework 1 Available
10/1
PRGs and stream cipher encryption
Lecture via Zoom

Lecture slides 		Boneh & Shoup Ch. 2.2, Ch. 3.1-3.3

Further reading/Research directions:
All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS by Vanhoef and Piessens
Attacks Only Get Better: Password Recovery Attacks Against RC4 in TLS by Garman, Paterson, and Van der Merwe
On the security of RC4 in TLS and WPA by AlFardan, Bernstein, Paterson, Poettering, and Schuldt 2013
The ChaCha family of stream ciphers by Bernstein
Security analysis of pseudo-random number generators with input: /dev/random is not robust by Dodis Pointcheval Ruhault Vergnaud Wichs 2013
10/3 Block ciphers
Lecture via Zoom

Lecture slides 		Boneh & Shoup Ch. 4.1-4.2

Further reading/Research directions:
Biclique Cryptanalysis of the Full AES by Bogdanov, Khovratovich, and Rechberger 2011
 Homework 2 Available
10/8 PRFs, chosen plaintext attacks, block cipher modes of operation
Lecture via Zoom

Lecture slides 		Boneh & Shoup Ch. 4.4, Ch. 5

Further reading/research:
Stealthy Dopant-Level Hardware Trojans by Becker, Regazzoni, Paar, Burleson 2013
 Homework 1 Due
10/10 Message authentication codes and message integrity; problems with CBC mode
Lecture via Zoom

Lecture slides 		Boneh & Shoup Ch. 6

Further reading:
Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS... by Vaudenay 2002
Here come the xor ninjas by Duong and Rizzo 2011
Compression and information leakage of plaintext by Kelsey 2002
The CRIME attack by Rizzo and Duong 2012
 Homework 3 Available
10/15 Hash functions
Lecture in person

Lecture slides 		Boneh & Shoup Ch. 8

Further reading/research directions:
A cryptanalytic time-memory tradeoff by Hellman 1980
Parallel collision search with cryptanalytic applications by van Oorschot and Wiener 1999
The making of Keccak by Bertoni, Daemen, Peeters, Van Assche 2015
MD5 to be considered harmful today by Sotirov, Stevens, Appelbaum, Lenstra, Molnar, Osvik, de Weger 2009
Counter-cryptanalysis by Stevens 2013
Speeding up detection of SHA-1 collision attacks using unavoidable attack conditions by Stevens and Shumow 2017
The first collision for full SHA-1 by Stevens, Bursztein, Karpman, Albertini, Markov 2017
Homework 2 Due
10/17 Hash functions, MACs, and authenticated encryption
Lecture in person

Lecture Slides 		Boneh & Shoup Ch. 8.7, 9

Further reading:
This POODLE Bites: Exploiting The SSL 3.0 Fallback by Möller, Duong, Kotowicz 2014
10/22 Computational number theory: Modular arithmetic, groups, rings, fields, efficient algorithms and hard problems
Lecture in person

Lecture Slides 		Boneh & Shoup Appendix A.

Further reading:
A Computational Introduction to Number Theory and Algebra, Ch. 3, 6 by Shoup
Fast multiplication and its applications by Bernstein
 Homework 3 Due
10/24 Diffie-Hellman, elementary discrete log cryptanalysis
Lectures in person for rest of quarter

Lecture Slides 		New Directions in Cryptography by Diffie and Hellman 1976
Boneh & Shoup Ch. 10
HAC Ch. 3.6
On Diffie-Hellman Key Agreement with Short Exponents by van Oorschot and Wiener
10/29
Chinese Remainder Theorem, Pohlig-Hellman algorithm, public-key cryptography, RSA
Guest lecture: Adam Suhl

Lecture Slides 		Boneh & Shoup Ch. 11
A method for obtaining digital signatures and public-key cryptography by Rivest, Shamir, and Adleman 1978

Further reading:
A personal view of average-case complexity by Impagliazzo 1995
10/31 Elementary factoring algorithms and RSA cryptanalysis
Guest lecture: Adam Suhl

Lecture Slides 		Boneh & Shoup Ch. 12

Further reading/Research directions:
Why Textbook ElGamal and RSA Encryption Are Insecure by Boneh, Joux, and Nguyen 2000
Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1 by Bleichenbacher 1998
DROWN: Breaking TLS using SSLv2 by Aviram et al. 2016
Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices by Heninger, Durumeric, Wustrow, and Halderman 2012
Random number generator enhancements for Linux 5.17 and 5.18 by Donenfeld
11/5 Digital signatures

Lecture Slides 		Boneh & Shoup Ch. 13
11/7 Elliptic curve cryptography

Lecture Slides 		Boneh & Shoup Ch. 15

Further reading/Research directions:
A riddle wrapped in an enigma by Koblitz and Menezes 2015
Curve25519: new Diffie-Hellman speed records by Bernstein 2006
11/12 Authenticated Key Exchange; TLS

Lecture Slides 		Boneh & Shoup Ch. 21

Further reading/research directions:
A Messy State of the Union: Taming the Composite State Machines of TLS by Beurdouche, Barghavan, Delignat-Lavaud, Fournet, Kohlweiss, Pironti, Strub, and Zinzindohoue 2015
SMACK: State Machine AttaCKs against TLS
Triple Handshakes and Cookie Cutters: Breaking and Fixing Authentication over TLS by Bhargavan et al. 2014
A Cross-Protocol Attack on the TLS Protocol by Mavrogiannopoulos, Vercauteren, Velichkov, Preneel 2012
11/14 Authenticated key exchange, continued
11/19 Index calculus for factoring and discrete log

Lecture Slides 		Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice by Adrian, Bhargavan, Durumeric, Gaudry, Green, Halderman, Heninger, Springall, Thome, Valenta, VanderSloot, Wustrow, Zanella-Beguelin, Zimmermann

Further reading:
A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic by Joux 2013
A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic by Barbulescu Gaudry Joux and Thome 2013
11/21 Lattice-based cryptanalysis

Lecture Slides 		Daniele Micciancio lecture notes 1 2
Oded Regev lecture notes
Factoring Polynomials with Rational Coefficients by Lenstra Lenstra and Lovasz 1982
The two faces of lattices in cryptology by Nguyen 2001
Using LLL-reduction for solving RSA and factorization problems: a survey by May 2007
Recovering cryptographic keys from partial information, by example by De Micheli and Heninger 2020
11/26 Lattice-based cryptography
11/28 No lecture: Thanksgiving
12/3 Post-quantum cryptography

Lecture Slides 		Further reading
Algorithms for Quantum Computation: Discrete Logarithms and Factoring by Shor 1994
Quantum Computing: Progress and Prospects
National Academies report 2019
A Resource Estimation Framework for Quantum Attacks Against Cryptographic Functions by Mosca and Gheorghiu 2017
NIST Post-Quantum Cryptography Round 3 Submissions
Boneh & Shoup Ch. 14
12/5 TBD

Homework

There will be eight homework assignments, each involving both programming and written exercises. Many of the programming exercises have been inspired by the Cryptopals challenges. Of course I expect you to produce your own independent implementations, without using tools that solve the problem for you, and without using AI. But if you're really enthusiastic and want more fun exercises, you are more than welcome to work through the Cryptopals challenges yourself.

Textbooks