MasterMath Cryptology Course
Spring 2019
Part I - Cryptanalysis
dr. ir. Marc Stevens
Email: mastermath AT marc DASH stevens DOT nl
News
- Part I website up
Description
The official home page is
here.
The first part will be taught from February 5 to March 19, and April 2, by
Marc Stevens.
The second part will be taught from March 26, and April 9 until May 21 by
Tanja Lange
and Andreas Hulsing.
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 2017: link.
Exam
See the MasterMath course website for the exam date and location.
For practice you can look at a previous exam:
(exam.pdf)
(Exclude 6(a) as that material has not been covered this year)
and the exercises below.
Some additional hints can be found here:
(hints.pdf).
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) and estimate (offline/online) complexity and success probability in other settings for, e.g., key recovery, state recovery or distinguishing
- 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 for a given primitive over a few rounds
- to construct a (partial) key recovery attack based on a given linear approximation or (normal,truncated or impossible) differential
- 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
- to apply modular and/or bitwise-signed differential cryptanalysis and construct a simple differential path over a few steps of a MD5-like hash function
- to determine an advanced message modification for an MD5-like hash function
- to compute above mentioned attacks for very small instances that can be done by hand
Planning
Lectures for this part will be on the following Tuesdays: Feb 5 (week 6),
Feb 12 (week 7), Feb 19 (week 8), Feb 26 (week 9), March 5 (week 10), March
12 (week 11), March 19 (week 12), and April 2 (week 14).
March 26 (week 13) will be used for Part II.
Lectures will take place at the University of Utrecht, see the official webpage for the actual location!
Lecture Notes
These notes will be updated as the course continues.
Lecture Notes version 12-march-2019.
Lecture February 5: chapters 1 - 4.
Lecture February 12: chapter 5.
Lecture February 19: chapter 6 - 6.7.2.
Lecture February 26: chapter 6.7.3 - 7.5.
Lecture March 5: chapter 7.6 - 7.8.
Lecture March 12: chapter 8 - 9.2.5.
Lecture April 2: chapter 9.2.6 - 9.6.4.
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]".
Week 1
Exercise 1
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.
What is the online complexity (including false alarms) for Hellman's attack chosing parameters for the same estimated success probability using only
N^(1/2) memory?
Week 2
Exercise 2
The O(2^(n/2)) distinguishing attack from section 5.9 also applies to Counter Mode.
How can this attack be slightly simplified compared to CBC?
Exercise 3
Assume Cipher FeedBack (CFB) Mode is used with padding and there exists a padding oracle as in section 5.10.
Show how to adapt the padding oracle attack against CFB with padding.
Week 3
Exercise 4
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.)
Exercise 5
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.)
Week 4
Exercise 6
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 bits of K5 (i.e., 2 round-4 SBoxes).
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).
Exercise 7
Find another differential over the first 3 rounds of the toy cipher.
Exercise 8
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).
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]".
Week 1
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: RB, JL
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: RB, JL
Week 3
Challenge 3
Fully recover the final round key K5 that was used to generate the
plaintext-ciphertext pair list in ptctlist.txt/ptctlist.sobj in this page's Files
section.
Solved by:
Week 4
Challenge 4
Recover round key K4 that was used to generate the
plaintext-ciphertext pair list in ptctlist.txt/ptctlist.sobj.
Solved by:
Challenge 5
Recover round keys K3, K2 and K1 that were used to generate the
plaintext-ciphertext pair list in ptctlist.txt/ptctlist.sobj.
Solved by:
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: KS
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: