DES (Data Encryption Standard)

History

In the 70s by IBM, ordered by National Bureau for Standards.

56-bit key (or 64 bit but each byte has a parity bit — NSA trolling)

64-bit blocks.

NSA influenced S-boxes to make the cipher stronger.

Structure

Feistel network with 16 rounds working with 32-bit half-blocks.

Initial and Final Permutation (IP & FP) — useless

Key schedule

bit mapping

16 boxes

another mapping and we have a round-key

then continue to another box/round

Critique of DES

Kyes: all ones, all zeros, $\text{\#e}1\text{e}1...$, and $\text{\#}1\text{e}1\text{e}...$ are weak.

There also exist key pairs (semi-weak keys) such that ($K, K’$) produces ($K_1, K_2, K_1,...$) and ($K_2, K_1, K_2,...$)

DES has complementarity property

Keys are so short that it's unsafe.

you can even pay for a service that breaks DES for you.

Small blocks, collisions every $2^{32}$.

Differential cryptoanalysis needs $2^{47}$ chosen plaintexts (the S-boxes chosen by NSA made it stronger so Differential cryptoanalysis isn’t so easy-peasy.)

Linear cryptoanalysis $2^{43}$ known plaintexts.

Put all together it’s broken.

Tries to save the day

2-DES won’t help because we can meet-in-the-middle

3-DES

sometimes with $K_1 = K_3$, in such case security level is $80$, in cases where all keys are different security level is $112$.

AES (Advanced Encryption Standard)

1997 NIST (successor of NBS) announces a competition. They get 15 proposals, it takes a few years to choose the best one.

criteria: security, speed, easiness of implementation

2001 Rijndael wins, renamed AES

128-bit blocks, key 128 (10 rounds), 192 (12) or 256 (14) bits

SPN with linear transformation

inner state and round key are both 4x4 matrices

Round

• bytesub, s-boxes work in $GF(2^8)$ field + affine transformation with rotations and xors
• shift row, shifts to the left
• mix column, not in the last round
• Add round key, xor with the key

Before the first round we add round key.

The following operations commute:

• add round key and inv mix Column (when $K_i$ is replaced with it’s mix)
• inv shift row and inv byt sub

Critique

• simple algebraic structure
• small margin of safety (small number of rounds). There are attacks on smaller number of rounds. Someday they might be extended.
• Collisions likely after $2^{64}$ blocks, recommended to change key every $2^{32}$ blocks.
• $128$-bit key is to weak against quantum computers.

Types of padding

• non-zero and then only zeros
• repeat the byte containing the size of padding
• add $p-1$ zeros and then $p$

Block Cipher Modes

ECB (Electronic Codebook)

Each block is encrypted independently of the other blocks.

If two blocks are identical then the corresponding cipher blocks are the same.

No IV, so it’s deterministic

It is possible to swap blocks, change one block without influencing other

So this is the worst block cipher mode which could be made. — Martin Mareš.

CBC (Cipher Block Chaining)

Uses IV.

XORs preceding block to the current.

Decryption can be parallelized and random access. But changes of blocks are not possible because you have to recalculate everything after the changed block.

The most frequently used mode.

Leak

After about $2^{keysize/2}$ there are two same blocks.

$$E_K (X_i \oplus Y_{i-1}) = E_k (X_j \oplus Y_{j-1})$$ $$X_i \oplus X_j = Y_{i-1} \oplus Y_{j-1}$$ this leaks blocksize bits of information on the plaintext.

CTR (Counter)

Turns block cipher into a stream cipher.

IVs need to be random (when using the same key).

Easily parallelized.

Leak

Every keystream is different which leaks some fraction of information over a long period of time.

OFB (Output FeedBack)

Uses IV and then the output of the preceding key stream is used to create key-stream for the next block.

Problem: we're following some cycle in a permutation, there’s a possibility we hit some short cycle.

Padding Oracle (on CBC)

The attacker is able to know if the message had a valid padding.

Assume the padding: repeat the byte containing the size of the padding

We will try all the possible values in the last byte of the padding. There is exactly one solution to obtain padding of size 1 in the block. With this, we can recover the size of the original padding. Now we need to recover the previous byte. We’ll be flipping the previous byte until we create in it p+1. Thus, we recovered it. We recover the whole block like this. Then we discard the block and repeat the process on the previous block.

This allows us to recover the block in $$256 \cdot \text{bytes in a block}$$

Some versions of TLS permit padding oracles.

Ciphertext Stealing