The Kryptos Sculpture, Langley, VA.

CSC507/609-B: Cryptography

by: burt rosenberg
at: university of miami
semester: fall 2021 (221)
time: MWF 9:15 AM – 10:05 AM
location: Mahoney/Pearson Com 116

Calendar:

• Monday, 23 Aug 2021, Class begins
• Midterm: Wednesday, 20 October.
• Final: 8:00–10:30, Monday, 13 December.

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, and computational and informational model variants are introduced.
• The course emphasizes a computational approach where programming exercises practice the conceptual and mathematical framework.

Table of Contents:

• Reading Assignments
• Frightful Fridays
• Assignments
• Class Notes
• Syllabus
• Books
• Other resources
• Attacks
• References

Reading Assignments:

1. Asymptotic Order Notation (Big-Oh) PDF
2. Probabilistic Polynomial Time Algorithms & Cryptography PDF
3. Please read the first two chapters in Katz and Lindell (2nd ed. numbering)
4. Perfect Secrecy PDF
5. Please read the third chapter in Katz and Lindell (2nd ed. numbering)
6. Pseudo-Randomness and Stream Ciphers PDF
7. Views and a Chosen Plaintext Attack on a Pseudorandom Function PDF
8. Please read the fourth chapter in Katz and Lindell (2nd ed. numbering)
9. Please read the ninth and tenth chapters in Katz and Lindell (2nd ed. numbering)
10. Be familiar with the contents of the seventh chapter in Katz and Lindell.
11. New Directions In Cryptography, Diffie and Hellman (1976).
12. Finish reading about public key, chapters 11 and 12 in Katz and Lindell.
13. RSA Quick Intro
14. Read Chapter 12 in Katz and Lindell
15. The knowledge complexity of Interactive Proof Systems, Goldwasser, Micali, Rackoff (1985)

Frightful Fridays:

• Frightful October 1:
  Flaws in MS-CHAP v2 ☢PDF
• Frightful October 8:
  Blind TCP/IP hijacking is still alive ☢HTML
• Frightful October 15:
  Frightfully on break
• Frightful October 22:
  NFT's: only Halloween could be more frightful.
• Frightful October 29:
  Denning-Sacco Attack on Needham Schroeder
  The logic of authentication protocols, Syverson and Cervesato
• Frightful November 5:
  Sneaking a bit (or more) from the discrete log
• Frightful November 12:
  Ron was wrong, Whit is right, ☢PDF
  There's no need to panic over factorable keys - just mind your Ps and Qs ☢website

Assignments:

• Project 1: Coding Vigenere.
  Due: Wednesday, Sept 1.
• Project 2: Breaking Vigenere.
  Due: Wednesday, Sept 15.
• Project 3: Adversarial Indistinguishability.
  Due: Wednesday, Oct 6.
• Project 4: CBC Mode Padding Attack.
  Due: Wednesday, Oct 27.
• Project 5: Elliptic Curve Cryptosystems.
  Due: Friday, Dec. 3.
• Final Project: Pohlig-Hellman for Elliptic Curves
  Due: Wednesday, Dec. 8.

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.
• Pseudorandom Generators
  • Adversarial indistinguishability games
  • The eaves-dropper attack model
  • Pseudorandomness and PPT distinguisher games
  • Stream Ciphers
  • Multiple message attacks and malleability
• Practical CPA-Security
  • Implementation of CPA strong cipher
  • Initial vectors
  • Security reduction proofs
    • Definition of pseudorandom permutation
    • Perfect security when using a random permutation
    • Reduction of breaking PRP Discrimination to breaking CPA Inv.
  • Modes of operation
    • Encryption: CBC, CFB, OFB
    • Decryption: CBC
    • counter mode, GCM
  • The limitations of the CPA model.
    • Malleability
    • Truncation attacks, replay attacks, reordering attacks
• Practical CCA-Security
  • Chosen Ciphertext Attack
  • Message Authentication Codes (MAC)
  • Message forgery models
  • CBC-MAC
  • Authenticated Encryption
  • Implementation of CCA strong cipher

Hashing and Block-chains

• Cryptographic Hash Functions
  • Mathematical framework and security definitions
  • Collision free, 2nd pre-image resistance, pre-image resistance.
  • Birthday attack
  • Merkle-Damgard construction
• Bitcoin and Blockchain
  • The (Real) Blockchain mini-course
  • 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
• References
  • The Genesis Block
  • Mastering Bitcoin
  • Princeton Bitcoin

Public Key Cryptography

• Introduction to Public Key
  • The New Directions paper.
  • GCHQ, James Ellis, Clifford Cocks and Malcolm Williamson.
  • Needham-Schroeder
  • Discrete Logs
  • Diffie-Hellman Key Exchange
• Public Key Encryption
  • El Gamal Systems
    • El Gamal encryption, and reduction of El Gamal to DDH
    • Quadratic Residue attacks, and extensions to other prime powers (python)
    • Bit Commitment
  • RSA Systems
    • Integer factoring and the RSA hardness assumption.
    • OAEP
  • Adversarial indistinguishability: Diagram
    • The consequences of a public key
      • Perfect secrecy is impossible
      • Deterministic public key schemes are insecure under any model.
      • Ease-dropping security is the same as CPA security.
    • KEM/DEM (EAV secret scheme is sufficient)
• Public Key Signatures
  • Definition, and adversary
  • Identification schemes, perfect correctness and probabilistic soundness
  • Schnorr identification, and knowledge extraction
  • Fiat-Shamir transformation and Schnorr dig-sig's

Zero Knowledge Proof Systems

• Interactive Proof systems
  • Completeness, and soundness
  • Relationship to NP and BPP
  • Graph Non-isomorphism is in IP
• Zero knowledge, knowledge and information
  • ZK proof for Graph Isomorphism
  • Simulator, role of non-halting for language instances
  • Zero Knowledge proofs of knowledge: modular square root
  • All of NP in Zero Knowledge: 3-colorability
• Fiat-Shamir zero-knowledge identification system
• Simple demonstration of ZK with a deck of cards.
• References
  • The Knowledge Complexity of Interactive Proof-Systems, Goldwasser, Micali and Rackoff. (FoCS 1985) and the final (SIAM J.Comp 1989) version.
  • Proofs that Yield Nothing But Their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems, Goldreich, Micali, Wigderson (JACM 1991)
  • How To Play Any Mental Game (SToC 1987)

Syllabus:

• Textbooks and slack:
  • Required: Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell. (Amazon)
    The 3ird addition is a great new edition. However, for this class, either the 3ird or the 2nd edition will be fine.
  • 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.
  • Join us on slack and post to #csc507-221.
• Homework and Grading:
  • 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.
• Computer Needs:
  • The computer work will use python, make and subversion.
  • Windows users have the unix options described in CSC Lab Page
  • OSX users can install the tools using the brew package manager.
  • Please see my mildly humorous subversion tutorial.
• Honor Code:
  • Class participants read and accept the University Honor Code, available from the Dean of Students.
  • Work resulting from an integrity violation will not be graded. A no-grade arising in this way can be numerically distinct from a zero.

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
• Proof of the 4 square roots in an RSA modulus.
  1. Square the relation sq+rp=1.
  2. Mod pq inner terms cancel, and outer terms are invariant to signs of s and r.
  3. So all the following will square to 1: ±(sq ± rp).
  4. The non-trivial square roots of one are ±(sq − rp).

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: 2 dec 2021