October 9, 2003Digital SignatureCommon ErrorClassical Digital SignaturesPublic Key Digital Signatures (RSA)RSA Digital SignaturesAttack #1Attack #2: Bob’s RevengeEl Gamal Digital SignatureExampleAttackKerberosOverviewTicketAuthenticatorProtocolAnalysisProblemsSlide 19MidtermRoughly speakingChapter 1Chapter 2Chapter 3Chapter 4Chapter 5, 6 and 7Chapter 9Chapter 10Courtesy of Professors Chris Clifton & Matt BishopINFSCI 2935: Introduction of Computer Security1October 9, 2003October 9, 2003Introduction to Introduction to Computer SecurityComputer SecurityLecture 7Lecture 7Digital SignatureDigital SignatureINFSCI 2935: Introduction to Computer Security 2Digital SignatureDigital SignatureConstruct that authenticates origin, contents of Construct that authenticates origin, contents of message in a manner provable to a message in a manner provable to a disinterested third party (“judge”)disinterested third party (“judge”)Sender cannot deny having sent message Sender cannot deny having sent message (service is “nonrepudiation”)(service is “nonrepudiation”)Limited to technical proofsInability to deny one’s cryptographic key was used to signOne could claim the cryptographic key was stolen or compromisedLegal proofs, etc., probably required;INFSCI 2935: Introduction to Computer Security 3Common ErrorCommon ErrorClassical: Alice, Bob share key Classical: Alice, Bob share key kkAlice sends m || { m }k to BobDoes this satisfy the requirement for message authentication? How?Does this satisfy the requirement for a digital signature? This is not aThis is not a digital signaturedigital signatureWhy? Third party cannot determine whether Alice or Bob generated messageINFSCI 2935: Introduction to Computer Security 4Classical Digital SignaturesClassical Digital SignaturesRequire trusted third partyRequire trusted third partyAlice, Bob each share keys with trusted party CathyThe judge must trust the trusted party CathyThe judge must trust the trusted party CathyTo resolve dispute, judge gets { To resolve dispute, judge gets { mm } }kkAliceAlice, { , { mm } }kkBobBob, and has Cathy decipher them; if messages matched, contract was , and has Cathy decipher them; if messages matched, contract was signed, else one is a forgerysigned, else one is a forgeryAliceBobBobCathyCathyBob{ m }kAlice{ m }kAlice{ m }kBobINFSCI 2935: Introduction to Computer Security 5Public Key Digital SignaturesPublic Key Digital Signatures(RSA)(RSA)Alice’s keys are Alice’s keys are ddAliceAlice, , eeAliceAliceAlice sends BobAlice sends Bobm || { m }dAliceIn case of dispute, judge computesIn case of dispute, judge computes{ { m }dAlice }eAliceand if it is and if it is mm, Alice signed message, Alice signed messageShe’s the only one who knows dAlice!INFSCI 2935: Introduction to Computer Security 6RSA Digital SignaturesRSA Digital SignaturesUse private key to encipher messageUse private key to encipher messageProtocol for use is criticalKey points:Key points:Never sign random documents, and when signing, always sign hash and never documentMathematical properties can be turned against signerSign message first, then encipherChanging public keys causes forgeryINFSCI 2935: Introduction to Computer Security 7Attack #1Attack #1Example: Alice, Bob communicatingExample: Alice, Bob communicatingnA = 95, eA = 59, dA = 11nB = 77, eB = 53, dB = 1726 contracts, numbered 00 to 2526 contracts, numbered 00 to 25Alice has Bob sign 05 and 17:c = mdB mod nB = 0517 mod 77 = 3c = mdB mod nB = 1717 mod 77 = 19Alice computes 0517 mod 77 = 08; corresponding signature is 0319 mod 77 = 57; claims Bob signed 08Note: [(a mod n) × (b mod n)] mod n = (a × b) mod nJudge computes ceB mod nB = 5753 mod 77 = 08Signature validated; Bob is toast!INFSCI 2935: Introduction to Computer Security 8Attack #2: Bob’s RevengeAttack #2: Bob’s RevengeBob, Alice agree to sign contract 06Bob, Alice agree to sign contract 06Alice enciphers, then signs:Alice enciphers, then signs:Enciper: c = meB mod nB = (0653 mod 77)11Sign: cdA mod nA = (0653 mod 77)11 mod 95 = 63Bob now changes his public keyBob now changes his public keyBob wants to claim that Alice singed N (13)Computes r such that 13r mod 77 = 6; say, r = 59Computes r.eB mod (nB) = 59 53 mod 60 = 7Replace public key eB with 7, private key dB = 43Bob claims contract was 13. Judge computes:Bob claims contract was 13. Judge computes:(6359 mod 95)43 mod 77 = 13Verified; now Alice is toastSolution: sign first and then enciher!!Solution: sign first and then enciher!!INFSCI 2935: Introduction to Computer Security 9El Gamal Digital SignatureEl Gamal Digital SignatureRelies on discrete log problemRelies on discrete log problemChoose Choose pp prime, prime, gg, , dd < < pp; ; Compute Compute yy = = ggdd mod mod ppPublic key: (Public key: (yy, , gg, , pp); private key: ); private key: ddTo sign contract To sign contract mm::Choose k relatively prime to p–1, and not yet usedCompute a = gk mod pFind b such that m = (da + kb) mod p–1Signature is (a, b)To validate, check thatTo validate, check thatyaab mod p = gm mod pINFSCI 2935: Introduction to Computer Security 10ExampleExampleAlice chooses Alice chooses pp = 29, = 29, gg = 3, = 3, dd = 6 = 6y = 36 mod 29 = 4Alice wants to send Bob signed contract 23Alice wants to send Bob signed contract 23Chooses k = 5 (relatively prime to 28)This gives a = gk mod p = 35 mod 29 = 11Then solving 23 = (611 + 5b) mod 28 gives b = 25Alice sends message 23 and signature (11, 25)Bob verifies signature: Bob verifies signature: ggmm mod mod pp = 3 = 32323 mod 29 = mod 29 = 8 and 8 and yyaaaabb mod mod pp = 4 = 4111111112525 mod 29 = 8 mod 29 = 8They match, so Alice signedINFSCI 2935: Introduction to Computer Security 11AttackAttackEve learns Eve learns kk, corresponding message , corresponding message mm, , and signature (and signature (aa, , bb))Extended Euclidean Algorithm gives d, the private keyExample from above: Eve learned Alice Example from above: Eve learned Alice signed last message with signed last message with kk = 5 = 5m = (da + kb) mod p–1 = 23 =(11d + 525) mod 28So Alice’s private key is d = 6INFSCI 2935: Introduction to Computer Security 12KerberosKerberosAuthentication systemAuthentication systemBased on