path: root/ss2017/cryptography/Notes08.txt

8 DES (Data encryption standard) and AES (Advanced encryption standard)
-----------------------------------------------------------------------

The Data Encryption Standard (DES) was published 1975 by the
US-administration after public consultation. It was designed and used
as a standard for non-military secrte communication e.g. between
government bodies but also in the private sector. It is a 16-round
Feistel network of message length 64 and key length 56. Mainly due to
its relatively short key length it is no longer considered secure.  It
is nevertheless still widely used in legacy applications and in the form
of three-fold repetition (3DES) which is considered secure but
somewhat inefficient.

The Feistel mixing function of DES uses a round key k_i of length 48
which is applied to a 32 bit long half block as follows:

1) The 32 bit half block is expanded to 48 bit by repeating half of
its bits using an expansion function E() (see table below) 

2) The round key is XOR-ed with the resulting block

3) The result is divided into eight 6-bit blocks to which S-boxes
S_1..S_8 are applied (see table below). Each S-box has 6 inputs and 4
outputs, so a 32bit block results.

4) a mixing permutation P is applied to the resulting 32bit. 

The DES key schedule is as follows: initially the master key is
subjected to a mixing permutation on 56 bits. Thereafter, the round
key for the each round is applied by extracting (in a round-dependent
fashion) 48 bits from these 56 bits in such a way that the first 24
bits stem from the first half of the (permuted) key and the second 24
bits from the second half. See below for the exact form of the bit
extraction functions.

The DES encryption function is now obtained by enclosing the 16-round
Feistel network FN_k described above by an initial permutation IP and
its inverse listed below, thus Enc_k(x) = IP^{-1}(FN_k(IP(x))).

The initial permutation has no influence on security. It is there only
for historical reasons having to do with 8-bit hardware.

Each S-Box can be regarded as a package consisting of four
*invertible* operations on size 4 bitstrings. In conjunction with the
expansion function they operate as follows: The current size 32
bitstring is divided into 8 blocks of size 4. To the ith such block
the ith S-box (eight in total) is applied in the following way: first
the two neighbouring bits (modulo 32) are taken, e.g. for the block
comprising bits 5,6,7,8 these neighbouring bits are 4 and 9. For the
first block comprising bits 1,2,3,4 the neighbouring bits are 32 and
5. These two bits then are used to select the invertible substitution
to be applied to the block. This intuition is reflected in the
tabulation of the S-boxes below as binary functions of the central
size four block and the neighbouring two bits. Also, the expansion
function E() is designed to implement this idea, i.e. it duplicates
the "neighbouring bits.
"


DES supplementary material
- - - - - - - - - - - - -

Initial permutation: The first bit of IP(x) is the 58th bit of x; the
second bit of IP(x) is the 50th bit of x etc (read left to right and
top to bottom). 

IP: 
58 	50 	42 	34 	26 	18 	10 	2
60 	52 	44 	36 	28 	20 	12 	4
62 	54 	46 	38 	30 	22 	14 	6
64 	56 	48 	40 	32 	24 	16 	8
57 	49 	41 	33 	25 	17 	9 	1
59 	51 	43 	35 	27 	19 	11 	3
61 	53 	45 	37 	29 	21 	13 	5
63 	55 	47 	39 	31 	23 	15 	7


Expansion function: to be read left to right, top to bottom. First bit
of E(x) is the 32th, i.e. last, bit of x. 

E:
32 	1 	2 	3 	4 	5
4 	5 	6 	7 	8 	9
8 	9 	10 	11 	12 	13
12 	13 	14 	15 	16 	17
16 	17 	18 	19 	20 	21
20 	21 	22 	23 	24 	25
24 	25 	26 	27 	28 	29
28 	29 	30 	31 	32 	1


Mixing permutation P:

16  7 20 21 29 12 28 17
 1 15 23 26  5 18 31 10
 2  8 24 14 32 27  3  9
