WIXLIB

IntroductionKey-DistributionDiffie-Hellman ExchangeThe key-distribution problemA public-key solutionFoundations of CryptographyComputer Science DepartmentWellesley CollegeFall 2016IntroductionKey-DistributionTable of contentsIntroductionKey-DistributionDiffie-Hellman ExchangeDiffie-Hellman Exchange

IntroductionKey-DistributionDiffie-Hellman ExchangeThe key-distribution problemSecurity servicesConfidentiality Private-key cryptographyProtection of data fromrequires shared,unauthorizedsecret keysdisclosure.between eachAuthenticationpair ofAssurance that thecommunicatingoriginparties.of a communication iscorrectly identified.Integrity How are all thesekeysOnly authorized entities areshared in the firstable place?to modify resources.Nonrepudiation In situations where Protectiona large again denialby one of the parties.number of partiesmustAccess controlpairwise, secretly Prevention ofunauthorized use of acommunicate, manyresource.schemes do not scale well.Intro to cryptologyIntroductionKey-DistributionKey storage and secrecy When there are Uemployees, the number ofsecret keys isU (U 2 ) and every2employee holds U 1 keys. The situation is worse whenemployees mustcommunicate with remotedatabases, servers, and soforth. All these keys need must besecurely store.1-5Diffie-Hellman Exchange

IntroductionKey-DistributionDiffie-Hellman ExchangeOpen systems Private-key cryptographycan be used to solve theproblem of securecommunication in ”closed”systems where it is possibleto distribute secret keys viaphysical means. What happens when partiescannot physically meet, orwhere parties have Diffie-Hellman ExchangeKey distribution centers (KDC)All employees share a key with theKDC.1. When Alice wants to communicatewith Bob, she encrypts, using thesecret key she shares with KDC: ‘Alice wishes to communicatewith Bob’2. The KDC chooses a new randomkey, called the session key andsends this to Alice (encrypted usingAlice’s shared key) and Bob(encrypted using Bob’s shared key).3. Alice and Bob communicate usingthe session key and destroy it whenthey are done.

IntroductionKey-DistributionDiffie-Hellman ExchangeGood news/Bad newsPlus side:1. Each employee needs to store onlyone secret key. Limited storagedevices, such as smart cards, couldbe used.2. When an employee joins theorganization all that must be doneis set up a secret-key with theKDC. No other employees need beupdated.Minus side:1. A successful attack on the KDCresults in a complete break ofsecurity for all parties.2. When the KDC is down, securecommunications come to a halt.IntroductionKey-DistributionDiffie-Hellman ExchangeThe state of a airs before 1976

IntroductionKey-DistributionDiffie-Hellman ExchangeAfter 1976, a new kid on the blockIn 1976, Whitfield Diffie and Martin Hellman published a papertitled ”New Directions in Cryptography” in which they proposed acompletely new cryptographic n ExchangeAddressing the limitations of private-key encryption*1. Public-key allows key distribution to be done over publicchannels. Initial deployment and system maintenance issimplified.2. Public-key vastly reduces the need to store many di erentsecret keys. Even if a large number of pairs want tocommunicate secretly, each party needs store only one key:her own.3. Finally, public-key is suitable for open environments whereparties who have never previously interacted can communicatesecretly.*There are a fair number of details glossed over here, e.g., ensuring authenticdistribution of public keys in the first place.

IntroductionKey-DistributionDiffie-Hellman ExchangeDigital signaturesIn addition to the public-key encryption, Diffie and Hellmanintroduced a public-key analogue to message authentication codes,call digital signatures.*Not only does this scheme prevent undetected tampering of a message,authenticity can be verified by anyone knowing the public key of the sender.Nonrepudiation: Alice cannot deny her signature.IntroductionKey-DistributionPublic-key implementation Although Diffie and Hellmanintroduced public-keyencryption and digitalsignatures, they did notprovide an implementationof either. A year later, Ron Rivest, AdiShamir, and Len Adlemanproposed the RSA problemand presented the firstpublic-key encryption anddigital signature schemes.Diffie-Hellman Exchange

IntroductionKey-DistributionDiffie-Hellman ExchangeImplements of war Diffie and Hellman (andothers publishing incryptography) were underthreat of prosecution. Under the InternationalTraffic in Arms Regulations,technical literature oncryptography was consideredan implement of war.IntroductionKey-DistributionInteractive key exchange Finally, in their now famouspaper, Diffie and Hellmanprovided an implementationof an interactive keyexchange. An interactive key exchangeprotocol is a methodwhereby parties who do notshare any secret informationcan generate a shared,secret key by communicatingover a public channel.Diffie-Hellman Exchange

