DES and Cryptanalysis

Key is 48 bits, not 64 as NSA found it too difficult to

Key Schedule - The DES key schedule simply returns various permutations of $k$ as sub-keys

<<< - left rotation >>> - right notation

PC-1

• Permuted Choice 1 - Selects 56 of the 64 bits
• The other "parity" bits are discarded: DES only uses a 56-bit key
• Spread throughout the internal state of the key schedule
• DES was good the hardware back in the day

Left Rotations

• Represent a left shift where the left most numbers wrap around to the right hand side
• In DES, each 28-bit block is rotated left by <<<1 for rounds {1,2,9,16} and <<<2 otherwise
• The total rotation is $4\times 1+ 12\times 2 = 28$ which means $C_0=C_{16}$ and $D_0=D_{16}$

PC-2 - Permuted choice 2 select 48 of the 56 bits to be used as keys

Breaking DES

Des has a key length of 56-bits A brute force attack requires no knowledge of the cipher, only a pair of plaintext and ciphertext

Key collisions - For a 56-bit key but a 64-bit block its possible a different key could work, but unlikely

Meet-in-the-middle

Attack splits the search space into two

1. Calculate encryptions of $x_1$ for all $k_{L,i}$ and store intermediate values $Z_{L,i}$
2. Calculate all decryptions of $y_1$ for all $k_{R,j}$ to find $Z_{R,j}$

Practicalities

• Requires $2^{k+1}$ attempts rather than $2^{k\times2}$
• Much better than the brute force attempt
• Trades off computation for storage
• Assumes some king of O(1) lookup

3DES

• Triple DES uses three different keys
• Either enc->enc->enc or enc->dec->enc (is backwards compatible)
• Often used in banking, smart cards and other payment systems
• 3 times slower than AES, and less secure

DES-X

• Key whitening
• Taking first key, xoring with input, then encrypt with 2nd key, then xor with 3rd key
• MITM can still be used here, as well as other more advanced

Cryptanalysis

Types of attacks:

• Brute-force
• Ciphertext-only
• Known-plaintext
• Chosen-plaintext
• Chosen-ciphertext
• Related-key attack

In modern cryptography, a cipher is declared broken by any attack that is more efficient than brute force

Analytical Attacks - Exploit some underlying structural or mathematical weakness in a cipher

• e.g. MITM
• Derivation of taps in LFSRs

Statistical Attacks - Capture statistical patterns between input and output to recover key bits

• Differential cryptanalysis
• Linear cryptanalysis

Differential Cryptanalysis

• Perhaps ow the most important modern method for breaking block ciphers
• It is a chosen plaintext attack
• Aim to find predictable changes in output bits caused by known changes in input bits

Resisting

• S-boxes must be designed such that the probability of any pair is as low as possible
• More rounds make differentials even less likely
• Good permutation to involve more S-boxes is vital
• DES was specifically designed to resist this kind of attack - in secret