CYG Chapter 5 Fast Block Ciphers

1. Devide 56 key bits into 28 bits each C₀ and D₀

2. Generate C_n,D_n via cyclic leftshift by s_n from C_n-1,D_n-1 with n = 1,…,16 and s_n := {If n \in {1,2,9,16} then 1; else 2}

3. Of each (C_n,D_n) select 48 bit

1. Get IP of input bits and divide plaintext into blocks of 64 bits

2. Split into two blocks of 32 bits

3. 16 rounds of SBB

4. Obtain inverse IP^-1

1. Expansion map E doubles 16 of 32 input bits and permutes resulting 48 bits

2. Proceed bitwise xor with round key K_i

3. Obtain P via transformation S

1. {0,1}⁴⁸ → {0,1}³²

2. Divide 48 bits into 8 blocks of 6 bits

3. r = 2*b_i1 + b_i6

4. s = Sum_j=2⁵ 2^5-j*b_ij

1. L_i = R_i-1, R_i = L_i-1 xor f(R_i-1,K_i)

2. R_i-1 = L_i, L_i-1 = R_i xor f(L_i,K_i)

Use encryption algorithm with keys in reverse

1. Look for 2⁵⁶ possible keys

2. Realized in 1999 with 100.000 workstations in 22h

1. Lower complexity of attack with differential cryptanalysis

2. Realized in 1992 at CRYPTO by Biham and Shamir

3. Attack is still complex due to S-Boxes // Did IBM knew about this?

DES can be broken with todays hardware in relatively short time

1. Perform DES three times with different keys

2. c = DES_K3(DES_K2^-1(DES_K1(m))) or DES_K1(DES_K2^-1(DES_K1(m)))

3. Ensure compatibility with DES via second step and K₁=K₂=K₃

K₀ has a length of 128, 192 or 256 bits

r := {10 for 128 bits; 12 for 192 bits; 14 for 256 bits}

Organize each roundkey into a 4x4 matrix of bytes

Generates r+1 round keys of 128 bits // Similar for other sizes

1. View K as a 4-tuple of 32 bit words W₀,…,W₃

2. Generate 4*(r+1) 32 bit words W₀,…,W_4r+3

3. Every 4 words form a roundkey

1. Start with i=4

2. If i%4==0 then W_i=W_i-4 xor (SubBytes(RotByte(W_i-1)) xor Rcon(i/4)) else W_i=W_i-4 xor W_i-1

Shift cyclically left by one byte

Rcon(i) = (RC(i),0x00,0x00,0x00)

RC(i) represents x^i-1 as element of F_2^8

In the field F_2^8=F₂[X]/(x⁸+x⁴+x³+x+1)F₂[X]

1. Divide plaintext into blocks of 128 bits

2. Organize each block into a 4x4 matrix of bytes, so-called state

3. Bytewise xor of each state with roundkey K₀ // AddRoundKey

4. r-1 rounds // SubBytes, ShiftRows, MixColumns and AddRoundKey

5. Perform last round without MixColumns

1. B → B

2. Each byte is viewed as b=b₇x⁷+…+b₀ of F_2^8

3. Write out the coefficients as y=y₇,…,y_{0 // Multiplicative inverse of b}

4. Compute r by affine map A*y +b // Use 256-entry lookup table

A has 5*1 in a row, starting with (1,0,0,0,1,1,1,1)

B:=(1;1;0;0;0;1;1;0)

1. B → C

2. Shift second row cyclically left by one byte

3. Shift third row cyclically left by two byte

4. Shift fourth row cyclically left by three byte

1. C → D

2. Each byte is viewed as c=c₇x⁷+…+c₀ of F_2^8

3. Compute D by multiplication A*C

4. Alternative, compute columns of D as four term polynomial

1. A has 6*0 +ab starting with (10, 11, 01, 01)

2. Can be computed efficiently with shift and xor

1. f=c₃u³+…+c₀

2. Multiply by fix polynomial a(u)=(x+1)u³+u²+u+x

3. Reduce modulo u⁴+1 afterwards

4. Can be rewritten as T*c

5. T has rows starting with (x, x+1, 1, 1)

Perform bitwise xor with roundkey K_i in i^th round

Use encryption algorithm with inverted transformations in reverse

1. Design criteria of AES are fully documented and discussed

2. Open discussion foreclosed suspicion of built-in trapdoors

1. If 1 byte is modified then 16 bytes are modified after 2 rounds

2. S-Boxes are non-linear to resist differential cryptanalysis

3. Simple algebraic design allows efficient implementations

4. ShiftRows avoids ‘truncated differential-’ and ‘square attack’

5. MixColumns causes diffusion among bytes

6. KeySchedula avoids advantages from knowing parts of the key

1. AES128, AES192 and AES256 are attacked by exhaustive key search

2. Faster attacks can be applied when reducing number of rounds

3. Attacks with complexity 2¹¹⁹ and 2^99.5 are known since 2009

NIST solicited 21 proposals for a replacement for DES till 6.1998