MasterMath Cryptology Course
Spring 2025
Part I

dr. ir. Marc Stevens
Email: mastermath AT marc DASH stevens DOT nl

News

Course General Information

The official home page is here. The official time slot for this course is Wednesday 10:00 - 12:45 at Utrecht University, Buys Ballot Gebouw, room 005. The first part will be taught from February 5 to March 26 by Marc Stevens. The second part will be taught from April 2 to May 21 by Subhasree Patro. The exam is planned for June 11. The exam will be a written or an oral exam, depending on the number of students.
 

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. The first part covers symmetric-key cryptographic primitives, such as hash functions and block ciphers, and important attack techniques against them. These remain secure against quantum computers. We then cover the design and analysis of post-quantum public-key cryptography built from these symmetric-key cryptographic primitives. The second part covers the design and cryptanalysis of important post-quantum public-key cryptography built from mathematical structures, such as lattices and error-correcting codes. This will also include relevant quantum attacks.

Exam

See the MasterMath course website for the exam date and location. You can expect to be asked: For this part of the course, the exam will typically contain

Lecture Notes

These notes will be updated as the course continues.

Lecture Notes (v3: 26 feb 2025).


Lecture 1 Material
Lecture 2 Material
Lecture 3 Material
Lecture 4 Material
Lecture 5 Material
Lecture 6 Material
Lecture 7 Material

Files

Files belonging to chapters.

Files belonging to chapter 6:

You can check out this SAGE tutorial.

Exercises

I recommend doing the exercises. Solutions can emailed to the email address above if you want me to verify. Please use subject line "[exercise N]". Questions can be placed online, via email or in the designated Q & A session.

Week 1

Exercise 1

Q1. Consider the algorithm that takes as input a positive integer n, and outputs a uniformly randomly sampled n-bit key. Is this algorithm probabilistic polynomial time? Why Yes/No?
Q2. Consider a similar algorithm as above, but where the input is 1^n: a string of n bits with value 1, and which outputs a uniformly randomly sampled n-bit key. Is this algorithm probabilistic polynomial time? Why Yes/No?
Q3. Consider the algorithm that on input 1^n: 
1. Queries K <‐ A(1^n), where A is the algorithm from Q2.
2. If the first bit of K is 0 then starts over at step 1.
3. Outputs K
Is this algorithm probabilistic polynomial time? Why Yes/No?

Exercise 2

Hellman's suggested parameters for his Time-Memory Trade Off attack are m=t=r=N^(1/3) which requires mr=N^(2/3) memory and has success probability about 0.8, where N=|K| is the size of the space.
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?

Week 2

Exercise 3

Find a 4x4 SBox (i.e. a permutation on strings of 4bits) with no non-trivial linear relations with an absolute bias larger than 4/16. (Trivial linear relations are those that involve no input bits and/or no output bits, i.e., the first row and first column of the SBOX LAT.) (Hint: Use sagemath online at sagemath or cocalc.)

Exercise 4

Find another linear relation over the first 3 rounds of the toy cipher with absolute bias greater or equal to 1/32. (Different from the one in Chapter 6.)

Exercise 5

Find a complete sequence of linear relations over the first 3 rounds of the toy cipher with absolute bias greater or equal to 1/32 that enables the recovery of K5. No relation must cover more than 8 *unknown* bits of K5.

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).

Week 3

Exercise 6

Find another differential over the first 3 rounds of the toy cipher.

Exercise 7

Find a complete sequence of differentials over the first 3 rounds of the toy cipher that enables the recovery of K5. No relation must cover more than 8 bits of K5 (i.e., 2 round-4 SBoxes).

Exercise 8

Q1. Construct another boomerang where each 2-round differential relation has only 2 active S-Boxes.
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.

Week 4

Exercise 9

The improved collision attack has various added costs. Namely, to actually find the collision and various losses. Consider an expected trail length of t=2^l with l=n/2-20.
Q1. What is the probability of a 'Robin Hood'? I.e., given two trails that end at the same distinguished point, the probability that the shortest trail starts at a point on the longest trail.
Q2. Express these added costs in terms of the expression 2^(n/2).

Exercise 10

The reduction proof for the Merkle-Damgard Framework uses the fact that the message bit length is present in the final message block to be compressed. Consider a simpler version where the message bit length is not present, and the last message block is simply padded with 0-bits to the block size. Does the reduction proof still hold? If no, can you find a counter-example?

Week 5

Exercise 11

Consider WOTS+ with 256-bit hashes and w=2^8. Suppose an attacker sees two signatures s1 and s2 for two messages m1 and m2 that are different, how can it construct a third message m3 and valid signature s3?

Exercise 12

Given a hash function f that is UD-secure, and positive integers n, and k,w \in poly(n).
Define the set D={ (e_i)_(i=1)^k | 0 ≤ e_i < w } and define kg_e for e in D as follows:
kg_e: Sample x_1,...,x_k \in {0,1}^n then output (f^e_1(x_1), ..., f^e_k(x_k)).
 
