diff options
Diffstat (limited to 'ss2017/cryptography/Notes08.txt')
-rw-r--r-- | ss2017/cryptography/Notes08.txt | 382 |
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 @@ | |||
1 | |||
2 | |||
3 | 8 DES (Data encryption standard) and AES (Advanced encryption standard) | ||
4 | ----------------------------------------------------------------------- | ||
5 | |||
6 | The Data Encryption Standard (DES) was published 1975 by the | ||
7 | US-administration after public consultation. It was designed and used | ||
8 | as a standard for non-military secrte communication e.g. between | ||
9 | government bodies but also in the private sector. It is a 16-round | ||
10 | Feistel network of message length 64 and key length 56. Mainly due to | ||
11 | its relatively short key length it is no longer considered secure. It | ||
12 | is nevertheless still widely used in legacy applications and in the form | ||
13 | of three-fold repetition (3DES) which is considered secure but | ||
14 | somewhat inefficient. | ||
15 | |||
16 | The Feistel mixing function of DES uses a round key k_i of length 48 | ||
17 | which is applied to a 32 bit long half block as follows: | ||
18 | |||
19 | 1) The 32 bit half block is expanded to 48 bit by repeating half of | ||
20 | its bits using an expansion function E() (see table below) | ||
21 | |||
22 | 2) The round key is XOR-ed with the resulting block | ||
23 | |||
24 | 3) The result is divided into eight 6-bit blocks to which S-boxes | ||
25 | S_1..S_8 are applied (see table below). Each S-box has 6 inputs and 4 | ||
26 | outputs, so a 32bit block results. | ||
27 | |||
28 | 4) a mixing permutation P is applied to the resulting 32bit. | ||
29 | |||
30 | The DES key schedule is as follows: initially the master key is | ||
31 | subjected to a mixing permutation on 56 bits. Thereafter, the round | ||
32 | key for the each round is applied by extracting (in a round-dependent | ||
33 | fashion) 48 bits from these 56 bits in such a way that the first 24 | ||
34 | bits stem from the first half of the (permuted) key and the second 24 | ||
35 | bits from the second half. See below for the exact form of the bit | ||
36 | extraction functions. | ||
37 | |||
38 | The DES encryption function is now obtained by enclosing the 16-round | ||
39 | Feistel network FN_k described above by an initial permutation IP and | ||
40 | its inverse listed below, thus Enc_k(x) = IP^{-1}(FN_k(IP(x))). | ||
41 | |||
42 | The initial permutation has no influence on security. It is there only | ||
43 | for historical reasons having to do with 8-bit hardware. | ||
44 | |||
45 | Each S-Box can be regarded as a package consisting of four | ||
46 | *invertible* operations on size 4 bitstrings. In conjunction with the | ||
47 | expansion function they operate as follows: The current size 32 | ||
48 | bitstring is divided into 8 blocks of size 4. To the ith such block | ||
49 | the ith S-box (eight in total) is applied in the following way: first | ||
50 | the two neighbouring bits (modulo 32) are taken, e.g. for the block | ||
51 | comprising bits 5,6,7,8 these neighbouring bits are 4 and 9. For the | ||
52 | first block comprising bits 1,2,3,4 the neighbouring bits are 32 and | ||
53 | 5. These two bits then are used to select the invertible substitution | ||
54 | to be applied to the block. This intuition is reflected in the | ||
55 | tabulation of the S-boxes below as binary functions of the central | ||
56 | size four block and the neighbouring two bits. Also, the expansion | ||
57 | function E() is designed to implement this idea, i.e. it duplicates | ||
58 | the "neighbouring bits. | ||
59 | " | ||
60 | |||
61 | |||
62 | DES supplementary material | ||
63 | - - - - - - - - - - - - - | ||
64 | |||
65 | Initial permutation: The first bit of IP(x) is the 58th bit of x; the | ||
66 | second bit of IP(x) is the 50th bit of x etc (read left to right and | ||
67 | top to bottom). | ||
68 | |||
69 | IP: | ||
70 | 58 50 42 34 26 18 10 2 | ||
71 | 60 52 44 36 28 20 12 4 | ||
72 | 62 54 46 38 30 22 14 6 | ||
73 | 64 56 48 40 32 24 16 8 | ||
74 | 57 49 41 33 25 17 9 1 | ||
75 | 59 51 43 35 27 19 11 3 | ||
76 | 61 53 45 37 29 21 13 5 | ||
77 | 63 55 47 39 31 23 15 7 | ||
78 | |||
79 | |||
80 | Expansion function: to be read left to right, top to bottom. First bit | ||
81 | of E(x) is the 32th, i.e. last, bit of x. | ||
82 | |||
83 | E: | ||
84 | 32 1 2 3 4 5 | ||
85 | 4 5 6 7 8 9 | ||
86 | 8 9 10 11 12 13 | ||
87 | 12 13 14 15 16 17 | ||
88 | 16 17 18 19 20 21 | ||
89 | 20 21 22 23 24 25 | ||
90 | 24 25 26 27 28 29 | ||
91 | 28 29 30 31 32 1 | ||
92 | |||
93 | |||
94 | Mixing permutation P: | ||
95 | |||
96 | 16 7 20 21 29 12 28 17 | ||
97 | 1 15 23 26 5 18 31 10 | ||
98 | 2 8 24 14 32 27 3 9 | ||
99 | 19 13 30 6 22 11 4 25 | ||
100 | |||
101 | The S-boxes given as binary functions: | ||
102 | |||
103 | S_1: to be applied to the first block | ||
104 | E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7 | ||
105 | 0 F 7 4 E 2 D 1 A 6 C B 9 5 3 8 | ||
106 | 4 1 E 8 D 6 2 B F C 9 7 3 A 5 0 | ||
107 | F C 8 2 4 9 1 7 5 B 3 E A 0 6 D | ||
108 | |||
109 | This is to be read as follows: upon receiving a 6bit block the S-box | ||
110 | uses the outer 2 bits to select the row and the inner four bits (read | ||
111 | in decimal). The decimal number found there represents the output. For | ||
112 | example, on input 011011 we select row #1 (0xxxx1) and the column #13 | ||
113 | (x1101x) (counting from 0 each time). There we find (hexa)decimal | ||
114 | number 5 representing output 0101. Similarly, on input 101000 we | ||
115 | select row #2, column #4, finding D=13, hence outputting 1101. | ||
116 | For the remaining S-boxes S_2,...,S_8 we refer to the Internet. | ||
117 | |||
118 | Initial mixing function selecting 56 out of 64 bits. The remaining 8 | ||
119 | bits serve as parity bits (each of the eight bytes comprising the key | ||
120 | must have even parity). Does not have any influence on security. | ||
121 | |||
122 | PC1: | ||
123 | |||
124 | 57 49 41 33 25 17 9 | ||
125 | 1 58 50 42 34 26 18 | ||
126 | 10 2 59 51 43 35 27 | ||
127 | 19 11 3 60 52 44 36 | ||
128 | |||
129 | 63 55 47 39 31 23 15 | ||
130 | 7 62 54 46 38 30 22 | ||
131 | 14 6 61 53 45 37 29 | ||
132 | 21 13 5 28 20 12 4 | ||
133 | |||
134 | |||
135 | The ith round key is obtained from the 56bit key by rotating both | ||
136 | halves i bits to the left and then selecting 48 bits with the | ||
137 | following function. | ||
138 | |||
139 | |||
140 | PC2: | ||
141 | |||
142 | 14 17 11 24 1 5 | ||
143 | 3 28 15 6 21 10 | ||
144 | 23 19 12 4 26 8 | ||
145 | 16 7 27 20 13 2 | ||
146 | 41 52 31 37 47 55 | ||
147 | 30 40 51 45 33 48 | ||
148 | 44 49 39 56 34 53 | ||
149 | 46 42 50 36 29 32 | ||
150 | |||
151 | |||
152 | |||
153 | |||
154 | Discussion of DES | ||
155 | - - - - - - - - - | ||
156 | |||
157 | The S-boxes have the important property that changing one bit of the | ||
158 | input always changes two bits of the output. For example, the first | ||
159 | row of S_4 maps 7=0111 to 10=1010. The 1bit alterations of 7 are | ||
160 | 15=1111, 3=0011, 5=0101, 6=0110. These are mapped to 15=1111, 3=0011, | ||
161 | 6=0110, 9=1001. All of these differ from 10=1010 in two bits. | ||
162 | |||
163 | Furthermore, the mixing permutation is such that any two bits from the | ||
164 | same 4 bit block end up in *different* 4 bit blocks where they will | ||
165 | cause more bit differences and so on thus ensuring the desired | ||
166 | avalanche effect. | ||
167 | |||
168 | Purportedly, the S-boxes have been designed so as to withstand a | ||
169 | particular attack called *differential cryptanalysis* which was known | ||
170 | to the developers but not published. Only 15 years later was this | ||
171 | discovered again and published by Biham and Shamir. | ||
172 | |||
173 | The text KL contains some more detail about attacks on variants of DES | ||
174 | with fewer rounds which exploit the fact that the avalanche effect has | ||
175 | not fully unfolded then. | ||
176 | |||
177 | With today's technology the 2^56 keyspace can be completely searched | ||
178 | with special hardware in several hours so that DES is no longer secure | ||
179 | for critical applications. There is a variant 3DES (Triple DES) which | ||
180 | uses three DES keys k1,k2,k3 (hence has key size 168) and encrypts according to the formula | ||
181 | |||
182 | Enc^3DES_{(k1,k2,k3)}(m) = Enc^DES_k3(Dec^DES_k2(Enc^DES_k1(m))) | ||
183 | |||
184 | Thus, to encrypt a message we encrypt it (using DES) with key k1 then | ||
185 | decrypt it with key k2 and then encrypt it with key k3. | ||
186 | |||
187 | The fact that we use decryption rather than encryption in the second | ||
188 | phase ensures that standard DES arises as the special case of three | ||
189 | identical keys: | ||
190 | |||
191 | Enc^3DES_{(k,k,k)}(m) = Enc^DES_k(m) | ||
192 | |||
193 | A version with just two phases does not provide the desired increased | ||
194 | security due to the possibility of a meet-in-the-middle attack: | ||
195 | suppose we (temprorarily) define 2DES by | ||
196 | |||
197 | Enc^2DES_{(k1,k2)}(m) = Enc^DES_k2(Enc^DES_k1(m)) | ||
198 | |||
199 | Then given a pair (m,c) where c=Enc^2DES_{(k1,k2)}(m) we can recover | ||
200 | k1 and k2 in time ~2^56 as follows: | ||
201 | |||
202 | Define x_k = Dec^DES_k(c) and y_q = Enc^DES_q(m) and tabulate x_k and | ||
203 | y_q for any DES keys k and q. This takes 2*2^56 DES operations (and | ||
204 | also requires this much space to store the tables). One can then sort | ||
205 | the tables and in this way quickly find k,q so that x_k=y_q. This pair | ||
206 | then is the desired 2DES key. | ||
207 | |||
208 | One can also use this attack against 3DES (splitting either after the | ||
209 | third or after the second phase) which reduces the effective key size | ||
210 | to 112. | ||
211 | |||
212 | It is not clear whether "meet-in-the-middle" is really practical | ||
213 | because, at least when implemented naively, the storage requirements | ||
214 | for the tables exceed current technology. | ||
215 | |||
216 | |||
217 | Advanced Encryption Standard (AES) | ||
218 | - - - - - - - - - - - - - - - - - - | ||
219 | |||
220 | The AES which was selected by the US administration (NIST) from | ||
221 | submissions to a public competition in 2000 is an S/P-network with | ||
222 | block size 128bit and key sizes of 128, 192, or 256 bit (AES-128, | ||
223 | AES-192, AES-256). AES-128 being the most popular variant we will only | ||
224 | describe this one here. The original name of the cipher prior to being | ||
225 | selected as the AES was "Rijndael" (Dutch for Rhine Valley) and chosen | ||
226 | by its Belgian authors Joan Daemen and Vincent Rijmen. | ||
227 | |||
228 | |||
229 | The substitution operation applies a fixed invertible function (the | ||
230 | AES S-box) on size-8 bitstrings (bytes) to each of the 16 bytes of the | ||
231 | text. | ||
232 | |||
233 | The subsequent mixing step is in the case of AES not just a bit | ||
234 | permutation but in fact an invertible linear transformation. | ||
235 | |||
236 | AES operates on the byte level and the text is arranged into a 4x4 | ||
237 | matrix whose entries are bytes (4x4x8=128). The bytes are mostly | ||
238 | understood as elements of the 256-element field GF(256). Thus, there | ||
239 | is also a multiplication operation b*b' on bytes which together with | ||
240 | the XOR-operation (bitwise addition mod2) endows the bytes with the | ||
241 | structure of a field. In particular, each byte b:{00,...,FF} (one | ||
242 | adopts hexadecimal notation) except 00 has an inverse b^{-1} such that | ||
243 | b^{-1} * b = 1. Caveat: this multiplication is not multiplication of | ||
244 | binary numbers mod 256. We describe below how it is defined in | ||
245 | detail. For now it suffices to know that together with addition (XOR) | ||
246 | it satisfies the usual algebraic laws (commutativity, associativity, | ||
247 | distributivity, inverse). | ||
248 | |||
249 | Now, each round comprises the following four steps: | ||
250 | |||
251 | 1. AddRoundKey(): Addition mod2 of the 128 bit round key derived from the | ||
252 | master key according to the key schedule. Can be viewed as the | ||
253 | addition of a "round key matrix". | ||
254 | |||
255 | 2. SubBytes(): Application of the S-Box to each of the 16 bytes of the | ||
256 | text. First, each of the 16 bytes comprising the current text matrix | ||
257 | is replaced with its inverse in GF(256). Exception: 00 for which there | ||
258 | is no inverse is left alone (not replaced). | ||
259 | |||
260 | Thereafter, each byte is transformed by the following affine map: | ||
261 | |||
262 | (b_7') (1 1 1 1 1 0 0 0) (b_7) (0) | ||
263 | (b_6') (0 1 1 1 1 1 0 0) (b_6) (1) | ||
264 | (b_5') (0 0 1 1 1 1 1 0) (b_5) (1) | ||
265 | (b_4') = (0 0 0 1 1 1 1 1) (b_4) + (0) | ||
266 | (b_3') (1 0 0 0 1 1 1 1) (b_3) (0) | ||
267 | (b_2') (1 1 0 0 0 1 1 1) (b_2) (0) | ||
268 | (b_1') (1 1 1 0 0 0 1 1) (b_1) (1) | ||
269 | (b_0') (1 1 1 1 0 0 0 1) (b_0) (1) | ||
270 | |||
271 | These matrix and vector operations are understood in GF(2), | ||
272 | ie. addition is (as usual) XOR of bits whereas multiplication is | ||
273 | logical AND. | ||
274 | |||
275 | The purpose of the inversion part is to introduce a high degree of | ||
276 | nonlinearity, i.e. to not even be close to a linear function. The | ||
277 | purpose of the affine transformation (which is linear) is to introduce | ||
278 | a certain amount of diffusion, i.e. that changes in one bit in the | ||
279 | input of the S-box result in >1 bit changes at the output. The affine | ||
280 | transformation also ensures that not the entire operation of AES can | ||
281 | be regarded in terms of GF(256) which could possibly result in | ||
282 | vulnerabilities based on algebraic properties. | ||
283 | |||
284 | Usually, the entire S-box is implemented as a 256 byte lookup table. | ||
285 | |||
286 | |||
287 | 3. ShiftRows(): The ith row is (cyclically) shifted i-1 columns to the | ||
288 | left (i=1,2,3,4): | ||
289 | |||
290 | (a b c d) (a b c d) | ||
291 | (A B C D) |-> (B C D A) | ||
292 | (u v w x) (w x u v) | ||
293 | (U V W X) (X U V W) | ||
294 | |||
295 | |||
296 | 4. MixColumns(): The 4x4 text matrix is multiplied (from the left) by | ||
297 | the (invertible) matrix | ||
298 | |||
299 | (02 03 01 01) | ||
300 | (01 02 03 01) | ||
301 | (01 01 02 03) | ||
302 | (03 01 01 02) | ||
303 | |||
304 | The entries of this matrix are understood as hexadecimal notation for | ||
305 | bytes, e.g.03 stands for the element 00000011 of GF(256). Thus, we | ||
306 | have 02+01=03 but 01+01=00 and 02+03=01. | ||
307 | |||
308 | In the last (16th) round, MixColumns() is replaced with another | ||
309 | AddRoundKey(). Notice that---as pointed out earlier---key-independent | ||
310 | steps at either the beginning or the end of the cipher could be easily | ||
311 | undone by an attacker and thus are worthless. | ||
312 | |||
313 | The AES key schedule thus must transform the 128bit master key into 17 | ||
314 | equally sized round keys. Let k be the 128bit master key. Just as the | ||
315 | texts we view it as a 4x4 matrix with entries from GF(256). We now | ||
316 | generate a sequence k_0,...,k_{16} of round keys (17 in number) as follows: | ||
317 | |||
318 | |||
319 | k_0 = k (01 01 01 01) | ||
320 | k_{i} = (k_{i-1} + (c'|0|0|0)) (00 01 01 01) | ||
321 | (00 00 01 01) | ||
322 | (00 00 00 01) | ||
323 | \______ ______/ | ||
324 | V | ||
325 | M | ||
326 | |||
327 | where the column c' is obtained from the last column c of k_{i-1} as follows: | ||
328 | |||
329 | (00 00 00 01) (02^i) | ||
330 | c' := (01 00 00 00) SubBytes(c) + ( 00 ) | ||
331 | (00 01 00 00) ( 00 ) | ||
332 | (00 00 01 00) ( 00 ) | ||
333 | \______ _____/ | ||
334 | V | ||
335 | R | ||
336 | |||
337 | Here SubBytes(c) denotes the result of the application of the AES | ||
338 | S-box to each byte in the column c. The byte 02^i is 02*02*...*02 (i | ||
339 | times) in GF(256). The matrix R cyclically rotates the column | ||
340 | downwards. To then obtain k_i we add c' to the first column of k_{i-1} | ||
341 | to obtain the first column of k_i. The next three columns are obtained | ||
342 | by adding the previous one (of k_i) to the corresponding one of | ||
343 | k_{i-1}. The matrix M does just that. | ||
344 | |||
345 | We see that the next round key is obtained from the previous one by | ||
346 | some simple linear operations and one nonlinear function of the last | ||
347 | column. | ||
348 | |||
349 | Decryption: We notice that all the functions used are invertible so | ||
350 | the decryption just performs these inverse operations in the opposite | ||
351 | order. We omit the details. | ||
352 | |||
353 | |||
354 | Arithmetic in GF(256) | ||
355 | - - - - - - - - - - - | ||
356 | |||
357 | In order to understand how multiplication in GF(256) works one | ||
358 | represents a byte b=b0..b7 as a polynomial with coefficients in | ||
359 | GF(2)={0,1} | ||
360 | |||
361 | b(X) = b7 * X^7 + b6 * X^6 + ... + b1 * X + b0 | ||
362 | |||
363 | In order to multiply two bytes one multiplies them qua polynomials and | ||
364 | then takes the remainder (using polynomial division) modulo the | ||
365 | polynomial | ||
366 | |||
367 | p(X) = X^8 + X^4 + X^3 + X + 1 | ||
368 | |||
369 | For example, 03 is X+1, so 03*03 = X^2+1 = 05 (the coefficients are | ||
370 | calculated modulo 2). The inverse of 03 is F6=11111010 because | ||
371 | |||
372 | (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 = | ||
373 | \___________ _________/ \_ _/ = X^8+X^4+X^3+X = 1 (mod p) | ||
374 | V V | ||
375 | F6 03 | ||
376 | |||
377 | One finds such inverses using the extended Euclidean algorithm or | ||
378 | using a table of logarithms. Indeed, each element of GF(256) \ {0} can | ||
379 | be written as a power of 03 (some other elements can be used in place | ||
380 | of 03). One may write log(x) for the number t:{0..254} such that x = | ||
381 | 03^t. One then has x^{-1} = 03^{255-t}. The logarithms can also be | ||
382 | used to reduce multiplication to addition mod 255. | ||