IntroductionKey-DistributionDiffie-Hellman ExchangeThe settingAlice and Bob run some protocol in order to generate a sharedsecret. Beginning with a security parameter 1n , Alice and Bob choose(independent) random coins and run protocol : At the end of the protocol, Alice and Bob output keyskA , kB 2 {0, 1}n , respectively. The basic correctness requirement is that kA kB for allchoices of random coins.**Thus, we can speak of the key k kA kB .IntroductionKey-DistributionDiffie-Hellman ExchangeA definition of securityThe key-exchange experiment KEeavA, (n):1. Two parties holding 1n execute protocol resulting in atranscript trans containing all the messages sent by theparties, and a key k that is output by each of the parties.2. A random bit b{0, 1} is chosen. If b 0 then choosenk̂{0, 1} uniformly at random, and if b 1 set k̂ : k.3. A is given trans and k̂, and outputs a bit b 0 .4. The output of the experiment is defined to be 1 if b 0 b, and0 otherwise.Definition 10.1 A key-exchange protocol is secure in the presenceof an eavesdropper if for every probabilistic polynomial-timeadversary A there exists a negligible function negl such thatPr[KEeavA, (n) 1] 1 negl(n).2

IntroductionKey-DistributionDiffie-Hellman ExchangeThe Diffie-Hellman key-exchange protocol*Construction 10.2. Common input: The security input 1n The protocol:1. Alice runs G(1n ) to obtain (G, q, g ).2. Alice chooses xZq uniformly at random, and computesxhA : g .3. Alice sends (G, q, g , hA ) to Bob.4. Bob receives (G, q, g , hA ). He chooses yZq uniformly atyrandom and computes hB : g . Bob sends hB to Alice andoutputs the key kB : hAy .5. Alice receives hB and outputs the key kA : hBx .*Checking correctness is easy.IntroductionKey-DistributionDiffie-Hellman ExchangeSecurity of the Diffie-Hellman exchange At a bare bones minimum, inorder for the Diffie-Hellmanexchange to be secure it isnecessary for the discretelogarithm problem to be hardrelative to G. However, this is not sufficientsince is may be possible tocompute the key kA kBwithout explicitly finding x or y . What is required is that g xy beindistinguishable from randomfor any adversary given g , g x ,and g y .

IntroductionKey-DistributionDiffie-Hellman ExchangeDecisional Diffie-Hellman (DDH) problem once moreThe decisional Diffie-Hellman (DDH) problem is to distinguishDHg (h1 , h2 ) from a random group element for randomly chosenh1 , h2 .Definition 8.63. We say that the DDH problem is hard relative toG if for all probabilistic polynomial-time algorithms A there existsa negligible function negl such that Pr[A(G, q, g , g x , g y , g z ) 1]Pr[A(G, q, g , g x , g y , g xy ) 1] negl(n),where in each case the probabilities are taken over the experimentin which G(1n ) outputs (G, q, g ), and the random x, y , z 2 Zq an ExchangeProof of securityTheorem 10.3. If the decisional Diffie-Hellman problem is hardrelative to G, then the Diffie-Hellman key-exchange protocol issecure in the presence of an eavesdropper (with respect to theˆ eavexperiment KEA, .Proof. Let A be a PPT adversary. SincePr[b 0] Pr[b 1] 1/2, we haveh eaviˆ A, (n) 1Pr KEh eavi 1h eavi1ˆˆ · Pr KEA, (n) 1 b 1 · Pr KEA, (n) 1 b 0 .22ˆ eav*Here KEA, stands for a modified experiment where if b 0 the adversary isgiven k̂G chosen uniformly at random.

IntroductionKey-DistributionDiffie-Hellman ExchangeThe adversary’s goalˆ eavIn experiment KEA, (n), adversary A receives (G, q, g , hA , hB , k̂),where (G, q, g , hA , hB ) is the transcript of the protocol execution,and k̂ is either the actual key g xy (if b 1) or a random groupelement (if b 0).Distinguishing between these two cases is exactly equivalent tosolving the decisional Diffie-Hellman problem.**So are we really doing anything here?IntroductionKey-DistributionDiffie-Hellman ExchangeAdversary’s probability of successh eaviˆ A, (n) 1Pr KEh eavih eavi1ˆ A, (n) 1 b 1 1 · Pr KEˆ A, (n) 1 b 0 · Pr KE2211xyxy · Pr[A(G, g , q, g , g , g ) 1] · Pr[A(G, g , q, g x , g y , g z ) 0]2211xyxy · Pr[A(G, g , q, g , g , g ) 1] · (1 Pr[A(G, g , q, g x , g y , g z ) 1])2211xyxy · (Pr[A(G, g , q, g , g , g ) 1] Pr[A(G, g , q, g x , g y , g z ) 1])2211 · Pr[A(G, g , q, g x , g y , g xy ) 1] Pr[A(G, g , q, g x , g y , g z ) 1] .22If the decisional Diffie-Hellman assumption is hard relative to G, this theabsolute value in the final line is bounded by some negligible runction negl, andh eaviˆ A, (n) 1 1 1 · negl(n).Pr KE22

Introduction Key-Distribution Diffie-Hellman Exchange Addressing the limitations of private-key encryption* 1. Public-key allows key distribution to be done over public channels. Initial deployment and system maintenance is simplified. 2. Public-key vastly reduces the need to store many di erent secret keys. Even if a large number of pairs .