Fall 2015

Part II - Cryptanalysis

Email: mastermath AT marc DASH stevens DOT nl

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.

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:

- 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 LAT, DDT and/or SCT(for m=1, ch10)
- 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

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

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

>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

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

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

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

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