Applied Cryptography

**Instructor:**

Nadia Heninger
(nadiah at cs dot ucsd dot edu, EBU3B 3138)

Office hours: Wednesday 3:30-4:30pm 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

If you are interested in enrolling in this course, please add yourself to the waitlist and send me an email at nadiah at cs dot ucsd dot edu and tell me how you did in your CS theory or previous cryptography courses to meet the prerequisites.

Topic
| References
| Assignments
| |

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

4/1 | PRGs |
Boneh & Shoup Ch. 3Further reading:Security analysis of pseudo-random number generators with input: /dev/random is not robust by Dodis Pointcheval Ruhault Vergnaud Wichs 2013 | |

4/6 | Stream ciphers |
Boneh & Shoup Ch. 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 Spritz-a spongy RC4-like stream cipher and hash function by Rivest and Schuldt 2014 The ChaCha family of stream ciphers by Bernstein | |

4/8 | Chosen plaintext attacks | Boneh & Shoup Ch. 5 | |

4/13 | Block ciphers and modes of operation | Boneh & Shoup Ch. 4 | Homework 1 Due |

4/15 | Chosen ciphertext attacks |
Boneh & Shoup Ch. 6 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 | |

4/20 | Hash functions | Boneh & Shoup Ch. 8Further reading/research directionsThe 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 The first collision for full SHA-1 by Stevens, Bursztein, Karpman, Albertini, Markov 2017 | |

4/22 | Message authentication codes and authenticated encryption | Boneh & Shoup Ch. 9 | |

4/27 | Computational number theory: Modular arithmetic, groups, rings, fields, efficient algorithms and hard problems |
Boneh & Shoup Appendix AFurther reading:A Computational Introduction to Number Theory and Algebra, Ch. 3, 6 by Shoup Fast multiplication and its applications by Bernstein | |

4/29 | More computational number theory: arithmetic modulo composites, Chinese Remainder Theorem | ||

5/4 | Diffie-Hellman, ElGamal | New Directions in Cryptography by Diffie and Hellman 1976Further reading:A personal view of average-case complexity by Impagliazzo 1995 | |

5/6 | Elementary discrete log algorithms | HAC Ch. 3.6 | |

5/11 | RSA encryption | Boneh & Shoup Ch. 11 A method for obtaining digital signatures and public-key cryptography by Rivest, Shamir, and Adleman 1978 Further reading/Research directions:Why Textbook ElGamal and RSA Encryption Are Insecure by Boneh, Joux, and Nguyen 2000 | |

5/13 | Elementary factoring algorithms and RSA cryptanalysis | ||

5/18 | Digital signatures | Boneh & Lindell Ch. 13 | |

5/20 | Authenticated Key Exchange; TLS | Boneh & Shoup Ch. 21 | |

5/25 | Lattices |
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 | |

5/27 | Lattice-based cryptanalysis |
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 | |

6/1 | Index calculus for factoring and discrete log |
SMACK: State Machine AttaCKs against TLS 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 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 | |

6/3 | Grab bag/TBD |

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