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/Notes06.txt | 216 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 216 insertions(+) create mode 100644 ss2017/cryptography/Notes06.txt (limited to 'ss2017/cryptography/Notes06.txt') 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 @@ + +6 Block ciphers, Modes of operation (KL3.6.3 KL3.6.4) +----------------------------------------------------- + +A pseudorandom function F() with the additional property that F_k is +invertible and the inverse F_k^{-1} is computable in polynomial time +is known as *block cipher* or *pseudorandom permutation*. It is not +hard to see that in this case, + +Enc_k(m) = F_k(m) +Dec_k(c) = F_k^{-1}(c) + +is semantically secure (hence the name "block cipher"). While a simple +PRG already suffices to build a semantically secure cryptosystem those +based on PRF as above enjoy stronger properties as we now explain. + +With the help of a block cipher it is possible to design encryption +schemes for messages of arbitrary length using various *modes of +operation* that we now describe. In practice, the underlying block +ciphers (or pseudorandom functions) are heuristically designed +functions like DES or AES which we we will look at later. In some +modes of operation it suffices to have a pseudorandom function rather +than permutation. + +In each mode of operation we divide the message to be encrypted into +blocks of size n, where n is the security parameter and hence the size +of the messages the pseudorandom function can work with. If the length +of the whole message is not a multiple of n we must *pad* the last +block in some way, e.g. by adding 1000...0. There are various padding +schemes which describe this in detail. We henceforth assume that +padding has already taken place and that the message comprises l +blocks m_1,...,m_l of length n each. + +Remark: it is possible to vary l from message to message and in this +way to encrypt a *stream* of bits rather than a block. One thus +effectively obtains so-called *stream ciphers*. Such stream ciphers +are also constructed and studied in their own right, see +e.g. KL3.4. In this course, we do not consider stream ciphers. + + +ECB mode (electronic code book) +- - - - - - - - - - - - - - - - + +This is the simplest mode of operation and it is actually not secure +at all, hence obsolete and included only for historical reasons. Let F +be a block cipher. + +The encryption of the plaintext m = m1..ml under ECB-mode is given by + + Enc_k(m) = F_k(m1) F_k(m2) ... F_k(ml) + +i.e. the encodings F_k(mi) of the blocks mi are simply +concatenated. This mode receives its name from the fact that it +resembles a code book (which for each short message lists the +corresponding code) albeit in electronic form. + +It is easy to see that ECB is not even secure against an +eavesdropper. If, assuming blocklength 3, we choose messages m=000000 +and m'=000111 we can tell them apart on the basis of the corresponding +ciphertexts c,c' alone because c has the form xyzxyz whereas c' does +not. This deficiency of ECB shows in practice when it is used to +encode images, see KL (2nd ed) for an example. + + +CBC mode (cipher block chaining) +- - - - - - - - - - - - - - - - - + +Here we choose a random initialisation vector IV:{0,1}^n and encrypt as + +Enc_k(m) = IV c1 c2 c3 ... cl + +where c1=F_k(IV+m1), c2=F_k(c1+m2), c3=F_k(c2+m3), ... + +I.e. each block is xor-ed with the encoding of the previous block +prior to sending it through F_k. + +One can show that CBC-mode is CPA-secure, however it suffers from the +disadvantage that the ith ciphertext is needed to compute the i+1-st +one so the scheme cannot be parallelized. + +The following variant of CBC-mode has been used in practice (SSL 3.0, TLS 1.0): + + +Chained CBC-mode (not CPA secure) +- - - - - - - - - - - - - - - - - + +Rather than choosing a fresh initialisation vector each time it has +been proposed to use instead the last ciphertext, i.e., c_l as the new +initialisation vector. This reduces the size of the subsequent +message by one block and should intuitively be as good as CBC-mode +proper. However, this scheme is vulnerable to a CPA-attack as follows: +Suppose that the attacker knows that m_1 is one out of m_1^0 and m_1^1 +and that m = m_1 m_2 m_3 has already been encrypted as IV c_1 c_2 +c_3. The attacker could now request the encryption of another message +starting with the block + + m_1' := IV + m_1^0 + c_3 + +The first ciphertext block c_1' then satisfies + + c_1' = F_k(c_3+m_1') = F_k(IV + m_1^0) + + +Noticing that c_1 = F_k(IV + m_1) we then have m_1 = m_1^0 iff c_1' = +c_1. + + + +OFB mode (output feedback) +- - - - - - - - - - - - - - + +Here we only need a pseudorandom function. From a randomly chosen +initialisation vector IV we first compute pseudorandom strings r1...rl +as follows: + +r1 = F_k(IV), r2 = F_k(r1), ... + +and then encrypt using xor: + +Enc_k = IV m1+r1 m2+r2 m3+r3 ... ml+rl + +So, in essence, we use F_k as a pseudorandom generator of expansion +l(n) = l*n and then apply the earlier construction of an EAV-secure +scheme from a PRG. Due to the additional randomization via the +initialisation vector OFB-mode is even CPA-secure. + + +CTR mode (counter) +- - - - - - - - - + +This mode is similar to OFB, but we compute the pseudorandom string by +successively incrementing IV: + +r_i = F_k(IV+i) /* this + is binary addition, not XOR */ + +Enc_k = IV m1+r1 m2+r2 m3+r3 ... ml+rl + +This has the advantage that the ri and hence the ciphertexts can be +computed in parallel. A further advantage that it shares with OFB is +that the pseudorandom string IVr1..rl can be computed ahead of time +and stored until the message to be encrypted arrives. Furthermore, +portions of the ciphertext can be decrypted without computing or +decrypting anything else. This property is known as *random access*. + + +Theorem: If F is a pseudorandom function then (randomised) counter +mode (as described above) is CPA-secure. + +Proof: (Unlike KL we make the simplifying assumption that message +length l is always the same). Let A be an adversary as in the Priv^cpa +experiment. We transform it into a distinguisher D for the underlying +pseudorandom function as we did in the proof of the last Theorem. + +Given security parameter n and oracle access to a function h (which is +instantiated as either F_k() or a truly random f()) the distinguisher +begins by passing the security parameter n to the adversary. + +Now, whenever the adversary queries its own oracle which it assumes to +be of the form Enc_k() then the distinguisher chooses IV:{0,1}^n at +random, computes the sequence ri=h(IV+i) and submits IV m1+r1 +... ml+rl to the adversary. + +When the adversary enters the second phase and outputs two messages +m^0, m^1 to distinguish based on their descriptions the distinguisher +then chooses a random bit b:{0,1} and IV:{0,1}^n uniformly at random +and returns the encryption of m^b w.r.t. IV to A. Further oracle +queries from A are answered as before. + +When A eventually outputs a bit b' reply 1 if b=b' and 0 otherwise. + +Let us see what the adversary can do when h is a truly random +function. Again, the adversary has a certain advantage which we now +try to bound from above. + +Let us assume that for any two encryptions requested the sequences of +the counter values do not overlap, i.e. the sets +{IV,IV+1,IV+2,...,IV+l} and {IV',IV'+1,IV'+2,...,IV'+l}, where IV and +IV' are the respective initialisation vecotrs chosen, are disjoint. In +this case, the ciphertexts follow a uniform random distribution and +the adversary cannot glean any information whatsoever, i.e. has +success probability 1/2. If they do overlap the adversary may or may +not use the extra information but if we can show that the probability +of this happening is negligible we are good. So, this is what we now +try to do. + +Let us first consider that the overlap happens between the first and +second oracle question. In this case, once IV has been chosen, at most +2l values for IV' are unfavorable (or favorable depending on +viewpoint): IV, IV-1 ... IV-l, IV+1, IV+2, ... IV+l. Thus, we have a +probability of 2l*2^n. Now, since such a clash can happen anywhere we +multiply this with q(n), the number of questions being asked. Thus, we +get an overall bound of q(n)*2l/2^n on the probability of an +overlap. Even if l is not constant, but polynomial in the security +parameter this is negligible (noting of course that in view of the +time bounds q(n) is polynomially bounded). As a result, the success +probability for the adversary can be bounded by 1/2+negl(n). + +The rest of the argument is as before: If h is F_k(), then let p be +the success probability of the adversary A on our new cryptosystem. It +is clear that our distinguisher will output 1 with probability p for +we have used A according to the rules of the +PrivK^cpa-experiment. Since F was assumed to be a PRF we thus know that +|p-(1/2+negl(n))| is itself negligible. It then follows that p is +bounded by 1/2 plus a negligible function. Q.E.D. + + +We close by remarking that none of the schemes presented so far is +secure against chosen ciphertext attacks (CCA) where one may request +the decryption of arbitrary ciphertexts different from the +challenge. Consider, e.g. the encryption of m as r || F_k(r)+m. An +adversary can prepare messages m0=00..0 and m1=11..1. Upon receiving a +ciphertext c= r || s corresponding to one of these two the adversary can +flip the first bit of s and ask for the decryption of the resulting +ciphertext. This must be either 100..0 or 011..1 according to whether +m was 00..0 or 11..1. + -- cgit v1.2.3