Spring 2017

Part II - Cryptanalysis

Email: mastermath AT marc DASH stevens DOT nl

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

Lecture Notes version 31-may-2017.

Lecture April 4: chapters 1-5.

Lecture April 11: chapters 6 & 7.

Lecture April 18: chapter 8.

Lecture April 25: chapter 9.

Lecture May 16: chapter 10 (first half).

Lecture May 23: chapter 10 (second half).

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

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

>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

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