advertisement

Introduction to Computer Security Lecture 7 Digital Signature October 9, 2003 Courtesy of Professors Chris Clifton & Matt Bishop INFSCI 2935: Introduction of Computer Security 1 Digital Signature Construct that authenticates origin, contents of message in a manner provable to a disinterested third party (“judge”) Sender cannot deny having sent message (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 2 Common Error Classical: Alice, Bob share key k 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 a digital signature Why? Third party cannot determine whether Alice or Bob generated message INFSCI 2935: Introduction to Computer Security 3 Classical Digital Signatures Require trusted third party Alice, Bob each share keys with trusted party Cathy The judge must trust the trusted party Cathy Alice { m }kAlice Bob Bob { m }kAlice Cathy Cathy { m }kBob Bob To resolve dispute, judge gets { m }kAlice, { m }kBob, and has Cathy decipher them; if messages matched, contract was signed, else one is a forgery INFSCI 2935: Introduction to Computer Security 4 Public Key Digital Signatures (RSA) Alice’s keys are dAlice, eAlice Alice sends Bob m || { m }dAlice In case of dispute, judge computes { { m }dAlice }eAlice and if it is m, Alice signed message She’s the only one who knows dAlice! INFSCI 2935: Introduction to Computer Security 5 RSA Digital Signatures Use private key to encipher message Protocol for use is critical 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 forgery INFSCI 2935: Introduction to Computer Security 6 Attack #1 Example: Alice, Bob communicating nA = 95, eA = 59, dA = 11 nB = 77, eB = 53, dB = 17 26 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 0517 mod 77 = 08; corresponding signature is 0319 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 7 Attack #2: Bob’s Revenge Bob, Alice agree to sign contract 06 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 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) = 5953 mod 60 = 7 Replace public key eB with 7, private key dB = 43 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!! INFSCI 2935: Introduction to Computer Security 8 El Gamal Digital Signature Relies on discrete log problem Choose p prime, g, d < p; Compute y = gd mod p Public key: (y, g, p); private key: d To sign contract m: 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 that yaab mod p = gm mod p INFSCI 2935: Introduction to Computer Security 9 Example Alice chooses p = 29, g = 3, d = 6 y = 36 mod 29 = 4 Alice 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 = (611 + 5b) mod 28 gives b = 25 Alice sends message 23 and signature (11, 25) Bob verifies signature: gm mod p = 323 mod 29 = 8 and yaab mod p = 4111125 mod 29 = 8 They match, so Alice signed INFSCI 2935: Introduction to Computer Security 10 Attack Eve learns k, corresponding message m, and signature (a, b) Extended Euclidean Algorithm gives d, the private key Example from above: Eve learned Alice signed last message with k = 5 m = (da + kb) mod p–1 = 23 =(11d + 525) mod 28 So Alice’s private key is d = 6 INFSCI 2935: Introduction to Computer Security 11 Kerberos Authentication system Based on Needham-Schroeder with Denning-Sacco modification Central server plays role of trusted third party (“Cathy”) Ticket (credential) Issuer vouches for identity of requester of service Authenticator Identifies sender Alice must 1. Authenticate herself to the system 2. Obtain ticket to use server S INFSCI 2935: Introduction to Computer Security 12 Overview User u authenticates to Kerberos server Obtains ticket Tu,TGS for ticket granting service (TGS) User u wants to use service s: User sends authenticator Au, ticket Tu,TGS to TGS asking for ticket for service TGS sends ticket Tu,s to user User sends Au, Tu,s to server as request to use s Details follow INFSCI 2935: Introduction to Computer Security 13 Ticket Credential saying issuer has identified ticket requester Example ticket issued to user u for service s Tu,s = s || { u || u’s address || valid time || ku,s } ks where: ku,s is session key for user and service Valid time is interval for which the ticket is valid u’s address may be IP address or something else Note: more fields, but not relevant here INFSCI 2935: Introduction to Computer Security 14 Authenticator Credential containing identity of sender of ticket Used to confirm sender is entity to which ticket was issued Example: authenticator user u generates for service s Au,s = { u || generation time || kt } ku,s where: kt is alternate session key Generation time is when authenticator generated Note: more fields, not relevant here INFSCI 2935: Introduction to Computer Security 15 Protocol user Cathy user user user user user || TGS { ku,TGS } ku || Tu,TGS service || Au,TGS || Tu,TGS user || { ku,s } ku,TGS || Tu,s Au,s || Tu,s { t + 1 } ku,s INFSCI 2935: Introduction to Computer Security Cathy user TGS TGS service service 16 Analysis First two steps get user ticket to use TGS User u can obtain session key only if u knows key shared with Cathy Next four steps show how u gets and uses ticket for service s Service s validates request by checking sender (using Au,s) is same as entity ticket issued to Step 6 optional; used when u requests confirmation INFSCI 2935: Introduction to Computer Security 17 Problems Relies on synchronized clocks If not synchronized and old tickets, authenticators not cached, replay is possible Tickets have some fixed fields Dictionary attacks possible Kerberos 4 session keys weak (had much less than 56 bits of randomness); researchers at Purdue found them from tickets in minutes INFSCI 2935: Introduction to Computer Security 18 Midterm Courtesy of Professors Chris Clifton & Matt Bishop INFSCI 2935: Introduction of Computer Security 19 Midterm Midterm date: Duration: Coverage: Closed Book: October 16, 2003 2:30 minutes Material till today Yes INFSCI 2935: Introduction to Computer Security 20 Roughly speaking Chapter 1, 2, 4: Chapter 3: Chapter 5, 6, 7: Chapter 9 and 10: 20% 20% 35% 25% May vary slightly!! INFSCI 2935: Introduction to Computer Security 21 Chapter 1 Understand the general concepts/issues Components of security: confidentiality, integrity, availability, etc. Threats Policy vs. mechanisms Assumptions of trust Assurance Specification/design/implementation Operational issues Cost-benefit; risk analysis; Human issues, etc. Organizational problems Security life cycle INFSCI 2935: Introduction to Computer Security 22 Chapter 2 Understand that access control matrix is an abstract model Understand the notation of state transitions Formal definitions of primitive commands Structure of conditional commands Principle of attenuation of privilege INFSCI 2935: Introduction to Computer Security 23 Chapter 3 Understand the working of Turing machine and the mapping Take-grant model Understand the concepts well Witness Sharing Stealing/conspiracy No need to remember definitions (e.g., initial/terminal spans, bridges etc.) SPM model Understand link/f, cc, cr functions well Understand the examples well INFSCI 2935: Introduction to Computer Security 24 Chapter 4 Policy definitions Types of access control Policy language (Pandey & Hashii) Security and precision Observability postulate Secure and precise mechanism Understand the definitions – no need to memorize (they will be provided if needed) INFSCI 2935: Introduction to Computer Security 25 Chapter 5, 6 and 7 Confidentiality: Bell-LaPadula model [5] Security levels, categories, dominates relation Not the formal model Integrity policies Biba’s integrity models Lipner’s integrity model Clark-wilson model Hybrid policies Chinese wall (informal) Clinical and originator control (understand the basic requirements) Role-based access control (NIST) INFSCI 2935: Introduction to Computer Security 26 Chapter 9 Classical crypto systems Transposition ciphers Substitution ciphers (caesar cipher) Vigenere cipher One-time pad Data Encryption Standard (DES) General working of DES Cipher Block Chaining mode Public-key Diffie-hellman RSA Cryptographic checkcsum INFSCI 2935: Introduction to Computer Security 27 Chapter 10 Classical cryptographic key exchange and authentication Basic protocol Needham-Schroeder Denning and Sacco Otway-Rees protocol Kerberos Digital Signature INFSCI 2935: Introduction to Computer Security 28