19 13 30  6 22 11  4 25

The S-boxes given as binary functions:

S_1: to be applied to the first block
E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7
0 F 7 4 E 2 D 1 A 6 C B 9 5 3 8
4 1 E 8 D 6 2 B F C 9 7 3 A 5 0
F C 8 2 4 9 1 7 5 B 3 E A 0 6 D

This is to be read as follows: upon receiving a 6bit block the S-box
uses the outer 2 bits to select the row and the inner four bits (read
in decimal). The decimal number found there represents the output. For
example, on input 011011 we select row #1 (0xxxx1) and the column #13
(x1101x) (counting from 0 each time). There we find (hexa)decimal
number 5 representing output 0101. Similarly, on input 101000 we
select row #2, column #4, finding D=13, hence outputting 1101.
For the remaining S-boxes S_2,...,S_8 we refer to the Internet. 

Initial mixing function selecting 56 out of 64 bits. The remaining 8
bits serve as parity bits (each of the eight bytes comprising the key
must have even parity). Does not have any influence on security. 

PC1:

57 	49 	41 	33 	25 	17 	9
1 	58 	50 	42 	34 	26 	18
10 	2 	59 	51 	43 	35 	27
19 	11 	3 	60 	52 	44 	36

63 	55 	47 	39 	31 	23 	15
7 	62 	54 	46 	38 	30 	22
14 	6 	61 	53 	45 	37 	29
21 	13 	5 	28 	20 	12 	4


The ith round key is obtained from the 56bit key by rotating both
halves i bits to the left and then selecting 48 bits with the
following function.


PC2:

14 	17 	11 	24 	1 	5
3 	28 	15 	6 	21 	10
23 	19 	12 	4 	26 	8
16 	7 	27 	20 	13 	2
41 	52 	31 	37 	47 	55
30 	40 	51 	45 	33 	48
44 	49 	39 	56 	34 	53
46 	42 	50 	36 	29 	32




Discussion of DES
- - - - - - - - -

The S-boxes have the important property that changing one bit of the
input always changes two bits of the output. For example, the first
row of S_4 maps 7=0111 to 10=1010. The 1bit alterations of 7 are
15=1111, 3=0011, 5=0101, 6=0110. These are mapped to 15=1111, 3=0011,
6=0110, 9=1001. All of these differ from 10=1010 in two bits.

Furthermore, the mixing permutation is such that any two bits from the
same 4 bit block end up in *different* 4 bit blocks where they will
cause more bit differences and so on thus ensuring the desired
avalanche effect.

Purportedly, the S-boxes have been designed so as to withstand a
particular attack called *differential cryptanalysis* which was known
to the developers but not published. Only 15 years later was this
discovered again and published by Biham and Shamir. 

The text KL contains some more detail about attacks on variants of DES
with fewer rounds which exploit the fact that the avalanche effect has
not fully unfolded then.

With today's technology the 2^56 keyspace can be completely searched
with special hardware in several hours so that DES is no longer secure
for critical applications. There is a variant 3DES (Triple DES) which
uses three DES keys k1,k2,k3 (hence has key size 168) and encrypts according to the formula

  Enc^3DES_{(k1,k2,k3)}(m) = Enc^DES_k3(Dec^DES_k2(Enc^DES_k1(m)))

Thus, to encrypt a message we encrypt it (using DES) with key k1 then
decrypt it with key k2 and then encrypt it with key k3.

The fact that we use decryption rather than encryption in the second
phase ensures that standard DES arises as the special case of three
identical keys:

              Enc^3DES_{(k,k,k)}(m) = Enc^DES_k(m)

A version with just two phases does not provide the desired increased
security due to the possibility of a meet-in-the-middle attack:
suppose we (temprorarily) define 2DES by

  Enc^2DES_{(k1,k2)}(m) = Enc^DES_k2(Enc^DES_k1(m))

