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/Notes01.txt | 108 +++++++++++ ss2017/cryptography/Notes02.txt | 214 ++++++++++++++++++++++ ss2017/cryptography/Notes03.txt | 100 ++++++++++ ss2017/cryptography/Notes04.txt | 78 ++++++++ ss2017/cryptography/Notes05.txt | 217 ++++++++++++++++++++++ ss2017/cryptography/Notes06.txt | 216 ++++++++++++++++++++++ ss2017/cryptography/Notes06a.txt | 105 +++++++++++ ss2017/cryptography/Notes07.txt | 204 +++++++++++++++++++++ ss2017/cryptography/Notes08.txt | 382 +++++++++++++++++++++++++++++++++++++++ ss2017/cryptography/Notes09.txt | 259 ++++++++++++++++++++++++++ ss2017/cryptography/Notes10.txt | 257 ++++++++++++++++++++++++++ ss2017/cryptography/Notes11.txt | 310 +++++++++++++++++++++++++++++++ ss2017/cryptography/Notes12.txt | 274 ++++++++++++++++++++++++++++ ss2017/cryptography/Notes13.txt | 162 +++++++++++++++++ ss2017/cryptography/Notes14.txt | 208 +++++++++++++++++++++ ss2017/cryptography/Notes15.txt | 279 ++++++++++++++++++++++++++++ ss2017/cryptography/Notes16.txt | 318 ++++++++++++++++++++++++++++++++ ss2017/cryptography/Notes17.txt | 194 ++++++++++++++++++++ 18 files changed, 3885 insertions(+) create mode 100644 ss2017/cryptography/Notes01.txt create mode 100644 ss2017/cryptography/Notes02.txt create mode 100644 ss2017/cryptography/Notes03.txt create mode 100644 ss2017/cryptography/Notes04.txt create mode 100644 ss2017/cryptography/Notes05.txt create mode 100644 ss2017/cryptography/Notes06.txt create mode 100644 ss2017/cryptography/Notes06a.txt create mode 100644 ss2017/cryptography/Notes07.txt create mode 100644 ss2017/cryptography/Notes08.txt create mode 100644 ss2017/cryptography/Notes09.txt create mode 100644 ss2017/cryptography/Notes10.txt create mode 100644 ss2017/cryptography/Notes11.txt create mode 100644 ss2017/cryptography/Notes12.txt create mode 100644 ss2017/cryptography/Notes13.txt create mode 100644 ss2017/cryptography/Notes14.txt create mode 100644 ss2017/cryptography/Notes15.txt create mode 100644 ss2017/cryptography/Notes16.txt create mode 100644 ss2017/cryptography/Notes17.txt diff --git a/ss2017/cryptography/Notes01.txt b/ss2017/cryptography/Notes01.txt new file mode 100644 index 0000000..75c4cc6 --- /dev/null +++ b/ss2017/cryptography/Notes01.txt @@ -0,0 +1,108 @@ +Throughout the notes the acronym KL stands for the book "Introduction +to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, Chapman & +Hall, 2008. + +Set braces {} may be used to enclose a subscript consisting of more +than one letter. E.g x_{10} is "x sub ten". Sometimes we omit the +underscore vor subscripting and write x1 or xi for x_1 and x_i. + + +1 Overview, Historic Ciphers: Caesar, Vigenere, (KL1.3) +--------------------------------------------------------- + + +The Shift Cipher +- - - - - - - - - + +Identify the 26 upper case alphabet letters with numbers 0..25, +e.g. A=0, B=1. Choose an integer k:{0..25} as "key" and encrypt a +letter x as x+k mod 26. Encrypt a text as the sequence of the +encryption of its letter. For example, if k=3 then the text +BEGINTHEATTACKNOW is encrypted as EHJLQWKHDWWDFNQRZ. The decryption +of a letter x is just x-k mod 26 and the decryption of a text is +obtained by applying this procedure letterwise. + +The special case k=3 is known as "Caesar Cipher" since purportedly +Julias Caesar used it to encrypt some of his letters. The special case +k=13 is known as ROT-13. + +There are two simple attacks on a shift cipher. The first one uses the +fact that there are only 26 possible keys so one can try them all +out. This, however, requires that one can recognize the right +plaintext, e.g. because it is correct English. + +The second is based on frequencies of letters. In a standard English +text the letters occur with typical frequencies. E.g. E is the most +frequent letter with likelihood 12.7%. Then follows T with 9.0% and A +with 8.2% etc. Thus, we can count the relative frequencies of the +letters in the ciphertext and thus work out the key. + +An improved and more systematic attack based on frequencies goes as +follows: Let p_i stand for the frequency of letter i, e.g. p_4 = 12.7% +since E=4. One has + + sum_{i=0..25} p_i^2 =~= 0.065 + +So, if q_i is the frequency of the letter i *in the ciphertext* then +we expect q_{i+k} to be close to p_i so that we can recover k by +choosing j in such a way that the following quantity I_j is as close to +0.065 as possible. + + I_j := sum_{i=0..25} p_i * q_{i+j mod 26} + + + +The Vigenere Cipher +- - - - - - - - - - + +The shift cipher suffers from two problems: + +1) the number of possible keys is too small +2) the frequency distribution of letters in the plain text shows in + the ciphertext + +A famous historic cipher not suffering from the first problem is the +Vigenere cipher. Here one selects a word or a short text as key, +writes the key repeatedly under the plaintext and then "adds" letters +one above another (as numbers mod 26). Here is an example with key BEADS: + +THEMANANDTHEWOMANRETRIEVEDTHELETTERFROMTHEPOSTOFFICE +BEADSBEADSBEADSBEADSBEADSBEADSBEADSBEADSBEADSBEADSBE +ULEPSOENGLIIWREBRRHLSMEYWEXHHDFXTHJGVOPLIIPRKUSFIADI + +Alas, the frequency distribution of the plaintext still seeps through +and we can use this information to break the cipher without knowing +the key: + +If we know the length of the key, e.g. 5, and the ciphertext is x_0 +x_1 x_2 ... then we can apply the previous frequency analysis (with +the I_j scores) to the 5 texts + +x_0 x_5 x_10 ... +x_1 x_6 x_11 ... +... +x_4 x_9 x_14 ... + +all of which are obtained by encrypting the corresponding plaintext +fragments with a shift cipher. Therefore, their frequency spectrum +should be a shift of the standard one and the corresponding shift, +hence the individual letters of the key, can be retrieved. + +In order to get the key length we can follow a similar approach. For a +given shift t let q_i be the relative frequency of letter i (e.g. E +when i=4) in the sequence x_t, x_2t, x_3t. If the shift t is the +actual key length then this subsequence will have the frequency +spectrum as English plaintexts just shifted by t so we expect that + + J_t := sum_{i=0..25} q_i^2 =~= 0.065 + +since the summation is invariant under the any shift. If, however, the +shift was the wrong one then we expect the letters to appear +completely random so that in that case the above sum is rather close +to 1/26 = 0.038. Thus, we compute J_t for t=1,2,3,... and pick the t +for which J_t is largest (and close to 0.065). + +Other historic ciphers include monoalphabetic substitution (key = +arbitrary permutation of the 26 letters), Grand Chiffre, the German +Enigma, etc. All these historic ciphers have been broken. See +Wikipedia and other online resources. diff --git a/ss2017/cryptography/Notes02.txt b/ss2017/cryptography/Notes02.txt new file mode 100644 index 0000000..59da143 --- /dev/null +++ b/ss2017/cryptography/Notes02.txt @@ -0,0 +1,214 @@ +2 Principles of cryptography (KL1.1, KL1.2, KL1.4, KL2) +-------------------------------------------------------- + +These considerations and similar ones applying to other historical +ciphers have led to the principles for the design of cryptosystems. + +Before stating these we describe somewhat more formally what a +(private-key) cryptosystem is. + +A cryptosystem comprises three algorithms: + +- A key generation algorithm Gen which outputs a key according to some + format an probability distribution. + +- An encryption algorithm Enc which given plaintext m and key k + produces a ciphertext Enc_k(m) + +- A decryption algorithm Dec which given ciphertext c and key k + produces a plaintext Dec_k(m). + +The set of all keys possibly put out by the key generator Gen is +called keyspace (K). For every key k produced by Gen it must hold +that Dec_k(Enc_k(m)) = m. There is also a finite set of possible +messages M and ciphertexts C. Clearly, Gen must be randomized, +otherwise it would always return the same key. Sometimes Enc is also +randomized, i.e. ciphertexts may contain some random information and +do not depend functionally on plaintext and key. + +One of the most important design principles is Kerckhoff's rule (19th +century): Security of the cryptosystem should rely on secrecy of the +key not on secrecy of the method. In other words, the cryptosystem +should remain secure if everything about the three algorithms involved +is publicly known. "No security through obscurity". + +In addition to this, the cryptosystem should withstand some or all of +the following kinds of attack: + +Ciphertext only attack: an eavesdropper observes ciphertext and aims +at determining the underlying plaintexts. + +Known plaintext attack (KPA): This is when the eavesdropper knows some +ciphertext-plaintext pairs for one and the same key and tries to use +this information to then decrypt additional ciphertexts (again +w.r.t. the same key). + +Chosen plaintext attack (CPA): Here the adversary may prepare +plaintexts of its choice and request the corresponding ciphertexts. + +Chosen ciphertext attack (CCA): Here the adversary can even request +the decryption of ciphertexts of its choice. + +Modern cryptography, say since WW2, holds the following additional +principles: + + +Principle 1: Formulation of exact definitions + +Which notion of security is one aiming at? + +No adversary should be able to know the key ... But what if they can +decrypt ciphertexts without knowing the key? + +No adversary should be able to decrypt any ciphertext unless they know +the key. But what if they can find out some bits of the ciphertext, +e.g. every second letter, or a block of letters somewhere in the +middle? + + +Principle 2: Reliance on precise assumptions + +Typically, security of a cryptosystem can be guaranteed only by making +assumptions on the computational power of an adversary (with unlimited +resources they could always try out all plaintexts) and also on the +computational difficulty of solving certain algorithmic +problems. Desirable as it would be to have unconditional security; if +one has to work with assumptions one should at least state them +precisely. Sometimes, security can only be proven for idealized +versions of cryptosystems that use components not known to exist but +which are believed to be "approximated" by existing components. Again, +it is then important to clearly state what these idealized components +or versions are. + + +Principle 3: Rigorous proofs of security + +Once the desired notion of security and the assumptions are clearly +defined one should then establish a rigorous mathematical proof of +conditional security. + +"Given that Assumption X is true, Construction Y is secure according +to the given definition." + +As an example, we now look at perfect security in the sense of Shannon +and see how Vernam's cipher (patented in 1919) implements it. + + +In order to get around the fact that an adversary can always try out +all possible plaintexts but that this kind of attack "doesn't count" +Claude Shannon suggested to use probabilities: if one out of two +messages is selected at random and the adversary gets to see the +ciphertexts only it has a chance of no more than 50% of determining +the plaintext correctly from the ciphertext. For cryptosystem Pi and +adversary A we thus define the following + +Eavesdropping indistinguishability experiment PrivK^eav_{A,Pi}: + + 1. The adversary produces two messages m0, m1 from the message space M. + 2. Gen is used to generate a (random) key k and a bit b <- {0,1} is + chosen uniformly at random (50/50). The (or rather a) ciphertext + c = Enc_k(m_b) is then given to A. + 3. A answers by outputting a bit b'. + 4. The output of the experiment is defined 1 if b=b' and 0 otherwise. + +Definition (perfect secrecy): The encryption scheme Pi=(Gen,Enc,Dec) +is perfectly secret if for all adversaries A it holds that + + Pr[PrivK^eav_{A,Pi} = 1] = 0.5 + +The following cryptosystems are not perfectly secure: + +A book cipher which uses a secret code book containing for each *word* +another word to replace it. E,g. "bomb" gets enciphered as "cake" and +"dollars" gets enciphered as "grams". Here the adversary could select +m0="bomb bomb" and m1="dollar bomb". If the received ciphertext has +the form c = x x then it will output b'=0 and if c = x y with x =/= y +it goes for 1. + +The Vigenere cipher with key length uniformly chosen at random from +{1,2} (and once the length is fixed keys also chosen at random). The +adversary can choose m0 = aa and m1=ab. If the ciphertext has the form +xx it goes for b'=0. Otherwise it returns b'=1. + +Now, if b=0 then there is a 1/2+1/2*1/26 chance that the ciphertext +has the form xx (key length 1 or key length 2 with equal letters) and thus +the adversary is right with probability 1/2+1/52 + +If b=1 then the adversary is right with probability 1-1/52 (the only +way to be wrong is key length two and two key letters of distance 1). + +Thus, the total probability for A to be right is 1/2*(1/2+1/52) + +1/2*(1-1/52) = 3/4. + + +Proposition: Fix a cryptosystem Pi and suppose that plaintexts and +keys are drawn according to some, not necessarily uniform +distribution. The sytem Pi is perfectly secret if and only if + + Pr[M=m | C=c] = Pr[M=m] + +for every fixed plaintext m and ciphertext c such that Pr[C=c] != +0. + +Proof (sketch): Suppose that Pr[M=m | C=c] != Pr[M=m] for some c and +m. Since sum_m Pr[M=m | C=c] = sum_m Pr[M=m] = 1 (both are probability +measures) there must exist m_0,m_1 (one of them m) such that Pr[M=m0 | +C=c] < Pr[M=m0] and Pr[M=m1 | C=c] > Pr[M=m1]. By Bayes' theorem it +follows that Pr[C=c|M=m0]Pr[C=c], thus in +particular, Pr[C=c|M=m0] < Pr[C=c|M=m1]. + +Now, consider the adversary who presents these messages m_0, m_1 and +if the ciphertext returned is c +then outputs b'=1, i.e. assume that the plaintext was not +m0 and outputs b'=0 otherwise. Its success probability is + +1/2*(1-Pr[C=c|M=m0]) + 1/2*Pr[C=c|M=m1] = +1/2 + 1/2(Pr[C=c|M=m1] - Pr[C=c|M=m0]) + +which is strictly above 1/2. + +For the converse, one uses the fact that all the adversary knows is +the ciphertext, but according to the assumed equality Pr[M=m | C=c] = +Pr[M=m] this does not help. Q.E.D. + +Now, such perfectly secret cryptosystems exist indeed: for fixed n:N +put M=C=K={0,1}^n and let Gen return k:K uniformly at random. The +encryption function is Enc_k(m) = m+k and Dec_k(m) = m+k as well, +where + denotes pointwise addition modulo 2 (XOR). For example, if n=5 +and k=11010 and m=11100 then Enc_k(m)=00110. + +This system is known as Vernam's cipher or "one time pad" the point +being that its secrecy relies on the key being chosen afresh at random +every time one wants to use the scheme. It can also be seen as a +special case of the Vigenere cipher with the key being as long as the +entire text to be enciphered. + +Proposition: The Vernam cipher is perfectly secret. + +Proof: This is because for a given plaintext m the ciphertexts are +uniformly distributed, i.e., their distributions are identical and +independent for m0 and m1. As a result, the adversary cannot have an +advantage. Q.E.D. + +The obvious disadvantage of the one-time pad is the key length, +nevertheless it is sometimes used, e.g. purportedly during the Cold +War for secure communication between the White House and the Kremlin. + +Unfortunately, this key length is the price of perfect secrecy: + +Theorem: If Pi is a perfectly secret cryptosystem with key space K and +message space M then |K|>=|M|, i.e. there have to be at least as many +possible keys as there are possible messages ("the key must be as long +as the message"). + +Proof: Suppose for a contradiction that |K|<|M| and that ciphertext +c:C occurs with nonzero probability. Let M(c) = {m | Dec_k(c)=m for +some k:K}. We must have |M(c)|<=|K| since for each m:M(c) there is at +least one k:K such that m=Dec_k(c) and the keys thus corresponding to +distinct messages are distinct. If now |K|<|M| there must exist some +m' not in M(c). But then Pr[M=m'|C=c] = 0 =/= Pr[M=m'], so the scheme +is not perfectly secret. + +This result is due to Claude Shannon who gives in fact a more precise +characterisation of perfect secrecy, see (KL2.4). + diff --git a/ss2017/cryptography/Notes03.txt b/ss2017/cryptography/Notes03.txt new file mode 100644 index 0000000..fb94b87 --- /dev/null +++ b/ss2017/cryptography/Notes03.txt @@ -0,0 +1,100 @@ + + +3 Semantic Security (KL3.1, KL3.2) +---------------------------------- + +In order to formally study secrecy of schemes that use shorter keys +one must somehow incorporate the computational power of an +adversary. One way of doing this is to use concrete bounds: + +A scheme is (t,epsilon)-secure if every adversary running for time t +succeeds in breaking the scheme (in the appropriate sense) with +probability at most epsilon. + +For example, if we use keys of bit length n and the only possible +attack is by trying out all keys (this happens e.g. with Vernam's +cipher) then assuming that 10^9 keys can be tried out every second +(1GHz) trying out 2^60 operations takes 35years thus several years +even with highly parallel computers. Thus, a 60bit key takes this time +to be broken with certainty, a 64 bit key takes this time to be broken +with probability 1/16 etc. Currently, one recommends key lengths of +128bit (128 *bits of security*) to make the success probability +negligible (e.g. lower than that of a meteor crashing into the device) +and to allow for future technological advances. + +Now, working with concrete runtimes and probabilities is difficult and +brittle because of its dependency on concrete hardware configuration, +programming language, implementation details, etc. As a result, one +uses instead an asymptotic approach where runtimes and probabilities +as well as sizes of keys and texts are functions of a *security +parameter* n. One then wants that the success probability of an +adversary whose runtime is polynomial in the security parameter is a +*negligible function* of the security parameter, i.e. smaller than n^k +for any k. + +Definition: A private-key encryption scheme is a tuple of +probabilistic polynomial-time algorithms (Gen,Enc,Dec) such that: + +1. Gen computes a key (in {0,1}^*) from the security parameter +(presented in unary, i.e. as 1...1 (n times)). We write this as k <- +Gen(n) or k <- Gen(1^n) to emphasize the unary notation. + +2. Enc_k(m) and Dec_k(c) are as before, except that m, c are +bitsequences (in {0,1}^*). In particular, we must have Dec_k(Enc_k(m))=m. + +A fixed-length private-key encryption scheme is defined analogously, +but there is a function l(n) fixing the length of plaintexts as a +function of the security parameter. Formally, when k is returned from +Gen(n) then Dec_k(m) is defined only for m of length exactly l(n). + +For example, the one-time pad can be cast into this framework. Given +the security parameter n, Gen generates a random bit sequence of +length n. One has l(n)=n and Enc_k(m) = m+k etc. + + + +Indistinguishability in the presence of an eavesdropper +- - - - - - - - - - - - - - - - - - - - - - - - - - - - + +We now want to adapt the notion of perfect secrecy from above to the +asymptotic framework. An adversary thus also gets the security +parameter n and its runtime must be bounded by a polynomial in n. It +is allowed to use randomization (has access to random bits). + +Given a scheme Pi=(Gen,Enc,Dec) and an adversary A the experiment +PrivK^eav_{A,Pi}(n) is now defined as follows: + + + 1. The adversary produces two messages m0, m1 of equal length + and of length l(n) in the case of fixed length. + 2. Key k is generated by Gen(n) and a bit b <- {0,1} is + chosen uniformly at random (50/50). The (or rather a) ciphertext + c = Enc_k(m_b) as well as the security parameter n are then given to A. + 3. A 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 in the presence of an eavesdropper* if there is a +negligible function negl(n) such that for all adversaries A + + Pr[PrivK^eav_{A,Pi}(n) = 1] <= 1/2 + negl(n) + +Remark: rather than having the adversary supply m0 and m1 they could +also be universally quantified. Randomizing over m0 and m1 would lead +to a weaker (and unreasonable) definition though. + + +*Semantic security* proper: + +One can show (see 3.2) that this definition is equivalent to other +ones that give even more power to the adversary. The most compelling +one is "semantic security" which assumes an arbitrary probability +distribution on the plaintexts and also partial information on the +plaintexts to be given to the adversary. + +We remark that in general proofs of semantic security (in the sense of +the above definition) are constructive in that the negligible function +bounding the probability can be read off as an explicit term. From +this, one can --- possibly after optimizing the constructions used in +the proof --- read off concrete bounds for fixed security parameter n. diff --git a/ss2017/cryptography/Notes04.txt b/ss2017/cryptography/Notes04.txt new file mode 100644 index 0000000..cabf8f9 --- /dev/null +++ b/ss2017/cryptography/Notes04.txt @@ -0,0 +1,78 @@ +4 Pseudorandomness (3.3) +------------------------ + +In order to arrive at cryptosystems with keys considerably shorter +than messages it is natural to use a generator which from a truly +random seed produces (deterministically!) a sequence of bits that +looks random. Indeed, such generators are often used in the +implementation of random in standard libraries e.g. for C or Java. + +The question is whether a so constructed cryptosystem might be while +not perfectly secret still enjoy semantic security. The answer is yes +if the generator is a *pseudorandom generator*, PRG for short, in the +following sense. + +Definition (pseudorandom generator): Let l(n) be a polynomial and G a +deterministic polynomial time algorithm that for any bitstring s of +length n outputs a bitstring G(s) of length l(n). We call G a +*pseudorandom generator* with expansion l(n) if for any probabilistic +polynomial time adversary D ("distinguisher") it holds that + + | Pr[D(r)=1] - Pr[D(G(s))=1] | = negl(n) + +for some negligible function negl(n) and for all n. Here s and r are +bitstrings of lengths n and l(n), respectively, chosen uniformly at +random. + +We remark that if l(n)=n then G(s)=s is trivially a pseudorandom +generator and if l(n)>n and G is any function sending length n +bitstrings to length l(n) bitstrings will be vulnerable against +distinguishers with exponential computing power. Simply let D +enumerate all length n bitstrings s' and check for each of them +whether its input equals G(s'). Return 1 if yes, 0 otherwise. When fed +G(s) the distinguisher will output 1 with certainty and if fed a +random string then it will output one with probability 2^{-(l(n)-n)} +only. The difference between these probabilities is not negligible. + +In summary, pseudorandom strings are as good as truly random ones so +long as they are used in a probabilistic polynomial time context and +one accepts negligible probability of failure. + +Unfortunately, one does not know whether there exist PRG with l(n)>n +at all, but it is generally believed that they do. At least, there do +exist several such objects for which no (probabilistic, polynomial +time) distinguisher is currently known despite a lot of research. + + +Semantically secure cryptosystems from PRG (KL3.4.1) +- - - - - - - - - - - - - - - - - - - - - - - - - - + +Assuming that we have a PRG G with expansion factor l(n). We can use +it in order to construct a semantically secure fixed-length encryption +scheme for messages of length l(n) as follows: + +Gen(n): return a random bitstring of length n as key. +Enc_k(m): return G(k)+m /* + = bitwise XOR */ +Dec_k(c): return G(k)+c + +Notice that Dec_k(Enc_k(m)) = G(k)+G(k)+m = m + +Theorem: If G is a PRG of expansion l then the above construction has +indistinguishable encryptions in the presence of an eavesdropper. + +Proof: Let Pi stand for the scheme constructed above from G and +l(n). Assume further, that A is an adversary against Pi. We construct +from A a distinguisher D as follows: + +Given a string w (either random or of the form G(s)) the distinguisher +begins by letting the assumed adversary A produce two messages m0 and +m1. It then selects b:{0,1} at random and sends m_b + w to the adversary A. +If A outputs b the distinguisher returns 1 and it returns +0 otherwise. Let p be the success probability of A in the PrivK^eav +experiment which must be shown to be 0.5+negl(n). If w is truly random +then so is m_b+w and the chance that A finds out b is exactly 1/2. If, +on the other hand, w is G(s) for random s, then this likelihood is +p. The difference between the two, i.e. p-1/2 is negligible since G +was assumed to be a PRG and as a result p=1/2+negl(n) as required. +Q.E.D. + 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. + + 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. + diff --git a/ss2017/cryptography/Notes06a.txt b/ss2017/cryptography/Notes06a.txt new file mode 100644 index 0000000..6791ce9 --- /dev/null +++ b/ss2017/cryptography/Notes06a.txt @@ -0,0 +1,105 @@ + + +Multiple encryptions from cpa-secure cryptosystem +- - - - - - - - - - - - - - - - - - - -- - - - - - + +We have seen that a block cipher can be used repeatedly with the same +key (using e.g. CTR-mode) without compromising security. We show now +that this is true for an arbitrary cpa-secure cryptosystem. From a +practical point of view this is not so important because cpa-secure +cryptosystems typically come from block ciphers, and a block cipher is +used more efficiently through one of the modes of operation given. + +However, the proof of the result (cpa->multiple) is interesting at +this point because it is the first time where we use semantic security +(here in the cpa sense) as an assumption rather than establishing +it. Furthermore, the result becomes practically relevant in the +context of public key cryptography where by definition security +against eavesdroppers and cpa security coincide. + +Theorem. Let Pi=(Gen,Enc,Dec) be cpa-secure. Build + +Pi'=(Gen,Enc',Dec') + +Enc'_k(m1 || m2) = Enc_k(m1) || Enc_k(m2) + +Then Pi' is cpa-secure, too. + +Proof: Consider an adversary A' against Pi'. We run A' and answer +oracle queries honestly using Enc'_k. Adversary A' eventually +produces + +m^0 = m1^0 || m2^0 +m^1 = m1^1 || m2^1 + +and asks for a ciphertext c1 || c2. For b1,b2,b':{0,1} define +P(b1,b2,b') to be the probability that A' outputs b' when +c1<-Enc_k(m1^b1); c2<-Enc_k(m2^b2). + +The success probability of A' equals 1/2 * (P(0,0,0) + P(1,1,1)) + +The probabilities P(0,1,0) and P(0,1,1) are somewhat funny since they +correspond to replies to the adversary's question that are against +the rules. However, we still know that their sum is one and this can +be used as follows: + +Let us design an adversary A against the original system Pi. This +adversary A produces m2^0 and m2^1 and receives a ciphertext c2 for +one of the two. It can then obtain c1<-Enc_k(m1^0), forward c1||c2 to +A' and output the bit b' it eventually receives from A'. The +probability that this bit is correct then is 1/2 P(0,0,0) + 1/2 +P(0,1,1) by making a case distinction over the equally likely +possibilities b=0 or b=1. So, assuming that Pi is cpa secure, we +obtain a negligible function negl(n) so that + +1/2 P(0,0,0) + 1/2 P(0,1,1) <= 1/2+negl(n) + +Similarly, by producing m1^0 and m1^1 instead and using +c2<-Enc_k(m2^1), we obtain a bound + +1/2 P(0,1,0) + 1/2 P(1,1,1) <= 1/2+negl(n) + +Summing up and using the fact that the sum of negligibles is +negligible we get + +1/2(P(0,0,0)+P(1,1,1)) + 1/2 <= 1 + negl(n) +and so 1/2(P(0,0,0)+P(1,1,1)) <= 1/2 + negl(n) QED. + +Let us now consider the more general case where Pi is used to encode a +sequence of message of some arbitrary length l=l(n), i.e., depending +on n. Thus, define Pi'=(Gen,Enc',Dec') by + +Enc'_k(m1||...||ml) = Enc_k(m1) || ... || Enc_k(ml) etc + +Theorem: If Pi is cpa-secure so is Pi' as defined above. + +Proof: The proof is similar to the one before. Adversary A' against +Pi' eventually produces m1^0...ml^0 and m1^1...ml^1 and waits for +ciphertexts c1..cl. For 0<=j<=l define P_j(b') to be the probability +that A' outputs b' assuming that + +c1<-Enc_k(m1^0) ... cj<-Enc_k(mj^0), +c_{j+1}<-Enc_k(m_{j+1}^1) ... cl<-Enc_k(ml^1) + +The success probability for A' is 1/2 * (P_l(0) + P_0(1)) and, as +before, we should bound this by 1/2+negl(n). + +For the skew probabilities it holds as before P_j(0)+P_j(1)=1. + +For each t=1..l we build an adversary A_t against Pi by outputting +mt^0 and mt^1, receiving ct, requesting c1<-Enc_k(m1^0), +c2<-Enc_k(m2^0) ... c_{t-1}<-Enc_k(m_{t-1}^0), +c_{t+1}<-Enc_k(m_{t+1}^1)...c_l<-Enc_k(m_l^1). Notice the switch from +^0 to ^1 after we reach t. Adversary A_t then forwards c1..cl to A' +and returns its answer. The success probability is +1/2(P_{t}(0)+P_{t-1}(1)) which is hence bounded by 1/2 + negl(n): + +For all t=1..l : 1/2(P_t(0)+P_{t-1}(1)) <= 1/2+negl(n) + +Summing all these inequalities noticing P_t(0)+P_t(1)=1 yields + +1/2(P_l(0) + (l-1)*1 + P_0(1)) <= 1/2*l + negl(n) /* another + negligible function */ + +and thus 1/2(P_l(0) + P_0(1)) <= 1/2 + negl(n) as required. QED + diff --git a/ss2017/cryptography/Notes07.txt b/ss2017/cryptography/Notes07.txt new file mode 100644 index 0000000..6d60d56 --- /dev/null +++ b/ss2017/cryptography/Notes07.txt @@ -0,0 +1,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. diff --git a/ss2017/cryptography/Notes08.txt b/ss2017/cryptography/Notes08.txt new file mode 100644 index 0000000..fd5c54b --- /dev/null +++ b/ss2017/cryptography/Notes08.txt @@ -0,0 +1,382 @@ + + +8 DES (Data encryption standard) and AES (Advanced encryption standard) +----------------------------------------------------------------------- + +The Data Encryption Standard (DES) was published 1975 by the +US-administration after public consultation. It was designed and used +as a standard for non-military secrte communication e.g. between +government bodies but also in the private sector. It is a 16-round +Feistel network of message length 64 and key length 56. Mainly due to +its relatively short key length it is no longer considered secure. It +is nevertheless still widely used in legacy applications and in the form +of three-fold repetition (3DES) which is considered secure but +somewhat inefficient. + +The Feistel mixing function of DES uses a round key k_i of length 48 +which is applied to a 32 bit long half block as follows: + +1) The 32 bit half block is expanded to 48 bit by repeating half of +its bits using an expansion function E() (see table below) + +2) The round key is XOR-ed with the resulting block + +3) The result is divided into eight 6-bit blocks to which S-boxes +S_1..S_8 are applied (see table below). Each S-box has 6 inputs and 4 +outputs, so a 32bit block results. + +4) a mixing permutation P is applied to the resulting 32bit. + +The DES key schedule is as follows: initially the master key is +subjected to a mixing permutation on 56 bits. Thereafter, the round +key for the each round is applied by extracting (in a round-dependent +fashion) 48 bits from these 56 bits in such a way that the first 24 +bits stem from the first half of the (permuted) key and the second 24 +bits from the second half. See below for the exact form of the bit +extraction functions. + +The DES encryption function is now obtained by enclosing the 16-round +Feistel network FN_k described above by an initial permutation IP and +its inverse listed below, thus Enc_k(x) = IP^{-1}(FN_k(IP(x))). + +The initial permutation has no influence on security. It is there only +for historical reasons having to do with 8-bit hardware. + +Each S-Box can be regarded as a package consisting of four +*invertible* operations on size 4 bitstrings. In conjunction with the +expansion function they operate as follows: The current size 32 +bitstring is divided into 8 blocks of size 4. To the ith such block +the ith S-box (eight in total) is applied in the following way: first +the two neighbouring bits (modulo 32) are taken, e.g. for the block +comprising bits 5,6,7,8 these neighbouring bits are 4 and 9. For the +first block comprising bits 1,2,3,4 the neighbouring bits are 32 and +5. These two bits then are used to select the invertible substitution +to be applied to the block. This intuition is reflected in the +tabulation of the S-boxes below as binary functions of the central +size four block and the neighbouring two bits. Also, the expansion +function E() is designed to implement this idea, i.e. it duplicates +the "neighbouring bits. +" + + +DES supplementary material +- - - - - - - - - - - - - + +Initial permutation: The first bit of IP(x) is the 58th bit of x; the +second bit of IP(x) is the 50th bit of x etc (read left to right and +top to bottom). + +IP: +58 50 42 34 26 18 10 2 +60 52 44 36 28 20 12 4 +62 54 46 38 30 22 14 6 +64 56 48 40 32 24 16 8 +57 49 41 33 25 17 9 1 +59 51 43 35 27 19 11 3 +61 53 45 37 29 21 13 5 +63 55 47 39 31 23 15 7 + + +Expansion function: to be read left to right, top to bottom. First bit +of E(x) is the 32th, i.e. last, bit of x. + +E: +32 1 2 3 4 5 +4 5 6 7 8 9 +8 9 10 11 12 13 +12 13 14 15 16 17 +16 17 18 19 20 21 +20 21 22 23 24 25 +24 25 26 27 28 29 +28 29 30 31 32 1 + + +Mixing permutation P: + +16 7 20 21 29 12 28 17 + 1 15 23 26 5 18 31 10 + 2 8 24 14 32 27 3 9 +19 13 30 6 22 11 4 25 + +The S-boxes given as binary functions: + +S_1: to be applied to the first block +E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7 +0 F 7 4 E 2 D 1 A 6 C B 9 5 3 8 +4 1 E 8 D 6 2 B F C 9 7 3 A 5 0 +F C 8 2 4 9 1 7 5 B 3 E A 0 6 D + +This is to be read as follows: upon receiving a 6bit block the S-box +uses the outer 2 bits to select the row and the inner four bits (read +in decimal). The decimal number found there represents the output. For +example, on input 011011 we select row #1 (0xxxx1) and the column #13 +(x1101x) (counting from 0 each time). There we find (hexa)decimal +number 5 representing output 0101. Similarly, on input 101000 we +select row #2, column #4, finding D=13, hence outputting 1101. +For the remaining S-boxes S_2,...,S_8 we refer to the Internet. + +Initial mixing function selecting 56 out of 64 bits. The remaining 8 +bits serve as parity bits (each of the eight bytes comprising the key +must have even parity). Does not have any influence on security. + +PC1: + +57 49 41 33 25 17 9 +1 58 50 42 34 26 18 +10 2 59 51 43 35 27 +19 11 3 60 52 44 36 + +63 55 47 39 31 23 15 +7 62 54 46 38 30 22 +14 6 61 53 45 37 29 +21 13 5 28 20 12 4 + + +The ith round key is obtained from the 56bit key by rotating both +halves i bits to the left and then selecting 48 bits with the +following function. + + +PC2: + +14 17 11 24 1 5 +3 28 15 6 21 10 +23 19 12 4 26 8 +16 7 27 20 13 2 +41 52 31 37 47 55 +30 40 51 45 33 48 +44 49 39 56 34 53 +46 42 50 36 29 32 + + + + +Discussion of DES +- - - - - - - - - + +The S-boxes have the important property that changing one bit of the +input always changes two bits of the output. For example, the first +row of S_4 maps 7=0111 to 10=1010. The 1bit alterations of 7 are +15=1111, 3=0011, 5=0101, 6=0110. These are mapped to 15=1111, 3=0011, +6=0110, 9=1001. All of these differ from 10=1010 in two bits. + +Furthermore, the mixing permutation is such that any two bits from the +same 4 bit block end up in *different* 4 bit blocks where they will +cause more bit differences and so on thus ensuring the desired +avalanche effect. + +Purportedly, the S-boxes have been designed so as to withstand a +particular attack called *differential cryptanalysis* which was known +to the developers but not published. Only 15 years later was this +discovered again and published by Biham and Shamir. + +The text KL contains some more detail about attacks on variants of DES +with fewer rounds which exploit the fact that the avalanche effect has +not fully unfolded then. + +With today's technology the 2^56 keyspace can be completely searched +with special hardware in several hours so that DES is no longer secure +for critical applications. There is a variant 3DES (Triple DES) which +uses three DES keys k1,k2,k3 (hence has key size 168) and encrypts according to the formula + + Enc^3DES_{(k1,k2,k3)}(m) = Enc^DES_k3(Dec^DES_k2(Enc^DES_k1(m))) + +Thus, to encrypt a message we encrypt it (using DES) with key k1 then +decrypt it with key k2 and then encrypt it with key k3. + +The fact that we use decryption rather than encryption in the second +phase ensures that standard DES arises as the special case of three +identical keys: + + Enc^3DES_{(k,k,k)}(m) = Enc^DES_k(m) + +A version with just two phases does not provide the desired increased +security due to the possibility of a meet-in-the-middle attack: +suppose we (temprorarily) define 2DES by + + Enc^2DES_{(k1,k2)}(m) = Enc^DES_k2(Enc^DES_k1(m)) + +Then given a pair (m,c) where c=Enc^2DES_{(k1,k2)}(m) we can recover +k1 and k2 in time ~2^56 as follows: + +Define x_k = Dec^DES_k(c) and y_q = Enc^DES_q(m) and tabulate x_k and +y_q for any DES keys k and q. This takes 2*2^56 DES operations (and +also requires this much space to store the tables). One can then sort +the tables and in this way quickly find k,q so that x_k=y_q. This pair +then is the desired 2DES key. + +One can also use this attack against 3DES (splitting either after the +third or after the second phase) which reduces the effective key size +to 112. + +It is not clear whether "meet-in-the-middle" is really practical +because, at least when implemented naively, the storage requirements +for the tables exceed current technology. + + +Advanced Encryption Standard (AES) +- - - - - - - - - - - - - - - - - - + +The AES which was selected by the US administration (NIST) from +submissions to a public competition in 2000 is an S/P-network with +block size 128bit and key sizes of 128, 192, or 256 bit (AES-128, +AES-192, AES-256). AES-128 being the most popular variant we will only +describe this one here. The original name of the cipher prior to being +selected as the AES was "Rijndael" (Dutch for Rhine Valley) and chosen +by its Belgian authors Joan Daemen and Vincent Rijmen. + + +The substitution operation applies a fixed invertible function (the +AES S-box) on size-8 bitstrings (bytes) to each of the 16 bytes of the +text. + +The subsequent mixing step is in the case of AES not just a bit +permutation but in fact an invertible linear transformation. + +AES operates on the byte level and the text is arranged into a 4x4 +matrix whose entries are bytes (4x4x8=128). The bytes are mostly +understood as elements of the 256-element field GF(256). Thus, there +is also a multiplication operation b*b' on bytes which together with +the XOR-operation (bitwise addition mod2) endows the bytes with the +structure of a field. In particular, each byte b:{00,...,FF} (one +adopts hexadecimal notation) except 00 has an inverse b^{-1} such that +b^{-1} * b = 1. Caveat: this multiplication is not multiplication of +binary numbers mod 256. We describe below how it is defined in +detail. For now it suffices to know that together with addition (XOR) +it satisfies the usual algebraic laws (commutativity, associativity, +distributivity, inverse). + +Now, each round comprises the following four steps: + +1. AddRoundKey(): Addition mod2 of the 128 bit round key derived from the +master key according to the key schedule. Can be viewed as the +addition of a "round key matrix". + +2. SubBytes(): Application of the S-Box to each of the 16 bytes of the +text. First, each of the 16 bytes comprising the current text matrix +is replaced with its inverse in GF(256). Exception: 00 for which there +is no inverse is left alone (not replaced). + +Thereafter, each byte is transformed by the following affine map: + +(b_7') (1 1 1 1 1 0 0 0) (b_7) (0) +(b_6') (0 1 1 1 1 1 0 0) (b_6) (1) +(b_5') (0 0 1 1 1 1 1 0) (b_5) (1) +(b_4') = (0 0 0 1 1 1 1 1) (b_4) + (0) +(b_3') (1 0 0 0 1 1 1 1) (b_3) (0) +(b_2') (1 1 0 0 0 1 1 1) (b_2) (0) +(b_1') (1 1 1 0 0 0 1 1) (b_1) (1) +(b_0') (1 1 1 1 0 0 0 1) (b_0) (1) + +These matrix and vector operations are understood in GF(2), +ie. addition is (as usual) XOR of bits whereas multiplication is +logical AND. + +The purpose of the inversion part is to introduce a high degree of +nonlinearity, i.e. to not even be close to a linear function. The +purpose of the affine transformation (which is linear) is to introduce +a certain amount of diffusion, i.e. that changes in one bit in the +input of the S-box result in >1 bit changes at the output. The affine +transformation also ensures that not the entire operation of AES can +be regarded in terms of GF(256) which could possibly result in +vulnerabilities based on algebraic properties. + +Usually, the entire S-box is implemented as a 256 byte lookup table. + + +3. ShiftRows(): The ith row is (cyclically) shifted i-1 columns to the +left (i=1,2,3,4): + +(a b c d) (a b c d) +(A B C D) |-> (B C D A) +(u v w x) (w x u v) +(U V W X) (X U V W) + + +4. MixColumns(): The 4x4 text matrix is multiplied (from the left) by +the (invertible) matrix + +(02 03 01 01) +(01 02 03 01) +(01 01 02 03) +(03 01 01 02) + +The entries of this matrix are understood as hexadecimal notation for +bytes, e.g.03 stands for the element 00000011 of GF(256). Thus, we +have 02+01=03 but 01+01=00 and 02+03=01. + +In the last (16th) round, MixColumns() is replaced with another +AddRoundKey(). Notice that---as pointed out earlier---key-independent +steps at either the beginning or the end of the cipher could be easily +undone by an attacker and thus are worthless. + +The AES key schedule thus must transform the 128bit master key into 17 +equally sized round keys. Let k be the 128bit master key. Just as the +texts we view it as a 4x4 matrix with entries from GF(256). We now +generate a sequence k_0,...,k_{16} of round keys (17 in number) as follows: + + +k_0 = k (01 01 01 01) +k_{i} = (k_{i-1} + (c'|0|0|0)) (00 01 01 01) + (00 00 01 01) + (00 00 00 01) + \______ ______/ + V + M + +where the column c' is obtained from the last column c of k_{i-1} as follows: + + (00 00 00 01) (02^i) +c' := (01 00 00 00) SubBytes(c) + ( 00 ) + (00 01 00 00) ( 00 ) + (00 00 01 00) ( 00 ) + \______ _____/ + V + R + +Here SubBytes(c) denotes the result of the application of the AES +S-box to each byte in the column c. The byte 02^i is 02*02*...*02 (i +times) in GF(256). The matrix R cyclically rotates the column +downwards. To then obtain k_i we add c' to the first column of k_{i-1} +to obtain the first column of k_i. The next three columns are obtained +by adding the previous one (of k_i) to the corresponding one of +k_{i-1}. The matrix M does just that. + +We see that the next round key is obtained from the previous one by +some simple linear operations and one nonlinear function of the last +column. + +Decryption: We notice that all the functions used are invertible so +the decryption just performs these inverse operations in the opposite +order. We omit the details. + + +Arithmetic in GF(256) +- - - - - - - - - - - + +In order to understand how multiplication in GF(256) works one +represents a byte b=b0..b7 as a polynomial with coefficients in +GF(2)={0,1} + +b(X) = b7 * X^7 + b6 * X^6 + ... + b1 * X + b0 + +In order to multiply two bytes one multiplies them qua polynomials and +then takes the remainder (using polynomial division) modulo the +polynomial + +p(X) = X^8 + X^4 + X^3 + X + 1 + +For example, 03 is X+1, so 03*03 = X^2+1 = 05 (the coefficients are +calculated modulo 2). The inverse of 03 is F6=11111010 because + +(X^7+X^6+X^5+X^4+X^2+X)*(X+1) = X^8+X^7+X^6+X^5+X^3+X^2+X^7+X^6+X^5+X^4+X^2+X = +\___________ _________/ \_ _/ = X^8+X^4+X^3+X = 1 (mod p) + V V + F6 03 + +One finds such inverses using the extended Euclidean algorithm or +using a table of logarithms. Indeed, each element of GF(256) \ {0} can +be written as a power of 03 (some other elements can be used in place +of 03). One may write log(x) for the number t:{0..254} such that x = +03^t. One then has x^{-1} = 03^{255-t}. The logarithms can also be +used to reduce multiplication to addition mod 255. diff --git a/ss2017/cryptography/Notes09.txt b/ss2017/cryptography/Notes09.txt new file mode 100644 index 0000000..7c6f51d --- /dev/null +++ b/ss2017/cryptography/Notes09.txt @@ -0,0 +1,259 @@ + +9 Cryptanalysis +--------------- + +Cryptanalysis is aimed at breaking ciphers in the sense of +reconstructing a key from given or chosen pairs of plain- and +ciphertext. In the first chapter, we saw how various historic ciphers +can be broken using regularities in the statistical distribution of +ciphertexts or rather using the fact that known properties of the +statistical distribution of plaintexts shine through in the +statistical distribution of plaintexts. Modern cryptographic schemes +avoid such attacks by making sure that the statistical distribution of +ciphertext looks close to uniform no matter what the statistical +distribution of the plaintexts is. The principles of confusion and +diffusion were introduced to ensure this property at least +approximately in practice. The notion of pseudo random generator +furnishes an ideal yet useful theoretical model. + +Attacks against cryptographic schemes that properly implement +confusion and diffusion are much more complicated and in many cases, +in particular DES and AES not known to exist except in the sense that +the computational time needed to carry them out is close to that of a +brute-force attack (trying out all keys) which is always +possible. Nevertheless, it is important to know and study principles +of such attacks in order to avoid them when designing a new cipher, +e.g. a smaller variant of existing ones to be run in +resource-constrained environments e.g. "Internet of Things". + +We have already seen that a cipher that only uses linear or affine +linear operations is vulnerable to an attack based on solving systems +of linear equations. In this chapter we take a brief look at three +more principles of cryptanalysis. First, we show why feedback shift +registers which are a popular device for generating pseudorandom +numbers are not secure. + +Linear Feedback Shift Registers (LFSR): Such a device is given by a +sequence of shift registers with some outputs fed back via XOR to the +input. For instance: + + >[D]-o->[D]-o->[D]---o-------------> + | | | | + -(+)-----------(+)---- + +When the shift registers (here noted [D]) are initialised with some +bits then a stream of bits is generated at the output. E.g. starting from 100 +we obtain the following sequence of states: + +100,110,111,011,101,010,001,100,... +and the following output sequence 00111010... + +Here, from xyz we get to uxy where u=x+z (mod 2). Of course, the +sequence repeats after at most 8 steps, but until then looks rather +random. With a chain 16 shift registers one can achieve a period +length of 65535. In order to encrypt a stream of bits ("stream +cipher") one can initialise the shift registers with the secret key +and then add (XOR) the generated stream to the data stream. Due to the +relative simplicity of implementation this has been used for a long +time in esp. military applications. + +However, LFSR are linear (the sequence generated by the sum of two +keys equals the sum of the sequences generated by the keys +individually) and this can be exploited in various ways. The most +interesting way uses the Berlekamp Massey algorithm which from a given +sequence of bits computes the shortest LFSR which generates it. If one +knows the beginning m of a plaintext and the corresponding ciphertext +c, e.g. because the plaintext starts with the date or some formal +greeting one can then apply the Berlekamp-Massey algorithm to m+c and +use the computed LFSR to decode the remaining ciphertext. + +In order to circumvent this one can use nonlinear functions in the +feedback loop, e.g. logical or use nonlinear combinations of several +LFSR. The resulting stream ciphers, e.g. A5/1 and A5/2, E0 are still +in use in GSM and Bluetooth but are known to have vulnerabilities +too. Indeed, the design of secure stream ciphers is very difficult and +for high security applications one resorts to block ciphers run, +e.g. in CTR mode in order to encrypt bitstreams. + + +Linear cryptanalysis +- - - - - - - - - - - + +Linear cryptanalysis was developed in the 90s by Matsui and apparently +was not known to the DES developers. Nevertheless, it can only produce +a theoretical attack on the latter and on AES. + +We illustrate linear cryptanalysis with the toy cryptosystem from +Michael Heys' tutorial +https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf. + +It is an S/P network with a block length of 16 and four proper rounds, +i.e. four rounds and an additional key mixing step. We regard each +block as a 4x4 bit matrix. The substitution step applies the first +S-Box of DES S_1, i.e. + +0 1 2 3 4 5 6 7 8 9 A B C D E F +------------------------------- +E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7 + +separately to each of the four rows (regarded as a hexadecimal number). So + +(1 0 1 0) (A) (6) (0 1 1 0) +(0 1 1 0) which is (6) becomes (B) which is (1 0 1 1) +(1 1 0 1) (D) (9) (1 0 0 1) +(0 0 0 1) (1) (4) (0 1 0 0) + +The permutation step is simply matrix transposition, thus our example +becomes + +(0 1 1 0) (6) +(1 1 0 0) which is (C) +(1 0 0 1) (9) +(0 1 1 0) (6) + +As usual, each round consists of addition mod2 of the round key, +substitution (S), and permutation (P), i.e. transposition. After four +rounds we add one more key. The master key simply consists of the +concatenation of the five round keys k = k1 k2 k3 k4 k5. + +We can now observe that the S-box S is not completely balanced in the +following sense. Let WX1 be (1 0 1 1)^T and WY1 = (0 1 0 0)^T. The ^T +suffix means transposition so W1, W2 are actually columns. We now have + + Pr(WX1^T x + WY1^T S(x) = 0) = 3/4 + +where the probability is taken over uniformly distributed +x:{0,1}^4. In other words, for 12 out of the 16 possible inputs x=(x1 +x2 x3 x4)^T and results S(x)=(y1 y2 y3 y4)^T one has x1+x3+x4=y2 +whereas for the remaining four one has x1+x3+x4=/=y2, +i.e. x1+x3+x4=y2+1. + +One can find such an imbalance by exhaustive search. Another such +imbalance is given by WX2=(0 1 0 0)^T WY2 = (0 1 0 1)^T: + + Pr(WX2^T x + WY2^T S(x) = 0) = 1/4 + +Chaining these imbalances through the whole cipher (using the first +one on round 1 and the second one on the other rounds) one obtains a +similar linear relationship between the plaintext, the ciphertext just +after round four, and the four round keys that have been used until +then: Letting P be the plaintext (now written as dim16 vector) and U +the ciphertext prior to applying the last S-boxes, permuting, and +mixing with the fifth and last round key we find dim16 vectors A, B +D1, D2, D3, D4 such that + + Pr(A^T P + B^T U + D1^T K1 + D2^T K2 + D3^T K3 + D4^T K4 = 0) = 15/32 + +with keys K1 ... K4 fixed and probability taken over the plaintexts P. + + +Since D1^T K1 + D2^T K2 + D3^T K3 + D4^T K4 is either 0 or 1 we have that + + Prob(A^T P + B^T U = 0) = 15/32 or Prob(A^T P + B^T U = 0) = 17/32 + +irrespective of K1,..,K4. This allows us to work out a likely value +for K5 or rather some bits of it. + +Namely, given a list of plaintexts P_1..P_N and corresponding +ciphertexts C_1..C_n we can try out all 2^16 possible choices for K_5, +for each one compute the corresponding U_i := S^{-1}(P^{-1}(C_i+K_5)), +and compute the ratio + + p(K_5) = {i | A^T P_i + B^T U_i = 0} / N + +We choose a value K_5 for which this ratio is close to 15/32 or 17/32 +and discard all those where it is close to 1/2. Now, p(K_5) does not +actually depend on all bits of K_5 but only on those where the +corresponding bit in B^T is set for the other ones only influence +components of U_i which are not used in p(K_5). Nevertheless, this +allows us to considerably narrow down the possible options for +K_5. For each of those, we can then continue in the same fashion and +thus peel off the fourth round key etc. + + +Differential cryptanalysis +- - - - - - - - - - - - - - + +Differential cryptanalysis was developed by Biham and Shamir as an +attack against DES but apparently already known to the DES +developers. It has been used to successfully break other ciphers. It +uses the fact that the effect of adding a round key cancels out when +we consider differences between two plaintexts. However, this +requires the preparation of chosen plaintexts. In more detail, the +*differential* between two plaintexts X1 and X2 is simply X1+X2, +i.e. the bitvector which has a 1 where X1 and X2 differ and a 0 where +they are equal. + +Coming back to our 4bit example S-box for any given differential there +then are 2^4=16 different ways of realising it. E.g. the differential +1010 arises for the plaintext pair 0011,1001 and also for +1111,0101. Indeed, for any plaintext X1 there is a unique X2 such that +X1, X2 have a given differential. + +Given two differentials X* and Y* we are interested in the following +question. For how many of the (16) plaintext pairs X1,X2 with +differential X* is it the case that the results of applying the S-box +Y1=S(X1), Y2=S(X2) have differential Y*. Tabulating these numbers by +exhaustive search yields the following table: + + Output differential + 0 1 2 3 4 5 6 7 8 9 A B C D E F +I 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 +n 1 0 0 0 2 0 0 0 2 0 2 4 0 4 2 0 0 +p 2 0 0 0 2 0 6 2 2 0 2 0 0 0 0 2 0 +u 3 0 0 2 0 2 0 0 0 0 4 2 0 2 0 0 4 +t 4 0 0 0 2 0 0 6 0 0 2 0 4 2 0 0 0 + 5 0 4 0 0 0 2 2 0 0 0 4 0 2 0 0 2 +d 6 0 0 0 4 0 4 0 0 0 0 0 0 2 2 2 2 +i 7 0 0 2 2 2 0 2 0 0 2 2 0 0 0 0 4 +f 8 0 0 0 0 0 0 2 2 0 0 0 4 0 4 2 2 +f 9 0 2 0 0 2 0 0 4 2 0 2 2 2 0 0 0 +' A 0 2 2 0 0 0 0 0 6 0 0 2 0 6 0 0 +i B 0 0 8 0 0 2 0 2 0 0 0 0 0 2 0 2 +a C 0 2 0 0 2 2 2 0 0 0 0 2 0 6 0 0 +l D 0 4 0 0 0 0 0 4 2 0 2 0 2 0 2 0 + E 0 0 2 4 2 0 0 0 6 0 0 0 0 0 2 0 + F 0 2 0 0 6 0 0 0 0 4 0 2 0 0 2 0 + + +The high entries 8 and 6 are of particular interest because they +constitute a deviation of an intuitive pseudorandom permutation. +Let us now see how we can exploit these in order to attack our cipher. + +We feed in a pair of 16bit plaintexts X1 X2 which differ in the second +block by B=1011 and are equal everywhere else. With probability 8/16 +this will result in differential 2=0010 at the output of the second +S-box. The output of the other S-boxes will be equal for X1 and X2. +This differential 2=0010 will be propagated through the P network and +results in a differential of 4=0100 at the entry of the third S-box of +the second round: + + Differential before P Differential after P + 0 0 0 0 0 0 0 0 + 0 0 0 0 ------P----> 0 0 1 0 + 0 1 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 + + +There, with probability 6/16 it will produce differential 6=0110 at +the output. This results in differential 2=0010 at the input of the +second and third S-boxes of the third round. With probability 36/256 +this will lead to differential 5 at both outputs which propagates to +differential 6=0110 at the entries to the second and fourth S-boxes of +the final round. + + 0 0 0 0 0 0 0 0 + 0 0 1 0 -------P-----> 0 0 0 0 + 0 0 1 0 0 1 1 0 + 0 0 0 0 0 0 0 0 + +Summing up, when we encipher plaintexts with differential 0B00 we will +obtain with probability 1/2*3/8*9/64=27/1024 a differential 0606 at +the entry to the last round. We now have to set the relevant +components (second and fourth block) of the final key in such a way +that this ratio (after inverting the last layer of S-boxes) is +actually reproduced. This allows us (with high probability) to guess +hone half of the bits of the last round key. Continuing in this way +with other differentials combined with exhaustive search allows us to +undo the entire last round and then to proceed from there. + diff --git a/ss2017/cryptography/Notes10.txt b/ss2017/cryptography/Notes10.txt new file mode 100644 index 0000000..5457bf3 --- /dev/null +++ b/ss2017/cryptography/Notes10.txt @@ -0,0 +1,257 @@ + + +10 Message integrity, CBC-MAC (KL4.1-4.5) +----------------------------------------- + +So far, we wanted to prevent an eavesdropper or a more active attacker +from getting to know the content of encrypted messages or at least +partial information about them. + +Another important objective for cryptography is message integrity and +authenticity. We want to prevent the attacker from being able to +manipulate an encrypted message or from fabricating one such. + +It is not the case that encryption automatically guarantees +integrity. For example, with the Vernam cipher and derived systems +flipping one bit in the ciphertext results in the same bit in the +plaintext being flipped. Also, randomly chosen ciphertexts correspond +to plaintexts albeit probably nonsensical ones. + + +Message authentication codes +- - - - - - - - - - - - - - - + +Definition: A message authentication code (MAC) consists of two +probabilistic polynomial time algorithms (Gen,Mac) where + +1. On input n (security parameter) Gen outputs a key k of length >= n +2. Given key k and message m:{0,1}* the tag-generation algorithm Mac outputs + t = Mac_k(m) + +We assume (unlike in KL where this is a special case) that Mac is +deterministic. + +If m is furthermore constrained to be from {0,1}^l(n) for some length +function l(n), e.g. l(n)=n then the MAC is called *fixed length*. EOD + +The intended usage is as follows: Alice and Bob share a secret key k +that has been obtained with Gen(). If Alice wants to send a message m +to Bob she could compute the tag t=Mac_k(m) and transmit (m,t) either +encrypted or not. + +In order to be sure that the received message (m,t) was really from +Alice he can then compute t'=Mac_k(m) and check that t=t'. The MAC +should be designed in such a way that no adversary can fabricate valid +tags unless it knows the key so that if the verification succeeds Bob +can indeed be sure that the message was from Alice. The following +experiment formalizes this. + + +The message authentication experiment Mac-forge_{A,Pi}(n): + +Pi = (Gen,Mac) a MAC, A an adversary, n the security parameter + +1. A random key k is generated with Gen(n). + +2. The adversary is given n and oracle access to Mac_k(), i.e. it can +request arbitrary tags w.r.t k. The adversary eventually outputs a +pair (m,t). + +3. The output of the experiment is defined to be 1 if + (1) Mac_k(m)=t and (2) m has not previously been queried by A. + +Thus, the adversary must prepare a valid tag for a message it has not +previously requested a tag for. + +We define a MAC to be secure if for all adversaries +the probability that Mac-forge yields 1 is negligible. + +While this notion of security is indeed very strong there are some +attacks it cannot withstand: + +1) Replay attacks. The adversary can store an authenticated message +(m,t) and send it at some later point. In order to prevent that one +can extend message with timestamps or similar. + +2) Timing attacks. If the check t=t'? proceeds by comparing bits +starting from the left until the first mismatch is encountered (cf +strcmp() from the C-library) then the time it takes to perform the +check depends on the tags. This can be used to find out the bits of a +valid tag one by one. According to KL this kind of attack has been +used against an early version of the Xbox in order to install +unlicensed games. To prevent the attack one should make sure that the +computation time for the comparison is always the same. + +Construction of a fixed-length MAC from a pseudorandom function: + +Let F_k() be a pseudorandom function. The following then is a secure +fixed-length MAC. + +1. Gen(): Given n choose k:{0,1}^n uniformly at random +2. Mac(): On input k and m output the tag t=F_k(m) + +Theorem: The above MAC is secure. + +Proof sketch: As in the other security proofs it suffices to show this for +truly random F (selected at the beginning of the experiment). The +passage to a pseudorandom F then incurs a negligible change in +probability. In order to produce a valid tag the adversary would have +to correctly guess a random value from {0,1}^n which has indeed +negligible probability. QED + + +CBC-MAC +- - - - + +In order to extend a fixed-length MAC to variable length messages one +can break the message up into equal length blocks m=m_1,...m_l of +length n each possibly padding the last block with 0s and then +authenticate each block separately. In order that this is secure, one +must, however augment each block with + +- the length l, +- its sequence number i:{1..l} +- a random identifier r:{0,1}^n (the same for each block) + +Thus, the blocks to be authenticated have length 4n each (assuming +that l and i fit into n bits) and an appropriate MAC must be +used. Alternatively, one can break m into blocks of size n/4.... + +These additional data prevent the adversary from dropping blocks at +the end (length), changing the order of blocks (sequence numbers), +mixing blocks from two different messages (random identifier). + +One can show that this scheme is indeed secure, but it is rather +inefficient since the tags are 4 times as long as the message itself. + +A more efficient method mimicks the CBC-mode encryption but is subtly +different: + +Rather than an arbitrary MAC we need a pseudorandom function F_k, +i.e. a block cipher. We then decompose the message m into equal sized +blocks + +m = m_1 .. m_l + +as before (using padding if needed). We then *prepend* the message +with another block encoding the length l (which is thus assumed +smaller than 2^n). Then blocks are encrypted and XORed with the +encryption of the previous block prior to encryption. The encryption +of the last block then is the desired MAC: + +t_0 = F_k(l) +t_{i+1} = F_k(t_i + m_i) +t = t_l + +We will prove that this scheme is secure. Notice, however, that +seemingly innocuous modifications thwart its security: + +First, let us see why we need to incorporate the length. Suppose we +would just put: + +t_1 = F_k(m_1) +t_2 = F_k(m_2+t_1) +... +t = t_l + +Then, if t=Mac_k(m_1 m_2) and t'=Mac_k(m_3+t m_4) then t'=Mac_k(m_1 +m_2 m_3 m_4) thus allowing us to forge a previously unqueried tag. + +Now suppose that we would start with a random initialisation vector IV +and transmit it along with the tag: + +t_0 = F_k(l+IV) +... + +This would allow us to modify the length: If (IV,t) is the MAC of l,m +then (IV+l+l',t) is the MAC of l',m. + +It is also not ok to attach the length at the end rather than at the +beginning. Namely, suppose that we obtain the following tags where the +length is added in parenthesis for clarity. + + +ABCDE(5) : t +XYZKL(5) : t' +ABCDE5UVW(9) : t'' + +We then have that the tag of XYZKL5 U+t+t' VW(9) is also t''. + +We will now sketch a proof that CBC-MAC is indeed secure. We will show +the following theorem from which the claim follows by the standard +reasoning used in earlier security proofs. + +Theorem: Fix a security parameter n. For g:{0,1}^n->{0,1}^n and m=m1 +m2 ... mk write CBC_g(m) = CBC_g(m1,m2,...,mk) = + + g(ml+g(m_{k-1}+ ... g(m2 + g(m1)) ... ) + +Also let f:({0,1}^n)* -> {0,1}^n be an arbitrary function. Let D be an +adversary which is given oracle access to a function ({0,1}^n)* -> +{0,1}^n. + +Suppose that D queries its oracle on a prefix-free set, i.e. if X and +Y are both queried then X is not a prefix of Y nor is Y a prefix of X. +One then has + + |Pr(D^{CBC_g()}(n) = 1) - Pr(D^{f()}(n) = 1)| = negl(n) + +where probabilities are taken over g and f chosen uniformly at random. + +To see why this implies the theorem we first consider that the +difference between CBC_g and CBC_{F_k} is negligible since F_k is +assumed to be pseudorandom. Furthermore, notice that in CBC-MAC proper +the function CBC_{F_k} is applied to a subset of P:={|m| m | +m:({0,1}^n)*} which itself is a prefix-free set. Thus, the whole +business with including the length and putting it into the first +position rather than anywhere else serves to ensure prefix-free-ness. + +Proof of Theorem (sketch; for details see KL, 2nd ed): + +Let Q={X1..Xq} be the (prefix-free) set of queries (q = number of +queries) made by the distinguisher D to the oracle. Let l be the +maximum number of blocks in those queries. Notice that both q---the +number of queries---and l---their maximum length are polynomial in n +since the distinguished is assumed to run in polynomial time. If D +queries X and X = m1 m2 ... mk then (in the case where the oracle is +instantiated with CBC_g()) the function g() will be evaluated at m1, +m2+g(m1), m3+g(m2+g(m1)), ... . Write C_g(X) for this sequence (of +length < l). We say that Q exhibits a collision if among the +g-evaluations occurring in {C_g(X) | X:Q} one finds the situation +g(x)=g(x') where x =/= x'. We also consider it a collision if at some +point we have mi+g(x) = mj'+g(x') despite x=/=x' (and then necessarily +mi=/=mj'). + +Under the assumption that g() is random, the probability that such a +collision is exhibited is bounded by q^2 * l^2 * negl(n) for there are +<= q^2 * l^2 possibilities for where such a collision might occur and +the probability for a collision at a given position is negligible. +Since q and l are polynomial in n this probability is therefore +negligible itself. + +Let us assume that no collision is exhibited. Now, for each X:Q let +v(X) be the last value in C_g(X). We have CBC_g(X) = g(v(X)). The +values v(X) are pairwise distinct and do not agree with any of the +other values in {C_g(X) | X:Q}. This is where prefix-freeness is +used. As a result, since g() is random, the answers to the queries +g(v(X)) are uniformly random and thus adhere to the same distribution +as f(X) for the random f. Thus, the only advantage that the +distinguisher has stems from the possibility of a collision being +exhibited which, as we saw above, is negligible. + + + +In conclusion, we note that an already existing implementation of +CBC-mode (for encryption) can be turned into an implementation of +CBC-MAC by + + - using IV=0 + - discarding all but the last blocks of the ciphertext + - prepending the plaintext with its length + +Mistakes in any one of these (e.g. using a random IV and transmitting +it, omitting the length or placing it elsewhere, transmitting other +blocks of the ciphertext, lead to insecurities. See the nice blog +article "Why I hate CBC-MAC"). + +https://blog.cryptographyengineering.com/2013/02/15/why-i-hate-cbc-mac/ diff --git a/ss2017/cryptography/Notes11.txt b/ss2017/cryptography/Notes11.txt new file mode 100644 index 0000000..839d24b --- /dev/null +++ b/ss2017/cryptography/Notes11.txt @@ -0,0 +1,310 @@ + + +11 Hashing, Merkle-Damgard transform, SHA, HMAC +----------------------------------------------- + +Hash functions serve a related but slightly different purpose to that +of MACs. Unlike those (and private key encryption) they are not +immediately useful on their own but rather are building blocks and +indeed are "a workhorse of cryptography" like e.g. solving systems of +linear equations is to engineering. + +Intuitively, a hash function H() transforms a long string m into a +short digest ("hash") t=H(m) such that it is extremely difficult to +produce two texts x =/= x' with H(x)=H(x'). Such pair x,x' is known as +a *collision*. + +As such, the notion cannot really be made sense of in the context of +computational complexity for once we have x=/=x' with H(x)=H(x') then +we can just hardwire x,x' into a program. In order to get around this, +we introduce as before randomly chosen keys and security parameters. +This will allow us to formulate meaningful security goals and +meaningful security proofs for various constructions involving hash +functions. + +Definition: A *hash function* consists of a (probabilistic polytime) +key generation algorithm Gen(n) as before and a polytime function H +taking as input a key s ("seed") and m:{0,1}^* then +H_s(m):{0,1}^{l(n)} where l(n) is a fixed, and typically simple, +length function, e.g. l(n)=n. + +There may also be another length function l'(n)>l(n) and +H_s:{0,1}^{l'(n)} -> {0,1}^{l(n)}. In that case, we have a +fixed-length hash function. + +Definition: A hash function Pi=(Gen,H) as above is *collision resistant* if +for all probabilistic polytime adversaries A one has + + Pr[Hash-coll_{A,Pi}(n)=1] = negl(n) + +for some negligible function negl(n). Here, Hash-coll_{A,Pi}(n) is the +following experiment: + +1) s <-Gen(n) /* s = "seed" */ +2) A is given s and then outputs x,x' +3) The result of the experiment is 1 if x=/=x' and H_s(x)=H_s(x') and +0 otherwise. + +Thus, the adversary must provide a collision given a key s and the +probability that it succeeds in doing so should be negligible. In +contrast, in the case of MACs the adversary does not get access to the +key. + + + +Weaker notions of security +- - - - - - - - - - - - - - + +In this context one may ask why being able to produce a collision +should be considered dangerous. Firstly, if a hash function is +collision resistant then it follows that it is also not possible to +forge a message x' =/=x such that H(x)=H(x') given x. So collision +resistance is certainly a "good enough" notion. However, one could +instead ask for the weaker property of "second preimage resistance": +it should be difficult to, given x, produce x'=/=x such that +H(x)=(x'). + +A typical application of hash functions is message integrity: If we +send someone a message x via some untrusted channel (which can be +modified by an adversary) and the hash value t=H(x) via a trusted +channel then the receiver can check that the message has not been +tampered with by checking that t=H(x') with x' being the received +(possibly modified) message. + +While being able to produce an arbitrary collision may be harmless, +being able to find a collision in a given set of texts of size ~ +2^{l(n)} can be very dangerous and is not covered by "second preimage +resistance": Consider the following scenario: we produce a letter L, +have its hash signed by a responsible person, and then send it to some +recipient. Now, it is very easy to produce functions +f,g:{0,1}^{l(n)}->{0,1}^* such that for each z the string f(z) is, +say, a different rejection letter, and g(z) is a different acceptance +letter. E.g. by introducing various switches dear/esteemed, Sir/Madam +or pleased/delighted etc. Or, if one is dealing with images rather +than letters by slightly altering intensity values. Then if, one can +produce z, z' such that H(f(z))=H(g(z')) one can have the hash +t=H(f(z)) signed and communicate along with g(z'), for which the hash +is also valid due to the collision. While this still requires +collisions of a special kind it is sufficiently close to arbitrary +collisions and for this reason one considers collision resistance as +the "gold standard" for hash functions. + + + +Birthday paradox +- - - - - - - - - + +Let us see, how many steps a brute force attack requires. In order to +do that, we (simplifyingly) assume that H_s is a random function. Let +us write H(x)=H_s(x). So we assume that H is drawn uniformly at random +from {0,1}^*->{0,1}^{l} where l=l(n). + +Clearly, if we fix x then the likelihood for x' drawn uniformly at +random to satisfy H(x)=H(x') is 2^{-l(n)} and thus, we need to try out +ca N/2 values (N=2^l) to get a 50% success probability. This also +holds, if x has been drawn at random. Things are different, if we +randomly choose a set of values S and then *search* for a collision +within S. Of course, if |S|>N then we find a collision with certainty, +but perhaps surprisingly |S|>=2*sqrt(N) ensures that the likelihood of +a collision within S is above 50%. + +So, to find a collision one can choose a set S of size 2*sqrt(N), sort +it according to hash values and then search (in linear time) for the +desired collision. If one does not find one, repeat with new data. + +Thus, for example if l(n)=64 then trying out 2^63 values will (with +probability >=50%) lead to a collision with a fixed left hand side, +but trying out 2^33 values will suffice to get an arbitrary collision +using the birthday paradox. While 2^63 steps can only be carried out +with special hardware resources, carrying out ~2^33 steps is trivial on +today's computers. One must bear this in mind when trying to estimate +"bits of security" of a hash function. Even assuming that the hash +function does not contain systematic security holes we will only get +one half of the hash size (size of the digest) many bits of security. + + + +Improved birthday attack +- - - - - - - - - - - - - + +The implementation of the "birthday attack" sketched above takes not +only roughly O(sqrt(N)) steps but also O(sqrt(N)) memory which is a +more expensive resource. Indeed, storing 2^33 thirty-two byte words +requires 64TB. We now describe a version of the birthday attack that +runs in constant space. + +If we choose x0:{0,1}^l uniformly at random then, assuming as we did, +that H is a random function then + +S={x0,H(x0),H(H(x0)),H(H(H(x0))),...,H^{2*sqrt(N)-1}(x0)} + +is also random and thus contains a collision with >=50% +likelihood. Let us write xi:=H^i(x0). Suppose that i,j are such that +xi=xj, but x_{i-1} =/= x_{j-1}, so x_{i-1},x_{j-1} form a +collision. Note that xi=H(x_{i-1}). Assuming i=0 and thus x_{i+z}=x_{i+kd+z} +for all k>=0 and z>=0. If we choose k such that kd>=i then +x_{kd}=x_{2kd} follows with z=kd-i. + +This suggests the following +algorithm for finding a collision with high likelihood: + +x0 <- {0,1}^l /* uniformly at random */ +x = x0;y = x0; +for (r=1..4*sqrt(N)) { + x = H(x); /* x=H^r(x0) */ + y = H(H(y)); /* y=H^{2r}(x0) */ + if (x==y) break;} +if (x!=y) start over with new x0; else +y=x;x=x0; /* y=H^{kd}(x0) */ +if (x==x0) start over with new x0; else /* very unlikely */ +for (i=0..r) do { + x = H(x); /* x=H^i(x0) */ + y = H(y); /* y=H^{i+kd}(x0) */ + if (x==y) break; /* must happen before loop runs out */} +return H^{i-1}(x0),H^{i+kd-1}(x0); /* can optimize recomputation */ + + + +Merkle-Damgard Transform +- - - - - - - - - - - - - + +The Merkle-Damgard Transform constructs a collision-resistant hash +function (Gen,H) from a given *fixed length* collision-resistant hash +function (Gen,h) with length 2*l(n), i.e. the h-hash is half as long +as the input. The key generation remains unchanged and H is as follows. + +1) Given key s and input x:{0,1}^* divide message into blocks x1,x2,...,x_B +of length l=l(n) possibly padding the last block with zeroes. Set x_{B+1}=L. + +2) Set z0=0...0 /* l zeroes */ + +3) for i=1..B+1 do zi = h_s(z_{i-1} || x_i) + +4) Output z_{B+1} + + + x1 x2 x_B L +0 | _____ | _____ | _____ | _____ +| |_| | |_| | |_| | |_| | +|___| h_s |______| h_s |_...._____| h_s |_____| h_s |-----> H_s(x) + |_____| |_____| |_____| |_____| + + +Theorem: If (Gen,h) is a collision-resistant fixed length hash +function of length l'(n)=2*l(n) then (Gen,H) is a collision-resistant +hash function. + +Proof: We first show that any collision in H_s yields a collision in +h_s. Suppose that H_s(x)=H_s(x') and write x_1..x_B,L for the blocks +and length of x and x'_1..x'_B' L' for x'. Also write z_1..z_{B+1}, +z'_1..z'_B' for the intermediate results. We have H_s(x)=h_s(z_B||L) +and H_s(x')=h_s(z'_B'||L'), so, if L=/=L' we already have produced the +desired collision in h_s. This also holds, if L=L' and z_B =/= z'_B +(notice that B=B' in this case). If L=L' and z_B=z'_B then, since +z_B=h_s(z_{B-1}||x_B) we get a collision unless x_B=x'_B. Continuing +in this way, we eventually find our collision since x_i =/= x'_i for +at least one i. + +Now, suppose that A is an adversary against H_s. We construct an +adversary A' against h_s as follows. If A outputs x,x' we check +whether H_s(x)=H_s(x') and if so, construct the corresponding +collision h_s(y)=h_s(y') in h_s as described above and output +y,y'. Otherwise, we output 0,0. The likelihood for succeeding, i.e., +for the output to be a h_s-collision is negligible by assumption and +thus the probability that A output a collision is negligible as +well. Notice that the computations we carried out as A' were clearly +in polynomial time. QED + +The well-known and standardized cryptographic hash functions MD5, +SHA-1, SHA-2 use the Merkle-Damgard transform. The underlying +fixed-length hash function (called compression function) in this +context is built using the heuristic principles that were described in +Section 7 (Practical block ciphers. Principles: s/p- and Feistel +networks). We remark here that MD5 and SHA-1 are no longer consider +sufficiently secure whereas SHA-2 is. + +The latest standard SHA-3 which is not yet widely used but might +eventually supersede SHA-2 does not use Merkle-Damgard but instead +relies on the so-called *sponge construction*, see Wikipedia. + + + +MACs from hash functions +- - - - - - - - - - - - - + +A natural question is whether one can use hash functions also for the +purpose of authentication, i.e. MAC. First, we note that naive +attempts (which according to KL have been actually used in practice!) + + +do not work. Consider for example the definition Mac_k(x) = H_s(k||x) +where s is some public seed. If H_s was constructed with the +Merkle-Damgard transform from h_s then we can easily forge MACs as +follows: if t is the MAC of x then t'=h_s(t||L') is the +MAC of (x || |x|) (glossing over the padding). + +Suppose that we are given a *fixed-length* MAC (Gen,Mac) capable of +authenticating messages of length l(n). Suppose furthermore, that we +have a collision-resistant hash function (Gen',H) which produces +hashes of length l(n). We can then build a MAC (Gen'',Mac'') for +arbitrary length messages as follows: + +Gen''(n): k<-Gen(n); s<-Gen'(n);return (k,s) /* use some encoding of pairs */ +Mac''_{(k,s)}(m): return Mac_k(H_s(m)) + +Theorem: Assuming that (Gen,Mac) is secure and (Gen',H) is +collision-resistant then (Gen'',Mac'') is secure. + +Proof: Suppose that an adversary A asks questions Q and then succeeds +in forging a MAC t=Mac''_{(k,s)}(x), i.e., x is not in Q. If H_s(x) is +different from all the H_s(y) for y:Q then A has succeeded in forging +a MAC for Mac_k. Namely then t=Mac_k(H_s(x)) and H_s(x) was not +previously asked. If, however, H_s(x) is contained in {H_s(y) | y:Q} +then A has produced a collision. Since both events occur with +negligible probability the probability that A can forge a MAC is also +negligible. QED + +Suppose that H_s() above has been constructed using the Merkle-Damgard +construction from the fixed-length hash function h_s(). For seed s +define a fixed-length MAC by + + Mac_k(m) = h_s(k||m) + +We now make the assumption that h_s() is such that this is a secure +fixed-length MAC. Notice that the abovedescribed extension attack on +MACs of this sort does not apply due to the fixed length. + +If we now apply the above hash-and-MAC construction then it turns out +that the arbitrary-length MAC obtained satisfies "essentially" + +Mac''_{(k,s)}(m) = H_s(k||H_s(m)) + +because the last H_s degenerates to h_s due to the shortness of +H_s(m). The quoted "essentially" refers to the fact that for this +equation to hold exactly one needs to assume some conventions about +how exactly the padding in the Merkle-Damgard construction is +performed. We want to ignore these details here and refer to the +literature. + + +The HMAC construction +- - - - - - - - - - - + +The widely used and standardised HMAC construction is essentially the +above except that another key is added to the message m prior to +invoking the inner hash function and that the two keys that are thus +needed are derived from a single one by XOR-ing with certain fixed +words ipad and opad: + +HMAC_{(k,s)}(m) = H_s( (k+opad) || H_s((k+ipad) || m)) + +In practice, ipad and opad are chosen to be 00110110 and 01011100 each +repeated as often as necessary. + +The additional inner keying with k+ipad allows one to weaken the +assumptions on the collision freeness of H_s(). The details of these +assumptions and their practical relevance are still subject to debate +(see a 2012 paper by Koblitz and Menezes); however, no practical +attack has been found to date and HMAC is considered secure in +practice. diff --git a/ss2017/cryptography/Notes12.txt b/ss2017/cryptography/Notes12.txt new file mode 100644 index 0000000..a1299d7 --- /dev/null +++ b/ss2017/cryptography/Notes12.txt @@ -0,0 +1,274 @@ +12 Number theory and hardness assumptions +----------------------------------------- + +The next few sections are about *public-key cryptography* (different +keys for encryption and decryption, one public, the other +private). This area makes heavy use of number theory, in particular +arithmetic. In this section we review the necessary mathematics and +formulate hardness assumptions on which the security of public key +cryptography is based. + +We assume standard knowledge about + +- arithmetic: division with remainder, gcd, extended Euclidean +algorithm, i.e. for all integers u,v, there exists integers s, t such +that gcd(u,v)=su+tv, Chinese remainder theorem, modular arithmetic, in +particular inverses modulo. + +- groups: additive and multiplicative notation; exponentiation; the + additive group Z_N (addition modulo N); the multiplicative group + (Z_N)^* of order phi(N) (Euler's phi function); the consequence + x^(phi(N)) = 1 (mod N) and the special case x^{p-1}=1 (mod p); the + group isomorphisms derived from the Chinese remainder theorem (Z_pq + =~= Z_p x Z_q, Z_pq^* =~= Z_p^* x Z_q^*), primitive elements in + Z_p^* (cyclicity of Z_p^*). + +The required knowledge is part of "Logik und Diskrete Strukturen" and +can also be looked up in KL. + +Next, we discuss the computational complexity of various arithmetic +operations. We always measure runtimes in terms of the *sizes* +(lengths in binary representation) of the numbers in question. Notice +that the size of a number n is O(log(n)). The basic arithmetic +operations +,-,*,/ can be performed in polynomial time (in terms of +the sizes) with the standard algorithms taught at school. The same is +true for gcd-computations using Euclid's algorithm. Furthermore, +computing modular powers, i.e. a^b mod N can also be done in +polynomial time using repeated squaring based on the binary expansion +of N. Note though that a^b cannot be computed in polynomial time +simply because the result is too long. + +Testing whether a given number n is prime can also be done in +polynomial time; the most efficient algorithms for this use +probabilistic polynomial time computation, however. This means that +one has randomised algorithms which given a number n answer either +"composite" in which case n is definitely composite or "prime" in +which case n is prime except for a negligible error probability. The +simplest of these tests is the Miller-Rabin test (KL 7.2.2). + +Using such a primality test it is also possible to generate a random +prime number of a given size s. To that end one chooses random n of +size s and then tests n,n+1,n+2,n+3,... for primality until a prime +number has been found. Theorems about the distribution of prime +numbers assert that this search is successful after a small (in any +case expected polynomial) time. + + +Factoring +- - - - - + +The factoring problem asks the following question. Given a natural +number N find a non-trivial factor of N unless N is prime (as usual +the trivial factors are 1 and N). + +If N is even or has some other small divisor then this question is +easily solved by trial division (the factoring method taught at +school). If, however, N has only large factors, e.g. is the product of +two primes of roughly equal size then factoring is believed to be a +very hard problem and at any rate no efficient algorithm is +known. Notice that trial division is linear in sqrt(N) hence +exponential in the size of N. (sqrt(N)=2^{1/2*log(N)}). There do exist +better algorithms for factoring, but with today's technology finding +out the factors of a product of two ~512bit primes must be considered +infeasible with a broad security margin. + + +RSA Cryptosystem +- - - - - - - - - +It is believed to be hard to reconstruct x from x^e knowing merely N +and e so this procedure is used as the basis of a public key +cryptosystem: RSA. Intuitively, Enc_e(x)=x^e mod N and Dec_d(y)=y^d +mod N. The encryption key e can be publicized whereas the decryption +key d must be kept private. + +Consider the situation where N=pq for primes p,q. The ring Z_N of +integers mod N contains phi(N)=(p-1)(q-1) invertible elements. Recall +that x:Z_N is invertible if gcd(x,N)=1. The elements with a gcd > 1 +are the multiples of p and of q of which there are (q-1) + (p-1) + 1 +with the last summand corresponding to 0=pq. Thus, the number of +invertible elements is pq-q-p+1 = (p-1)(q-1). Equivalently, with the +Chinese Remainder Theorem we have Z_N =~= Z_p x Z_q and the invertible +elements correspond to those pairs (x,y):Z_p x Z_q where x=/=0 and +y=/=0. + +The (multiplicative) group Z^*_N of invertible elements (mod N) thus +has order /* number of elements */ phi(N)=(p-1)(q-1). For each element +x:Z^*_N it holds that x^phi(N) = 1 (mod N) (general result about +groups). + +Now suppose that we have e such that gcd(e,phi(N))=1 and ed=1 +(mod phi(N)). Then we can solve the RSA problem, + i.e. determine x such that x^e = y mod N for given y, N, e. +More precisely, if x:Z^*_N we can recover x from y:=x^e as y^d +(all computations done mod N). Indeed, (x^e)^d = x^{ed} = +x^{t*phi(N)+1} = x (for any t). + + +Security of RSA relative to factoring +- - - - - - - - - - - - - - - - - - - + +If given e we are able to find d such that x^{ed}=x holds for all +invertible (mod N) x then we can find the factors of N as follows: +Namely, in this case, we have a value a (=ed-1) such that x^a=1 (mod +N) holds for all x:Z^*_N. Such value must necessarily be even as can +be seen by taking x=-1. Now we can successively divide a by two until +we have found a value b such that x^{2b} = 1 (mod N) holds for all x +but x^b =/= 1 for some x. The crucial observation is that once x^b =/= +1 for some x then x^b =/= 1 for at least 50% of all x so we can find +such a witness value x by repeated guesses. The reason for the 50% +bound is that {x | x^b=1} is a proper subgroup of Z^*_N and its order +must therefore be a proper divisor of |Z^*_N|=phi(N). + +So, summing up, we are in possession of a value b such that x^{2b}=1 +for all x, but x^b=1 not for all x. Let us consider u := x^b mod p and +v := x^b mod q. Since u^2=v^2=1 we have u,v:{-1,1}. Moreover, by the +Chinese Remainder Theorem, we have Z_N^* =~= Z_p^* x Z_q^* so that if +x is chosen uniformly at random then u and v are also uniformly at +random and independent. As before, if one of them *may* be =/=1 then +this happens for at least 50% of them. As a result, under the +assumptions, the event u*v=-1 has a a likelihood of at least 50% and +in this event gcd(x^b-1,N) yields a nontrivial divisor of N. + + +Unfortunately, there is no known reduction from RSA to factoring in +the sense that we would be able to prove that RSA is semantically +secure on condition that factoring is hard. Namely, notwithstanding +the above, it might be possible to break RSA without actually +producing an exponent d such that x^ed=1 mod N. To date, it is not +known whether RSA is sec ure relative to factoring, let alone in +itself. + + +RSA hardness assumption +- - - - - - - - - - - - + +The computational hardness of RSA is thus not proven and not reducible +to factoring but at least to some extent plausible. It is thus +justified to formulate the following RSA hardness assumption. + +There exists a randomised polynomial time algorithm GenRSA() which +given security parameter n produces (N,e,d) such that N is the product +of two primes N=pq and d = e^{-1} mod phi(N) and such that the following +experiment has negligible success property for all probabilistic polynomial time adversaries A: + +RSA-inv_A(n): + +1. Run GenRSA(n) to obtain (N,e,d) +2. Choose x<-Z^*_N +3. A is given N,e, and x^e mod N and outputs x' +4. The output of the experiment is 1 if x=x' and 0 otherwise. + + +It is believed that the RSA assumption holds with GenRSA(n) selecting +two random primes of length n, choosing e at random and outputting +(pq,e,e^{-1} mod phi(N)). + + +Groups for cryptography +- - - - - - - - - - - - + +A *group generating* algorithm G(n) is a probabilistic polynomial time +algorithm which given security parameter n produces a description of a +group G_n whose order is polynomial in n. The description of the group +comprises generators, a well-formedness test, testing whether a given +bitstring encodes a group element or not and algorithms implementing +multiplication and inverses on these representations. + +For example, G(n) might determine a random prime p of length n and +then return an algorithmic description of the group Z_p^*. As for a +generator, it could produce a primitive element. + +For some applications, groups of prime order are preferred. One +example of those is the following: If q is a prime such that p=2q+1 is +also prime (p is then called a "strong prime") then the subgroup of +Z^*_p consisting of the elements of the form y^2 for y:Z_^*p (the +quadratic residues mod p) form a subgroup of Z^*_p of order q which by +assumption is prime. + +Further examples are furnished by groups of points on an elliptic +curve. The elements of such a group are pairs (x,y) of elements of +a finite field GF(q) (q prime) such that + + y^2 = x^3 + Ax + B + +holds for fixed parameters A, B which thus determine the elliptic +groups. In addition to these pairs (x,y) the group contains a special +element O. + +For example, if the field is GF(7) = Z_7 and A=B=3 then the group (the +elliptic curve) has elements (1,0), (3,2), (3,5), (4,3), (4,4), +O. Indeed, whenever x^3+3x+3 is (zero or) a quadratic residue mod 7 we find (one +or) two points and otherwise not. + +The group operation, i.e. how elements of the group are added (or +multiplied, depending on notation), is omitted for now. +We come back to it later. + + + + + +Discrete logarithm and Diffie Hellman +- - - - - - - - - - - - - - - - - - - + +Given a cyclic group G with generator g the discrete logarithm problem +is the following: given h:G determine e such that h=g^e. Formally, +suppose that we are given a group generating algorithm G(n) outputting +for each n a cyclic group G_n and a generator g. + +For adversary A the experiment DLog_{A,G}(n) then is the following: + +1. Run G(n) to obtain (G,q,g) where G is a cyclic group of order q +with generator g. + +2. Choose h<-G /* e.g. by putting h=g^d for d<-Z_q */ +3. A is given G,q,g,h and outputs e:Z_q +4. The output of the experiment is 1 if g^e = h + +By definition, the discrete logarithm problem is hard for G() if for +all adversaries A one has Pr(DLog_{A,G}(n)=1) = negl(n). + +It is generally believed that discrete logarithm is hard for the +aforementioned example groups. + +Related problems are computational Diffie-Hellman (CDH) and decisional +Diffie-Hellman (DDH). + +Computational Diffie-Hellman: given a cyclic group G of order q and +generator g as above and h=g^x, h'=g^y determine (without knowing x,y !) +the value g^{xy}. + +Decisional Diffie-Hellman: given a cyclic group G of order q and +generator g as above and h=g^x, h'=g^y and h''=g^z determine (without +knowing x,y,z !) whether or not g^{xy}=g^z. + +Clearly, a solution to the discrete logarithm problem implies a +solution to Diffie-Hellman, but the converse is not known. As a +result, hardness of discrete log is a weaker assumption than hardness +of DDH (and CDH) + +Diffie-Hellman is important for the eponymous Diffie-Hellman +key-exchange protocol: In order to share a common secret key Alice may +choose random x:Z_q and send u=g^x to Bob. Bob does the same and thus +sends v=g^y to Alice. Now, Alice and Bob can both compute the shared +key g^{xy} as u^x (Alice) and v^y (Bob). We will show later that +assuming DDH is hard this scheme is secure in a precise sense. + +Formal definition of hardness of DDH: + +Given a group-generating algorithm G() producing cyclic groups as +above, we say that the decisional Diffie Hellman problem is hard for +G() if for all probabilistic polynomial-time adversaries A and all n we have + + |Pr(A(G,q,g,g^x,g^y,g^z)=1) - Pr(A(G,q,g,g^x,g^y,g^{xy}))| = negl(n) + +where G(n)=(G,q,g) and x,y,z <- Z_q. + +Thus, DDH is hard, if g^{xy} looks like a random element of G even if +g^x and g^y are known. + +We close this chapter by remarking that under the assumption that RSA +is hard thre exist pseudo random generators, pseudorandom functions, +and permutations (see KL6 and 7.4.1). Under the assumption that +discrete logarithm is hard for some group then there exist collision +resistant hash functions. (KL7.4.2). diff --git a/ss2017/cryptography/Notes13.txt b/ss2017/cryptography/Notes13.txt new file mode 100644 index 0000000..b8e5f0a --- /dev/null +++ b/ss2017/cryptography/Notes13.txt @@ -0,0 +1,162 @@ + + +13 Diffie-Hellman key exchange and RSA +-------------------------------------- + + +Diffie Hellman +- - - - - - - - + +As already mentioned, the Diffie-Hellman key exchange system allows +two people, say Alice and Bob, who do not share any secret information +to obtain a shared secret key (which can then for example be used for +subsequent private key cryptography). It thus avoids the need for the +sharing of secret keys which is difficult in practice and involves +trusted third parties or similar (see KL9.1-3 for a discussion). + +We now formalize what should be expected from such a key exchange protocol: + +The key exchange experiment KE^eav_{A,Pi}(n): + +1. Two parties both holding n execute the protocol Pi. This results in + a transcript trans containing all messages exchanged and a string + ("key") k:{0,1}^n that is output by both parties. Thus, both + parties must output the same key. + +2. b<-{0,1}. if b then k':=k else k'<-{0,1}^n +3. Adversary A is given trans and k' and outputs a bit b'. +4. Output = 1 iff b'=b + +The protocol Pi is deemed secure if the success probability for any +prob.polytime adversary A is bounded by 1/2+negl(n). + + +The Diffie-Hellmann protocol Pi for some cyclic group (generating +algorithm) G() now works as follows: + +1. Alice runs (G,q,g) := G(n) and sends (G,q,g) to Bob. +2. Alice chooses x<-Z_q and computes h1:=g^x +3. Alice sends (G,q,g,h1) to Bob +4. Bob chooses y<-Z_q and sends h2:=g^y to Alice. Bob then outputs k_B:=h1^x +5. Alice outputs k_A:=h2^x /* Note that k_A=k_B=g^{xy} */ + +We will now show that the Diffie-Hellman protocol is secure under the +assumption that DDH is hard for the group in question and the further +assumption that the random key k' chosen in the KE^eav experiment is a +random element of G rather than an arbitrary random string. Let us +call KE'^eav the thus modified experiment. We note that a random group +element can be taken of the form g^z for z<-Z_q. + +We now have + +Pr(KE'^eav_{A,Pi}(n)=1) = 1/2*Pr(KE'^eav(n)=1 | b=1) + 1/2*Pr(KE'^eav(n)=1 | b=0) = +1/2*(Pr(A(G,g,q,g^x,g^y,g^{xy})=1)+ Pr(A(G,g,q,g^x,g^y,g^z)=0)) = +1/2+1/2*(Pr(A(G,g,q,g^x,g^y,g^{xy})=1)- Pr(A(G,g,q,g^x,g^y,g^z)=1)) <= +1/2+1/2*|Pr(A(G,g,q,g^x,g^y,g^{xy})=1)- Pr(A(G,g,q,g^x,g^y,g^z)=1)| <= +1/2 + 1/2*negl(n) /* assuming hardness of DDH for G() */ + +We remark that while (under assumptions) Diffie-Hellman is secure +against passive eavesdroppers it is vulnerable against more active +adversaries that may also send, modify, and swallow messages during +the run of the protocol. Achieving security against those requires +some means of authenticating messages sent between the parties; a +precise formulation of the additional assumptions needed for this is +beyond the scope of this book. + + + +Public key cryptosystems +- - - - - - - - - - - - - + +We give a formal definition of a public key cryptosystem and its +security. + + +Definition: a public key cryptosystem Pi comprises + +-) a (probabilistic) key generation algorithm Gen() which given + security parameter n outputs a pair of keys (pk,sk) /* public, secret + */ + +-) a (probabilistic) encryption algorithm which given plaintext m from +some message space and the public key pk produces a ciphertext c: +c<-nc_pk(m) + +-) a deterministic decryption algorithm which given ciphertext c and +the secret key sk produces a plaintext m<-Dec_sk(c) in such a way that +if c<-Enc_pk(m) then Dec_pk(End_sk(m)) = m. + + +Definition: A public key scheme Pi is semantically secure in the +presence of an eavesdropper if the for all (prob. polytime) +adversaries A the success probability in the following experiment is +bounded by 1/2+negl(n). + +Experiment PubK^eav_{A,Pi}(n): + +1. (pk,sk)<-Gen(n) +2. Adversary A is given pk and outputs messages m0 m1 +3. b <- {0,1}; c <- Enc_pk(m_b); c is given to A +4. A outputs a bit b' +5. Outcome is 1 if b=b' and 0 otherwise End of definition + + +We notice that this is just like semantic security in the private key +setting except that the adversary has access to the public key which +after all is supposed to be public. This means that, since by +Kerckhoff's principle, the encryption algorithm is also public, the +adversary has access to an encryption oracle and thus---in the public +key setting---semantic security in the presence of an eavesdropper +(the one above) is as powerful as cpa security. + +This has the consequence that no public key cryptosystem in which +Enc_pk() is deterministic can be semantically secure. Indeed, all the +adversary has to do in this case is to precompute the encryptions of +its chosen messages m0 and m1. + +We remark that a semantically secure public key cryptosystem can be +combined with any cps-secure private key system by first using the +public key to transmit a secret key. This is known as *hybrid +encryption*. One can show (Theorem 10.13 of KL) that hybrid encryption +yields semantically secure public-key encryption schemes. + + + +RSA cryptosystem +- - - - - - - - - + +For this reason, the "textbook RSA" cryptosystem, as indicated in the +last chapter, is actually insecure. In order to make it work, it must +be enhanced with randomization for example as follows. + +Fix a length function l(n). + +Gen(): On input n run GenRSA(n) to obtain (N,e,d). Output + pk=(N,e) and sk=(N,d) +Enc(): On input m:{0,1}^l(n) and pk=(N,e) choose + r<-{0,1}^{||N||-l(n)-1} and output c=(r||m)^e mod N + /* the -1 is there to make sure that r||m is in Z_N^* */ +Dec(): On input c and sk=(N,d) compute m'=c^d mod N and output the l(n) + low-order, i.e. rightmost, bits of m' + +Now, if the "padding" r is too short, then this does not help because +an adversary could try out all possible values for r. It is believed +that when r has a length comparable to |m|, then the above scheme is +secure (relative to the RSA assumption), but unfortunately, no proof +has been found. According to KL (Theorem 10.19) one can show that the +scheme is secure when l(n)=O(log(n)), again under the RSA +assumption. Note that this means that in order to increase the message +size by just one bit one has to double the security parameter and +hence the length of the modulus N and the ciphertexts. + +In practice, one does not want to waste so much bandwidth on the +padding and uses heuristic schemes like e.g. RSA-PKCS#1v1.5 which uses +a random padding string of length at least 64bit. + +Another, more modern, method is RSA-OAEP which mixes the padding with +the actual plaintext by way of a Feistel network of cryptographic hash +functions. Intuitively, this makes the input to the actual RSA +encryption look like a random string which then makes the RSA +assumption applicable. Viewed more practically, it prevents attacks +which only recover parts of the plaintext. In the random oracle model +(Lecture 16) RSA-OAEP can be proved semantically secure. diff --git a/ss2017/cryptography/Notes14.txt b/ss2017/cryptography/Notes14.txt new file mode 100644 index 0000000..e6075ff --- /dev/null +++ b/ss2017/cryptography/Notes14.txt @@ -0,0 +1,208 @@ +14 El Gamal and elliptic curve cryptography +------------------------------------------- + +The El Gamal cryptosystem is based on the DDH assumption and is +provably secure under the assumption of the latter. Just like DH-key +exchange it is parametrised by a group (generating algorithm) G(n) and +works as follows: + +Gen(n) : + (G,q,g) = G(n) + x <- Z_q + h <- g^x + pk = (G,q,g,h) + sk = (G,q,g,x) + output (pk,sk) + +Enc_(G,q,g,h)(m) : + check that m:G + y <- Z_q + c = (g^y,h^y*m) + output c + +Dec_(G,q,g,g,x)(c1,c2) : + m = c2 / c1^x + output m + + +Let us first see that this scheme is correct: If c1=g^y and c2=h^y*m +where h=g^x then c2 / c1^x= g^(xy) * m / g^(xy) = m + +We also notice that messages and ciphertexts are actually elements of +the group G which must therefore by somehow encoded as binary +strings. This can be done in various ways for the various groups, see +KL for details. + +Theorem: If the DDH assumptions holds for a group (generating +algorithm) G() then the El Gamal cryptosystem basd on G() is +semantically secure. + +Proof: Let A be an adversary against the El Gamal system and let its +success probability be 1/2+eps(n). We must show that eps(n) is +negligible. We construct from A an adversary A' as in the DDH +assumption. + +Suppose that A' receives g^x, g^y, u where u is either g^(xy) or g^z +for random z and A' is to decide which of the two. + +We forward (G,q,g,g^x) as "public key" to A and wait for it to output +m0,m1:G. We choose a random bit b and build c = (g^y,u*m_b) and let b' +be the bit that A returns. + +If u=g^(xy) then A is played with according to the rules of the El +Gamal cryptosystem and therefore b'=b with probability 1/2+eps(n). If +u=g^z for random z then u*m0 is also uniformly random (since x|->x*m0 +is a bijection G->G) and therefore the probability that b'=b is +exactly 1/2. The difference between the two probabilities is precisely +eps(n) which under the DDH assumption will be negligible. QED + + +Elliptic curve cryptography +- - - - - - - - - - - - - - + +As already mentioned, elliptic curves furnish a large reservoir of +cyclic groups for which taking discrete logarithms, CDH, and DDH are +believed to be hard. With existing algorithms, solving these problems +on elliptic curve groups is consistently harder than doing so for +groups of invertible elements mod p or in a finite field. + +Recall that an elliptic curve over some field F of characteristic =/= +2,3 is defined by two constants a, b and comprises the points (x,y) +that solve the equation + + y^2 = x^3 + ax + b + +Here, one assumes that the *discriminant* 4a^3+27b^2 =/= 0 for +otherwise the curve might be *singular*, i.e. contain anomalies like +isolated points, sharp bends ("cusps") or similar. When viewed over +the reals such a curve looks roughly as follows: + + | | + | / + - | - / + / | \ _ - + | | +--------------------------------------------------------------------- + | | - _ + \ | / \ + -| - \ + | | + +Depending on the parameters the knob to the left may also become +detached and form a closed loop sitting to the right. In either case +whenever a line intersects the curve in two points it meets it again +in a third point except when the line is parallel to the y-axis in +which case we say that the third point of intersection is at infinity, +here denoted O. + +This property also holds for curves over other fields, in particular +finite ones which are of interest for cryptography. There is an +explicit formula for obtaining the third point of intersection. To +wit, if (x1,y1) and (x2,y2) lie on the curve then the line through +them is y=m(x-x1)+y1 where m=(y2-y1)/(x2-x1). Plugging this into the +curve yields + + (m(x-x1)+y1)^2 = x^3+ax+b + +The three solutions of this equation are x=x1, x=x2, x=m^2-x1-x2, so +the last one is the desired third point of intersection. + +Now, it is a remarkable fact that the points on the curve together +with O form an abelian group, traditionally written additively, where +the sum of points P and Q is obtained by first taking the third curve +point on the line through P and Q, call it R=(x_R,y_R), and then +reflecting R on the x-axis, i.e. P+Q=(x_R,-y_R). + +This, however, only applies when P=/=Q and when P and Q do not have +the same x-coordinate. In the latter case, one has P+Q=O, the special +point at infinity. In the former case, i.e. when P=Q, one must take +the tangent through P and intersect it with the curve. + +One can show using implicit differentiation that the coordinates of +that point are given by + + (((3x_1^2+a)/2y_1)^2 - 2x1, -y1+((3x_1^2+a)/2y_1)^2(x1-x2)) + +and this formula, just as the one above for the general case, also +makes sense for finite fields where there are no "tangents". Yet +another special case is when P or Q is O. One simply puts O+P=P+O=P. + +Curves over fields of characteristic 2 or 3 are also possible, but +then both the defining equations and the formulas for addition of +points become slightly different (notice e.g. that in the formula +above we divide by 2). We refer to the literature, but stress that it +is very important not to make mistakes with the implementation of the +addition formulas and that doing so has lead to security flaws. + +We have already seen that addition of points is well-defined and +commutative. It is also clear that the inverse of a point (x,y) is +given by (x,-y), i.e. reflection on the x-axis. Associativity of +addition follows from nontrivial results, e.g. the Weierstrass +p-function, but can in principle also be validated "by hand" on the +basis of the above formulas. + +For integer n and point P on a curve we use the notation n.P for +P+P+...+P with summands. This is the same as the exponent notation in +multiplicatively written groups. Therefore, the "repeated squaring" +method can be used here as well: + + 100.P = 4.P+32.P+64.P = 2.(2.(P + 2.(2.(2.(P+2.P))))) + +Now, the plan is to use the groups coming from elliptic curves for +cryptosystems like Diffie-Hellman key exchange or El Gamal. For this +to work, a couple more considerations are in order: we need to encode +plaintexts as points on the group and we need to ascertain that the +group is cyclic or else move to a cyclic subgroup. + +In order to find a cyclic group one can rely on one of the publicly +available and recommended curves. Many of them have a prime number of +points and hence are cyclic with any element other than O being a +generator. Alternatively, one can try out random coefficients a and b +until one finds a curve with a prime number of points. To do this, one +needs to invoke Schoof's algorithm which allows one to determine the +number of points on a given elliptic curve. + +If one would like to use a curve with a nonprime number, say N, of +points, then one must factor N and it is then important that N has a +large prime factor p, i.e. p>sqrt(N). In this case, by the +representation theorem for finite(ly generated) abelian groups there +is a subgroup of order p and any of its nonzero elements are +generators. Moreover, the remaining subgroups have smaller order. To +check whether a point P is in the subgroup of order p it suffices to +check that p.P = O. To obtain a point in that subgroup one can pick a +random point P and if Q := N/p.P =/= O then p.Q is in the subgroup, +hence Q can serve as a generator. + +For the most, however, one uses one of the already publicised elliptic +curves such as those recommended by the NIST "for government use". +See http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf +There is no need to choose a "fresh" curve for every application and +on the other hand, some curves are "weak" and should be avoided. + +In order to encode plaintexts as points we can proceed as +follows. First, we note that it suffices to store the x-coordinate of +a point and a single bit telling whether the y-coordinate is above or +below the x-axis, i.e., which of the two square roots of x^3 +ax+b are +meant. This is known as point compression. As for the x-coordinates +one fixes a bijection alpha between bitstrings of length l=log(q) and +field elements. Now one puts t=l-k where k is chosen sufficiently +large. Then, to encode message x of length t one searches for a string +z of length k so that alpha(x||z) has a square root y over GF(q), +i.e., is a quadratic residue. At that point, (alpha(x||z),y) can be +taken as the desired encoding of x as a curve point. For random +padding z the chance for alpha(x||z) to be a quadratic residue is +about 1/2, so after a short number of iterations one is almost sure to +find an appropriate encoding. We also remark that there exist +efficient algorithms for testing whether a given field element is a +quadratic residue and if so to compute its square root. + +With all this machinery in place, the Diffie-Hellman and El Gamal +cryptosystems can be used with elliptic curve groups without any +change, bearing in mind, of course, that instead of exponentiation +g^x, we now use multiplication x.P and instead of multiplication we +use addition, so that, e.g. the encryption of message m encoded as a +point M becomes (y.P,y.Q+M) where P is the generator and Q=x.P + +We close by remarking that since the early 2000 elliptic curve +cryptography (ECC) has become more and more common. Also the bitcoin +cryptocurrency uses it. diff --git a/ss2017/cryptography/Notes15.txt b/ss2017/cryptography/Notes15.txt new file mode 100644 index 0000000..e76ada5 --- /dev/null +++ b/ss2017/cryptography/Notes15.txt @@ -0,0 +1,279 @@ + + +15 Factoring and computing discrete logarithms +---------------------------------------------- + +In this chapter we survey algorithms for factoring large numbers, in +particular products of equal sized primes, and for computing discrete +logarithms. These algorithms or rather their runtime provide lower +bounds on the necessary key lengths for public key cryptography for it +relies on the difficulty of these problems. + +For the sections about factoring we let N=pq be a product of two +roughly equal sized primes and n = O(log(N)) be the length of N in +binary. The task is to find p,q from N. + +For the sections about discrete logarithms let G be a cyclic group of +order q and g,y:G with g a generator. The task is to find x:Z_q such +that g^x=y. + +Trial division +- - - - - - - - + +In order to factor N=pq, i.e. to find p or q given N, we can try out +divisors d=1...sqrt(N). The runtime of this is polynomial in sqrt(N), +hence takes time exponential in n. Once n>120, hence ||sqrt(N)||=~=60 +this is no longer feasible. + + +Pollard's p-1 method +- - - - - - - - - - - + +Pollard's p-1 method may help when p-1 is a product of powers of small +primes. We let p_1,...p_k be the first k primes and construct + + B_k = prod_{i=1..k}p_i^{n / ||p_i||} + +The exponent n/||p_i|| is chosen so that if some power of p_i divides +p-1 then that power is at most n/||p_i||. As a result, if p-1 is a +product of powers of primes from among the set {p_1..p_k} then p-1 | +B_k. If, in addition, q-1 does *not* divide B_k then we can find out p +as we show shortly. In order that q-1 does *not* divide B_k we can +repeatedly execute the method with increasing values for k hoping that +at some point one of the two prime factors "works" and the other does +not. + +OK so, now let B any number so that p-1 | B and q-1 does not divide +B. For any x it holds that x^B mod p = 1 whereas with constant +probability x^B mod q =/= 1. The former holds since the order of Z_p^* +is p-1 and B is a multiple thereof. The latter holds since when x is a +generator of Z_q^* then x^B mod q is not 1 and the proportion of those +generators is about 50% (not hard to see or use Thm B.15 of KL). + +Now let y = x^B-1 mod N. We have y mod p = 0 and y mod q =/= 0. Thus, +p divides y and q does not divide y so gcd(y,N)=p. + +The resulting algorithm is now as follows: + +for k=1,2,3,... do the following until either a factor of N is found +or computing resources are exhausted. + Put B = B_k + for a certain number of times do the following + x<-Z_N + d = gcd(x^B-1 mod N,N) + if d=/=1 then a factor of N has been found. + + + +Pollard's rho method +- - - - - - - - - - - + +This algorithm is based on the observation that once we have two +distinct values x,y:Z_N such that x mod p = y mod p then p = +gcd(x-y,N). Thus, factoring amounts to finding a collision in the +"hash function" H(x) = x mod p. Notice that while we cannot compute +this function we can detect whether x,y constitute a collision by gcd +computation. + +Now, by the birthday paradox, a random set of size S := 2*sqrt(p) = +O(N^{1/4}) contains such a collision with likelihood 50%. Finding it, +requires S^2 collision tests thus, when implemented naively, this +method is no better than trial division. + +However, the constant space method for collision detection described +earlier only has a runtime of O(S), but of course, as already +mentioned, we cannot compute H(). However, we can replace it with any +function F which has the property that x = y (mod p) implies F(x)=F(y) +(mod p) and which is such that for random x0 the set +{x_0,F(x_0),F(F(x_0)),..., F^S(x_0)} is also sufficiently close to a +random set so that it is likely to contain a collision. The function +F(x)=x^2 + b for some b =/= 0, -2 mod N is believed to have this +property and at any rate behaves well in practice. Just as in the +earlier algorithm we have that F^i(x0) = F^j(x0) (mod p) implies +F^k(x0) = F^{2k}(x0) (mod p) for some k. + +So, the set of the first S iterates of F() starting from random x0 is +likely to contain a collision. But since once x,y form a collision so +do F(x), F(y), it suffices to search for a collision among the pairs +F^k(x0), F^{2k}(x0) which leads to the following algorithm: + +b <- Z_N \ {0,-2} +F(x) = x^2+b mod N + +x <- Z_N +y = x +for k=1..2*sqrt(N) do + x = F(x); y=F(F(x)) + if gcd(x-y,N) != 1 a factor is found. + +repeat the whole procedure until either a factor is found or resources +are exhausted. + +Assuming that the function F() has the required properties (which has +not been proved to this date!) the runtime of this algorithm is +proportional to N^{1/4} which is still exponential in n but requires +one to double n if one wants to stay immune against this +method. + + +The quadratic sieve method +- - - - - - - - - - - - - - + +The starting point for the most efficient factoring algorithms to this +date is the following observation made by Pierre de Fermat: + +If we succeed in expressing N as the difference of two +squares N=x^2-y^2 then N=(x+y)(x-y) so we have factored N. + +Fermat suggested to try out successive values for x starting at +sqrt(N) and for each of those checking whether x^2-N is a square. + +The first improvement one can make on this observation is that it +suffices that N divides x^2 - y^2 for if kN = (x+y)(x-y) +then---assuming that x != (+/-)y mod N---the factors p and q of N +must straddle the product so that gcd(x-y,N) or gcd(x+y,N) will be +different from 1. + +Thus, we seek x,y:Z_N such that x^2-y^2 = 0 (mod N) and x !=y, x!=-y mod N. + +Notice that by the Chinese Remainder Theorem each square has four +roots modulo N, so given x, two out of the four roots of x^2 are good. + +Now, to find such x,y more efficiently we proceed as follows. We +select a set B of small primes and try out various values x>sqrt(N) so +that x^2 mod N can be factored (because after reduction mod N it is +sufficiently small) and its factors are in B. In this way, we find +numbers x_1 .. x_l such that each x_i^2 mod N is expressed as a +product of primes in B. + +With each of these numbers x_i we associate a B-indexed 0,1 vector +whose entry at p:B is the exponent of p in the factorisation of x_i +modulo 2. + +For example, if B={2,3,5,11} and x_1^2 mod N is 2^5*3^2*11^2 then the +associated vector is (1 0 0 0). + +If l exceeds the size of k then there is a (mod 2) linear combination +of these vectors which results in the all zero vector. But multiplying +the corresponding x_i together then yields a square because all prime +factors have even exponents. + +Continuing the example, if x_2^2 mod N is 2^15*11, i.e. (1 0 0 1), and +x_3^2 mod N is 11^13, i.e. (0 0 0 1) then, since 1000+1001+0001=0000, +we obtain the following identity mod N: + + (x_1*x_2*x_3)^2 = (2^10 * 3 * 11^8)^2 + +and, heuristically, we may assume that there is a 50% chance for this +identity to be nontrivial in the sense that it yields a good pair of +square roots. + +Summing up, we build up a large basis of values x whose squares mod N +can be completely factored, then compute a linear combination (mod 2) +of the zero vector from the corresponding B-indexed vectors and check +whether the resulting identity of squares mod N is nontrivial which +then yields the desired factor. + +We now study the problem of finding discrete logarithms in a cyclic +group G as above. + + +The Pohlig-Hellman algorithm +- - - - - - - - - - - - - - - + +If we have a factorisation of the group order q as prod_{i=1}^n q^i +with the q_i relatively prime (gcd = 1) then, if we have values x_i +such that + + (g^{q/q_i})^x_i = y^{q/q_i} + +we can find x by solving (using the Chinese Remainder Theorem) the +system of modular equations + + x mod q_i = x_i + +Since g^{q/q_i} generates a subgroup of order q_i which is easier if +the q_i are small. It remains to see why x satisfies the above system +of equations. Indeed, if g^x=y then g^{q/q_i}^x = y^{q/q_i} so x mod +q_i solves the discrete log problem of order q_i. + +It remains to see how to deal with groups whose order is a prime power +q=p^f. In this case, one can expand the unknown x as + + x = x_0 + x_1 * p + x_2 * p^2 + ... + x_{f-1} p^{f-1} + +Now, by exhaustive search or using any other algorithm we can +determine x_0:Z_p such that g^{q/p}^{x_0} = y^{q/p} (mod p). Once we +know x_0 we can then recursively solve (g^p)^{x'} = y/g^{x_0} which +yields x_1,... The details are left as an exercise. + + +The giant-step baby-step algorithm +- - - - - - - - - - - - - - - - - - + +Here the idea is that the unknown x can be decomposed as x = +t*[sqrt(q)] + s for some s {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. diff --git a/ss2017/cryptography/Notes17.txt b/ss2017/cryptography/Notes17.txt new file mode 100644 index 0000000..6a15827 --- /dev/null +++ b/ss2017/cryptography/Notes17.txt @@ -0,0 +1,194 @@ +17 Digital signatures +--------------------- + +Digital signatures are the public key analogues of message +authentication schemes (MAC). They allow a *signer* to authenticate a +message with their *private key* by producing a tag that can +subsequently be verified by anyone who has the corresponding public +key. Just as with MACs the tags are specific to the message being +signed. Changing the message in any way should invalidate the tag, +thus the "signature". Also no-one who is not in the possession of the +private key corresponding to the public key used for verification +should be able to produce a valid signature. + +Definition: a signature scheme is a triple Pi=(Gen,Sign,Vrfy) of ppt +algorithms where + +1. Gen(n) produces a public/private key-pair (pk,sk) + +2. The signing algorithm Sign takes a secret key and a message m and +produces a signature sigma<-Sign_sk(m). + +3. The (deterministic) verification algorithm Vrfy takes a public key, +a message m, and a signature sigma, and answers 1 or 0. If +sigma<-Sign_sk(m) then Vrfy_pk(m,sigma) must return 1. + +If Sign_pk is defined only for messages of length l(n) for some +function l() then we speak of a *fixed length* signature scheme. + +The signature scheme Pi=(Gen,Sign,Vrfy) is *secure* if the +success probability of the following experiment is negligible for any +ppt adversary A: + +Experiment Sig-forge_{A,Pi}(n): + +1. (pk,sk)<-Gen(n) + +2. A gets n, pk, and oracle access to Sign_sk(). The adversary then +outputs (sigma,m). Let Q be the sequence of questions to the oracle +posed so far, i.e. messages for which a signature has been requested. + +3. The outcome of the experiment is 1 iff Vrfy_pk(m,sigma)=1 and m is not in Q. + +End of definition. + +In KL our "secure" is called "existentially unforgeable under an adaptive +chosen-message attack" to differentiate from other, weaker notions of +security. + + +Insecure signature based on textbook RSA +- - - - - - - - - - - - - - - - - - - - - + +A naive attempt at defining a signature scheme based on RSA goes as +follows: + +Gen(n): (N,e,d)<-GenRSA(n);pk=(N,e);sk=(N,d) + output (pk,sk) + +Sign_{(N,d)}(m): + output m^d mod N + +Vrfy_{(N,e)}(m,sigma): + output 1 iff sigma^e = m (mod N) + +Clearly, verification of a valid signature succeeds but the scheme is +insecure for several reasons. First, if an adversary can choose an +arbitrary signature sigma first and then fabricate a corresponding +"message" as m=sigma^e mod N. Notice that Vrfy_{(N,e)}(m,sigma) +succeeds, so this adversary will win the experiment with certainty. + +Second, and perhaps more realistically, if the adversary would like to +get a signature on a previously fixed message m it could request +signatures sigma1 for random m1 and sigma2 for m2:=m/m1 (mod N). It is +then clear that sigma1*sigma2 mod N is a valid signature for the +original m. + + +Secure signatures with random oracles +- - - - - - - - - - - - - - - - - - - + +It is possible, but rather inefficient, to construct secure signature +schemes based on the RSA assumption and a collision-resistant hash +function, see KL12.6. In practice, one uses signature schemes based on +cryptographic hash functions which can only be proved secure in the +random oracle model. We thus modify our definition of secure signature +scheme to the effect that both parties now have access to a function +H:{0,1}^n->{0,1}^n which is selected uniformly at random at the +beginning of the experiment. + +In this situation we have the following signature scheme RSA-FDH +("full domain hash"). + +RSA-FDH: + +Gen(n): (N,e,d)<-GenRSA(n);pk=(N,e);sk=(N,d) + output (pk,sk) + +Sign_{(N,d)}(m): + output H(m)^d mod N + +Vrfy_{(N,e)}(m,sigma): + output 1 iff sigma^e = H(m) (mod N) + +In practice, the random oracle H() will be replaced by a cryptographic +hash function such as SHA-2 and the scheme is just like the +abovedescribed insecure one with the exception that the message is +hashed prior to signing. + +Let us see how this prevents the previous two attacks. Firstly, if the +attacker starts with arbitrary sigma then in order to fabricate a +corresponding message it would have to find m such that sigma^e=H(m) +(mod N) and thus for a given H()-value which it *can* compute, namely +sigma^e, find an inverse image, which is infeasible. + +Similarly, in order to perpetrate the other attack it would have to +fabricate for given m two values x and y so that H(x)*H(y)=H(m). +While this is infeasible for truly random H() and not possible with +current knowledge for SHA-2 it is not prevented by mere +collision-resistance. + +Theorem: If GenRSA() fulfills the RSA assumption then RSA-FDA is +secure in the random oracle model. + +Proof: Let A be an attacker in the Sig-forge_{A,RSA-FDA} +experiment. We may fix a polynomial q(n) bounding the queries of A to +H() and also assume that A first queries H(m) for any message for +which it requests a signature or which it finally outputs. We also +assume that A makes exactly q(n) queries. All this is done in order to +save a few case distinctions in the argument. We now build from A an +attacker A' against GenRSA() in the RSA-inv(n) experiment from Chapter +12 as follows. + +Attacker A' against GenRSA: + +Given N, e, y* = x^e mod N we (assuming the role of A') choose +j<-{1..q(n)} and forward the public key pk=(N,e) to A. + +When A makes its i-th query m_i to H() we answer as follows: + +If i=j we return y*. If m_i has been asked previously, i.e., if +m_i=m_j for some j