1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
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.
|
