CIS 556, Fall 2018
Cryptography


Instructor:
  Nadia Heninger (nadiah at cis dot upenn dot edu, 604 Levine)
  Office hours: Tuesday 1-2pm

TA:
  Paul Lou (plou at seas dot upenn dot edu)
  Office hours: Tuesday 4-5pm, Levine 6th floor bump space

Lectures:
  Monday/Wednesday 3:00pm-4:30pm Towne 311

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:

If your primary interest is in cryptocurrencies or blockchain technology, you will probably be more interested in LGST 299/799.

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.

Schedule

Topic References Assignments
8/29 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/5 Math Review: Probability and basic number theory
Katz & Lindell Appendix A, Ch. 8.1
Boneh & Shoup Appendix A, B
Hoffstein, Pipher, & Silverman Ch. 1, Ch. 4.3, 4.6

Further reading:
Alistair Sinclair scribe notes on Chernoff bounds
9/10 Semantic security, pseudorandom generators, stream ciphers
Katz & Lindell Ch. 3
Boneh & Shoup Ch. 2.3, 3
Homework 1 due
Homework 2 assigned
9/12 Stream ciphers, chosen plaintext attacks
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
9/17 Block ciphers, modes of operation, block cipher attacks

Guest lecture: Barak Shani
Katz & Lindell Ch. 5
9/19 Chosen ciphertext attacks, malleability, padding oracles

Guest lecture: Marcella Hastings
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 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/24 Message authentication codes, hash functions, birthday attacks
Katz & Lindell Ch. 4
Boneh & Shoup Ch. 8.1-8.6
Homework 2 due
9/26 Hash functions in practice

Katz & Lindell Ch. 4.7-4.8
Boneh & Shoup Ch. 8.7

Further reading/research directions
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
The first collision for full SHA-1 by Stevens, Bursztein, Karpman, Albertini, Markov 2017
Homework 3 assigned
10/1 Length extension attacks, HMAC, authenticated encryption
Katz & Lindell Ch. 7
10/3 Computational number theory: Modular arithmetic, groups, rings, fields, efficient algorithms and hard problems
Katz & Lindell Ch. 8
HAC Ch. 3.6.3

Further reading:
A Computational Introduction to Number Theory and Algebra, Ch. 3, 6 by Shoup
Fast multiplication and its applications by Bernstein
10/8 Diffie-Hellman, ElGamal
New Directions in Cryptography by Diffie and Hellman 1976
Katz & Lindell Ch. 7.3, 8.2.1, 9, 10

Further reading:
A personal view of average-case complexity by Impagliazzo 1995
10/10
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
Homework 3 due
Homework 4 assigned
10/15 RSA encryption, textbook RSA is insecure

Katz & Lindell Ch. 10.4, 10.6
Boneh & Shoup 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
10/17 RSA and DSA digital signatures

Guest lecture: Barak Shani
Katz & Lindell Ch. 12
10/22 Constructing secure channels Further reading:
Ferguson Schneier & Kohno Ch. 14
SIGMA: the "SIGn-and-MAc" Approach to Authenticated Diffie-Hellman and its Use in the IKE Protocols by Krawczyk 2003
10/24 TLS Further reading:
The Transport Layer Security (TLS) Protocol Version 1.3 by Rescorla, 2018
TLS Ecosystem Woes by Benjamin 2018 (video)
The Transport Layer Security (TLS) Protocol Version 1.2 by Dierks and Rescorla 2008
Homework 4 due
Homework 5 assigned
10/29 Random number generation issues; Index calculus algorithms for factoring
Katz & Lindell Ch. 9.1,9.2
Mining your Ps and Qs: Detection of widespread weak keys in network devices by Heninger, Durumeric, Wustrow, and Halderman 2012

Further Reading:
Weak Keys Remain Widespread in Network Devices by Hastings, Fried, and Heninger 2016
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)

10/31 Index calculus for discrete log; Export cryptography, FREAK, Logjam TLS downgrade attacks 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 (slides)
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
Project proposals due
11/5 Midterm exam
11/7 Elliptic Curves and Primality Testing

Guest Lecture: Barak Shani
Homework 5 due
11/12 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/14 LLL, Coppersmith's method

Slides
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 6 assigned
11/20 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/26 Project presentations
11/28 Project presentations Homework 6 due

Project

Final project guidelines can be found here.

Assignments

There will be six homework assignments, each involving both programming and written exercises. Homework should be submitted using Canvas before 3pm 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.

Recommended Textbooks


Additional Resources