CIS 556, Fall 2015 Cryptography

Instructor:
Office hours: Tuesday 1-2pm

TA:
Luke Valenta (lukev at cis dot upenn.edu, DSL, Moore 102)
Office hours: Wednesday 4pm-5pm, Levine 3rd floor bump space

Lectures:
Tuesday/Thursday 10:30am-12pm

Teaching Resources:
Announcements/Questions on Piazza

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

Schedule

 Topic References Assignments 8/27 Introduction, one-time pad Katz & Lindell Ch. 1, 2 Boneh & Shoup Ch. 2.2 Further reading: Communication theory of secrecy systems Shannon 1949 Homework 1 assigned 9/1 Probability and entropy review Katz & Lindell Appendix A Boneh & Shoup Appendix B Hoffstein, Pipher, & Silverman Ch. 4.3, 4.6 Further reading: A mathematical theory of communication Shannon 1948 Alistair Sinclair scribe notes on Chernoff bounds 9/3 Semantic security, pseudorandom generators, stream ciphers Katz & Lindell Ch. 3 Boneh & Shoup Ch. 2.3, 3 9/8 Stream ciphers, chosen plaintext attacks, pseudorandom functions Katz & Lindell Ch. 3.5, 3.6 Boneh & Shoup Ch. 4 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 Spritz-a spongy RC4-like stream cipher and hash function by Rivest and Schuldt 2014 The ChaCha family of stream ciphers by Bernstein Homework 1 due Homework 2 assigned 9/10 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/15 Chosen ciphertext attacks, malleability, padding oracles, message authentication codes 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/17 Hash functions, birthday attacks Katz & Lindell Ch. 4 Boneh & Shoup Ch. 8.1-8.6 Homework 2 due (extended to 11:59pm on 09/18) Homework 3 assigned 9/22 Hash functions in practice, length extension attacks, HMAC 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/24 Authenticated encryption, computational number theory: modular arithmetic, GCDs, ideals Katz & Lindell Ch. 7 A Computational Introduction to Number Theory and Algebra by Shoup 9/29 Groups, discrete log HAC Ch. 3.6.3 10/1 Diffie-Hellman, ElGamal New Directions in Cryptography by Diffie and Hellman 1976 Katz & Lindell Ch. 7.3, 8.2.1, 9, 10 Homework 3 due Homework 4 assigned 10/6 Arithmetic modulo composites, Chinese 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 10/8 Fall break 10/13 No class 10/15 No class 10/20 RSA encryption, textbook RSA is insecure 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 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 Homework 4 due Homework 5 assigned 10/22 RSA digital signatures Katz & Lindell Ch. 12 10/27 Midterm exam 10/29 DSA; Constructing secure channels, TLS 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 11/3 Constructing secure channels, SSH; Factoring algorithms Katz & Lindell Ch. 9.1 11/5 Subexponential factoring, quadratic sieve Katz & Lindell Ch. 8.1.1, 8.1.3 Katz & Lindell 8.2.4 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 due 11/10 Index calculus algorithms for discrete log Slides Katz & Lindell Ch. 9.2.4 Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice by Adrian et al. 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/12 Secret sharing How to share a secret by Shamir 1979 Other resources: Secret-sharing schemes: A survey by Beimel 2011 David Wagner lecture notes 11/17 Commitment schemes Lecture notes by Yevgeniy Dodis Further reading: A practical scheme for non-interactive verifiable secret sharing by Feldman 1987 11/19 Zero-knowledge proofs Lecture notes by David Wagner Lecture notes by Boaz Barak 1 2 The knowledge complexity of interactive proof systems by Goldwasser, Micali, and Rackoff 1989 Further reading/research topics: Zerocoin: Anonymous Distributed E-Cash from Bitcoin by Miers, Garman, Green, Rubin 2013 Zerocash: Decentralized Anonymous Payments from Bitcoin by Ben-Sasson, Chiesa, Garman, Green, Miers, Tromer, Virza 2014 SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge by Ben-Sasson, Chiesa, Genkin, Tromer, Virza 2013 11/24 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 11/26 Thanksgiving 12/1 Project presentations 12/3 No class 12/8 Project presentations

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.