Cryptography course notes - Block Ciphers

https://www.coursera.org/learn/crypto

PRP/PRF - Psuedo Random Permutations/Functions and Block Ciphers are the terms which can be used independently.

They map a block of size n to output block of size n. For 3DES, n = 64 bits and k(key size) = 168 bits. For AES, n = 128 bits, k = 128, 192, 256

Key is expanded in round keys which are in turn applied to input. It's parallel in nature.

Key expansion. Round function.

Basic building block - Feistel netwrok - take functions which map n bits to n bits and construct invertible functions which map 2n bits to 2n bits.

DES is 16 round Feistel network. Function is same in all rounds, just that key is different.

Luby Rackoff theorem - 3 round Feistel network gives a secure PRF. Argue that 2 round is not secure.

Breaking DES with exhaustive search

Given 1 m,c pair there is 99.5% probability that a certain key was used.

With 2 pairs, prob. is even higher.

56-bit DES has been broken in 3 months, 3 days, 22 hours. In 7 days with 120 off-the-shelf FPGAs.

With double-DES, it can be broken in 2^63 time (vs 2^56 for single-DES) due to man in the middle attack. For triple-DES it's 2^118. 

DES-X can be used to make DES more secure by doing k1 XOR (E (k2, m XOR k3))

Attacks on the implementation

Side channel attacks
For e.g. if a smart card has a key which is used for encryption/decryption - by observing power consumption you can guess 1) number of cycles (peaks/troughs count) 2) by zooming in on the graph even 0s and 1s can be guessed of the key. 3) Smart card companies try to mask the power but by differential power analysis it can still be broken.

Also, if one core is used for enc/dec, on another core the attack can run which can monitor cache misses since both the cores share the cache.

Fault attacks

Computing errors in the last round expose the secret key k

Linear and Differential attacks
Given many inp/oup pairs, can we recover key in time less than 2^56 (Exhaustive search).

Linear cryptoanalysis -

If you XOR subset of message bits with subset of CT resulting value should be equal to subset of original key with prob = 1/2

But if it's 1/2 + epsilon then there is some bias.

In case of DES epsilon is non-trivial which breaks DES in 2 POW 42. Turns out the 5th S-box (S5) has some linearity which results in 2 POW 42 attack.

Quantum attacks:

Generic search problem:

Given f:X->{0,1}
Goal : find x e X s.t. f(x) = 1

Classical computer will take O(|X|) time. Quantum computing can help us to solve this problem faster, in O(|X| pow 1/2). A quantum computer can break DES in 2 POW 28 as opposed to 2 POW 56. And AES in 2 POW 64. These days 2 pow 64 is considered insecure.