Spring 2023

Part I - Cryptanalysis

Email: mastermath AT marc DASH stevens DOT nl

- Part I website up
- 9 February: Week 1 material. See 'reverse classroom' format explained below. The first week the course will be fully online due to public transport strikes. Watch the prerecorded lectures before the lecture timeslot, as the online session will be used for getting to know each other, exercises and Q & A.
- 16 February: Week 2 material. Watch the prerecorded lecture before. Room is available from 10:00 to prepare, we'll start at 11:00.
- 23 February: cancelled
- 2 March: Week 3 material. Fully online on wonder.me due to public transport strikes.
- 9 March: Week 4 material.
- 13 March: Week 5 material.
- 20 March: Week 6 material.
- Open position for Ph.D. position at CWI & ULeiden on Quantum-Safe Cryptanalysis: more information

**Links:**

- wonder.me room (only for online sessions instead of classroom sessions when announced)

**Goal:**
Cryptology deals with mathematical techniques for design and analysis of algorithms and protocols for digital security in the presence of malicious adversaries.
For example, encryption and digital signatures are used to construct private and authentic communication channels, which are instrumental to secure Internet transactions.

The goal of this course is to provide insight
into cryptography secure against quantum computers (post-quantum cryptography)
as well as various methods for the mathematical cryptanalysis of cryptographic systems.

This course in cryptology consists of two main topics. This part will cover various generic attacks against common cryptographic primitives (e.g., block ciphers, hash functions) and cover important cryptanalytic attack techniques like time-memory tradeoffs, linear cryptanalysis, differential cryptanalysis and algebraic cryptanalysis.

See also the website of this part from 2021: link.

Lecture Notes (version 2021 march 31).

Lecture 1 Material

- Lecture Notes chapters 1 - 4.
- Introduction Video: YouTube. <= watch first, but please disregard any information about the 2021 edition of this course when this was recorded.
- Lecture (full): Online Powerpoint with Video (PDF slides) or YouTube.
- Errrata: Hellman's Online complexity in the lecture video has a typo. It should be O(rt + rmt^3/|K|).
- Addendum: Computing the total success probability of Hellman's attack by simply multiplying the individual table success probability by the amount of tables is a first order approximation sufficient for this course and the exercise. But there is some loss due to overlap between tables. To be more precise, an accurate calculation can be done as follows.

Lecture 2 Material

- Lecture Notes chapter 5.
- Lecture Online Powerpoint (PDF slides) or YouTube.

Lecture 3 Material

- Lecture Notes chapter 6 - 6.7.2.
- Lecture Online Powerpoint (PDF slides) or YouTube.
- Errrata: slide 14: The block cipher oracle results in bias +/- 1/32, thus probability 0.5 +/- 1/32. The random oracle results in bias 0, thus probability 0.5.

Lecture 4 Material

- Lecture Notes chapter 6.7.3 - 7.5.
- Lecture Online Powerpoint (PDF slides) or YouTube.
- Errrata: slide 2: The block cipher oracle results in bias +/- 1/32, thus probability 0.5 +/- 1/32. The random oracle results in bias 0, thus probability 0.5.

Lecture 5 Material

- Lecture Notes chapter 7.6 - 7.8.
- Lecture Online Powerpoint (PDF slides) or YouTube.

Lecture 6 Material

- Lecture Notes chapter 8.
- Lecture Online Powerpoint (PDF slides) or YouTube.

- toycipher_definition.sage
- toycipher_gendata.sage
- linearcryptanalysis.sage
- ptctlist.txt
- ptctlist.sobj (SAGE binary format)
- Project on cocalc.com containing these files

Q1. What are the attack parameters corresponding to a memory complexity of N^(1/2) with the same success probability? (Use mt^2=N and Hellman's success probability estimation).

Q2. What is the online complexity (including false alarms) for these parameters?

Note errrata: Hellman's Online complexity in the lecture video has a typo. It should be O(rt + rmt^3/|K|).

Q. How and when does the attack fail?

Q1. Which structural properties of the ciphertext can you deduce when there exists at least one collision among ciphertext blocks?

Q2. How can you use this to slightly simplify the attack algorithm compared to CBC?

Relations with overlapping bits of K5 are recommended to achieve greater
confidence: the correct value of bits of K5 is not always the one with the
highest absolute bias, however it almost always is when taking the total
absolute bias over 2 relations together.
E.g., the linear relation from Chapter 8 can be modified by removing
plaintext bit P_8, this modified relation has bias +1/32 and covers the same
K5-bits. Whereas either individual relation succeeds often enough for random keys
(the correct value has the highest bias), using them together succeeds
almost always (the correct value has the highest total bias).

Q2. Compute an approximation of its success probability by considering all possible variations for the 2nd round and 3rd round S-Box. I.e., for the active 2nd round S-Box S_2i consider all possible output differences \Delta Y_2i. Similarly, for the active 3rd round S-Box S_3j consider all possible input differences \Delta X_3j.

>echo -n "plaintext" > plaintext.txt >openssl enc -aes-128-ecb -K 000000000000000000000000000000ff -in plaintext.txt -out ciphertext8.txt -base64 Content ciphertext8.txt: p8SkEqgGnsC7AY20RLcZPw==Recover the 32-bit key for the following AES-128 block encryption:

>echo -n "plaintext" > plaintext.txt >openssl enc -aes-128-ecb -K 000000000000000000000000xxxxxxxx -in plaintext.txt -out ciphertext32.txt -base64 Content ciphertext32.txt: fgpIqNL2jNOcnbGyeBH3wQ==

>echo -n "plaintext" > plaintext.txt >openssl enc -aes-128-ecb -K 0000000000000000000000xxxxxxxxxx -in plaintext.txt -out ciphertext40.txt -base64 Content ciphertext40.txt: yw+1N8hXE1gq/abtGamcsw==

Password1: d4ade12d94ef4c090c8f5a7b7a6f9449:034daff94d806cee29f310f5d6a77ba4 Password2: 382ee38891e7056e17306d272a9441bb:a107e5624083963db8dbe61f3d288588

Password: 78fc94b134540254c914c58291c22f87:e7ac4712dd6def58c4095a388b8eecda

Password: 956a82ed7ec234e17d97c13469bee91f

Password: 1eea849311fa5b43f479fcc94bf206c0

E.g., the following collision on the first 8 hexadecimals:

>echo -n 10029 > 10029.txt >echo -n 47427 > 42427.txt >sha1sum 10029.txt 42437.txt 38d0a030376c582fe818b544c1be3490c277f7cf 10029.txt 38d0a030efb24c67112fc76ea91c6fdfe33df53a 47427.txt

>echo -n '0ecc9a9dc8d18149' | sha1sum | cut -c-16 606cf52221c792f3 >echo -n 'f1a79915b25fbdf3' | sha1sum | cut -c-16 606cf52221c792f3