Cryptanalysis
Learn about cryptographic attacks and how to apply this knowledge to design secure cryptographic primitives.
Lecturer
Ling Song
Calendar and schedule/ 校历和课表
- Time: 18:30 - 20:10 Wednesday
- Calendar / 校历 Open
- Class schedule / 课表 Open
- Week 01 - Week 16: lecture
- Week 17 - Week 20: seminar and presentation
Goals and Contents
This course aims to give you in-depth knowledge about the cryptographic attacks, focusing on cryptanalysis of symmetric ciphers and asymmetric ciphers. More precisely, this course covers the following topics:
- Introduction to Cryptanalysis
- Kerckhoffs’ principle
- Notions of security: confidentiality, integrity, authenticity and more
- Models of attack
- Targets of attack
- Theoretical attacks vs. practical attacks
- Lessons learned from classic ciphers
- Cryptanalysis of block ciphers
- Meet-in-the-Middle attack & TMTO
- Basic differential analysis
- Basic linear analysis
- Wide-trail strategy and AES
- More (optional)
- Integral cryptanalysis
- Truncated differential attack
- Higher order differential attack
- Boomerang and rectangle attacks
- Impossible differential attack
- Multi dimensional linear attack
- Zero-correlation linear attack
- Division property
- Demirci-Selcuk MitM attack
- Subspace trail cryptanalysis
- Cryptanalysis of stream ciphers
- Guess-and-determine attack on stream ciphers
- Time-Memory-Data trade off attack
- Linear distinguisher and correlation attacks
- Cryptanalysis of hash functions
- Birthday attacks
- MD and Sponge
- Differential cryptanalysis and collision attacks
- Meet-in-the-Middle Pre-image attack
- Computer-aided cryptanalysis
- MILP-based cryptanalysis
- SAT-based cryptanalysis
- Algebraic cryptanalysis
- Interpolation attack
- Cube attacks and Higher order differential attack
- Linearization
- Merkle-Hellman Knapsack
- Diffie-Hellman Key Exchange and MitM
- Discrete Log algorithms
- Baby-step giant-step
- Factoring algorithms
- Dixon’s Algorithm
- Quadratic Sieve
- Quantum algorithms
Material
Slides
- Session 2 (MitM and TMTO)
- Session 3 (DC and LC)
- Session 4 (AES Wide Trail Strategy)
- Session 5 (Tools for Cryptanalysis)
- Session 6 (Hash Functions)
- Session 7 (MD4 and Collision Attacks)
- Session 8 (Permutation Based Cryptography)
- Session 9 (Boolean Functions)
- Session 10 (Cryptanalysis of Keccack)
- Session 14 (Introduction to NTRU Public Key Cryptosystem)
- Session 15 (RSA and Coppersmith Method)
Exercises
- Exercises after each section
Suggested Topics for Projects (choose one)
- Search for the best differential trails with MILP/SAT
- Search for the integral distinguishers based on division property using MILP/SAT
- Search for the cube attacks on stream ciphers with MILP/SAT
- Search for cubes for Keccak
- Find parameters for the guess-and-determine attacks with MILP
- Implement Wiener’s attack on RSA
Suggested Topics for Seminars (choose one)
- Designs of stream ciphers with small states
- RSA and Shor’s algorithm
- Differential analysis of keyless permutations
- Search for differential trails with MILP/SAT for pSP
- Machine learning-based symmetric cryptanalysis
- Hybrid approaches including:
- Differential-Linear Attack
- Algebraic-Differential Attack
Textbooks
Applied Cryptanalysis: Breaking Ciphers in the Real World
Algorithmic Cryptanalysis
Techniques for Cryptanalysis of Block Ciphers
The Block Cipher Companion
An Introduction to Mathematical Cryptography
A Salad of Block Ciphers
It is available on Cryptology ePrint Archive:
https://eprint.iacr.org/2016/1171
A Self-Study Course in Block-Cipher Cryptanalysis
Studying cryptanalysis is difficult because there is no standard textbook, and no way of knowing which cryptanalytic problems are suitable for different levels of students. This paper attempts to organize the existing literature of block-cipher cryptanalysis in a way that students can use to learn cryptanalytic techniques and ways to break new algorithms.
It is publicly available via the following link:
https://www.schneier.com/wp-content/uploads/2016/02/paper-self-study.pdf