1 files changed, 382 insertions, 0 deletions

diff --git a/ss2017/cryptography/Notes08.txt b/ss2017/cryptography/Notes08.txt
new file mode 100644
index 0000000..fd5c54b
--- /dev/null
+++ b/ss2017/cryptography/Notes08.txt
@@ -0,0 +1,382 @@
+
+
+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.