From 162df3190c4e179ef968b0a467ddd4951faba336 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Tue, 24 Oct 2017 15:33:07 +0200 Subject: Notes on cryptography --- ss2017/cryptography/Notes07.txt | 204 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 204 insertions(+) create mode 100644 ss2017/cryptography/Notes07.txt (limited to 'ss2017/cryptography/Notes07.txt') 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 @@ +7 Practical block ciphers. Principles: s/p- and Feistel networks (5.1-5.2) +- - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - -- - - - + +We now describe how pseudorandom functions and block ciphers are +practically constructed. The constructions given do not ensure the +pseudorandom property, and in fact do not even fit into the asymptotic +paradigm since the blocklength is typically fixed. Their design is +guided by heuristic principles and the practical evidence that so far +no attacks have been found. As already mentioned, there are other, +less efficient constructions that merely require the existence of a +PRG, but again, the latter has not yet been shown to exist +unconditionally. + +In this section, a block cipher (of key length n and block length l) +thus is simply a function F:{0,1}^n x {0,1}^l -> {0,1}^l such that F_k +given by F_k(m)=F(k,m) is invertible (a permutation) for each k. + +Claude Shannon formulated two important principles guiding the design +of block ciphers: + +Confusion: statistical regularities in the plaintexts, e.g. letter +frequencies or frequencies of n-grams should not show up in the +ciphertext. + +Diffusion: changing one bit of the plaintext should (on average) +change a large proportion, e.g. one half of the bits in the +ciphertext. + +These principles are not rigorously defined and should be seen rather +as guidelines. The following procedure shows intuitively how they +could be observed. + +Let us say that the key comprises 16 byte-substitutions f_1, ... f_16 +: {0,1}^8->{0,1}^8, e.g. various shifts or other operations. So k = +(f_1,..,f_16). A first attempt at constructing a block cipher of +length 128 would be as follows: + +F_k(x) = f_1(x_1) ... f_16(x_16) + +where x is decomposed into 16 consecutive 8-bit blocks (bytes) x_1 +.. x_16. + + +This introduces confusion because each byte is subjected to a +different permutation. However, the cipher still has insufficient +diffusion since x1 only influences the first byte of the ciphertext +etc. This lack of diffusion implies in particular that with chosen +plaintexts we can learn parts of the value tables of individual key +substitutions. + +To remedy this, we subject the individual bits of the ciphertext to +some global, known permutation P:{1..128}->{1..128} of the positions +and repeat this entire procedure several times ("rounds"). After a few +rounds a large degree of diffusion will be reached ("avalanche +effect") provided that the permutation mixes across block boundaries +and that the substitutions in themselves already achieve a certain +degree of diffusion in the sense that each input bit influences +several output bits and vice versa. + +The substitutions and permutations used in each round need not always +be the same which then leads to the following general pattern. +Repeatedly break the text into equal size blocks, e.g. bytes which are +subjected to individual substitutions. Afterwards, the bits are +shuffled across the entire text using a permutation of the +positions. The key determines the substitutions and permutations being +used. Some of them may be independent of the key. + + +S/P-networks +- - - - - - - + +A substitution-permutation network (S/P-network) implements this idea +in principle, however, neither the substitutions f_i, nor the +permutations on positions depend on the key but are rather fixed +upfront. In this way, confusion and diffusion are maintained, but of +course key dependency needs to be introduced one way or another. This +happens by XOR-ing the intermediate results with parts of or a known +function of the key. The key itself is often called *master key* and +the portions of it used as XOR-masks in the different rounds are known +as *key schedule*. The substitution functions being used are commonly +known as *S-boxes*. The permutations on positions are called *mixing +permutations*. Thus, in an S/P-network the message is repeatedly +subjected to the following three steps: + +a) XOR-ing with keys derived from the master key through a key schedule +b) blockwise application of the S-boxes +c) global application of a mixing permutation + +There are a number of principles to be followed when designing an +S/P-network. + +1. The S-boxes used *should be invertible* for otherwise one would not +obtain an invertible cipher in the end. + +2. The S-boxes *should not be linear* functions in the sense of XOR +for then the entire cipher would be a linear function which opens it +up to a variety of attacks based on solving linear equations, see +below. In fact they should not even be close to linear functions in +the sense of Hamming distance. + +3. The S-boxes should implement the *avalanche effect*. Changing one +bit in the input changes at least two bits in the output no matter +what the other bits are set to. In addition, the mixing permutations +should spread the output bits of any given S-box, i.e. in one block to +different S-boxes, i.e. blocks in the next round. + +It is not hard to see that after a modest (polynomial in the message) +number of rounds these design principles ensure sufficient diffusion +because after each round the number of bits affected by a single bit +flip in the input roughly doubles. + + + +Attacks against badly designed S/P-networks +- - - - - - - - - - - - - -- - - - - - - - - + +Suppose we have an S/P-network with only one round. Given a plaintext +m and a ciphertext c we can then work out the key as follows. Undoing +the (known!) mixing permutation and the S-boxes yields c' := m+k from +which we retrieve k by adding m since m+k+m = k. + +Indeed, practical implementations of S/P-networks usually omit the +application of S-boxes and the mixing permutation in the last round +since it can be undone anyway as we just saw. (NB in the 2nd edition +of KL the S/P-networks are set up in this fashion from the beginning; +however the present approach looks more systematic) + +Suppose now that we have an S/P-network with two rounds. Suppose for +the sake of concreteness that the cipher uses 16 S-boxes operating on +4-bit each so that the total message length is 64. Suppose +furthermore, that the key k consists of 128 bits of which the first +half is used in the first round and the other half in the +second. Given m and c we, being the attacker, first undo the +S/P-operation of the second round as before. Now consider any 4-bit +block in the output. It depends on at most four 4-bit blocks from the +input because in the worst case each bit comes from a different +S-box. We also know from the mixing permutation in the first round +which these four 4-bit blocks are. Its 16 bits are transformed into +the 4 bits of the block we're looking at using a known function and 16 ++ 4 bits of the key. These can all be tried out in 2^20 =~= 10^6 time +which is altogether feasible. A similar argument applies to a three +round S/P-network, however the number of key bits influencing a four +bit block then goes up to 4+16+64 = 84 which is still a bit shorter +than 128, but cannot really be feasibly explored by brute force. + +However, even after three rounds the S/P-network can be efficiently +distinguished from a truly random permutation. Namely, each output bit +is then not influenced by 44 of the input bits. A distinguisher can +then toggle these bits and see whether the observed bit changes. If it +does not for, say 10^9 out of the 2^44 possible combinations then the +possibility that the distinguisher deals with a truly random function +is extremely small so it has an advantage. + +Once we use four or more rounds (and the mixing permutations as well +as the S-boxes) were well designed then the avalanche effect has fully +kicked in and attacks like the ones sketched are no longer possible. + +Let us also see why linear S-boxes cannot be recommended: if all +S-boxes f are linear functions in the sense that f(x+y)=f(x)+f(y) then +for each key k the function Enc_k() is linear too, i.e., we have +Enc_k(x+y)=Enc_k(x)+Enc_k(y). In this case, there exists for each key +an nxn matrix A_k with 0,1 entries (n the message length) such that + + Enc_k(m) = A_k m + +If we now have n^2 many pairs of plaintext-ciphertext we obtain n^2 +linear equations which we can solve for the entries of A_k. Once A_k +is known then even if we do not know k itself we can decrypt arbitrary +ciphertexts encrypted with the same key using the inverse matrix. This +kind of attack applies to all linear encryption functions regardless +whether they are S/P-networks. It also applies to affine linear +ciphers, where Enc_k(m) = A_k m + b_k. + + + +Feistel networks +- - - - - - - - + +Feistel networks are an alternative approach to designing practical +pseudorandom permutations. It also operates in rounds and each round a +key-dependent *mixing function* f_i() is applied to the second half of +the current text which is then XOR-ed with its first half to become +the new second half. The new first half is the old second half. Thus, +if L_i and R_i denote the first and second halves of the text after +round i then we have + + L_0 R_0 := "plaintext" + L_{i+1} := R_i + R_{i+1} := L_i + f_i(k_i,R_i) + +Here k_i is the round key used in the i-th round which is derived from +the master key through the key schedule as usual. + +Notice that, + + R_i = L_{i+1} + L_i = R_{i+1}+f_i(k_i,L_{i+1}) + +so that the Feistel network is invertible as desired no matter what +f_i() does. + +One can show (KL6.4) that if the mixing functions f_i are pseudorandom +functions then the function defined by a four round Feistel network is +a pseudorandom permutation. -- cgit v1.2.3