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/Notes06.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/Notes06.txt')
-rw-r--r-- | ss2017/cryptography/Notes06.txt | 216 |
1 files changed, 216 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes06.txt b/ss2017/cryptography/Notes06.txt new file mode 100644 index 0000000..a14e840 --- /dev/null +++ b/ss2017/cryptography/Notes06.txt | |||
@@ -0,0 +1,216 @@ | |||
1 | |||
2 | 6 Block ciphers, Modes of operation (KL3.6.3 KL3.6.4) | ||
3 | ----------------------------------------------------- | ||
4 | |||
5 | A pseudorandom function F() with the additional property that F_k is | ||
6 | invertible and the inverse F_k^{-1} is computable in polynomial time | ||
7 | is known as *block cipher* or *pseudorandom permutation*. It is not | ||
8 | hard to see that in this case, | ||
9 | |||
10 | Enc_k(m) = F_k(m) | ||
11 | Dec_k(c) = F_k^{-1}(c) | ||
12 | |||
13 | is semantically secure (hence the name "block cipher"). While a simple | ||
14 | PRG already suffices to build a semantically secure cryptosystem those | ||
15 | based on PRF as above enjoy stronger properties as we now explain. | ||
16 | |||
17 | With the help of a block cipher it is possible to design encryption | ||
18 | schemes for messages of arbitrary length using various *modes of | ||
19 | operation* that we now describe. In practice, the underlying block | ||
20 | ciphers (or pseudorandom functions) are heuristically designed | ||
21 | functions like DES or AES which we we will look at later. In some | ||
22 | modes of operation it suffices to have a pseudorandom function rather | ||
23 | than permutation. | ||
24 | |||
25 | In each mode of operation we divide the message to be encrypted into | ||
26 | blocks of size n, where n is the security parameter and hence the size | ||
27 | of the messages the pseudorandom function can work with. If the length | ||
28 | of the whole message is not a multiple of n we must *pad* the last | ||
29 | block in some way, e.g. by adding 1000...0. There are various padding | ||
30 | schemes which describe this in detail. We henceforth assume that | ||
31 | padding has already taken place and that the message comprises l | ||
32 | blocks m_1,...,m_l of length n each. | ||
33 | |||
34 | Remark: it is possible to vary l from message to message and in this | ||
35 | way to encrypt a *stream* of bits rather than a block. One thus | ||
36 | effectively obtains so-called *stream ciphers*. Such stream ciphers | ||
37 | are also constructed and studied in their own right, see | ||
38 | e.g. KL3.4. In this course, we do not consider stream ciphers. | ||
39 | |||
40 | |||
41 | ECB mode (electronic code book) | ||
42 | - - - - - - - - - - - - - - - - | ||
43 | |||
44 | This is the simplest mode of operation and it is actually not secure | ||
45 | at all, hence obsolete and included only for historical reasons. Let F | ||
46 | be a block cipher. | ||
47 | |||
48 | The encryption of the plaintext m = m1..ml under ECB-mode is given by | ||
49 | |||
50 | Enc_k(m) = F_k(m1) F_k(m2) ... F_k(ml) | ||
51 | |||
52 | i.e. the encodings F_k(mi) of the blocks mi are simply | ||
53 | concatenated. This mode receives its name from the fact that it | ||
54 | resembles a code book (which for each short message lists the | ||
55 | corresponding code) albeit in electronic form. | ||
56 | |||
57 | It is easy to see that ECB is not even secure against an | ||
58 | eavesdropper. If, assuming blocklength 3, we choose messages m=000000 | ||
59 | and m'=000111 we can tell them apart on the basis of the corresponding | ||
60 | ciphertexts c,c' alone because c has the form xyzxyz whereas c' does | ||
61 | not. This deficiency of ECB shows in practice when it is used to | ||
62 | encode images, see KL (2nd ed) for an example. | ||
63 | |||
64 | |||
65 | CBC mode (cipher block chaining) | ||
66 | - - - - - - - - - - - - - - - - - | ||
67 | |||
68 | Here we choose a random initialisation vector IV:{0,1}^n and encrypt as | ||
69 | |||
70 | Enc_k(m) = IV c1 c2 c3 ... cl | ||
71 | |||
72 | where c1=F_k(IV+m1), c2=F_k(c1+m2), c3=F_k(c2+m3), ... | ||
73 | |||
74 | I.e. each block is xor-ed with the encoding of the previous block | ||
75 | prior to sending it through F_k. | ||
76 | |||
77 | One can show that CBC-mode is CPA-secure, however it suffers from the | ||
78 | disadvantage that the ith ciphertext is needed to compute the i+1-st | ||
79 | one so the scheme cannot be parallelized. | ||
80 | |||
81 | The following variant of CBC-mode has been used in practice (SSL 3.0, TLS 1.0): | ||
82 | |||
83 | |||
84 | Chained CBC-mode (not CPA secure) | ||
85 | - - - - - - - - - - - - - - - - - | ||
86 | |||
87 | Rather than choosing a fresh initialisation vector each time it has | ||
88 | been proposed to use instead the last ciphertext, i.e., c_l as the new | ||
89 | initialisation vector. This reduces the size of the subsequent | ||
90 | message by one block and should intuitively be as good as CBC-mode | ||
91 | proper. However, this scheme is vulnerable to a CPA-attack as follows: | ||
92 | Suppose that the attacker knows that m_1 is one out of m_1^0 and m_1^1 | ||
93 | and that m = m_1 m_2 m_3 has already been encrypted as IV c_1 c_2 | ||
94 | c_3. The attacker could now request the encryption of another message | ||
95 | starting with the block | ||
96 | |||
97 | m_1' := IV + m_1^0 + c_3 | ||
98 | |||
99 | The first ciphertext block c_1' then satisfies | ||
100 | |||
101 | c_1' = F_k(c_3+m_1') = F_k(IV + m_1^0) | ||
102 | |||
103 | |||
104 | Noticing that c_1 = F_k(IV + m_1) we then have m_1 = m_1^0 iff c_1' = | ||
105 | c_1. | ||
106 | |||
107 | |||
108 | |||
109 | OFB mode (output feedback) | ||
110 | - - - - - - - - - - - - - - | ||
111 | |||
112 | Here we only need a pseudorandom function. From a randomly chosen | ||
113 | initialisation vector IV we first compute pseudorandom strings r1...rl | ||
114 | as follows: | ||
115 | |||
116 | r1 = F_k(IV), r2 = F_k(r1), ... | ||
117 | |||
118 | and then encrypt using xor: | ||
119 | |||
120 | Enc_k = IV m1+r1 m2+r2 m3+r3 ... ml+rl | ||
121 | |||
122 | So, in essence, we use F_k as a pseudorandom generator of expansion | ||
123 | l(n) = l*n and then apply the earlier construction of an EAV-secure | ||
124 | scheme from a PRG. Due to the additional randomization via the | ||
125 | initialisation vector OFB-mode is even CPA-secure. | ||
126 | |||
127 | |||
128 | CTR mode (counter) | ||
129 | - - - - - - - - - | ||
130 | |||
131 | This mode is similar to OFB, but we compute the pseudorandom string by | ||
132 | successively incrementing IV: | ||
133 | |||
134 | r_i = F_k(IV+i) /* this + is binary addition, not XOR */ | ||
135 | |||
136 | Enc_k = IV m1+r1 m2+r2 m3+r3 ... ml+rl | ||
137 | |||
138 | This has the advantage that the ri and hence the ciphertexts can be | ||
139 | computed in parallel. A further advantage that it shares with OFB is | ||
140 | that the pseudorandom string IVr1..rl can be computed ahead of time | ||
141 | and stored until the message to be encrypted arrives. Furthermore, | ||
142 | portions of the ciphertext can be decrypted without computing or | ||
143 | decrypting anything else. This property is known as *random access*. | ||
144 | |||
145 | |||
146 | Theorem: If F is a pseudorandom function then (randomised) counter | ||
147 | mode (as described above) is CPA-secure. | ||
148 | |||
149 | Proof: (Unlike KL we make the simplifying assumption that message | ||
150 | length l is always the same). Let A be an adversary as in the Priv^cpa | ||
151 | experiment. We transform it into a distinguisher D for the underlying | ||
152 | pseudorandom function as we did in the proof of the last Theorem. | ||
153 | |||
154 | Given security parameter n and oracle access to a function h (which is | ||
155 | instantiated as either F_k() or a truly random f()) the distinguisher | ||
156 | begins by passing the security parameter n to the adversary. | ||
157 | |||
158 | Now, whenever the adversary queries its own oracle which it assumes to | ||
159 | be of the form Enc_k() then the distinguisher chooses IV:{0,1}^n at | ||
160 | random, computes the sequence ri=h(IV+i) and submits IV m1+r1 | ||
161 | ... ml+rl to the adversary. | ||
162 | |||
163 | When the adversary enters the second phase and outputs two messages | ||
164 | m^0, m^1 to distinguish based on their descriptions the distinguisher | ||
165 | then chooses a random bit b:{0,1} and IV:{0,1}^n uniformly at random | ||
166 | and returns the encryption of m^b w.r.t. IV to A. Further oracle | ||
167 | queries from A are answered as before. | ||
168 | |||
169 | When A eventually outputs a bit b' reply 1 if b=b' and 0 otherwise. | ||
170 | |||
171 | Let us see what the adversary can do when h is a truly random | ||
172 | function. Again, the adversary has a certain advantage which we now | ||
173 | try to bound from above. | ||
174 | |||
175 | Let us assume that for any two encryptions requested the sequences of | ||
176 | the counter values do not overlap, i.e. the sets | ||
177 | {IV,IV+1,IV+2,...,IV+l} and {IV',IV'+1,IV'+2,...,IV'+l}, where IV and | ||
178 | IV' are the respective initialisation vecotrs chosen, are disjoint. In | ||
179 | this case, the ciphertexts follow a uniform random distribution and | ||
180 | the adversary cannot glean any information whatsoever, i.e. has | ||
181 | success probability 1/2. If they do overlap the adversary may or may | ||
182 | not use the extra information but if we can show that the probability | ||
183 | of this happening is negligible we are good. So, this is what we now | ||
184 | try to do. | ||
185 | |||
186 | Let us first consider that the overlap happens between the first and | ||
187 | second oracle question. In this case, once IV has been chosen, at most | ||
188 | 2l values for IV' are unfavorable (or favorable depending on | ||
189 | viewpoint): IV, IV-1 ... IV-l, IV+1, IV+2, ... IV+l. Thus, we have a | ||
190 | probability of 2l*2^n. Now, since such a clash can happen anywhere we | ||
191 | multiply this with q(n), the number of questions being asked. Thus, we | ||
192 | get an overall bound of q(n)*2l/2^n on the probability of an | ||
193 | overlap. Even if l is not constant, but polynomial in the security | ||
194 | parameter this is negligible (noting of course that in view of the | ||
195 | time bounds q(n) is polynomially bounded). As a result, the success | ||
196 | probability for the adversary can be bounded by 1/2+negl(n). | ||
197 | |||
198 | The rest of the argument is as before: If h is F_k(), then let p be | ||
199 | the success probability of the adversary A on our new cryptosystem. It | ||
200 | is clear that our distinguisher will output 1 with probability p for | ||
201 | we have used A according to the rules of the | ||
202 | PrivK^cpa-experiment. Since F was assumed to be a PRF we thus know that | ||
203 | |p-(1/2+negl(n))| is itself negligible. It then follows that p is | ||
204 | bounded by 1/2 plus a negligible function. Q.E.D. | ||
205 | |||
206 | |||
207 | We close by remarking that none of the schemes presented so far is | ||
208 | secure against chosen ciphertext attacks (CCA) where one may request | ||
209 | the decryption of arbitrary ciphertexts different from the | ||
210 | challenge. Consider, e.g. the encryption of m as r || F_k(r)+m. An | ||
211 | adversary can prepare messages m0=00..0 and m1=11..1. Upon receiving a | ||
212 | ciphertext c= r || s corresponding to one of these two the adversary can | ||
213 | flip the first bit of s and ask for the decryption of the resulting | ||
214 | ciphertext. This must be either 100..0 or 011..1 according to whether | ||
215 | m was 00..0 or 11..1. | ||
216 | |||