diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
commit | 162df3190c4e179ef968b0a467ddd4951faba336 (patch) | |
tree | 3c9628cf1abf259e1b897ac14b006e2b448cff27 /ss2017/cryptography/Notes07.txt | |
parent | 92ed41381f40c97b52b0e96f0eaeaa9025091411 (diff) | |
download | uni-162df3190c4e179ef968b0a467ddd4951faba336.tar uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.gz uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.bz2 uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.xz uni-162df3190c4e179ef968b0a467ddd4951faba336.zip |
Notes on cryptography
Diffstat (limited to 'ss2017/cryptography/Notes07.txt')
-rw-r--r-- | ss2017/cryptography/Notes07.txt | 204 |
1 files changed, 204 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes07.txt b/ss2017/cryptography/Notes07.txt new file mode 100644 index 0000000..6d60d56 --- /dev/null +++ b/ss2017/cryptography/Notes07.txt | |||
@@ -0,0 +1,204 @@ | |||
1 | 7 Practical block ciphers. Principles: s/p- and Feistel networks (5.1-5.2) | ||
2 | - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - -- - - - | ||
3 | |||
4 | We now describe how pseudorandom functions and block ciphers are | ||
5 | practically constructed. The constructions given do not ensure the | ||
6 | pseudorandom property, and in fact do not even fit into the asymptotic | ||
7 | paradigm since the blocklength is typically fixed. Their design is | ||
8 | guided by heuristic principles and the practical evidence that so far | ||
9 | no attacks have been found. As already mentioned, there are other, | ||
10 | less efficient constructions that merely require the existence of a | ||
11 | PRG, but again, the latter has not yet been shown to exist | ||
12 | unconditionally. | ||
13 | |||
14 | In this section, a block cipher (of key length n and block length l) | ||
15 | thus is simply a function F:{0,1}^n x {0,1}^l -> {0,1}^l such that F_k | ||
16 | given by F_k(m)=F(k,m) is invertible (a permutation) for each k. | ||
17 | |||
18 | Claude Shannon formulated two important principles guiding the design | ||
19 | of block ciphers: | ||
20 | |||
21 | Confusion: statistical regularities in the plaintexts, e.g. letter | ||
22 | frequencies or frequencies of n-grams should not show up in the | ||
23 | ciphertext. | ||
24 | |||
25 | Diffusion: changing one bit of the plaintext should (on average) | ||
26 | change a large proportion, e.g. one half of the bits in the | ||
27 | ciphertext. | ||
28 | |||
29 | These principles are not rigorously defined and should be seen rather | ||
30 | as guidelines. The following procedure shows intuitively how they | ||
31 | could be observed. | ||
32 | |||
33 | Let us say that the key comprises 16 byte-substitutions f_1, ... f_16 | ||
34 | : {0,1}^8->{0,1}^8, e.g. various shifts or other operations. So k = | ||
35 | (f_1,..,f_16). A first attempt at constructing a block cipher of | ||
36 | length 128 would be as follows: | ||
37 | |||
38 | F_k(x) = f_1(x_1) ... f_16(x_16) | ||
39 | |||
40 | where x is decomposed into 16 consecutive 8-bit blocks (bytes) x_1 | ||
41 | .. x_16. | ||
42 | |||
43 | |||
44 | This introduces confusion because each byte is subjected to a | ||
45 | different permutation. However, the cipher still has insufficient | ||
46 | diffusion since x1 only influences the first byte of the ciphertext | ||
47 | etc. This lack of diffusion implies in particular that with chosen | ||
48 | plaintexts we can learn parts of the value tables of individual key | ||
49 | substitutions. | ||
50 | |||
51 | To remedy this, we subject the individual bits of the ciphertext to | ||
52 | some global, known permutation P:{1..128}->{1..128} of the positions | ||
53 | and repeat this entire procedure several times ("rounds"). After a few | ||
54 | rounds a large degree of diffusion will be reached ("avalanche | ||
55 | effect") provided that the permutation mixes across block boundaries | ||
56 | and that the substitutions in themselves already achieve a certain | ||
57 | degree of diffusion in the sense that each input bit influences | ||
58 | several output bits and vice versa. | ||
59 | |||
60 | The substitutions and permutations used in each round need not always | ||
61 | be the same which then leads to the following general pattern. | ||
62 | Repeatedly break the text into equal size blocks, e.g. bytes which are | ||
63 | subjected to individual substitutions. Afterwards, the bits are | ||
64 | shuffled across the entire text using a permutation of the | ||
65 | positions. The key determines the substitutions and permutations being | ||
66 | used. Some of them may be independent of the key. | ||
67 | |||
68 | |||
69 | S/P-networks | ||
70 | - - - - - - - | ||
71 | |||
72 | A substitution-permutation network (S/P-network) implements this idea | ||
73 | in principle, however, neither the substitutions f_i, nor the | ||
74 | permutations on positions depend on the key but are rather fixed | ||
75 | upfront. In this way, confusion and diffusion are maintained, but of | ||
76 | course key dependency needs to be introduced one way or another. This | ||
77 | happens by XOR-ing the intermediate results with parts of or a known | ||
78 | function of the key. The key itself is often called *master key* and | ||
79 | the portions of it used as XOR-masks in the different rounds are known | ||
80 | as *key schedule*. The substitution functions being used are commonly | ||
81 | known as *S-boxes*. The permutations on positions are called *mixing | ||
82 | permutations*. Thus, in an S/P-network the message is repeatedly | ||
83 | subjected to the following three steps: | ||
84 | |||
85 | a) XOR-ing with keys derived from the master key through a key schedule | ||
86 | b) blockwise application of the S-boxes | ||
87 | c) global application of a mixing permutation | ||
88 | |||
89 | There are a number of principles to be followed when designing an | ||
90 | S/P-network. | ||
91 | |||
92 | 1. The S-boxes used *should be invertible* for otherwise one would not | ||
93 | obtain an invertible cipher in the end. | ||
94 | |||
95 | 2. The S-boxes *should not be linear* functions in the sense of XOR | ||
96 | for then the entire cipher would be a linear function which opens it | ||
97 | up to a variety of attacks based on solving linear equations, see | ||
98 | below. In fact they should not even be close to linear functions in | ||
99 | the sense of Hamming distance. | ||
100 | |||
101 | 3. The S-boxes should implement the *avalanche effect*. Changing one | ||
102 | bit in the input changes at least two bits in the output no matter | ||
103 | what the other bits are set to. In addition, the mixing permutations | ||
104 | should spread the output bits of any given S-box, i.e. in one block to | ||
105 | different S-boxes, i.e. blocks in the next round. | ||
106 | |||
107 | It is not hard to see that after a modest (polynomial in the message) | ||
108 | number of rounds these design principles ensure sufficient diffusion | ||
109 | because after each round the number of bits affected by a single bit | ||
110 | flip in the input roughly doubles. | ||
111 | |||
112 | |||
113 | |||
114 | Attacks against badly designed S/P-networks | ||
115 | - - - - - - - - - - - - - -- - - - - - - - - | ||
116 | |||
117 | Suppose we have an S/P-network with only one round. Given a plaintext | ||
118 | m and a ciphertext c we can then work out the key as follows. Undoing | ||
119 | the (known!) mixing permutation and the S-boxes yields c' := m+k from | ||
120 | which we retrieve k by adding m since m+k+m = k. | ||
121 | |||
122 | Indeed, practical implementations of S/P-networks usually omit the | ||
123 | application of S-boxes and the mixing permutation in the last round | ||
124 | since it can be undone anyway as we just saw. (NB in the 2nd edition | ||
125 | of KL the S/P-networks are set up in this fashion from the beginning; | ||
126 | however the present approach looks more systematic) | ||
127 | |||
128 | Suppose now that we have an S/P-network with two rounds. Suppose for | ||
129 | the sake of concreteness that the cipher uses 16 S-boxes operating on | ||
130 | 4-bit each so that the total message length is 64. Suppose | ||
131 | furthermore, that the key k consists of 128 bits of which the first | ||
132 | half is used in the first round and the other half in the | ||
133 | second. Given m and c we, being the attacker, first undo the | ||
134 | S/P-operation of the second round as before. Now consider any 4-bit | ||
135 | block in the output. It depends on at most four 4-bit blocks from the | ||
136 | input because in the worst case each bit comes from a different | ||
137 | S-box. We also know from the mixing permutation in the first round | ||
138 | which these four 4-bit blocks are. Its 16 bits are transformed into | ||
139 | the 4 bits of the block we're looking at using a known function and 16 | ||
140 | + 4 bits of the key. These can all be tried out in 2^20 =~= 10^6 time | ||
141 | which is altogether feasible. A similar argument applies to a three | ||
142 | round S/P-network, however the number of key bits influencing a four | ||
143 | bit block then goes up to 4+16+64 = 84 which is still a bit shorter | ||
144 | than 128, but cannot really be feasibly explored by brute force. | ||
145 | |||
146 | However, even after three rounds the S/P-network can be efficiently | ||
147 | distinguished from a truly random permutation. Namely, each output bit | ||
148 | is then not influenced by 44 of the input bits. A distinguisher can | ||
149 | then toggle these bits and see whether the observed bit changes. If it | ||
150 | does not for, say 10^9 out of the 2^44 possible combinations then the | ||
151 | possibility that the distinguisher deals with a truly random function | ||
152 | is extremely small so it has an advantage. | ||
153 | |||
154 | Once we use four or more rounds (and the mixing permutations as well | ||
155 | as the S-boxes) were well designed then the avalanche effect has fully | ||
156 | kicked in and attacks like the ones sketched are no longer possible. | ||
157 | |||
158 | Let us also see why linear S-boxes cannot be recommended: if all | ||
159 | S-boxes f are linear functions in the sense that f(x+y)=f(x)+f(y) then | ||
160 | for each key k the function Enc_k() is linear too, i.e., we have | ||
161 | Enc_k(x+y)=Enc_k(x)+Enc_k(y). In this case, there exists for each key | ||
162 | an nxn matrix A_k with 0,1 entries (n the message length) such that | ||
163 | |||
164 | Enc_k(m) = A_k m | ||
165 | |||
166 | If we now have n^2 many pairs of plaintext-ciphertext we obtain n^2 | ||
167 | linear equations which we can solve for the entries of A_k. Once A_k | ||
168 | is known then even if we do not know k itself we can decrypt arbitrary | ||
169 | ciphertexts encrypted with the same key using the inverse matrix. This | ||
170 | kind of attack applies to all linear encryption functions regardless | ||
171 | whether they are S/P-networks. It also applies to affine linear | ||
172 | ciphers, where Enc_k(m) = A_k m + b_k. | ||
173 | |||
174 | |||
175 | |||
176 | Feistel networks | ||
177 | - - - - - - - - | ||
178 | |||
179 | Feistel networks are an alternative approach to designing practical | ||
180 | pseudorandom permutations. It also operates in rounds and each round a | ||
181 | key-dependent *mixing function* f_i() is applied to the second half of | ||
182 | the current text which is then XOR-ed with its first half to become | ||
183 | the new second half. The new first half is the old second half. Thus, | ||
184 | if L_i and R_i denote the first and second halves of the text after | ||
185 | round i then we have | ||
186 | |||
187 | L_0 R_0 := "plaintext" | ||
188 | L_{i+1} := R_i | ||
189 | R_{i+1} := L_i + f_i(k_i,R_i) | ||
190 | |||
191 | Here k_i is the round key used in the i-th round which is derived from | ||
192 | the master key through the key schedule as usual. | ||
193 | |||
194 | Notice that, | ||
195 | |||
196 | R_i = L_{i+1} | ||
197 | L_i = R_{i+1}+f_i(k_i,L_{i+1}) | ||
198 | |||
199 | so that the Feistel network is invertible as desired no matter what | ||
200 | f_i() does. | ||
201 | |||
202 | One can show (KL6.4) that if the mixing functions f_i are pseudorandom | ||
203 | functions then the function defined by a four round Feistel network is | ||
204 | a pseudorandom permutation. | ||