Idea Transcript
CIS 556, Fall 2016 Cryptography Instructor: Nadia Heninger (nadiah at cis dot upenn dot edu, 604 Levine) Office hours: Tuesday 1-2pm TA: Marcella Hastings (mhast at seas dot upenn dot edu, DSL Moore 102) Office hours: Wednesday 5-6:30pm, DSL Conference Room Lectures: Tuesday/Thursday 10:30am-12pm Moore 212 Teaching Resources: Grades/Homework on Canvas Announcements/Questions on Piazza Grading: 30% Homework 30% Midterm 30% Final project 10% Participation, brownie points, and grading
Course Overview This course is a graduate-level introduction to cryptography, both theory and applications. A tentative list of topics includes: Symmetric cryptography: block ciphers, stream ciphers, modes of operation Message integrity, hash functions Public-key cryptography: number-theoretic notions, public-key encryption schemes, digital signatures Cryptographic security: key management, network security protocols, random number generation, side-channel attacks Magical crypto tricks: secret sharing, commitments, zero-knowledge proofs Research topics: privacy-enhancing technologies, lattices, etc. See the previous offering for a more detailed idea of what will be covered.
Prerequisites This course is intended for beginning graduate students. There are no formal prerequisites, but you should have mathematical maturity equivalent to having taken algorithms and complexity (CIS 320 or 502 and CIS 262 or CIS 511) or a proof-based math class like undergraduate algebra (Math 370/371) or number theory (Math 350). Undergraduates will need a permit to enroll. Please email me and tell me what grades you received in related courses. It is possible to enroll in both CIS 400 and this course even though there is a time conflict. You will just need to get the course conflict request form signed by all the instructors.
Schedule Topic
References
Assignments
Katz & Lindell Ch. 1, 2 Boneh & Shoup Ch. 2.2 8/30
Introduction, one-time pad
Further reading: Communication theory of secrecy systems Shannon 1949
Homework 1 assigned
Katz & Lindell Appendix A Boneh & Shoup Appendix B Hoffstein, Pipher, & Silverman Ch. 4.3, 4.6 9/1
Probability and entropy review Further reading: A mathematical theory of communication Shannon 1948 Alistair Sinclair scribe notes on Chernoff bounds Semantic security, pseudorandom generators, stream ciphers
9/6
Katz & Lindell Ch. 3 Boneh & Shoup Ch. 2.3, 3 Katz & Lindell Ch. 3.5, 3.6 Boneh & Shoup Ch. 4
9/8
Stream ciphers, chosen plaintext attacks
9/13
Chosen plaintext attacks, pseudorandom functions, block ciphers
Further reading/Research directions: Homework 1 due All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS by Vanhoef and Piessens Homework 2 Attacks Only Get Better: Password Recovery Attacks Against RC4 in TLS by Garman, Paterson, and Van der assigned 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
9/15
Block ciphers, modes of operation, block cipher attacks
Katz & Lindell Ch. 5 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
9/20
Chosen ciphertext attacks, malleability, padding oracles
Katz & Lindell Ch. 4.4-4.6 Boneh & Shoup Ch. 6 Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS... by Vaudenay 2002
9/22
Message authentication codes, hash functions
Katz & Lindell Ch. 4 Boneh & Shoup Ch. 8.1-8.6
Homework 2 due Homework 3 assigned
Katz & Lindell Ch. 4.7-4.8 Boneh & Shoup Ch. 8.7 Further reading/research directions MD5 to be considered harmful today by Sotirov, Stevens, Appelbaum, Lenstra, Molnar, Osvik, de Weger 2009 Counter-cryptanalysis by Stevens 2013 New collision attacks on SHA-1 based on optimal joint local-collision analysis by Stevens 2013
9/27
Birthday attacks, hash functions in practice
9/29
Length extension attacks, HMAC, authenticated encryption
Katz & Lindell Ch. 7
10/4
Computational number theory: Modular arithmetic, GCDs, ideals, groups, discrete log
A Computational Introduction to Number Theory and Algebra by Shoup HAC Ch. 3.6.3
Homework 3 due
10/6
Fall break
10/11 Diffie-Hellman, ElGamal
New Directions in Cryptography by Diffie and Hellman 1976 Katz & Lindell Ch. 7.3, 8.2.1, 9, 10
Homework 4 assigned
Arithmetic modulo composites, Chinese 10/13 Remainder Theorem, Pohlig-Hellman discrete log
Katz & Lindell Ch. 7.1.5, 7.2, 8.1.2, 8.2.2, 10.4 HAC Ch. 3.6.4 Katz & Lindell Ch. 10.4, 10.6 Boneh & Franklin Ch. 13 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 10/18 RSA encryption, textbook RSA is insecure Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1 by Bleichenbacher 1998 Efficient Padding Oracle Attacks on Cryptographic Hardware by Bardou, Focardi, Kawamoto, Simionato, Steel, Tsay 2012 Revisiting SSL/TLS Implementations: New Bleichenbacher Side Channels and Attacks by Meyer, Somorovsky, Weiss, Schwenk, Schinzel, Tews 2014 10/20 RSA and DSA digital signatures
10/25
Constructing secure channels, TLS, SSH, review
Katz & Lindell Ch. 12 Further reading: Ferguson Schneier & Kohno Ch. 14 The Secure Sockets Layer (SSL) Protocol Version 3.0 by Freier Karlton Kocher 2011 The Transport Layer Security (TLS) Protocol Version 1.2 by Dierks and Rescorla 2008 This POODLE Bites: Exploiting The SSL 3.0 Fallback by Moeller, Duong, Kotowicz 2014
Homework 4 due
10/27 Midterm exam Katz & Lindell Ch. 9.1,9.2 11/1
Subexponential factoring, quadratic sieve
Further Reading: A tale of two sieves by Pomerance (1996) Factoring integers with the number field sieve by Buhler, Lenstra, and Pomerance (1993) Factorization of a 768-bit RSA modulus by Kleinjung et al. (2010)
Homework 5 assigned
Katz & Lindell Ch. 9.2.4 Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice by Adrian et al. Index calculus algorithms for discrete log 11/3 Slides
Export cryptography, FREAK, Logjam TLS downgrade attacks
11/8
11/10 Lattices
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 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 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 Physical key extraction attacks on PCs by Genkin, Pachmanov, Pipman, Shamir, and Tromer 2016
11/15
Side-channel attacks Guest lecture: Daniel Genkin
LLL, Coppersmith's method 11/17 Slides
Other resources: KRSA Key Extraction via Low-bandwidth Acoustic Cryptanalysis by Genkin, Shamir and Tromer 2013 Get Your Hands Off My Laptop: Physical Side-Channel Key-Extraction Attacks on PCs by Genkin, Pipman and Tromer 2014 Stealing Keys from PCs using a Radio: Cheap Electromagnetic Attacks on Windowed Exponentiation by Genkin, Pachmanov, Pipman and Tromer 2015 ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels by Genkin, Pachmanov, Pipman, Tromer and Yarom 2016 ECDHE Key-Extraction via Low-Bandwidth Electromagnetic Attacks on PCs by Genkin, Pachmanov, Pipman and Tromer 2016 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 How to share a secret by Shamir 1979
11/22 Secret sharing
Other resources: Secret-sharing schemes: A survey by Beimel 2011 David Wagner lecture notes
Homework 5 due Homework 6 assigned
11/24 Thanksgiving 11/29 Project presentations 12/1
Project presentations
12/6
No class: Asiacrypt
12/8
No class: Asiacrypt
Homework 6 due
Project Final project guidelines can be found here.
Assignments Homework should be submitted using Canvas before noon on the day it is due. For programming exercises, submit the code you wrote and a short description of how you solved the problem. For mathematical or written exercises, please write up your solutions using Latex and submit a pdf to Canvas. If you've never used Latex before, you may want to make sure you can install and compile. Here is a useful reference for Latex. Homework 1 Homework 2 Homework 3 Homework 4 Homework 5 Homework 6 (Extra Credit)
Recommended Textbook Introduction to Modern Cryptography by Katz and Lindell. A copy should be on reserve in the Rosengarten Reserve Room in the Van Pelt-Dietrich Library Center.
Additional Resources A Graduate Course in Applied Cryptography by Boneh and Shoup. An Introduction to Mathematical Cryptography by Hoffstein, Pipher, and Silverman. A mathematically-oriented introductory text. Introduction to Modern Cryptography by Bellare and Rogaway. Online course notes for an introductory course. Cryptography Engineering by Ferguson, Schneier, and Kohno. A practice-oriented introductory text. The Handbook of Applied Cryptography by Menezes, van Oorschot, and Vanstone. A classic reference, available for free online.