Spring 2019

Part I - Cryptanalysis

Email: mastermath AT marc DASH stevens DOT nl

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

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

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

- 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