Applied Cryptography

**Instructor:**

Nadia Heninger
(nadiah at cs dot ucsd dot edu)

Office hours: Wednesday 3:30 until there are no more questions on Zoom

**TA:**

George Sullivan
(gsulliva at eng dot ucsd dot edu)

Office hours: Monday 1:00-2:00pm on Zoom

**Lectures:**

Monday/Wednesday 2:00pm-3:20pm, via Zoom (meeting information posted on Canvas; email for details if you are not enrolled in the course)

**Class Resources:**

Lecture information and gradebook on Canvas

Q&A on Piazza

**Grading:**

80%: Approximately weekly homework assignments that involve both programming and written exercises

20%: Peer grading

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

- Random number generation
- Symmetric cryptography: stream ciphers, block ciphers, hash functions, modes of operation
- Public-key cryptography and cryptanalysis: RSA, Diffie-Hellman, DSA
- Algorithmic techniques in cryptanalysis
- Secure channels, TLS, and cryptography in practice

Enrollment is closed.

Topic
| References
| Assignments
| |

3/30 | Introduction, one-time pad Lecture slides |
Boneh & Shoup Ch. 2.1 Further reading:Communication theory of secrecy systems Shannon 1949 | Homework 1 Available |

4/1 | PRGs and stream cipher encryption Lecture slides |
Boneh & Shoup Ch. 2.2, Ch. 3.1-3.3Further 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 | |

4/6 | Block ciphers Lecture slides |
Boneh & Shoup Ch. 4.1-4.2Further reading/Research directions:Biclique Cryptanalysis of the Full AES by Bogdanov, Khovratovich, and Rechberger 2011 | Homework 2 Available |

4/8 | PRFs, chosen plaintext attacks, block cipher modes of operation Lecture slides | Boneh & Shoup Ch. 4.4, Ch. 5Further reading/research:Stealthy Dopant-Level Hardware Trojans by Becker, Regazzoni, Paar, Burleson 2013 | Homework 1 Due |

4/13 | Message authentication codes and message integrity; problems with CBC mode Lecture slides | Boneh & Shoup Ch. 6Further 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 |

4/15 | Hash functions Lecture slides |
Boneh & Shoup Ch. 8Further 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 |

4/20 | Hash functions, MACs, and authenticated encryption Lecture Slides | Boneh & Shoup Ch. 8.7, 9Further reading:This POODLE Bites: Exploiting The SSL 3.0 Fallback by Möller, Duong, Kotowicz 2014 | Homework 4 Available |

4/22 | Computational number theory: Modular arithmetic, groups, rings, fields, efficient algorithms and hard problems 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 |

4/27 | Diffie-Hellman, elementary discrete log cryptanalysis 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 | Homework 5 Available |

4/29 | Chinese Remainder Theorem, Pohlig-Hellman algorithm, public-key cryptography, RSA 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 | Homework 4 Due |

5/4 | Elementary factoring algorithms and RSA cryptanalysis Lecture Slides | Boneh & Shoup Ch. 12Further 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 | |

5/6 | Digital signatures Lecture Slides | Boneh & Shoup Ch. 13 Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices by Heninger, Durumeric, Wustrow, and Halderman 2012 | Homework 6 Available Homework 5 Due 5/8 |

5/11 | Elliptic curve cryptography Lecture Slides | Boneh & Shoup Ch. 15Further reading/Research directions:A riddle wrapped in an enigma by Koblitz and Menezes 2015 Curve25519: new Diffie-Hellman speed records by Bernstein 2006 | |

5/13 | Authenticated Key Exchange; TLS Lecture Slides | Boneh & Shoup Ch. 21Further 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 | Homework 6 Due 5/15 |

5/18 | Random number generation Lecture Slides | Further reading/research directions:An Analysis of the NIST SP 800-90A Standard by Woodage and Shumow 2019 Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust by Dodis et al. 2013When Private Keys are Public: Results from the 2008 Debian OpenSSL Vulnerability by Yilek et al. 2009 Authentication Failures in NIST version of GCM by Joux Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS by Bock et al. 2016 On the Practical Exploitability of Dual EC in TLS Implementations by Checkoway et al. 2014 A Systematic Analysis of the Juniper Dual EC Incident by Checkoway et al. 2016 Cryptanalytic Attacks on Pseudorandom Number Generators by Kelsey Schneier Wagner and Hall 1998 Practical state recovery attacks against legacy RNG implementations by Cohney Green Heninger 2018 | Homework 7 Available |

5/20 | 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, ZimmermannFurther 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 | |

5/25 | No class; Memorial day | ||

5/27 | 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 | Homework 7 Due Homework 8 Available |

6/1 | Side-channel attacks | ||

6/3 TBD | Homework 8 Due 6/5 |

- A Graduate Course in Applied Cryptography by Boneh and Shoup.
- Introduction to Modern Cryptography by Katz and Lindell.
- An Introduction to Mathematical Cryptography by Hoffstein, Pipher, and Silverman. A mathematically-oriented introductory text.
- Introduction to Modern Cryptography by Bellare and Rogaway.
- Cryptography Engineering by Ferguson, Schneier, and Kohno.
- The Handbook of Applied Cryptography by Menezes, van Oorschot, and Vanstone.