MasterMath Cryptology Course
Fall 2015
Part II - Cryptanalysis

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

News

- Final grades have been sent out, you can check your grade with your University or here

Description

The official home page is here. The first part will be taught from Feb 03 until Mar 17 by Tanja Lange. The second part will be taught by Marc Stevens.
 
Goal: 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
 
Description: 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.
This course in cryptology consists of two main topics:
The first part focuses on post-quantum cryptography dealing with cryptographic systems that are secure even given the existence of quantum computers and the second part focuses on cryptanalysis, the analysis of the security of cryptographic systems.
After a general introduction to cryptography (the constructive side of cryptology) and cryptanalysis the course introduces the main contenders for secure systems: lattice-based encryption, code-based encryption, hash-based signatures, and multivariate-quadratic-based signatures. These systems are examples of public-key systems and this is the main area affected by quantum computers; symmetric-key systems, such as hash functions and block and stream ciphers) are used as building blocks inside them and for the transmission of data in bulk.
The second part of the course 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.

Exam

Exam: 9 June 2015, 14:00-17:00, Educatorium Beta.
Retake: 30 June 2015, 14:00-17:00, BBG 061.

To participate in the exam, registration for the course is sufficient and necessary. You will be allowed to use a collection of notes and a pocket calculator for the exam. No laptops, tablets, phones or other likewise computing devices allowed.

For practice you can look at the first exam: (exam.pdf). Some additional hints can be found here: (hints.pdf).

You can expect to be asked:

Planning

Lectures for the second part will be on the following Tuesdays: Mar 24, Mar 31, Apr 7, Apr 14, Apr 21, Apr 28, May 12. Note that May 5 is a public Holiday. May 12 will be used for questions for exam preparation. Lectures will take place at the University of Utrecht in Minnaertbuilding room 211.

Lecture Notes

Chapters 1-7 v5.
Chapter 8 v4.
Chapter 9 v2.
Chapter 10 v3.
These notes will be updated as the course continues.

Lecture March 24: covered sections 1 through 5.2, read section 5.3.
Lecture March 31: chapters 6 and 7
Lecture April 7: chapter 8
Lecture April 14: chapter 8 and chapter 9
Lecture April 21: chapter 10
Lecture April 28: chapter 10
May 5: no lecture
May 12: exam preparation

Files

Files belonging to chapter 8

You can check out this SAGE tutorial.

Challenges

Solutions can emailed to the email address above. Please use subject line "[challenge N]".

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: 1st J.A. (LU), 2nd H.d.V. (?), 3rd L.G.B. (TUe), 4th A.V. (RUG), 5th M.A. (LU), 6th A.B. (LU)
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: 1st H.d.V. (?), 2nd M.A. (LU), 3rd A.B. (LU)

Challenge 3

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 password. Recover the passwords with the following LMHASHes: 
Password1: d4ade12d94ef4c090c8f5a7b7a6f9449:034daff94d806cee29f310f5d6a77ba4
Password2: 382ee38891e7056e17306d272a9441bb:a107e5624083963db8dbe61f3d288588
Solved by: 1st H.d.V. (?), 2nd A.B. (LU), 3rd M.A. (LU), 4th A.M. (VU)

Challenge 4

Recover the password with the following LMHASH: 
Password: 78fc94b134540254c914c58291c22f87:e7ac4712dd6def58c4095a388b8eecda
Solved by: 1st A.B. (LU), 2nd H.d.V. (?), 3rd M.A. (LU)

Challenge 5

Recover the numeric password of length 12 with the following MD5-hash: 
Password: 956a82ed7ec234e17d97c13469bee91f
Solved by: 1st M.A. (LU), 2nd H.d.V. (?), 3rd A.B. (LU), 4th M.v.H. (TUe)

Challenge 6

Recover the lowercase alpha password of length 9 with the following MD5-hash: 
Password: 1eea849311fa5b43f479fcc94bf206c0
Solved by: 1st H.d.V. (?), 2nd M.A. (LU), 3rd A.B. (LU)

Challenge 7

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: 1st M.A. (LU), 2nd H.d.V. (?), 3rd B.J. (UU), 4th A.B. (LU), 5th A.V. (RUG)
Hint

Challenge 8

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: 1st A.B. (LU), 2nd H.d.V. (?), 3rd M.A. (LU), 4th A.V. (RUG)

Challenge 9

Find a 4x4 SBox 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.) 

Solved by: 1st A.V. (RUG), 2nd A.B. (LU), 3rd M.A. (LU), 4th B.J. (UU),
5th H.d.V. (?)






Challenge 10

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 8 or Challenge 10.5.)


Solved by: 1st M.A. (LU), 2nd A.B. (LU), 3rd H.d.V. (?), 4th B.J. (UU)






Challenge 10.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 bits of K5 
(i.e., 2 round-4 SBoxes) that are unknown (i.e., not yet recovered
using a prior relation in the sequence).





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




Solved by: 1st A.B. (LU), 2nd M.A. (LU)






Challenge 11

Fully recover final round key K5 that was used to generate the
plaintext-ciphertext pair list in ptctlist.txt/ptctlist.sobj.


Solved by: 1st A.B. (LU), 2nd M.A. (LU), 3rd A.V. (RUG)






Challenge 12

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


Solved by: 1st A.B. (LU), 2nd M.A. (LU), 3rd A.V. (RUG)






Challenge 13

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


Solved by: 1st A.B. (LU), 2nd M.A. (LU), 3rd A.V. (RUG)






Challenge 14

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


Solved by: 1st M.A. (LU), 2nd A.B. (LU)






Challenge 15

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) that are unknown (i.e., not yet recovered
using a prior relation in the sequence).


Solved by: 1st M.A. (LU), 2nd A.B. (LU)






Challenge 16

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: 1st A.B. (LU)






Challenge 17

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: 1st A.B. (LU), 2nd T.O. (TUD), 3rd M.A. (LU)


Hint




Sample functions





Sample 3x3 SBox


 x   | 0 1 2 3 4 5 6 7
S[x] | 0 1 3 6 7 4 5 2








Sample boolean function


BF(b,c) = NOT(b) XOR c