The Kryptos Sculpture, Langley, VA.

CSC507/609-C: Cryptography

by: burt rosenberg
at: university of miami
semester: fall 2020 (201)
time: MWF 10:10 AM – 11:00 AM
location: MM 214

Class Statement:

• This is a first course on formal cryptography with the goal of answering important questions about the "why" of cryptographic techniques.
• Computational models are presented of both the "good guys" and the "bad guys" and techniques for reasoning about the models and their interactions.
• The nature of randomness, information and knowledge is explored.
• The course emphasizes a computational approach where programming exercises practice the conceptual and mathematical framework.

Calendar:

• Final: Monday 2 December (in class)
• Midterm: Monday 14 October
• No class: Wednesday 9 October
• CIA visit: Monday 7 October
• No class: Monday 30 September

Midterm and Final:

• Midterm histogram
• Midterm (PDF) (Solutions)

Background Material:

• Probabilistic Polynomial Time Algorithms & Cryptography (PDF)
• Asymptotic Order Notation (Big-Oh) (PDF)
• Perfect secrecy and Adversarial Indistinguishability (PDF)

Assignments:

• Project 1: Cracking Vigenere.
  Due: Friday, Sept 6. Monday, Sept 9.
• Project 2: Adversarial Indistinguishability.
  Due: Monday, Sept 23.
• Project 3: Modes of Operation.
  Due: Monday, October 7.
• Project 4: CBC Mode Padding Attack.
  Due: Monday, October 28. Monday, November 4.
• Project 5: Exercises in Public Key.
  Due: Wednesday, December 4. Midnight EST.

Syllabus:

• Required textbook for both Csc 507 and 609 students:
  Introduction to Modern Cryptography,
  (Chapman & Hall/CRC Cryptography and Network Security Series) 2nd Edition,
  by Jonathan Katz and Yehuda Lindell.
  ((Amazon))
• Twitter (for updates on homework postings): csc609
• Join us on slack and post to #csc507-201.
• Additional books of interest:
  • The Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone
  • Introduction to Cryptography with Coding Theory by Trappe and Washington.
  • Codes and Cryptography by Dominic Welsh.
• Homework: Programming assignments count for 30% of the grade. Due at midnight local time.
• Lateness of Programming: deduct 1 point after 3 days, a 2nd point after 10 days, etc.
• Midterm: The midterm counts for 30% of the grade.
• Final: An in-class final counts for 40% of the grade.
• You will be using subversion to submit your python work. Please see my Subversion tutorial
• The projects will also use make. Windows users should install Cygwin, and select for install at least subversion, make, and python. Also Atom is an attractive editor instead of cygwin's offerings.
• Compare the princeton cos433

Class Notes:

Classical and Modern Encryption

• Encryption, History, and Politics
  • Crypto talk
  • Codes, ciphers and steganography
  • Substitution, transposition, playfair
    • Cracking substitutions
    • Fun game: try the above link on the enciphered word "november" and "asdlkjvb"
    • Think about how texts shorter then a fresh keyword have ambiguous decipherings.
  • Vignere
    • cracking vignere
  • Playfair and example cryptanalysis
  • The Enigma
• Perfect Secrecy and Adversarial Indistinguishability.
  • Shannon perfect secrecy definition
  • Equivalence of Adversarial Indistinguishability
  • Eavesdropping model; "knowledge" and the Bayesian probability framework.
  • One Time Pad
  • Shannon's theorem for perfect secrecy.
  • Some additional remarks
• Security models and Reductions
  • Computational complexity
    • Python code for nondeterministic polynomial algoritms and polynomial time verifiers.
    • Python code for the "language of primes".
  • Complexity theoretic security
  • Message length concerns, and attacks
  • Multiple Message Attack
  • Known Plaintext Attack
  • Chosen Plaintext Attack
  • CPA-Security
  • Semantic Security
• Practical CPA-Security
  • Implementation of CPA strong cipher
  • Analysis
    • Security reduction proofs
    • perfect security when using a random permutation
    • definition of pseudorandom permutation
    • reduction to the PRP Discrimination Game
    • reduction of breaking PRP Discrimination to breaking CPA Inv.
  • Initial vectors
  • Modes of operation, counter mode (ECB, CBC, CFB, OFB.)
  • AES as a PRP?
• Pseudorandom Generators
  • Pseudorandomness
  • Stream Ciphers
  • Weak pseudorandom generators:
    • From Knuth, an excerpt from Art of Computer Programming
    • The gcc Linear Congruential Generator rand function source code. (yay open source)
    • Linear Feedback Shift Register
