Spring 2021

Part II - Cryptanalysis

Email: mastermath AT marc DASH stevens DOT nl

**Links:**

- Zulip chat (for updates & questions)
- wonder.me room (for online sessions)

**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 2019: link.

You can expect to be asked:

- to apply the covered generic attacks
- exhaustive search,
- birthday search using distinguished points,
- Hellman's Time-Memory trade-off)

- for a given n*m SBox (n input bits, m output bits) to compute (partially) LAT and DDT
- to construct a linear approximation for a given primitive (e.g., SPN cipher) over a few rounds
- to construct a differential relation for a given primitive over a few rounds
- to construct a (partial) key recovery attack based on a given linear approximation or differential relation
- to construct a distinguishing attack based on boomerangs and estimate complexity
- to apply covered generic attacks against iterated (e.g., Merkle-Damgard) hash functions in other settings

Lecture Notes (version 2021 march 31).

Lecture Material April 8: moved due to lecture video difficulties

Lecture Material April 15

- Lecture Notes chapters 1 - 4.
- Introduction Video: YouTube. <= watch first
- 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|).

Lecture Material April 22

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

Lecture Material April 29

- 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 May 6: no lecture

Lecture Material May 13

- 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 Material May 20

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

Lecture Material May 27

- 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