Notes on cryptography

1 files changed, 318 insertions, 0 deletions

diff --git a/ss2017/cryptography/Notes16.txt b/ss2017/cryptography/Notes16.txt
new file mode 100644
index 0000000..f75607d
--- /dev/null
+++ b/ss2017/cryptography/Notes16.txt
@@ -0,0 +1,318 @@
+16 Chosen ciphertext and random oracles
+- - - - - - - - - - - - - - - - - - - -
+
+Many public key schemes including the ones using the RSA assumption
+presented earlier make use of an unkeyed hash function to scramble
+ciphertext and thus to enhance security, thus in particular preventing
+chosen-ciphertext attacks. In this chapter, we will formulate these
+attacks, remedies against them, and a semi-rigorous method for proving
+there relative security.
+
+
+Chosen ciphertext attacks
+- - - - - - - - - - - - -
+
+Chosen ciphertext attacks (CCA) model scenarios where the attacker can
+request the decryption of ciphertexts of its choice. This is relevant
+in a number of practical scenarios, where cryptosystems are used as
+building blocks in larger protocols. Here a "man in the middle" can
+intercept message and assume the role of one of the participants. The
+messages it fabricates will then---at least up to a point---be
+decrypted by the honest parties.
+
+None of the schemes presented to far is secure against CCA. Consider
+for example a symmetric key encryption given by Enc_k(m) =
+(r,F_k(r)+m) where r is a random nonce and F_k() is a PRF.
+
+Consider an attacker who wishes to distinguishes encryptions of m0 =
+000...0 and m1 = 1111..1 as in the PrivK^eav experiment. If the
+attacker is given (r,c) being the encryption of either m0 or m1 all it
+has to do is to request the decryption of the chosen ciphertext (r,c')
+where c' is c with the first bit flipped. Clearly, this will be
+1000..000 or 0111...111 according to whether m0 or m1 has been
+encrypted and hence the attacker wins.
+
+The situation is similar in the public key setting. Suppose for
+instance that (c1,c2) is an ElGamal encryption of some message
+m. Then, as we know, c1=g^y and c2=h^y*m where y is random but private
+and h=g^x is public. Now, for any m' we have that (c1,c2*m') is a
+valid encryption of m*m'. It is clear that this allows an adversary to
+win the PubK^eav experiment: Given (c1,c2), the adversary can request
+the decryption of (c1,c2*g). The adversary thus obtains m*g and can compute
+m by multiplication with g^(-1). A similar argument can be made for
+various cryptosytems based on RSA.
+
+The property of the cryptosystems making that form of attack possible
+is known as *malleability*. From a given ciphertext it is possible to
+produce another one that corresponds to a known transformation of the
+plaintext.
+
+We now define security against chosen ciphertext attacks formally in
+the public key setting. The corresponding definition for private keys
+is analogous.
+
+Let A be a ppt adversary and Pi be a public key cryptosystem. The experiment
+PubK^cca_{A,Pi}(n) is defined as follows.
+
+1. (pk,sk)<-Gen(n)
+2. A is given n, the public key pk, and access to a decryption oracle Dec_sk()
+/* in the private key setting A also gets access to an encryption oracle like in CPA security */
+   A outputs two messages m0,m1
+3. b<-{0,1}
+4. c<-Enc_pk(m_b) is given to A
+5. A continues to have access to the decryption oracle but may, of course, not
+   request the decryption of c itself. Any other ciphertext is allowed.
+6. A outputs a bit b' and the outcome is 1 if b=b', 0 otherwise.
+
+The cryptosystem is deemed CCA-secure if the success probability in
+this experiment is 1/2+negl(n).
+
+
+CCA secure private key cryptography using MACs
+- - - - - - - - - - - - - - - - - - - - - - - -
+
+In the private key case such CCA-secure schemes can be constructed by
+combining a CPA-secure system PiE with a secure MAC PiM as follows:
+
+A key pair (k1,k2) is generated, k1 for PiE and k2 for the MAC PiM.
+
+The encryption of m under (k1,k2) is given by (c,t) where
+c<-Enc_{k1}(m) and t<-Mac_{k2}(c).  Thus, we authenticate the
+ciphertext so as to prevent any modification.
+
+To decrypt (c,t) we first check that Mac_{k2}(c)=t and only then
+return Dec_{k1}(c). If Mac_{k2}(c) is different from t we return a
+default value _|_.
+
+One can now show that---assuming PiE and PiM are themselves
+secure---this scheme achieves CCA security. The proof idea is that
+assuming PiM is secure the probability that the adversary makes a
+query which is answered with a value different from _|_ is
+negligible. We can therefore assume that all queries are answered with
+_|_ and in this case the experiment degrades to a PrivK^cpa experiment
+against which PiE is assumed secure. For details see KL4.8.
+
+
+CCA-secure public key cryptography using hash functions
+- - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+Building CCA-secure public key systems is more difficult and typically
+uses hybrid encryption with a CCA-secure private key system and,
+additionally, a "cryptographic hash function" H(). Here we show one such
+system using RSA, which at the same time gives an example of a
+security proof based on the RSA assumption.
+
+Assume thus that Pi0=(Enc0,Dec0) is a CCA-secure private key
+cryptosystem which uses uniformly distributed keys from {0,1}^n (so
+there is no "Gen0"). Assume further that H:{0,1}^n->{0,1}^n is a
+"cryptographic hash function". We will later discuss what this should
+mean formally in this context. We will need stronger properties than
+just the collision-resistance that we have required of hash functions
+before.
+
+Finally, assume that GenRSA() is an RSA key generator for which the
+RSA hardness assumption holds.
+
+We then construct a public key cryptosystem Pi=(Gen,Enc,Dec) as follows.
+
+
+Gen(n):
+  (N,d,e)<- GenRSA(n)
+  pk = (N,e), sk=(N,d)
+  return (pk,sk)
+
+Enc_{(N,e)}(m):
+   1. r <- {0,1}^n
+   2. k = H(r)
+   3. return (r^e mod N, Enc0_k(m))
+
+Dec_{(N,d)}(c1,c2):
+   1. r = c1^d mod N
+   2. k = H(r)
+   3. return Dec0_k(c2)
+
+Why should this scheme be CCA secure? Intuitively, given the RSA-assumption,
+the attacker has no way of recovering r, hence the likelihood
+that it applies (the publicly known function) H() to r is negligible
+and as a result all H()-values it sees would look random to it. Thus,
+the key used in the private key encryption of the actual message is as
+good as random so that the security assumption on Pi2 applies and the
+entire scheme is secure.
+
+We need the function H to make the key k look random. It may be tempting
+to just try to use r as the encryption key. But the RSA-assumption gives
+us only that the attacker cannot recover r fully. It does not rule out
+that the attacker obtains a few bits of r. If we used r as key, then
+it would not be fully random and the security assumption on Pi2 could
+not be used.
+
+
+The random oracle model
+- - - - - - - - - - - -
+
+The question is under what assumptions on H() the above argument can
+be made rigorous. Assuming H() to be a PRF does not work because those
+always require a secret key. Once you know the key there is nothing
+random about a PRF. Taking a PRG also does not work, as its output
+looks random only if the input is random as well.
+Assuming that H() is merely a secure hash function does not suffice
+either because nothing prevents a good hash function from, for example,
+producing hash strings which contain predictable portions.
+E.g. if H0() is a secure hash function so is H(x) = 0.....0 H0(x).
+
+Unfortunately, there have not been found any plausible assumptions on
+the function H() under which schemes like the above could be proved
+secure. A possible way out is the random oracle model which we now describe.
+
+In this model, one instantiates H() with a function that is randomly
+chosen at the beginning of each experiment, i.e., the probabilities
+are taken over uniform random choices of H() which is therefore called
+*random oracle*. All participants in the experiment get access to H.
+It would be possible to actually implement this by using a trusted
+party, e.g. an internet server which must called for any evaluation of
+H().  It can either precompute the entire value table of H() (finite
+for a given security parameter) using random choices or alternatively,
+fill this table on demand, i.e. regurgitate H-values on previously
+requested arguments and make random choices for new requests.
+
+In practice, however, this approach is unfeasible, and so the random
+oracle, for which schemes like the above one *can be proved secure*,
+is replaced with a cryptographic hash function such as SHA-2. Whether
+or not the security proof in the random oracle model has any bearing
+on this instantiation remains open.
+
+In fact, it has been shown that there exist contrived cryptographic
+schemes which are secure in the random oracle model but insecure with
+any concrete instantiation. Nevertheless, a proof in the random oracle
+model consists strong evidence as to the security of a scheme and
+perhaps even more importantly, failure to prove a system secure in the
+random oracle model might point out actual flaws of a scheme. KL
+contains a longer discussion of the metamathematical or epistemic
+implications of the random oracle model without however being able to
+get over the central issue that a proof in the random oracle model
+does not imply anything---in the rigorous mathematical sense---about
+the "standard model" which is used in actual practice.
+
+
+
+Secure hash functions and pseudorandom functions in the random oracle model
+- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+As a warmup let us see how random oracles can be used to construct
+secure hash functions and pseudo random functions.
+
+We fix a length function l(n), e.g. l(n)=n or l(n)=n/2 and let H :
+{0,1}^n->{0,1}^{l(n)} be a random function.
+
+We now show that H() itself is a secure hash function. Consider a ppt
+adversary A who gets oracle access to H() and conduct the Hash-coll
+experiment from Chapter 11 with random H():
+
+1. Choose H() at random
+2. Adversary A gets oracle access to H() and outputs values x,x':{0,1}^n
+   such that x != x'.
+3. The outcome of the experiment is 1 iff H(x)=H(x')
+
+Theorem:
+
+The success probability of this experiment, taken over uniform random
+choice of H and the random choices that A might make is a negligible
+function of the security parameter.
+
+Proof. Let x1...xk be the sequence of values that A queries of H prior to
+outputting x,x'. Clearly, k is polynomial in the security parameter n
+due to the polynomial time bound on the computation time of A. The
+probability that H(xi)=H(xj) for some i!=j is therefore
+negligible. Notice that we can assume that H-values are selected "on
+demand". Thus, when x,x' are among the x1..xk the success probability
+is negligible. If, however, A chooses at least one of them afresh
+then, again, the success probability is negligible because only a
+negligible portion of the possible H-values is favourable. QED
+
+Notice that, in a way, the earlier account of hash functions in
+Chapter 11 was also based on some kind of random oracle in that we
+assumed a uniformly random selection of the seed which also does not
+happen in practice.
+
+
+A pseudorandom function from a random oracle
+- - - - - - - - - - - - - - - - - - - - - - -
+
+The random oracle can be used to obtain a PRF as follows:
+
+Theorem: Let l(n)=n/2 and define F_k(x) = H(k || x). Notice that for
+k,x:{0,1}^n we have F_k(x):{0,1}^n. Now, F_k() is a PRF in the
+following sense. Let D be a ppt distinguisher with oracle access to a
+function g():{0,1}^n->{0,1}^n *and* the random function H(). We write
+this as D^{g(),H()}(n). We then have
+
+| Pr[ D^{F_k(),H()}(n)=1 ] - Pr[ D^{f(),H()}(n)=1 ] | = negl(n)
+
+with probabilities taken over a random function f(), the key k and the
+random function H() appearing in F_k().
+
+Proof: As before, we can condition on the queries made to H() by D
+during its computation. So long as these are disjoint from those made
+as part of evaluations of F_k() we are in the situation of the
+previous theorem. But then the probability for such a coincidence is
+negligible by the randomization over k. The details are left as an
+exercise.  QED
+
+It is now also possible to show that the abovedescribed hybrid
+encryption system is CCA secure; however, for simplicity, we only show
+its CPA security which is already nontrivial. Also, we have not
+seen any provably secure RSA-based cryptosystem so far.
+
+Theorem: Let Pi0 be a CPA-secure private key system and let
+Pi be the hybrid system as described above. Then for any ppt adversary, which
+is given additional access to the random oracle H(), one has
+
+Pr[ PubK^eav_{Pi,A^{H()}}(n) = 1 ] = 1/2 + negl(n)
+
+with probabilities taken over random choice of H(), the random steps
+taken within A, and those in the PubK^eav experiment.
+
+Proof sketch: For convenience we recall the steps of the experiment.
+
+1. H() is chosen at random.
+2. (N,e,d) <- GenRSA(n); pk=(N,e); sk=(N,d)
+3. A is given access to pk and H()
+4. A outputs messages m0, m1.
+5. r<-{0,1}^n; k=H(r)
+6. b<-{0,1}
+7. c1<-r^e mod N
+8. c2<-Enc0_k(m_b)
+9. A is given (c1,c2) and returns b'
+10. Outcome is 1 iff b=b'
+
+The encryption and decryption algorithms that A is given oracle access
+to essentially follow lines 5-9 and are not repeated here.
+
+Let us call QUERY the event that A queries H() on one of the random
+nonces r used either in line 5 or as part of its queries to the
+encryption oracle.
+
+The idea is that since---assuming as we do---GenRSA satisfies the RSA
+hardness assumption, the probability of QUERY is negligible.
+This is because we can use A to construct an adversary in the RSA-inv
+experiment as follows. We use A as a subroutine and run it according
+to protocol. We monitor all queries of A to H() and for each one of
+those, call it r_q, check whether r_q^e mod N is correct. If this is
+the case, then we output r_q. By the RSA hardness assumption, this
+adversary can output the correct r only with negligible probability,
+which means that the probability of QUERY must be negligible.
+
+Once we know that QUERY is a negligible event we can assume without
+loss of generality that it does not occur, i.e., oracle access to H()
+returns random values that are completely unrelated to the experiment.
+We can thus assume that A does not get access to H() at all and then
+the CPA-secure scheme Pi0 is secure by assumption.
+
+We refer to KL Theorem 13.1 for details and to KL Theorem 13.5 for a
+proof that the hybrid scheme even yields CCA security assuming Pi0 is
+CCA secure.
+
+We also remark that the deterministic version of RSA used to encrypt
+the symmetric key can be replaced by an arbitrary so-called key
+encapsulation mechanism (KEM), without essentially changing the
+proof. See KL, 2nd ed for details.