• The limitations of the CPA model.
  • A chosen ciphertext attack
  • Malleability
  • Truncation attacks, replay attacks, reordering attacks
  • A failure of a CPA secure cipher
• Frightful Focus Friday:
  • Side channel attacks
• Practical CCA-Security
  • Message forgery models
  • Message Authentication Codes (MAC)
  • Chosen Ciphertext Attack
  • Authenticated Encryption
  • Implementation of CCA strong cipher

Hash functions and Applications

• Cryptographic Hash Functions
  • Mathematical framework and security definitions
  • Collision free, 2nd pre-image resistance, pre-image resistance.
  • Birthday attack
  • Merkle-Damgard construction
• Applications of Hash Functions
  • Authentication: Hash-and-MAC, and HMAC (keyed hash functions)
  • Key diversification (credit cards, HashPass)
  • Password hashes (Unix)
  • One Time Passwords and the Lamport Hash
  • Signatures and Merkle trees
• Bit commitment protocols
  • Hiding and Binding
  • Flipping a coin on the telephone
    — Manuel Blum, CRYPTO 1981: 11-15
• Bitcoin and Blockchain
  • Day 1
    • Public Ledger
    • Hash Chain
    • The Genesis block
      — The Times 03/Jan/2009 Chancellor on brink of second bailout for banks. from The Times
    • Trust/Attack model: threshold/consensus and Byzantine Agreement
      • Castro, and Liskov, Practical Byzantine Fault Tolerance and Proactive Recovery, (2002).
      • Bitcoin, Proof of Work
      • Algorand, https://arxiv.org/abs/1607.01341
  • Day 2
    • UTXO's, transactions and blocks
    • An example:
      • From this ATM,
        • I made this purchase
          • which is in the block chain as this transaction
            • that is collected with other transactions into this block.
    • Coinbase and fees
    • Public key signatures
    • Proof of work
  • Day 3
    • Blockchain forks
    • Attack scenarios
    • The incentives: Hash difficulty, Coinbase halving
    • developer documentation
    • Satoshi Nakamoto original paper.
  • The real blockchain
    • Mini-course modeled on a Berkeley DECAL course, I offred last year.
      • Lecture 1 Bimetalism and the Free Silver Movement
      • Lecture 2 If Blockchain is so good, why is everyone in jail?
      • Lecture 3 The mechanics of Bitcoin (The Audacity of Nope)
      • Lecture 4 The impossible and doing the impossible
      • Lecture 5 Authorizing the transaction
      • Lecture 6 The strange and twisty math
      • Lecture 7 Alt Coins
      • Lecture 8 Proof of Stake

  Public Key Cryptography

• Public Key Encryption
  • Introduction to Public Key,
    • The ideas (back to the talk)
    • The New Directions paper.
    • GCHQ, James Ellis, Clifford Cocks and Malcolm Williamson.
  • KEM/DEM
  • Adversarial indistinguishability: Diagram
• Background in algebra and computational number theory.
  • Groups, Z mod n, plus, and Z mod p, times.
  • Generators and subgroups, LeGrange theorem
  • Bezout's equation, and calculating relative primality and inverses.
  • Euler Phi function and Little Fermat
  • Fermat test and Carmichael numbers
  • Miller-Rabin test (Kleinberg at Cornell) (cached copy)
