IY3660 Applications Of Cryptography Week 9 Lecture PDF

IY3660 – Applications of Cryptography Week 9 Lecture Public-Key Encryption Part 2 Elizabeth Quaglia Information Security Group In today’s lecture The Discrete Logarithm setting and underlying maths Diffie-Hellman key exchange PKE from discrete logs Diff...

IY3660 – Applications of Cryptography Week 9 Lecture Public-Key Encryption Part 2 Elizabeth Quaglia Information Security Group In today’s lecture The Discrete Logarithm setting and underlying maths Diffie-Hellman key exchange PKE from discrete logs Diffie-Hellman Integrated Encryption Scheme (DHIES) Elliptic curve cryptography 2 The Discrete Logarithm setting 3 The discrete logarithm setting Recall that public key schemes are constructed based on algebraic operations The private key operation can be seen as a trapdoor operation The trapdoor operation is usually based on mathematical (hard) problems In RSA, the public key is (e, N) where N is the product of two primes, p,q The private key is an integer d such that de = 1 mod (p-1)(q-1) Security depends on hardness of factoring and related problems Solving discrete logarithms is another example of a mathematical hard problem We will see how this setting supports Diffie-Hellman key exchange Public-key encryption Digital signatures 4 Modular arithmetic over finite fields Recall we define the set of integers modulo a (positive) integer n as Zn = { 0 , 1, 2, …, n-1} with addition, multiplication, exponentation, operations all performed modulo n: a + b = c mod n, where c is the remainder of (a+b) divided by n a ! b = d mod n, where d is the remainder of (a!b) divided by n ak = b mod n, where b is the remainder of (a. a. …. a) [k times] divided by n If the modulus is a prime number p, all non-zero elements of Zp (denoted by Zp*) have a multiplicative inverse: For every a in Zp* = {1,2,…,p-1} there is a unique a-1 such that a. a-1 = 1 mod p You can divide by a non-zero a in Zp , as it is the case for the rational and real numbers We say that Zp , for p prime, is a (finite) field 5 A bit more algebra Let’s consider the set Zp* = {1,2,…,p-1} , for p prime Let’s further restrict to the multiplication operation only We will denote Zp* as G G under the multiplication operation is an example of a group The order of a (finite) group is its number of elements In this case the order of G is p-1 Fact: if a group G has order r, then for every g ∈ G, we have gr = 1 In this case gp-1 = 1 mod p for all elements in Zp* 6 Even more algebra… As before let G = Zp* = {1,2,…,p-1} , for p prime, under multiplication Fact: there is an element g of G = Zp* such that all h in G can be expressed as: h = gk mod p for some k between 1 and p-1. G is said to be a cyclic group, and g is a generator of G For example, if p=7, we have G = Z7*= {1,2,3,4,5,6} and 3 is a generator of G 31 = 3 mod 7 , 32 = 9 = 2 mod 7, 33 = 27 = 6 mod 7, 34 = (32)2 = 4 mod 7, 35 = (34).3 = 12 mod 7 = 5 mod 7 36 = (35).3 = 15 mod 7 = 1 mod 7 Note that 37 = (36).3 = (1).3 mod 7 = 3 mod 7, and so further powers just run through the same cycle… Notes: G = Zp* is an example of a group Groups arise elsewhere in cryptography, and in many, many more other contexts in mathematics and the sciences Not all groups are cyclic Even when they are, the generator is not necessarily unique E.g., 5 is also a generator of Z7* if G has a subset H which is also a group, then H is said to be a subgroup of G E.g., H = {2, 4, 1} is a cyclic subgroup of G = Z7* of order 3 generated by the element 2 7 The discrete logarithm problem (DLP) Let G = {g,g2,g3,…gr} be a cyclic group of order r generated by g for example, G = Zp* for p prime, of order r = p-1 we saw that gr = 1, and will thus write gr = g0 and take G = {g0,g1,g2,g3,…gr-1} to represent the elements of G The discrete logarithm problem in a cyclic group G of order r: Given a randomly selected element y = gx of G = {g0,g1,g2,g3,…gr-1}, find x In other words, given y such that y = gx for some x in [0,r-1], find x Think of x as being the logarithm of gx mod p when for the base g Recall that, over positive real numbers, if y = ax, then x = loga(y) 8 DLP hardness Over the real numbers, computing logarithms is easy Over arbitrary finite groups, computing discrete logarithms is (generally) hard DLP is not hard in every finite cyclic group, but it is the case for groups used in cryptography Analogy (RSA): computing eth-roots over the reals vs. over integers mod N=p.q Naïve algorithm: keep trying x in [0,r-1] until you have gx = h Applies to any finite group Time complexity: O(r), where r is the order of G i.e., exponential in the bit-size of r We can do better than the naïve algorithm! 9  Solving the DLP The DLP has received intense analysis from mathematicians and computer scientists Several different algorithms exist, but they are beyond the scope of this course If you are curious, check the Further Reading & Research section This is an active area of research, with reasonably recent breakthroughs in related settings Algorithms for solving the Discrete Log problem: the Pollard’s rho (ρ) algorithm and its variants: Can be applied to every group Complexity: O( !), where r is the order of the group Still exponential on the number of bits of r The Index Calculus algorithm: Dedicated algorithm for Zp* (p prime) A DL version of the NFS algorithm (for factorisation) Complexity of the form: exp[(1+o(1)).(32/9)1/3 (log p)1/3(loglog p)2/3] sub-exponential (but super-polynomial) on the bit size of prime p 10 The discrete logarithm setting in public-key cryptography We will work over Zp* = {1,2,…,p-1}, the integers modulo a large prime p The prime p will have a special structure: You can write p as p = kq + 1 where q is also a (reasonably large) prime, and k is some integer In this case the order of Zp* is p-1 = q!k In this case, G = Zp* has a cyclic subgroup H of prime order q now pick h, a random integer mod p, and compute g = hk mod p If g = 1 mod p, try again (this outcome is very unlikely) Fact: this element g ≠ 1 mod p is a generator of a cyclic subgroup of Zp* of order q This order-q subgroup generated by g will be the setting for our DL instantiations 12 The discrete logarithm setting in public-key cryptography We work over the integers modulo a large prime p of form p = k.q + 1 q is also a (reasonably large) prime The discrete log instances set in a subgroup of order q generated by g In typical real-world deployments: p has 1024 or 2048 bits, q has 160 bits Rationale for these choices: Index calculus is subexponential on the bit size of prime p, so p has to be large Pollard’s rho method is exponential on the half bit size of q, so q can be smaller If q has around 160 bits and p has around 1024 bits, we have 80-bit security If q has around 256 bits and p has around 3072 bits, we have 128-bit security 13 Diffie-Hellman key exchange 14 Diffie-Hellman Key Exchange scheme Public-key method for agreeing on a shared secret Introduced in a seminal paper from 1976 that launched public key cryptography But refer to reports of early work done inside GCHQ NOT Public-Key Encryption, but almost there! We will introduce DH in the Discrete Logarithm setting over the (multiplicative) group of (non-zero) integers modulo a prime p Recall: p = k.q + 1, and g generates G, a cyclic subgroup of prime order q in Zp*: G = {g0 = 1, g1,g2, … , gq-1} NB: we can also define an analogous scheme ECDH over the (additive) group of points of an Elliptic Curve G = {O, P, 2P, 3P, …, (r-1)P} of order r 15 Diffie-Hellman Key Exchange In Diffie and Hellman’s original presentation, we have a collection of n users All users make use of the same set of public parameters (p, q, !) Each of the n users Ui picks "# uniformly at random from {0,1,…,q-1} User Ui’s private key is "# ; its public key is $# = ! %& mod p All the public keys $' , …, $# , …, $( are assumed to be available in a public, authentic database To set up a shared, symmetric key between user Ui and user Uj: User Ui computes )#* = ($* )%& = ! %+%& = ! %&%+ mod p; User Uj computes )*# = ($# )%+ = ! %&%+ mod p. Critical point: the keys are the same for the two users! 16 Security of Diffie-Hellman Key Exchange Notice that no communication is needed between any pair of users in order to establish a key! Instead, the users are assumed to have access to the public, authentic database of public keys !" , …, !# , …, !$ An attacker can also learn public keys and would like to compute shared keys For example, it knows !# = & '( mod p and !) = & '* mod p, and would like to recover +#) = & '( '* mod p The underlying algorithmic problem can be stated as follows: Given (p,q,g), and the values ga mod p, gb mod p, find gab mod p This is known as the Computational Diffie-Hellman Problem (CDHP) 17 Security of Diffie-Hellman Key Exchange The Computational Diffie-Hellman Problem (CDHP): Given (p,q,g), and the values ga mod p, gb mod p, find gab mod p If we can efficiently solve the DLP, then we can efficiently solve CDHP: Find a from ga mod p by solving DLP, then compute (gb)a mod p So CDHP is not harder than DLP We don’t know in general whether CDHP is equivalent to DLP This is widely believed to be so This is known to be so in special cases This helps us choose secure parameters for Diffie-Hellman 18 A modern view of Diffie-Hellman Key Exchange Pick random '# ; !# !# = ( $& mod p Pick random '" ; !" = ( $% mod p !" K = (!#)$% mod p K = (!")$& mod p It follows that parties compute the same key K In practice, we view K as a shared secret, from which the actual keys are derived E.g., using a Key-Derivation Function (KDF) 19 A modern view of Diffie-Hellman Key Exchange The modern view of Diffie-Hellman key exchange regards the private values !" and the public values #" = $ %& mod p as being ephemeral That is, they are generated and used only once, setting up a fresh key each time Instead of looking up values in a public database: Users first agree on parameters g, p and q Then select fresh random private values !" , !' Then exchange the corresponding public values #" , #' over a public channel It now seems that any two parties can securely agree upon a key without having had any previous association! 20 MITM attack on Diffie-Hellman Key Exchange An active man-in-the-middle attacker can modify the public values in transit! For example, the attacker can change !" to a value # $ mod p for which he knows z The attacker can then compute the key that user j would compute on receipt of gz mod p, namely, (# $ )%& = (# %& )$ = (!' )z mod p And similarly in the other direction This enables the attacker to convince Alice and Bob that they are talking to each other, while in fact they are both talking to the attacker! It also means that the attacker can decrypt and read the messages between Alice and Bob 21  MITM attack on Diffie-Hellman Key Exchange Pick random +$ , +" ; !$ ′ = ' () mod p Pick random *$ ; !" ′ = ' (& mod p !$′ !$ !$ = ' %) mod p Pick random *" ; !" = ' %& mod p !" !"′ K’ = (!$′)%& mod p = ' () %& mod p K’’ = (!"′)%) mod p = ' (& %) mod p Attacker can also compute K’ = (!")() mod p = ' %& () mod p K’’ = (!$)(& mod p = ' %) (& mod p An active attacker can completely compromise the security of “modern” Diffie-Hellman key exchange This was not an issue in the original set-up: the public-key database was authentic 22 Preventing MITM attack on Diffie-Hellman Key Exchange The modern version requires the authenticity of the public values !" , !# How can this be done? Two solutions: use a MAC or use digital signatures Q: If we had a key for a MAC, why do we need to agree a new key via Diffie-Hellman? A: Forward security: even if the MAC key was later revealed, the new key from Diffie- Hellman would still be secure Q: What additional requirements does the use of signatures bring? A: We now need an assurance of the authenticity of the signature verification keys This is typically done using certificates, CAs, and PKI 23 Public Key Encryption from discrete logs 24 From DH Key Exchange to PK Encryption Diffie-Hellman paper appeared in 1976 https://www-ee.stanford.edu/~hellman/publications/24.pdf (see this week’s Further Reading & Research) Introduced the idea of public-key encryption No concrete example of a public-key encryption scheme Included Diffie-Hellman key exchange Q: Can we get from DHKE to PKE? A: Yes we can! We next define the ElGamal public-key encryption scheme from 1985 25 ElGamal Public-Key Encryption Scheme Public parameters (p,q,g) as usual KeyGen: Pick ! uniformly at random from {0,1,…,q-1}. Set public key to be " = $ % mod p and private key to be ! Enc: given public key " and message M (encoded as an element of Gq): 1. Pick & uniformly at random from {0,1,…,q-1}. 2. Set ' = $r mod p Intuition: Encryption masks message M with Z (mask via 3. Compute ( = " mod p. & multiplication, not XOR). 4. Output the ciphertext C = (', ) * ( mod p). Y gives information to private key owner for computing Z ElGamal Public Encryption Scheme Dec: given private key ! and ciphertext C = (", #’): 1. Check that " is in Gq, return “fail” if not 2. Compute %’ = "! mod p 3. Output ' = #’ ( (% * ),- mod p Correctness of the scheme: #’ ( (% * ),- = (' ( %) ( (% * ),- = (' (./) ( ("!),- mod p = ' ( 0! / ( 0/ ! -1 mod p = ' ( 0!/ ( (0!/) -1 mod p =' 27 Security of ElGamal Public Encryption scheme IND-CPA security for ElGamal encryption can be proven based on a variant of the CDH Problem, called the Decisional Diffie-Hellman (DDH) Problem DDH problem: Given (p,q,g), distinguish the triple (ga, gb, gab) from the triple (ga, gb, gc), where a, b, c are uniformly random values in {0,1,…,q-1} Informal proof of security: Ciphertext includes ! " # mod p where # = %&' mod p If (%&, %', %&') is indistinguishable from (%&, %', %)), then we can “replace” # = %&' by # = %) But, since %) can take any value in Gq, it follows that ! " # mod p is uniformly random in Gq Hence ! is perfectly hidden! 29 DHIES 30 Diffie-Hellman Integrated Encryption Scheme (DHIES) ElGamal has two significant disadvantages: It is not IND-CCA secure Messages need to be encoded as elements of Gq Usually inconvenient to work with DHIES addresses both problems 31 DHIES Public parameters (p,q,!) as usual, " a hash function KeyGen: Pick # uniformly at random from {0,1,…,q-1} Set public key to be $ = !# mod p and private key to be # Enc: given public key X and message M (a bit-string): 1. Pick r uniformly at random from {0,1,…,q-1} 2. Set & = !r mod p 3. Compute ' = $( mod p 4. Set ) = "(', $, &) 5. Split ) into Ke and Km 6. Compute C’ = EtM(M) using keys Ke and Km for encryption and MAC, respectively 7. Output the ciphertext C = (Y, C’) 32 DHIES Dec: given private key ! and ciphertext C = (Y, C’): 1. Check that Y is in Gq, return “fail” if not 2. Compute " = $! mod p 3. Set % = &(", ), $) 4. Split % into Ke and Km 5. Decrypt C’ using keys Ke and Km for encryption and MAC, respectively 6. Output “fail” if step 5 fails, otherwise output the message returned in step 5 Correctness relies on: )+ = " = $! mod p That is, we again implicitly have a Diffie-Hellman key exchange 33 DHIES DHIES is IND-CCA secure The security proof relies on The hardness of a variant of the Computational Diffie-Hellman Problem Assumption that H behaves like a random function The symmetric encryption scheme is IND-CPA The MAC scheme is UF-CMA DHIES an instance of a hybrid encryption scheme: Send information Y that allows a shared key K to be computed Use key K in a symmetric encryption scheme We could replace “EtM” with any AE scheme We have a combination of a Key Encapsulation Mechanism (KEM) and a Data Encapsulation Mechanism (DEM): the KEM/DEM paradigm 34 Elliptic curve cryptography 36 Recall: discrete logs over cyclic groups For a cyclic, finite (multiplicative) group G of order r generated by g, we defined the Discrete Logarithm Problem (DLP) in G as: given a randomly selected element h of G = {g0,g1,g2,g3,…gr-1} , find x in [0,r-1] such that h = gx The first platform we defined to construct cryptographic schemes based on the DLP was the multiplicative group of non-zero integers modulo a prime p Zp* = {1,2,…,p-1} We described how to select parameters to offer the desired level of security, based on the complexity of the main DLP-solving algorithms that apply to Zp* We took p = kq + 1, where q is also prime, and instantiated DL over the cyclic subgroup of Zp* of order q We now define another platform for constructing DLP-based crypto: Elliptic Curves 37  Elliptic Curves We have seen several fields: real numbers, rational numbers, Zp An elliptic curve over a field F is a set of pairs (x,y) ∈ F 2 that satisfy the following equation y2 =x3 + ax + b (where a,b ∈ F, and 4a3 + 27b2 ≠ 0), plus a special “point at infinity” O Using different fields F and different values for a,b give different curves We denote elliptic curve as E = E(F) = {(x,y) ∈ F 2 | y2 =x3 +a.x + b} ∪ {O} 38 An elliptic curve over the real numbers y2 = x3 - 5x + 3 39 An elliptic curve over Z5 y2 = x3 + 2x + 4 (mod 5) 40 Example: elliptic curve over Z97 y2 = x3 - x + 1 (mod 97) figure source: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ 41 The group of points of an elliptic curve We can define an addition operation over the points of an elliptic curve E = {(x,y) ∈ F 2 | y2 =x3 +a.x + b} ∪ {O} Points P = (x,y) on E can be added to obtain another point on the curve In fact, under this addition operation, E is an additive group! The point at infinity O is the (additive) identity of this group P + O = O + P = P for all elliptic curve points P Each point P has an (additive) inverse: −P if P =(x,y) then −P =(x,−y) P + (−P) = O Point at infinity O is its own inverse 42 Elliptic curve group: addition operation The addition operation is not simply adding the coordinates of P and Q It is more complicated: Notation: since the group is additive, with elliptic curves we write Q = (P + P + … + P) = k. P rather than Q = (P. P. …. P) = P k as we did with the multiplicative group Zp* 43 Geometric interpretation over the reals 44 Geometric interpretation over a finite field y2 = x3 - x + 1 (mod 97) figure source: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ 45 Properties of the elliptic curve group For curves over a finite field ! = #$, where $ is prime we have: The order % of E(!) satisfies $ + 1 − 2 $ ≤ % ≤ $ + 1 + 2 $ i.e., the order of E(!) is close to $ The group E(!) is either cyclic or the product of two cyclic (sub)groups We will be working over cyclic (sub)groups of E(!) of large order Example: E = {(x,y) | y2 =x3+2x+4 } over Z5 has 7 points (thus it is cyclic) P = (0,2) is a generator of E The correspondence between points and multiples kP is unclear This is the basis for the security of elliptic curve cryptosystems 46 Elliptic Curve Discrete Logarithm Problem (ECDLP) Let G be a cyclic subgroup of order r of the group of points of an elliptic curve E generated by the point P, i.e. G = { P, 2P, 3P, 4P, …, (r-1)P, O} Elliptic Curve Discrete Logarithm Problem (ECDLP) in G: Given randomly chosen point Q in G, find k such that Q = kP 47 Elliptic curve trapdoor illustrated figure/animation source: https://medium.com/@icostan/animated-elliptic-curves-cryptography-122fff8fcae 48 Elliptic Curve Cryptography (ECC) ECC replaces the finite multiplicative group of integers modulo a prime p with an elliptic curve group Instead of multiplication modulo p, the group operation is addition of curve points (i.e., P+Q) The analogue of exponentiation modulo p is computing scalar multiples of curve points (i.e., kP) The security of ECC schemes depends on hardness of ECDLP 49 Why ECC? Currently there are no sub-exponential algorithms for solving ECDLP Index Calculus does not apply to Elliptic curves! The best algorithms run in square-root time (e.g., Pollard’s rho) This allows us to work with smaller parameters We will use curves over a prime field ! which give rise to a cyclic group of curve points, of order " close to !. The best attack will then have complexity O( ") So ! ≈ " of 256 bits gives approximately 128 bits of security In turn this allows more efficient implementations We can define analogous ECC schemes for DH, ElGamal,… 50 Set-up of a system to use ECC We need to decide on a field F Specifically, a finite field !" for a prime p We need to decide on a curve E We need to find a base point P The generator of the cyclic group of E, of large, known order We need to support the new arithmetic In practice you will use a standardised curve! 52 ECC: standardised curves Standards (e.g. NIST, SECG, ANSI, Brainpool, CFRG) specify: Which fields F; coefficients a, b; and base points P to use e.g., ‘secp160r1’, ‘nistp256’ How to do point multiplication Given k,P, how to compute kP = P + · · · + P Representation of points (x,y) on the wire, point compression, etc Plus, a huge amount of possible optimisations 53 Example: NIST P-256 (FIPS 186-2) Parameters: ! = 2$%& − 2$$( + 2*+$ + 2+& − 1 -: / $ = 0 1 − 30 + 2627 $6 where 5 = − 789* :;;< , where >??@ = A49@360886?704936F6678?1139@2657819G7?90 Particular choices were apparently made for efficiency reasons 54 ECC: summary ECC gives alternative way to set up DLP-based cryptographic schemes ECC allows for smaller parameters and more efficient implementations Do not make your own curves and/or points, but use standards NIST curves are widely supported, e.g., NIST P-256 or NIST P-384 Curve 25519 is seeing increasing adoption for its implementation benefits If you want to learn more about these curves, see https://safecurves.cr.yp.to 55 Homework Read Chapters 5 and 9 of “Everyday Cryptography” Read Chapters 9, 11, 12 of “Serious Cryptography” Check out the Further Reading & Research on Moodle 56