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/Notes05.txt | 217 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 217 insertions(+) create mode 100644 ss2017/cryptography/Notes05.txt (limited to 'ss2017/cryptography/Notes05.txt') diff --git a/ss2017/cryptography/Notes05.txt b/ss2017/cryptography/Notes05.txt new file mode 100644 index 0000000..beca359 --- /dev/null +++ b/ss2017/cryptography/Notes05.txt @@ -0,0 +1,217 @@ +5 Security against chosen plaintext attacks (KL3.5) +--------------------------------------------------- + +We now consider security of cryptosystems against stronger adversaries +which may request the encryption of arbitrary plaintexts of their +choice. There are some practical scenarios where this might occur, +e.g. a smartcard which can be interacted with arbitrarily or by +preparing some situation whose description will then be transmitted by +the opposite party in encrpyted form. + + +Given a scheme Pi=(Gen,Enc,Dec) and an adversary A the experiment +PrivK^cpa_{A,Pi}(n) is now defined as follows: + + + 1. Key k is generated by Gen(n) + 2. The adversary A is given the security parameter n and the procedure + Enc_k as a black box (oracle access). After some interaction with + the oracle it then outputs two messages m0 and m1 from {0,1}^{l(n)} + (or of the same length in the case of variable length schemes). + 3. A bit b <- {0,1} is chosen uniformly at random (50/50). The + (or rather a) ciphertext c = Enc_k(m_b) is given to A. + 4. A continues to have oracle access to Enc_k and then answers by + outputting a bit b'. + 4. The output of the experiment is defined 1 if b=b' and 0 otherwise. + + +Definition: A scheme Pi=(Gen,Enc,Dec) has *indistinguishable +encryptions under a chosen plaintext attack* (is cpa-secure for short) +if there is a negligible function negl(n) such that for all (pr.-polytime) +adversaries A + + Pr[PrivK^cpa_{A,Pi}(n) = 1] <= 1/2 + negl(n) + +There is also a "known plaintext version" where the adversary does not +get full-blown oracle access to Enc_k but can merely request +encryptions of a previously submitted list of plaintexts. The details +of this are left to the reader. + +We first notice that no deterministic scheme can possibly be +cpa-secure. Given c simply compute (using the oracle) c_0=Enc_k(m_0) +and c_1=Enc_k(m_1) and return b' such that c_b'=c. Thus, any cpa-secure +scheme must include a random element into the encryption. But naive +ways of doing so will not be successful either. Suppose for example +that Pi=(Gen,Enc,Dec,l) is a deterministic scheme, i.e. Enc_k( ) is a +function. Design a new scheme Pi' as follows: + +For bitstrings u,v we let u || v stand for the concatenation of u and +v. If w is a bitstring of even length 2n then we let w.1 and w.2 stand +for its first and second halves. + +Gen' = Gen +l'(n) = l(n)/2 /* w.l.o.g. l(n) is even */ +Enc'_k(m) = Enc_k(r || m) where r is a random bitstring + of length l(n)/2. +Dec'_k(c) = Dec_k(c).1 + +Clearly, Pi' has indistinguishable encryptions in the presence of an +eavesdropper if Pi has, but Pi' does not in general withstand chosen +plaintext attacks. Namely, consider that Enc_k(m)=G(k)+m as above. We +then have Enc'_k(m) = G(k).1 + r || G(k).2 + m. As a result, the +adversary can take the first half of the received ciphertext c, +request encryptions c_0 nd c_1 of m_0 and m_1 and determine b' so that +c.1 = (c_b').1 . + +In order to achieve the desired security we need a *pseudorandom function* + +Definition: A pseudorandom function (PRF) is a binary function on bitstrings + + F : {0,1}^* x {0,1}^* -> {0,1}^* + +with application F(k,x) written F_k(x) such that + + 1) |k|=|x| implies |F_k(x)|=|k|=|x| (and F need not be defined on + arguments of different length) + + 2) F is deterministic, polynomial-time computable + + 3) For all probabilistic polynomial-time distinguishers D and all n + one has + + | Pr[ D^{F_k()}(n)=1 ] - Pr[D^{f()}(n)=1] | = negl(n) + + for some negligible function negl() and probabilities taken over + k and f(), see below. + +The distinguisher has access to an oracle, i.e. a subroutine of type +{0,1}^n->{0,1}^n. In the experiment, first k:{0,1}^n is drawn +uniformly at random and then a function f from {0,1}^n->{0,1}^n is +drawn uniformly at random (from the 2^{n*2^n} many possibilities). The +oracle is then instantiated with F_k() on the one hand and +with f on the other. The probabilities for the distinguisher to output +1 in either case should differ only negligibly. + +So, where a pseudorandom generator expands a size n key k to a size +l(n) bitstring that looks random a pseudorandom function expands a +size n key to a function F_k which could be written as a size n*2^n +bitstring. Again, this "very large" object should look +random. However, only a polynomial portion of it can be examined by +the distinguisher. On the other hand, which portion that is is up to +the distinguisher to decide and not priori fixed. + +We remark that one often uses variants of PRF where the size of +argument x and results are functions of a security parameter other +than the identity function. (The security parameter must then be +supplied explicitly to F) + +Relationship between PRF and PRG: + +It is not hard to see that every PRF can serve as a PRG. Given k +simply output the string F(k,0) || F(k,1) || F(k,2) || ... || F(k,N) for +sufficiently large N and where e.g. 2 stands for the encoding of 2 as +a length n bitstring. If a distinguisher could tell this from a random +string one could easily use it to distinguish F_k from a random +function. Surprisingly, the converse also holds, see (KL6.5). However, +we still do not know whether PRG exist. In practice, PRF are +constructed using heuristic approaches. + + +A CPA-secure cryptosystem from a PRF (KL3.6.2) +- - - - - - - - - - - - - - - - - - - - - - - - + +Here is, how we use a PRF to construct a CPA-secure cryptosystem. Note +that by our earlier observation the scheme itself must be randomised. + + +Gen(n): return a random bitstring of length n as key. +Enc_k(m): choose r:{0,1}^n uniformly at random and output the ciphertext + c := r || F_k(r)+m +Dec_k(c): given c extract c.1=r and c.2=F_k(r)+m then return c.2+F_k(r) + +Notice that Dec_k(Enc_k(m)) = F(k,r)+F(k,r)+m = m + +Remark: A random element like r added to a piece of data is known as a +*nonce*. + +Theorem: If F is a PRF then the above construction yields a fixed +length (l(n)=n) CPA-secure cryptosystem. + +Proof: Let Pi stand for the scheme constructed above from F and +l(n). Assume further, that A is an adversary against Pi. We construct +from A a distinguisher D for the PRF F as follows: + +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 A. + +Now, whenever the adversary queries its own oracle which it assumes to +be of the form Enc_k() then the distinguisher chooses r:{0,1}^n at +random and returns r || h(r)+m to A. + +When the adversary enters the second phase and outputs two messages +m_0, m_1 to distinguish based on their encryptions the distinguisher +then chooses a random bit b:{0,1} and r:{0,1}^n uniformly at random +and returns r || h(r)+m_b 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. Unlike in the "eavesdropper" case, A has a certain +advantage: namely suppose it has already requested encryptions c_0 and +c_1 of the messages m_0 and m_1 it then forwards (and it would be +"wise" for A to do so). If it now happens by accident that +c.1=c_0.1=c_1.1, i.e. the three random nonces used were all equal, +then since the rest is deterministic, the adversary can pick b' such +that c.2=c_{b'}.2 and be correct. Since, however, the adversary can +only make polynomially many queries the likelihood for this to happen +is negligible. If, however, the random nonce used in the preparation +of c is different from all the ones used in oracle queries then c +looks completely random to A and its success probability is exactly +1/2. Summing up, if h is truly random then A's success probability is +1/2+negl(n). + +If, on the other hand, 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. + + +Notice that this proof newly introduces negligible probabilities +rather than (or in addition to) just move them around and thus gives +further evidence as to why allowing negligible deviations from the +ideal situation is reasonable. + +We also remark that the way the system was presented the length of the +key equals that of the message. However, in the case of a CPA-secure +system we can encrypt several messages with the same key without +compromising security. We generalise this idea in the next chapter. + +Proposition: Let Pi=(Gen,Enc,Dec) be cpa-secure and define +Pi'=(Gen,Enc',Dec') by Enc'_k(m1 || m2) = Enc_k(m1) || Enc_k(m2). Then +Pi' is cpa-secure. Here m1, m2, as well as, c1,c2 are assumed to be of +equal length. + +Proof: From a hypothetical cpa-adversary A' against Pi' we construct a +cpa-adversary A against the original system Pi as follows: + +A runs A' and answers any oracle requests according to Pi'. E.g. if A' +asks for an encryption of m1||m2 it requests encryptions c1 and c2 of +m1, m2, respectively and then provides the answer c1||c2. + +When A' outputs the challenge m1^0||m2^0 vs m1^1||m2^1 A submits the +challenge m2^0 vs m2^1 and receives a ciphertext c2 (which should be an +encryption of m2^0 or m2^1). A then requests an encryption c1 of m1^0 and +passes c1||c2 to A'. + +The answer bit b' supplied by A' is then output. + +Let p be the success probability of A'. + +If the secret bit b is equal to 0 then the +success probability of A is p as well. + + -- cgit v1.2.3