1、June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-1,Chapter 10: Key Management,Session and Interchange Keys Key Exchange Key Generation Cryptographic Key Infrastructure Storing and Revoking Keys Digital Signatures,June 1, 2004,Computer Security: Art and Science 2002-200
2、4 Matt Bishop,Slide #10-2,Overview,Key exchange Session vs. interchange keys Classical, public key methods Key generation Cryptographic key infrastructure Certificates Key storage Key escrow Key revocation Digital signatures,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide
3、 #10-3,Notation,X Y : Z | W kX,Y X sends Y the message produced by concatenating Z and W enciphered by key kX,Y, which is shared by users X and Y A T : Z kA | W kA,T A sends T a message consisting of the concatenation of Z enciphered using kA, As key, and W enciphered using kA,T, the key shared by A
4、 and T r1, r2 nonces (nonrepeating random numbers),June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-4,Session, Interchange Keys,Alice wants to send a message m to Bob Assume public key encryption Alice generates a random cryptographic key ks and uses it to encipher m T
5、o be used for this message only Called a session key She enciphers ks with Bob;s public key kB kB enciphers all session keys Alice uses to communicate with Bob Called an interchange key Alice sends m ks ks kB,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-5,Benefits,
6、Limits amount of traffic enciphered with single key Standard practice, to decrease the amount of traffic an attacker can obtain Prevents some attacks Example: Alice will send Bob message that is either “BUY” or “SELL”. Eve computes possible ciphertexts “BUY” kB and “SELL” kB. Eve intercepts encipher
7、ed message, compares, and gets plaintext at once,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-6,Key Exchange Algorithms,Goal: Alice, Bob get shared key Key cannot be sent in clear Attacker can listen in Key can be sent enciphered, or derived from exchanged data plu
8、s data not known to an eavesdropper Alice, Bob may trust third party All cryptosystems, protocols publicly known Only secret data is the keys, ancillary information known only to Alice and Bob needed to derive keys Anything transmitted is assumed known to attacker,June 1, 2004,Computer Security: Art
9、 and Science 2002-2004 Matt Bishop,Slide #10-7,Classical Key Exchange,Bootstrap problem: how do Alice, Bob begin? Alice cant send it to Bob in the clear! Assume trusted third party, Cathy Alice and Cathy share secret key kA Bob and Cathy share secret key kB Use this to exchange shared key ks,June 1,
10、 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-8,Simple Protocol,Alice,Cathy, request for session key to Bob kA,Alice,Cathy, ks kA | ks kB,Alice,Bob, ks kB,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-9,Problems,How does Bob know he is tal
11、king to Alice? Replay attack: Eve records message from Alice to Bob, later replays it; Bob may think hes talking to Alice, but he isnt Session key reuse: Eve replays message from Alice to Bob, so Bob re-uses session key Protocols must provide authentication and defense against replay,June 1, 2004,Co
12、mputer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-10,Needham-Schroeder,Alice,Cathy,Alice | Bob | r1,Alice,Cathy, Alice | Bob | r1 | ks | Alice | ks kB kA,Alice,Bob, Alice | ks kB,Alice,Bob, r2 ks,Alice,Bob, r2 1 ks,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,
13、Slide #10-11,Argument: Alice talking to Bob,Second message Enciphered using key only she, Cathy knows So Cathy enciphered it Response to first message As r1 in it matches r1 in first message Third message Alice knows only Bob can read it As only Bob can derive session key from message Any messages e
14、nciphered with that key are from Bob,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-12,Argument: Bob talking to Alice,Third message Enciphered using key only he, Cathy know So Cathy enciphered it Names Alice, session key Cathy provided session key, says Alice is othe
15、r party Fourth message Uses session key to determine if it is replay from Eve If not, Alice will respond correctly in fifth message If so, Eve cant decipher r2 and so cant respond, or responds incorrectly,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-13,Denning-Sacc
16、o Modification,Assumption: all keys are secret Question: suppose Eve can obtain session key. How does that affect protocol? In what follows, Eve knows ks,Eve,Bob, Alice | ks kB,Eve,Bob, r2 ks,Eve,Bob, r2 1 ks,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-14,Solution
17、,In protocol above, Eve impersonates Alice Problem: replay in third step First in previous slide Solution: use time stamp T to detect replay Weakness: if clocks not synchronized, may either reject valid messages or accept replays Parties with either slow or fast clocks vulnerable to replay Resetting
18、 clock does not eliminate vulnerability,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-15,Needham-Schroeder with Denning-Sacco Modification,Alice,Cathy,Alice | Bob | r1,Alice,Cathy, Alice | Bob | r1 | ks | Alice | T | ks kB kA,Alice,Bob, Alice | T | ks kB,Alice,Bob,
19、r2 ks,Alice,Bob, r2 1 ks,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-16,Otway-Rees Protocol,Corrects problem That is, Eve replaying the third message in the protocol Does not use timestamps Not vulnerable to the problems that Denning-Sacco modification has Uses in
20、teger n to associate all messages with particular exchange,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-17,The Protocol,Alice,Bob,n | Alice | Bob | r1 | n | Alice | Bob kA,Cathy,Bob,n | Alice | Bob | r1 | n | Alice | Bob kA | r2 | n | Alice | Bob kB,Cathy,Bob,n | r
21、1 | ks kA | r2 | ks kB,Alice,Bob,n | r1 | ks kA,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-18,Argument: Alice talking to Bob,Fourth message If n matches first message, Alice knows it is part of this protocol exchange Cathy generated ks because only she, Alice kno
22、w kA Enciphered part belongs to exchange as r1 matches r1 in encrypted part of first message,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-19,Argument: Bob talking to Alice,Third message If n matches second message, Bob knows it is part of this protocol exchange Cat
23、hy generated ks because only she, Bob know kB Enciphered part belongs to exchange as r2 matches r2 in encrypted part of second message,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-20,Replay Attack,Eve acquires old ks, message in third step n | r1 | ks kA | r2 | ks
24、kB Eve forwards appropriate part to Alice Alice has no ongoing key exchange with Bob: n matches nothing, so is rejected Alice has ongoing key exchange with Bob: n does not match, so is again rejected If replay is for the current key exchange, and Eve sent the relevant part before Bob did, Eve could
25、simply listen to traffic; no replay involved,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-21,Kerberos,Authentication system Based on Needham-Schroeder with Denning-Sacco modification Central server plays role of trusted third party (“Cathy”) Ticket Issuer vouches f
26、or identity of requester of service Authenticator Identifies sender,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-22,Idea,User u authenticates to Kerberos server Obtains ticket Tu,TGS for ticket granting service (TGS) User u wants to use service s: User sends authen
27、ticator 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,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-23,Ticket,Credential saying issuer has identified ticket reque
28、ster Example ticket issued to user u for service s Tu,s = s | u | us address | valid time | ku,s ks where: ku,s is session key for user and service Valid time is interval for which ticket valid us address may be IP address or something else Note: more fields, but not relevant here,June 1, 2004,Compu
29、ter Security: Art and Science 2002-2004 Matt Bishop,Slide #10-24,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 altern
30、ate session key Generation time is when authenticator generated Note: more fields, not relevant here,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-25,Protocol,user,Cathy,user | TGS,Cathy,user, ku,TGS ku | Tu,TGS,user,TGS,service | Au,TGS | Tu,TGS,user,TGS,user | ku,
31、s ku,TGS | Tu,s,user,service,Au,s | Tu,s,user,service, t + 1 ku,s,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-26,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
32、 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,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-27,Problems,Relies on synchronized clocks I
33、f 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,June 1, 2004,Computer Securit
34、y: Art and Science 2002-2004 Matt Bishop,Slide #10-28,Public Key Key Exchange,Here interchange keys known eA, eB Alice and Bobs public keys known to all dA, dB Alice and Bobs private keys known only to owner Simple protocol ks is desired session key,Alice,Bob, ks eB,June 1, 2004,Computer Security: A
35、rt and Science 2002-2004 Matt Bishop,Slide #10-29,Problem and Solution,Vulnerable to forgery or replay Because eB known to anyone, Bob has no assurance that Alice sent message Simple fix uses Alices private key ks is desired session key,Alice,Bob, ks dA eB,June 1, 2004,Computer Security: Art and Sci
36、ence 2002-2004 Matt Bishop,Slide #10-30,Notes,Can include message enciphered with ks Assumes Bob has Alices public key, and vice versa If not, each must get it from public server If keys not bound to identity of owner, attacker Eve can launch a man-in-the-middle attack (next slide; Cathy is public s
37、erver providing public keys) Solution to this (binding identity to keys) discussed later as public key infrastructure (PKI),June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-31,Man-in-the-Middle Attack,Alice,Cathy,send Bobs public key,Eve,Cathy,send Bobs public key,Eve,
38、Cathy,eB,Alice,eE,Eve,Alice,Bob, ks eE,Eve,Bob, ks eB,Eve intercepts request,Eve intercepts message,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-32,Key Generation,Goal: generate keys that are difficult to guess Problem statement: given a set of K potential keys, ch
39、oose one randomly Equivalent to selecting a random number between 0 and K1 inclusive Why is this hard: generating random numbers Actually, numbers are usually pseudo-random, that is, generated by an algorithm,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-33,What is
40、“Random”?,Sequence of cryptographically random numbers: a sequence of numbers n1, n2, such that for any integer k 0, an observer cannot predict nk even if all of n1, , nk1 are known Best: physical source of randomness Random pulses Electromagnetic phenomena Characteristics of computing environment s
41、uch as disk latency Ambient background noise,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-34,What is “Pseudorandom”?,Sequence of cryptographically pseudorandom numbers: sequence of numbers intended to simulate a sequence of cryptographically random numbers but gene
42、rated by an algorithm Very difficult to do this well Linear congruential generators nk = (ank1 + b) mod n broken Polynomial congruential generators nk = (ajnk1j + + a1nk1 a0) mod n broken too Here, “broken” means next number in sequence can be determined,June 1, 2004,Computer Security: Art and Scien
43、ce 2002-2004 Matt Bishop,Slide #10-35,Best Pseudorandom Numbers,Strong mixing function: function of 2 or more inputs with each bit of output depending on some nonlinear function of all input bits Examples: DES, MD5, SHA-1 Use on UNIX-based systems: (date; ps gaux) | md5where “ps gaux” lists all info
44、rmation about all processes on system,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-36,Cryptographic Key Infrastructure,Goal: bind identity to key Classical: not possible as all keys are shared Use protocols to agree on a shared key (see earlier) Public key: bind id
45、entity to public key Crucial as people will use key to communicate with principal whose identity is bound to key Erroneous binding means no secrecy between principals Assume principal identified by an acceptable name,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-37,
46、Certificates,Create token (message) containing Identity of principal (here, Alice) Corresponding public key Timestamp (when issued) Other information (perhaps identity of signer)signed by trusted authority (here, Cathy) CA = eA | Alice | T dC,June 1, 2004,Computer Security: Art and Science 2002-2004
47、 Matt Bishop,Slide #10-38,Use,Bob gets Alices certificate If he knows Cathys public key, he can decipher the certificate When was certificate issued? Is the principal Alice? Now Bob has Alices public key Problem: Bob needs Cathys public key to validate certificate Problem pushed “up” a level Two app
48、roaches: Merkles tree, signature chains,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-39,Merkles Tree Scheme,Keep certificates in a file Changing any certificate changes the file Use crypto hash functions to detect this Define hashes recursively h is hash function C
49、i is certificate i Hash of file (h(1,4) in example) known to all,h(1,4),h(1,2) h(3,4),h(1,1) h(2,2) h(3,3) h(4,4),C1 C2 C3 C4,June 1, 2004,Computer Security: Art and Science 2002-2004 Matt Bishop,Slide #10-40,Validation,To validate C1: Compute h(1, 1) Obtain h(2, 2) Compute h(1, 2) Obtain h(3, 4) Compute h(1,4) Compare to known h(1, 4) Need to know hashes of children of nodes on path that are not computed,