Then given a pair (m,c) where c=Enc^2DES_{(k1,k2)}(m) we can recover
k1 and k2 in time ~2^56 as follows:

Define x_k = Dec^DES_k(c) and y_q = Enc^DES_q(m) and tabulate x_k and
y_q for any DES keys k and q. This takes 2*2^56 DES operations (and
also requires this much space to store the tables). One can then sort
the tables and in this way quickly find k,q so that x_k=y_q. This pair
then is the desired 2DES key.

One can also use this attack against 3DES (splitting either after the
third or after the second phase) which reduces the effective key size
to 112.

It is not clear whether "meet-in-the-middle" is really practical
because, at least when implemented naively, the storage requirements
for the tables exceed current technology.


Advanced Encryption Standard (AES)
- - - - - - - - - - - - - - - - - - 

The AES which was selected by the US administration (NIST) from
submissions to a public competition in 2000 is an S/P-network with
block size 128bit and key sizes of 128, 192, or 256 bit (AES-128,
AES-192, AES-256). AES-128 being the most popular variant we will only
describe this one here. The original name of the cipher prior to being
selected as the AES was "Rijndael" (Dutch for Rhine Valley) and chosen
by its Belgian authors Joan Daemen and Vincent Rijmen.


The substitution operation applies a fixed invertible function (the
AES S-box) on size-8 bitstrings (bytes) to each of the 16 bytes of the
text.

The subsequent mixing step is in the case of AES not just a bit
permutation but in fact an invertible linear transformation.

AES operates on the byte level and the text is arranged into a 4x4
matrix whose entries are bytes (4x4x8=128). The bytes are mostly
understood as elements of the 256-element field GF(256). Thus, there
is also a multiplication operation b*b' on bytes which together with
the XOR-operation (bitwise addition mod2) endows the bytes with the
structure of a field. In particular, each byte b:{00,...,FF} (one
adopts hexadecimal notation) except 00 has an inverse b^{-1} such that
b^{-1} * b = 1. Caveat: this multiplication is not multiplication of
binary numbers mod 256. We describe below how it is defined in
detail. For now it suffices to know that together with addition (XOR)
it satisfies the usual algebraic laws (commutativity, associativity,
distributivity, inverse).

Now, each round comprises the following four steps: 

1. AddRoundKey(): Addition mod2 of the 128 bit round key derived from the
master key according to the key schedule. Can be viewed as the
addition of a "round key matrix". 

2. SubBytes(): Application of the S-Box to each of the 16 bytes of the
text. First, each of the 16 bytes comprising the current text matrix
is replaced with its inverse in GF(256). Exception: 00 for which there
is no inverse is left alone (not replaced).

Thereafter, each byte is transformed by the following affine map:
       