• Number theory experiments,
  • github/burtr/*/crypto repository.
• RSA
  • RSA and Probabilistic Factoring
  • Small message attacks
  • chinese remainder attack on a multiply encrypted message
  • related message attack (m and m + D)
  • root-N trick
  • Optimal Asymmetric Encryption Padding, Bellare and Rogaway, Eurocrypt '94.
  • Pollard Rho algorithm for factoring
• El Gamal encryption
  • Discrete Logs
  • Diffie Hellman key exchange
  • El Gamal encryption, and reduction of El Gamal to DDH
  • CCA El Gamal KEM in the Random Oracle Model
  • Quadratic Residues and small subgroup disclosures
  • Pohlig-Hellman
• Elliptic Curves
  • The group law
  • The point at infinity
  • hard problems based on elliptic curves
• Digital Signatures
  • Definition, and adversary
  • Plain RSA signatures and forgeries
  • RSA-FDH (Full Domain Hash) and reduction to the RSA problem
  • Identification schemes, perfect correctness and probabilistic soundness
  • Schnorr identification, and knowledge extraction
  • Fiat-Shamir transformation and Schnorr dig-sig's
  • Notes (PDF) from Stanford University CS355 Spring 2019. Dima Kogan.
    These notes present material in the reverse order than in class. Please see the previous lecture in that course for background.

  Zero Knowledge Proof Systems

• Zero Knowledge Proof Systems
  • Example of quasi-ZK ceremonies.
  • Interactive Protocols (IP)
  • Proof systems and knowledge
  • Zero-knowledge
  • Zero-knowledge Proofs of Knowledge
  • Everything in NP is in ZK
  • Notes (PDF) from Stanford University CS355 Spring 2019. Henry Corrigan-Gibbs.
  • Non-interactive ZK, Honest Verifier ZK
  • The original paper:
    The Knowledge Complexity of Interactive Proof Systems, Shafi Goldwasser, Silvio Micali, Charles Rackoff.
  • Further reading:
    Probabilistic Proof Systems: A Primer, Oded Goldreich.

Books:

• Elementary Military Cryptography William F. Friedman.
• Lecture Notes on Cryptography by Goldwasser and Bellare.
• Enigma, Wladyslaw Kozaczuk. Articles on reconstruction and breaking of Enigma by Polish mathematicians prior to WWII.
• La cryptographie militaire by Auguste Kerckhoffs.
• Steganographia by Johannes Trithemius (1462-1516)
• Oorshot and Vanstone, Handbook of Applied Cryptography (Univ of Waterloo, D/L)
• Leo Marx, Between Silk and Cyanide, (Amazon)
• Frank Rowlett, The Story of Magic, Memoirs of an American Cryptologic Pioneer, (Amazon)
• Herbert Yardley, The American Black Chamber, (Amazon)
• Helen Gaines, Cryptanalysis: A Study of Ciphers and Their Solution, (Amazon)

Other resources:

• Nova: Decoding Nazi Secrets
• Simon Singh challenge
• Breaking Tunny by Tutte. Article on reconstructing the masking sequence for encryption of German High Command network.
• John Savard's page on machine ciphers.
• Rotonym, what the heck is a rotonym, Will McGugan. A nice Rot-13 implementation in Python.
• Elliptic Curves, John Milne.
• mersenne.org
• Prime network
• Random dot org: a supply of random numbers.
• The NIST Beacon

Attacks:

• WEP attacks
  • FMS attack on WEP realized
  • Korek WEP flaws
  • Korek's Chopper attacks against WEP.
• Side channel attacks
  • Timing attack on an XBOX signature.
  • Timing attacks on RSA, by Paul Kocher
  • Power analysis on smart cards, also by Paul Kocher
  • Covert channel using cache hits, see e.g. Osvik, Shamir and Tromer

References:

• Pascal Junod, Cryptographic Secure Psudo-Random Bit Generation: The Blum-Blum-Shub Generator.
• Cramer, Gennaro, Schoenmakers, A secure and optimally efficient mutli-authority election scheme, Eurocrypt 97.
• Jens Groth, Extracting witnesses from proofs of knowledge in the random oracle model
• Cramer, Damgard, Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, Crypto 94
• Michael Ben-Or, Shafi Goldwasser, Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proc. 20-th ACM Symposium on Theory of Computing, 1988. pp 1-10.
• Philippe Oechslin, Making a faster cryptanalytic time-memory trade-off, Crypto 03. (cached)
• Analysis of the popular linear congruential generator
• Norbert Biermann, Analysis of Giouan Battista Bellaso's cipher challenges of 1555, Cryptologia Volume 42, 2018 - Issue 5. doi.org/10.1080/01611194.2017.1422050
• Biham, Eli, Cryptanalysis of multiple modes of operation , J. Cryptology 11:1 (1998) 45-58.
• Biham, Eli, Cryptanalysis of triple modes of operation, J. Cryptology 12:3 (1999) 161-184.
• Equivalence between two flavours of oblivious transfers (PDF)
• Completeness Theoerms for Fault Tolerant Distributed Computing (PDF)
• Parallel Reducibility for Information-Theoretically Secure Computation (PDF)
• The best known SPRP bases
• Helger Lipmaa Notes
• MIT 6.876, Course in Cryptographic Game Theory.
• Van Eck radiation (security, not crypto, but an enjoyable group of pages anyway.)
• Cryptogram solver

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 21 jan 2018
update: 18 nov 2019