Take any e,d \in D. Prove that for any PPT A it cannot distinguish between kg_e and kg_d, i.e., |Pr[A(kg_e)=1] - Pr[A(kg_d)=1]| \in negl(n).
 
Hint: consider a bounded sequence c_1, ..., c_L in D such that c_1=e and c_L=d and each hop, c_i to c_(i+1), changes exactly 1 coefficient by 1. Use the triangle equality on the guessing probabilities to show that there exists an j such that A distinguishes between kg_c_j and kg_c_(j+1). And that this can be used to show to break UD.

Week 6

Exercise 13

Write down all the components of the public key and signatures for the basic SPHINCS+ scheme with a Tree-of-Trees of WOTS+ used to sign a leaf FORS public key to sign messages. Let each sub MerkleTree be of size 2^10, with a total of 2^60 OTS signatures to sign FORS instances. Consider WOTS+ with 256-bit hashes and w=2^8, and consider FORS with a=t=16. What's the total public key and signature size?

Week 7

Exercise 14 (updated)

In the MPC-in-the-Head examples only 2 randomly selected views are opened.
Q1. What is the soundness error upper bound for the following events?
1) Incorrectly simulated MPC protocol (i.e., not detecting inconsistency between 2 views or a view being dishonest);
2) At least one "Bad" v_i=0, thus t_i != r_i * s_i or c_i != a_i * b_i over F_256 for at least one index i;
3) event 1) and/or 2), i.e., what is the total soundness error upper bound?
Q2. Given MPC is simulated over n=16 parties and F_256, how many parallel executions do we need to get soundness amplification to a soundness error < 2^-128.
Q3. With additive secret sharing, how many views l can we open without breaking zero-knowledge?
Q4. If l randomly selected views (with l from Q3) are opened then what is the new soundness error and how many parallel executions do we need now?

Challenges

These challenges are optional and not part of the examined course material. They often require a bit of programming, but are fun to work with cryptanalysis in practice. Solutions can emailed to the email address above. Please use subject line "[challenge N]". Questions can be placed online, via email or in the designated Q & A session.

Challenge 1

Consider a file with the content "plaintext" (without line-breaks etc.). One can encrypt this file with a specified 128-bit key in hexidecimal notation using AES and PKCS#7-padding (choose paddinglength n>=1 to achieve multiple of block length, pad n bytes of value n) as follows: 
>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==
Solved by:
 
Hint

Challenge 2

Recover the 40-bit key for the following AES-128 block encryption: 
>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==
Solved by:

Challenge 3

Fully recover the final round key K5 that was used to generate the plaintext-ciphertext pair list in ptctlist.txt in this page's Files section. 

Solved by: DL, CvN







Challenge 4

Recover round key K4 that was used to generate the
plaintext-ciphertext pair list in ptctlist.txt/ptctlist.sobj.


Solved by: DL, CvN






Challenge 5

Recover round keys K3, K2 and K1 that were used to generate the
plaintext-ciphertext pair list in ptctlist.txt.


Solved by: DL, CvN







Challenge 6

Find a Boomerang Quartet for the toy cipher under key
(K1, K2, K3, K4, K5) = (9870, 15365, 46360, 58052, 43095).
Don't use the exact same plaintext and ciphertext difference from section 9.9.


Solved by: 






Challenge 7

LMHASH is the hash algorithm used to store passwords in Windows versions up
to XP. It has the "feature" that it is very weak even for long passwords.
Recover the passwords with the following LMHASHes:

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


Solved by: 






Challenge 8

Recover the password with the following LMHASH:

Password: 78fc94b134540254c914c58291c22f87:e7ac4712dd6def58c4095a388b8eecda


Solved by: 






Challenge 9

Recover the numeric password of length 12 with the following MD5-hash:

Password: 956a82ed7ec234e17d97c13469bee91f


Solved by: 






Challenge 10

Recover the lowercase alpha password of length 9 with the following MD5-hash:

Password: 1eea849311fa5b43f479fcc94bf206c0


Solved by: 






Challenge 11

Find a pair of messages that form a collision under the 
SHA-1-hash
that has been truncated from 40 hexadecimals / 160 bits to the first 12 hexadecimals / 48 bits.


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


Solved by: 

 

Hint






Challenge 12

Find a pair of messages that form a collision under the 
SHA-1-hash
that has been truncated from 40 hexadecimals / 160 bits to the first 16 hexadecimals /
64 bits.
E.g., not this one:

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


Solved by: 






Challenge 13

Find a collision for MD5's compression function using den Boer and
Bosselaers attack. 
You can base your attack on the straightforward version of their attack with complexity 2^49
in the Hint.
Don't run the attack as is, the 2^49 compression function calls will take about 1360 days on 1 CPUcore.
Compile and start the attack as follows:

gcc -o md5dbb -march=native -O3 md5.c
./md5dbb


Solved by:


Hint