(b_7')        (1 1 1 1 1 0 0 0) (b_7)     (0)
(b_6')        (0 1 1 1 1 1 0 0) (b_6)     (1)
(b_5')        (0 0 1 1 1 1 1 0) (b_5)     (1)
(b_4')    =   (0 0 0 1 1 1 1 1) (b_4)  +  (0)
(b_3')        (1 0 0 0 1 1 1 1) (b_3)     (0)
(b_2')        (1 1 0 0 0 1 1 1) (b_2)     (0)
(b_1')        (1 1 1 0 0 0 1 1) (b_1)     (1)
(b_0')        (1 1 1 1 0 0 0 1) (b_0)     (1)

These matrix and vector operations are understood in GF(2),
ie. addition is (as usual) XOR of bits whereas multiplication is
logical AND.

The purpose of the inversion part is to introduce a high degree of
nonlinearity, i.e. to not even be close to a linear function. The
purpose of the affine transformation (which is linear) is to introduce
a certain amount of diffusion, i.e. that changes in one bit in the
input of the S-box result in >1 bit changes at the output. The affine
transformation also ensures that not the entire operation of AES can
be regarded in terms of GF(256) which could possibly result in
vulnerabilities based on algebraic properties.

Usually, the entire S-box is implemented as a 256 byte lookup table.


3. ShiftRows(): The ith row is (cyclically) shifted i-1 columns to the
left (i=1,2,3,4):

(a b c d)      (a b c d)
(A B C D)  |-> (B C D A)
(u v w x)      (w x u v)
(U V W X)      (X U V W)


4. MixColumns(): The 4x4 text matrix is multiplied (from the left) by
the (invertible) matrix

(02 03 01 01)
(01 02 03 01)
(01 01 02 03)
(03 01 01 02)

The entries of this matrix are understood as hexadecimal notation for
bytes, e.g.03 stands for the element 00000011 of GF(256). Thus, we
have 02+01=03 but 01+01=00 and 02+03=01.

In the last (16th) round, MixColumns() is replaced with another
AddRoundKey().  Notice that---as pointed out earlier---key-independent
steps at either the beginning or the end of the cipher could be easily
undone by an attacker and thus are worthless.

The AES key schedule thus must transform the 128bit master key into 17
equally sized round keys. Let k be the 128bit master key. Just as the
texts we view it as a 4x4 matrix with entries from GF(256). We now
generate a sequence k_0,...,k_{16} of round keys (17 in number) as follows:


k_0 = k                        (01 01 01 01)
k_{i} = (k_{i-1} + (c'|0|0|0)) (00 01 01 01)
                               (00 00 01 01)  
		               (00 00 00 01)
                              \______ ______/
	                             V
	                             M

where the column c' is obtained from the last column c of k_{i-1} as follows:

       (00 00 00 01)               (02^i)
c' :=  (01 00 00 00) SubBytes(c) + ( 00 )
       (00 01 00 00)               ( 00 )
       (00 00 01 00)               ( 00 )
      \______ _____/
             V
	     R
	     
Here SubBytes(c) denotes the result of the application of the AES
S-box to each byte in the column c. The byte 02^i is 02*02*...*02 (i
times) in GF(256). The matrix R cyclically rotates the column
downwards. To then obtain k_i we add c' to the first column of k_{i-1}
to obtain the first column of k_i. The next three columns are obtained
by adding the previous one (of k_i) to the corresponding one of
k_{i-1}. The matrix M does just that.

We see that the next round key is obtained from the previous one by
some simple linear operations and one nonlinear function of the last
column.

Decryption: We notice that all the functions used are invertible so
the decryption just performs these inverse operations in the opposite
order. We omit the details.


Arithmetic in GF(256)
- - - - - - - - - - -

In order to understand how multiplication in GF(256) works one
represents a byte b=b0..b7 as a polynomial with coefficients in
GF(2)={0,1}

b(X) = b7 * X^7 + b6 * X^6 + ... + b1 * X + b0

In order to multiply two bytes one multiplies them qua polynomials and
then takes the remainder (using polynomial division) modulo the
polynomial

p(X) = X^8 + X^4 + X^3 + X + 1

For example, 03 is X+1, so 03*03 = X^2+1 = 05 (the coefficients are
calculated modulo 2).  The inverse of 03 is F6=11111010 because

(X^7+X^6+X^5+X^4+X^2+X)*(X+1) = X^8+X^7+X^6+X^5+X^3+X^2+X^7+X^6+X^5+X^4+X^2+X =
\___________ _________/ \_ _/ = X^8+X^4+X^3+X = 1 (mod p) 
            V             V
	   F6            03

One finds such inverses using the extended Euclidean algorithm or
using a table of logarithms. Indeed, each element of GF(256) \ {0} can
be written as a power of 03 (some other elements can be used in place
of 03). One may write log(x) for the number t:{0..254} such that x =
03^t. One then has x^{-1} = 03^{255-t}. The logarithms can also be
used to reduce multiplication to addition mod 255.