logging in or signing up chap12new aSGuest8911 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 233 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: January 03, 2009 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Key Establishment Protocols : 1 Key Establishment Protocols Maithili Narasimha January 3, 2009 Contents : 2 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Concepts and Classification : 3 Concepts and Classification Key establishment: a shared secret becomes available to two or more parties, for subsequent cryptographic use. key transport protocol one party creates, and securely transfers it to the other(s). key agreement protocol: key establishment technique in which a shared secret is derived by two (or more) parties key pre-distribution vs. dynamic(session) key establishment : 4 Use of trusted servers trusted third party, trusted server, authentication server, key distribution center (KDC), key translation center (KTC) and certification authority (CA). secure key establishment each party in a key establishment protocol be able to determine the true identity of the other(s) which could possibly gain access to the resulting key, implying preclusion of any unauthorized additional parties from deducing the same key secrecy of key and identification of those parties with access to it Authentication : 5 Authentication evidence that an identified party possesses a given key evidence that a key is possessed by some party identity of party which may possibly share a key identity of the source of data identity of a party, and aliveness at a given instant depends on context of usage Classification and concepts : 6 Classification and concepts (Implicit) Key authentication one party is assured that no other party aside from a specifically identified second party may gain access to a particular secret key independent of the actual possession of such key by the second party, or knowledge of such actual possession by the first party Key confirmation one party is assured that a second (possibly unidentified) party actually has possession of a particular secret key Explicit key authentication both (implicit) key authentication and key confirmation hold Motivation for use of session key : 7 Motivation for use of session key Session key ephemeral secret, i.e., one whose use is restricted to a short time period after which all trace of it is eliminated Motivation to limit available cipher-text to limit exposure in the event of (session) key compromise to avoid long-term storage of a large number of distinct secret keys to create independence across communications sessions or applications Key Establishment Protocol Characteristics : 8 Key Establishment Protocol Characteristics nature of the authentication reciprocity of authentication: unilateral vs. mutual key freshness key control: key distribution vs. key agreement efficiency number of message exchanges bandwidth complexity of computations pre-computation? third party requirements on-line (real-time), off-line, or no third party degree of trust required in a third party type of certificate used non-repudiation Assumptions and Adversaries : 9 Assumptions and Adversaries Attacks passive attack: adversary simply records data and analyzes active attack: adversary modifies or injects messages What are the attacker’s roles? deduce a session key using information gained by eavesdropping; participate covertly in protocol initiated by one party, and influence it by altering messages so as to be able to deduce the key initiate one or more protocol executions, and combine messages from one with another, so as to carry out one of the above attacks without being able to deduce the session key, deceive a legitimate party regarding the identity of the party with which it shares a key In entity authentication, adversary’s objective is to arrange that one party receives messages which satisfy that party that the protocol has been run successfully with a party other than the adversary. PFS and Known Key Attacks : 10 PFS and Known Key Attacks perfect forward secrecy Compromise of long-term key does not compromise past session keys PFS ensures that previous traffic is locked securely in the past known-key attack compromise of past session keys allows either a passive adversary to compromise future session keys, or impersonation by an active adversary in the future Contents : 11 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Point-to-Point Key Update : 12 Point-to-Point Key Update Key Transport with one pass Long term symmetric key K shared between A and B A ? B: EK(rA) {rA is the session key} Implicit key authentication Additional fields timestamp, sequence number: freshness target identifier: prevent undetectable message replay Hence A ? B: EK(rA, tA, B) Mutual authentication: B ? A: EK(rB, tB, A): K = f(rA, rB) Key Transport with challenge-response B ? A: nB : for freshness A ? B: EK(rA, nA, nB, B) B ? A: EK(rB, nB, nA, A) Does not provide PFS Point-to-Point Key Update : 13 Point-to-Point Key Update Authenticated Key Exchange Protocol 2 (AKEP2) rA (B, A, rA, rB), hK(B, A, rA, rB) (A, rB), hK(A, rB) Session key W = h’K’(rB) AKEP1 B ? A: (B, A, rA, rB, (r, W ? h’K’(r)), hK(B, A, rA, rB, (r, W ? h’K’(r)) Optimization: r = rB Shamir’s no key algorithm : 14 Shamir’s no key algorithm Protocol KA mod p (KA)B mod p (KAB) A-1 mod p Properties Provides key transport No a priori information is required Protection from passive adversaries Does not provide authentication Kerberos : 15 Kerberos Basic setup A, B, a trusted server share long-term pairwise secret keys a priori Server either plays the role of KDC and itself supplies the session key, or serves as a key translation center (KTC) A and B share no secret, while T shares a secret with each Goal: for B to verify A’s identity, establishment of a shared key Description A requests from T credentials to allow it to authenticate itself to B T plays the role of a KDC, returning to A a session key encrypted for A and a ticket encrypted for B The ticket contains the session key and A’s identity authentication of A to B when accompanied by appropriate message created by A containing a timestamp encrypted under that session key Kerberos : 16 Kerberos Protocol A ? T: A, B, NA NA: freshness T ? A: EKBT(k, A, L), EKAT(k, NA, L, B): L: lifetime A ? B: EKBT(k, A, L), Ek(A, TA, Asubkey) B ? A: Ek(TA, Bsubkey) Optional mutual authentication Properties Since timestamps are used, the hosts on which this protocol runs must provide both secure and synchronized clocks If initial shared keys are password-derived, protocol is no more secure than secrecy of such password or their resistance to password-guessing attack Asubkey and Bsubkey allow transfer of a key from A to B Lifetime is intended to allow A to re-use the ticket A creates new authenticator with new timestamp and same session key k Needham-Schroeder : 17 Needham-Schroeder important primarily for historical reasons Protocol A ? T: A, B, NA T ? A: EKAT(NA, B, k, EKBT(k, A)) A ? B: EKBT(k, A) B ? A: Ek(NB) A ? B: Ek(NB-1) Properties The protocol provides A and B with a shared key k with key authentication (4) and (5) provide entity authentication of A to B. B to A can be obtained using redundancy check on NB upon decrypting message (4). If acceptable for A to re-use key k with B, A may securely cache (3) with k To prevent replay of (4), Ek(NA’) should be appended to message (3), and (4) should be replaced by Ek(NA’-1, NB) allowing A to verify B’s knowledge of k Needham-Schroeder vs. Kerberos : 18 Needham-Schroeder vs. Kerberos Kerberos lifetime parameter is not present in N-S In N-S, (2) (which corresponds to Kerberos ticket) is double-encrypted authentication here employs nonce rather than timestamp since B has no way of knowing if k is fresh, should k ever be compromised, any party knowing it may both resend message (3) and compute a correct message (5) to impersonate A to B This situation is ameliorated in Kerberos by the lifetime parameter which limits exposure to a fixed time interval. Otway-Rees protocol : 19 Otway-Rees protocol Protocol A ? B: M, A, B, EKAT(M, A, B, NA) M: Another nonce B ? T: M, A, B, EKAT(M, A, B, NA), EKBT(M, A, B, NB) T ? B: EKAT(k, NA), EKBT(k, NB) B ? A: EKAT(k, NA) Properties Only 4 rounds Does not require timestamps Provides key authentication and key freshness but not entity authentication and key confirmation NA could be eliminated in (1), (2), and replaced by M in (3), (4) Could provide key confirmation and entity authentication (5 round) B ? A: EKAT(k, NA), Ek(NA, NB) A ? B: Ek(NB) to recap… : 20 to recap… 4 no KDC 5 no KDC 4 yes KDC 3 no none 1-3 optional none Otway-Rees Needham-Schroeder shared-key Kerberos Shamir’s no-key protocol point-to-point key update Contents : 21 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Key Agreement(Symmetric key encryption) : 22 Key Agreement(Symmetric key encryption) KDS is said to be j-secure if coalition of j or fewer users can do no better at computing the key shared by two than a party which guesses key without any pieces whatsoever Blom KDS bound: In any j-secure KDS(m-bit session key), secret data by each user must be at least m(j + 1) bits Blom’s scheme engineered to provide unconditional security against coalitions of a specified maximum size initial keying material assigned to each user allows computation of larger number of derived keys one per each other user derived keys of different user pairs are not statistically independent Contents : 23 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Key Transport using PKC without signature : 24 Key Transport using PKC without signature Needham-Schroeder PB(k1, A) PA(k1, k2) PB(k2) No signatures, Mutual authentication(key+entity), mutual key transport Modified NS PB(k1, A, r1) PA(k2, r1, r2) r2 eliminating third encryption Combining PK encryption and signature : 25 Combining PK encryption and signature Encrypting signed keys A ? B: PB(k, tA, SA(B, k, tA)) Problem: Data for encryption is too large Encrypting and signing separately A ? B: PB(k, tA), SA(B, k, tA) Acceptable only if no information regarding plaintext data can be deduced from the signature Signing encrypted keys A ? B: tA, PB(A, k), SA(B, tA, PB(A, k)) Can provide mutual authentication with two messages(timestamps) or three messages(challenge-response) X.509 strong authentication protocols : 26 X.509 strong authentication protocols Assurances of X.509 strong authentication identity of A, and that the token received by B was constructed by A the token received by B was specifically intended for B; the token received by B has “freshness” the secrecy of the transferred key. X.509 strong two-way authentication DA=(tA, rA, B, data1, PB(k1)), DB=(tB, rB, A, rA, data2, PA(k2)), A ? B: certA, DA, SA(DA) B ? A: certB, DB, SB(DB) Comments Since the protocol does not specify inclusion of an identifier within the scope of the encryption PB within DA, one cannot guarantee that the signing party actually knows (or was the source of) plaintext key Hybrid Key Transport using PKE : 27 Hybrid Key Transport using PKE Beller-Yacobi (4 pass) Properties mutual authentication, explicit key authentication for applications where there is an imbalance in processing power between the two parties identity of the weaker party remains concealed from eavesdroppers Algorithm B ? A : certB = (IB, nB, GB) : certificate generated with RSA A ? B : PB(K) =K3 mod nB B ? A : EK(m, {0}t) : symmetric key encryption A ? B : EK((v, w), certA) : DSA signature with precomputation Comment To achieve mutual authentication, each party carry out at least one private-key operation, and one or two public-key operations careful selection of two separate public-key schemes RSA public operation and ElGamal private-key operation are cheap Hybrid Key Transport using PKE : 28 Hybrid Key Transport using PKE Beller-Yacobi (2 pass) Algorithm A B precompute x, v = gx mod nS select random challenge m verify certB via PT(GB) ? send m, certB compute (v, w) =SA(m, IB) certB = (IB, nB, GB) send PB(v), Ev(certA, w) ? recover v, set K = v certA = (IA, uA, GA) verify certA, signature (v, w) Properties: slightly weaker authentication assurances B obtains entity authentication of A and obtains a key K that A alone knows, while A has key authentication with respect to B For A to obtain explicit key authentication of B, a third message may be added whereby B exhibits knowledge through use of K on a challenge or standard message (e.g., {0}t ) Key Transport based on PKC : 29 Key Transport based on PKC 2 unilateral yes 4 mutual yes 3 mutual yes 2 mutual yes 1 data origin only yes 1 data origin only yes 1 data origin only yes 3 mutual no 1 no no Contents : 30 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Diffie-Hellman and ElGamal : 31 Diffie-Hellman and ElGamal Diffie-Hellman Setup: prime p, generator g of Zp* gx mod p gy mod p gyx mod p fixed exponent: zero-pass key agreement with special certificates Signature is required! ElGamal one-pass key agreement ‘b’ is B’s secret key A ? B : gx mod p Shared key ? gxb Unilateral key authentication no entity authentication or key confirmation MTI/A0 : 32 MTI/A0 Protocol A ? B : gx mod p B ? A : gy mod p A: k = (gy)aPKbx = gya gbx = gya+bx B: k = (gx)bPKay Properties Message independent Secure against passive attacks only Provides mutual (implicit) key authentication but neither key confirmation nor entity authentication STS : 33 STS Algorithm gx mod p gy mod p, Ek(SB(gy, gx)) Ek(SA(gx, gy)) Properties Mutual entity authentication Mutual (explicit) key authentication Gunther’s implicitly-certified ID-based PK : 34 Gunther’s implicitly-certified ID-based PK Algorithm Summary: TTP creates an implicitly-certified, publicly-recoverable DH PK for A, and transfers to A the corresponding private key. TTP selects p and g of Zp*, a random integer t, gcd(t, p -1) = 1 as its private key, and publishes its public key u = gt mod p TTP assigns to each A DN IA and a random integer kA with gcd(kA, p-1) = 1, then computes PA = gkA mod p PA is A’s reconstruction public data, allowing other parties to compute PAa below. T solves the following equation for ‘a’ h(IA) = tPA + kAa (mod p - 1) T securely transmits to A the pair (r, s) = (PA, a) (ElGamal signature on IA) Any other party can then reconstruct A’s public key PAa(=gkA a ) by computing PAa = gh(IA) u-PA mod p DH with Implicitly-certified keys : 35 DH with Implicitly-certified keys Algorithm A ? B : IA, PA B ? A : IB, PB, (PA)y mod p A ? B : (PB)x mod p Shared key ? K = PAya PBxb Key Agreement (Asymmetric technique) : 36 Key Agreement (Asymmetric technique) 3 mutual mutual-implicit 2 none mutual-implicit 2 none mutual-implicit 1 none unilateral 2 none none #msg entity authentication key authentication Contents : 37 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Secret Sharing : 38 Secret Sharing Motivation To safeguard cryptographic keys from loss, desirable to create backups The greater the number of copies made, the greater the risk of security exposure; the smaller the number, the greater the risk that all are lost enhanced reliability without increased risk facilitate distributed trust or shared control for critical activities by gating the critical action on cooperation by t of n users. Basic idea to start with a secret, and divide it into pieces called shares which are distributed amongst users such that the pooled shares of specific subsets of users allow reconstruction of the original secret may be viewed as a key pre-distribution technique, facilitating one-time key establishment, wherein the recovered key is pre-determined Secret Sharing : 39 Secret Sharing Trivial (n, n) scheme S = ? Si Shouldn’t split r bit key into r/t pieces Threshold schemes A (t, n) threshold scheme (t ? n) is a method by which a trusted party computes secret shares Si, 1 ? i ? n from an initial secret S and securely distributes Si to user Pi such that the following is true: any t or more users who pool their shares may easily recover S but any group knowing only t - 1 or fewer shares may not Secret Sharing : 40 Secret Sharing Shamir’s threshold scheme based on polynomial interpolation, and that a uni-variate polynomial y = f(x) of degree t - 1 is uniquely defined by t points (xi, yi) Algorithm Setup: T begins with a secret integer S it wishes to distribute among n users. T chooses a prime p, defines a0 = S, selects t-1 random coefficients a1, …, at-1 defining the polynomial over Zp, f(x) = ?t-1j=0 ajxj T computes Si = f(i) mod p for all i (1<=i<=n), and securely transfers the share Si to Pi Pooling of shares: Group of t or more users pool shares, which provide t distinct points allowing computation of aj’s Secret Sharing : 41 Secret Sharing Properties perfect: Given knowledge of any t - 1 or fewer shares, the shared secret remain equally probable ideal: The size of one share is the size of the secret extendable for new users: New shares (for new users) may be computed and distributed without affecting shares of existing users. varying levels of control possible: Providing a single user with multiple shares bestows more control upon that individual no unproven assumptions Contents : 42 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Conferencing Keying : 43 Conferencing Keying A conference keying protocol is a generalization of two-party key establishment to provide three or more parties with a shared secret key Cliques, BD, TGDH, STR Contents : 44 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Attack strategies and classic flaws : 45 Attack strategies and classic flaws Intruder-in-the-middle “man-in-the-middle” attack on unauthenticated DH Reflection attack Original protocol A ? B : rA B ? A : Ek(rA, rB) A ? B : rB Attack A ? E : rA E ? A : rA : Starting a new session A ? E : Ek(rA, rA’) : Reply of (2) E ? A : Ek(rA, rA’) : Reply of (1) A ? E : rA’ Can be prevented by using two different keys k1 and k2 for encryption Attack strategies and classic flaws : 46 Attack strategies and classic flaws Interleaving attacks Flawed protocol A ? B : rA B ? A : rB, SB(rB, rA, A) A ? B : rA’, SA(rA’, rB, B) Attack E ? B : rA B ? E : rB, SB(rB, rA, A) E ? A : rB A ? E : rA’, SA(rA’, rB, B) E ? B : rA’, SA(rA’, rB, B) Due to symmetric messages (2), (3) Analysis methods : 47 Analysis methods ad hoc and practical analysis (Provide heuristic security) convincing arguments that any successful attack requires resource level greater than the resources of the perceived adversary May uncover protocol flaws establishing that a protocol is bad Subtle flaws in protocols typically escape ad hoc analysis reducibility from hard problems proving that any successful protocol attack leads directly to the ability to solve a well-studied reference problem provably secure protocol A challenge is to establish that all possible attacks have been taken into account, and can be equated to solving the identified reference problems Analysis methods : 48 Analysis methods complexity-theoretic analysis Model of computation is defined, and adversaries are modeled as having polynomial power. Security proof relative to the model is then constructed The existence of underlying cryptographic primitives with specified properties is typically assumed. An objective is to design cryptographic protocols which require the fewest cryptographic primitives, or the weakest assumptions. Polynomial attacks which are feasible under such a model may in practice be computationally infeasible Despite these issues, complexity-theoretic analysis is invaluable for formulating fundamental principles and confirming intuition. Analysis methods : 49 Analysis methods information-theoretic analysis mathematical proofs involving entropy relationships to prove protocols are unconditionally secure Adversaries are modeled to have unbounded computing resources not applicable to most practical schemes for several reasons many schemes can at best be computationally secure typically involve keys of impractically large size, or can only be used once formal methods logics of authentication (BAN), term re-writing systems, expert systems, and other methods combining algebraic and state-transition techniques help in finding flaws and redundancies in protocols the “proofs” provided are proofs within the specified formal system, and cannot be interpreted as absolute proofs of security Absence of discovered flaws does not imply the absence of flaws : 50 Thank You! You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
chap12new aSGuest8911 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 233 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: January 03, 2009 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Key Establishment Protocols : 1 Key Establishment Protocols Maithili Narasimha January 3, 2009 Contents : 2 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Concepts and Classification : 3 Concepts and Classification Key establishment: a shared secret becomes available to two or more parties, for subsequent cryptographic use. key transport protocol one party creates, and securely transfers it to the other(s). key agreement protocol: key establishment technique in which a shared secret is derived by two (or more) parties key pre-distribution vs. dynamic(session) key establishment : 4 Use of trusted servers trusted third party, trusted server, authentication server, key distribution center (KDC), key translation center (KTC) and certification authority (CA). secure key establishment each party in a key establishment protocol be able to determine the true identity of the other(s) which could possibly gain access to the resulting key, implying preclusion of any unauthorized additional parties from deducing the same key secrecy of key and identification of those parties with access to it Authentication : 5 Authentication evidence that an identified party possesses a given key evidence that a key is possessed by some party identity of party which may possibly share a key identity of the source of data identity of a party, and aliveness at a given instant depends on context of usage Classification and concepts : 6 Classification and concepts (Implicit) Key authentication one party is assured that no other party aside from a specifically identified second party may gain access to a particular secret key independent of the actual possession of such key by the second party, or knowledge of such actual possession by the first party Key confirmation one party is assured that a second (possibly unidentified) party actually has possession of a particular secret key Explicit key authentication both (implicit) key authentication and key confirmation hold Motivation for use of session key : 7 Motivation for use of session key Session key ephemeral secret, i.e., one whose use is restricted to a short time period after which all trace of it is eliminated Motivation to limit available cipher-text to limit exposure in the event of (session) key compromise to avoid long-term storage of a large number of distinct secret keys to create independence across communications sessions or applications Key Establishment Protocol Characteristics : 8 Key Establishment Protocol Characteristics nature of the authentication reciprocity of authentication: unilateral vs. mutual key freshness key control: key distribution vs. key agreement efficiency number of message exchanges bandwidth complexity of computations pre-computation? third party requirements on-line (real-time), off-line, or no third party degree of trust required in a third party type of certificate used non-repudiation Assumptions and Adversaries : 9 Assumptions and Adversaries Attacks passive attack: adversary simply records data and analyzes active attack: adversary modifies or injects messages What are the attacker’s roles? deduce a session key using information gained by eavesdropping; participate covertly in protocol initiated by one party, and influence it by altering messages so as to be able to deduce the key initiate one or more protocol executions, and combine messages from one with another, so as to carry out one of the above attacks without being able to deduce the session key, deceive a legitimate party regarding the identity of the party with which it shares a key In entity authentication, adversary’s objective is to arrange that one party receives messages which satisfy that party that the protocol has been run successfully with a party other than the adversary. PFS and Known Key Attacks : 10 PFS and Known Key Attacks perfect forward secrecy Compromise of long-term key does not compromise past session keys PFS ensures that previous traffic is locked securely in the past known-key attack compromise of past session keys allows either a passive adversary to compromise future session keys, or impersonation by an active adversary in the future Contents : 11 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Point-to-Point Key Update : 12 Point-to-Point Key Update Key Transport with one pass Long term symmetric key K shared between A and B A ? B: EK(rA) {rA is the session key} Implicit key authentication Additional fields timestamp, sequence number: freshness target identifier: prevent undetectable message replay Hence A ? B: EK(rA, tA, B) Mutual authentication: B ? A: EK(rB, tB, A): K = f(rA, rB) Key Transport with challenge-response B ? A: nB : for freshness A ? B: EK(rA, nA, nB, B) B ? A: EK(rB, nB, nA, A) Does not provide PFS Point-to-Point Key Update : 13 Point-to-Point Key Update Authenticated Key Exchange Protocol 2 (AKEP2) rA (B, A, rA, rB), hK(B, A, rA, rB) (A, rB), hK(A, rB) Session key W = h’K’(rB) AKEP1 B ? A: (B, A, rA, rB, (r, W ? h’K’(r)), hK(B, A, rA, rB, (r, W ? h’K’(r)) Optimization: r = rB Shamir’s no key algorithm : 14 Shamir’s no key algorithm Protocol KA mod p (KA)B mod p (KAB) A-1 mod p Properties Provides key transport No a priori information is required Protection from passive adversaries Does not provide authentication Kerberos : 15 Kerberos Basic setup A, B, a trusted server share long-term pairwise secret keys a priori Server either plays the role of KDC and itself supplies the session key, or serves as a key translation center (KTC) A and B share no secret, while T shares a secret with each Goal: for B to verify A’s identity, establishment of a shared key Description A requests from T credentials to allow it to authenticate itself to B T plays the role of a KDC, returning to A a session key encrypted for A and a ticket encrypted for B The ticket contains the session key and A’s identity authentication of A to B when accompanied by appropriate message created by A containing a timestamp encrypted under that session key Kerberos : 16 Kerberos Protocol A ? T: A, B, NA NA: freshness T ? A: EKBT(k, A, L), EKAT(k, NA, L, B): L: lifetime A ? B: EKBT(k, A, L), Ek(A, TA, Asubkey) B ? A: Ek(TA, Bsubkey) Optional mutual authentication Properties Since timestamps are used, the hosts on which this protocol runs must provide both secure and synchronized clocks If initial shared keys are password-derived, protocol is no more secure than secrecy of such password or their resistance to password-guessing attack Asubkey and Bsubkey allow transfer of a key from A to B Lifetime is intended to allow A to re-use the ticket A creates new authenticator with new timestamp and same session key k Needham-Schroeder : 17 Needham-Schroeder important primarily for historical reasons Protocol A ? T: A, B, NA T ? A: EKAT(NA, B, k, EKBT(k, A)) A ? B: EKBT(k, A) B ? A: Ek(NB) A ? B: Ek(NB-1) Properties The protocol provides A and B with a shared key k with key authentication (4) and (5) provide entity authentication of A to B. B to A can be obtained using redundancy check on NB upon decrypting message (4). If acceptable for A to re-use key k with B, A may securely cache (3) with k To prevent replay of (4), Ek(NA’) should be appended to message (3), and (4) should be replaced by Ek(NA’-1, NB) allowing A to verify B’s knowledge of k Needham-Schroeder vs. Kerberos : 18 Needham-Schroeder vs. Kerberos Kerberos lifetime parameter is not present in N-S In N-S, (2) (which corresponds to Kerberos ticket) is double-encrypted authentication here employs nonce rather than timestamp since B has no way of knowing if k is fresh, should k ever be compromised, any party knowing it may both resend message (3) and compute a correct message (5) to impersonate A to B This situation is ameliorated in Kerberos by the lifetime parameter which limits exposure to a fixed time interval. Otway-Rees protocol : 19 Otway-Rees protocol Protocol A ? B: M, A, B, EKAT(M, A, B, NA) M: Another nonce B ? T: M, A, B, EKAT(M, A, B, NA), EKBT(M, A, B, NB) T ? B: EKAT(k, NA), EKBT(k, NB) B ? A: EKAT(k, NA) Properties Only 4 rounds Does not require timestamps Provides key authentication and key freshness but not entity authentication and key confirmation NA could be eliminated in (1), (2), and replaced by M in (3), (4) Could provide key confirmation and entity authentication (5 round) B ? A: EKAT(k, NA), Ek(NA, NB) A ? B: Ek(NB) to recap… : 20 to recap… 4 no KDC 5 no KDC 4 yes KDC 3 no none 1-3 optional none Otway-Rees Needham-Schroeder shared-key Kerberos Shamir’s no-key protocol point-to-point key update Contents : 21 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Key Agreement(Symmetric key encryption) : 22 Key Agreement(Symmetric key encryption) KDS is said to be j-secure if coalition of j or fewer users can do no better at computing the key shared by two than a party which guesses key without any pieces whatsoever Blom KDS bound: In any j-secure KDS(m-bit session key), secret data by each user must be at least m(j + 1) bits Blom’s scheme engineered to provide unconditional security against coalitions of a specified maximum size initial keying material assigned to each user allows computation of larger number of derived keys one per each other user derived keys of different user pairs are not statistically independent Contents : 23 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Key Transport using PKC without signature : 24 Key Transport using PKC without signature Needham-Schroeder PB(k1, A) PA(k1, k2) PB(k2) No signatures, Mutual authentication(key+entity), mutual key transport Modified NS PB(k1, A, r1) PA(k2, r1, r2) r2 eliminating third encryption Combining PK encryption and signature : 25 Combining PK encryption and signature Encrypting signed keys A ? B: PB(k, tA, SA(B, k, tA)) Problem: Data for encryption is too large Encrypting and signing separately A ? B: PB(k, tA), SA(B, k, tA) Acceptable only if no information regarding plaintext data can be deduced from the signature Signing encrypted keys A ? B: tA, PB(A, k), SA(B, tA, PB(A, k)) Can provide mutual authentication with two messages(timestamps) or three messages(challenge-response) X.509 strong authentication protocols : 26 X.509 strong authentication protocols Assurances of X.509 strong authentication identity of A, and that the token received by B was constructed by A the token received by B was specifically intended for B; the token received by B has “freshness” the secrecy of the transferred key. X.509 strong two-way authentication DA=(tA, rA, B, data1, PB(k1)), DB=(tB, rB, A, rA, data2, PA(k2)), A ? B: certA, DA, SA(DA) B ? A: certB, DB, SB(DB) Comments Since the protocol does not specify inclusion of an identifier within the scope of the encryption PB within DA, one cannot guarantee that the signing party actually knows (or was the source of) plaintext key Hybrid Key Transport using PKE : 27 Hybrid Key Transport using PKE Beller-Yacobi (4 pass) Properties mutual authentication, explicit key authentication for applications where there is an imbalance in processing power between the two parties identity of the weaker party remains concealed from eavesdroppers Algorithm B ? A : certB = (IB, nB, GB) : certificate generated with RSA A ? B : PB(K) =K3 mod nB B ? A : EK(m, {0}t) : symmetric key encryption A ? B : EK((v, w), certA) : DSA signature with precomputation Comment To achieve mutual authentication, each party carry out at least one private-key operation, and one or two public-key operations careful selection of two separate public-key schemes RSA public operation and ElGamal private-key operation are cheap Hybrid Key Transport using PKE : 28 Hybrid Key Transport using PKE Beller-Yacobi (2 pass) Algorithm A B precompute x, v = gx mod nS select random challenge m verify certB via PT(GB) ? send m, certB compute (v, w) =SA(m, IB) certB = (IB, nB, GB) send PB(v), Ev(certA, w) ? recover v, set K = v certA = (IA, uA, GA) verify certA, signature (v, w) Properties: slightly weaker authentication assurances B obtains entity authentication of A and obtains a key K that A alone knows, while A has key authentication with respect to B For A to obtain explicit key authentication of B, a third message may be added whereby B exhibits knowledge through use of K on a challenge or standard message (e.g., {0}t ) Key Transport based on PKC : 29 Key Transport based on PKC 2 unilateral yes 4 mutual yes 3 mutual yes 2 mutual yes 1 data origin only yes 1 data origin only yes 1 data origin only yes 3 mutual no 1 no no Contents : 30 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Diffie-Hellman and ElGamal : 31 Diffie-Hellman and ElGamal Diffie-Hellman Setup: prime p, generator g of Zp* gx mod p gy mod p gyx mod p fixed exponent: zero-pass key agreement with special certificates Signature is required! ElGamal one-pass key agreement ‘b’ is B’s secret key A ? B : gx mod p Shared key ? gxb Unilateral key authentication no entity authentication or key confirmation MTI/A0 : 32 MTI/A0 Protocol A ? B : gx mod p B ? A : gy mod p A: k = (gy)aPKbx = gya gbx = gya+bx B: k = (gx)bPKay Properties Message independent Secure against passive attacks only Provides mutual (implicit) key authentication but neither key confirmation nor entity authentication STS : 33 STS Algorithm gx mod p gy mod p, Ek(SB(gy, gx)) Ek(SA(gx, gy)) Properties Mutual entity authentication Mutual (explicit) key authentication Gunther’s implicitly-certified ID-based PK : 34 Gunther’s implicitly-certified ID-based PK Algorithm Summary: TTP creates an implicitly-certified, publicly-recoverable DH PK for A, and transfers to A the corresponding private key. TTP selects p and g of Zp*, a random integer t, gcd(t, p -1) = 1 as its private key, and publishes its public key u = gt mod p TTP assigns to each A DN IA and a random integer kA with gcd(kA, p-1) = 1, then computes PA = gkA mod p PA is A’s reconstruction public data, allowing other parties to compute PAa below. T solves the following equation for ‘a’ h(IA) = tPA + kAa (mod p - 1) T securely transmits to A the pair (r, s) = (PA, a) (ElGamal signature on IA) Any other party can then reconstruct A’s public key PAa(=gkA a ) by computing PAa = gh(IA) u-PA mod p DH with Implicitly-certified keys : 35 DH with Implicitly-certified keys Algorithm A ? B : IA, PA B ? A : IB, PB, (PA)y mod p A ? B : (PB)x mod p Shared key ? K = PAya PBxb Key Agreement (Asymmetric technique) : 36 Key Agreement (Asymmetric technique) 3 mutual mutual-implicit 2 none mutual-implicit 2 none mutual-implicit 1 none unilateral 2 none none #msg entity authentication key authentication Contents : 37 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Secret Sharing : 38 Secret Sharing Motivation To safeguard cryptographic keys from loss, desirable to create backups The greater the number of copies made, the greater the risk of security exposure; the smaller the number, the greater the risk that all are lost enhanced reliability without increased risk facilitate distributed trust or shared control for critical activities by gating the critical action on cooperation by t of n users. Basic idea to start with a secret, and divide it into pieces called shares which are distributed amongst users such that the pooled shares of specific subsets of users allow reconstruction of the original secret may be viewed as a key pre-distribution technique, facilitating one-time key establishment, wherein the recovered key is pre-determined Secret Sharing : 39 Secret Sharing Trivial (n, n) scheme S = ? Si Shouldn’t split r bit key into r/t pieces Threshold schemes A (t, n) threshold scheme (t ? n) is a method by which a trusted party computes secret shares Si, 1 ? i ? n from an initial secret S and securely distributes Si to user Pi such that the following is true: any t or more users who pool their shares may easily recover S but any group knowing only t - 1 or fewer shares may not Secret Sharing : 40 Secret Sharing Shamir’s threshold scheme based on polynomial interpolation, and that a uni-variate polynomial y = f(x) of degree t - 1 is uniquely defined by t points (xi, yi) Algorithm Setup: T begins with a secret integer S it wishes to distribute among n users. T chooses a prime p, defines a0 = S, selects t-1 random coefficients a1, …, at-1 defining the polynomial over Zp, f(x) = ?t-1j=0 ajxj T computes Si = f(i) mod p for all i (1<=i<=n), and securely transfers the share Si to Pi Pooling of shares: Group of t or more users pool shares, which provide t distinct points allowing computation of aj’s Secret Sharing : 41 Secret Sharing Properties perfect: Given knowledge of any t - 1 or fewer shares, the shared secret remain equally probable ideal: The size of one share is the size of the secret extendable for new users: New shares (for new users) may be computed and distributed without affecting shares of existing users. varying levels of control possible: Providing a single user with multiple shares bestows more control upon that individual no unproven assumptions Contents : 42 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Conferencing Keying : 43 Conferencing Keying A conference keying protocol is a generalization of two-party key establishment to provide three or more parties with a shared secret key Cliques, BD, TGDH, STR Contents : 44 Contents Classification and framework Key transport based on symmetric encryption Key agreement based on symmetric techniques Key transport based on public-key encryption Key agreement based on asymmetric techniques Secret sharing Conference keying Analysis of key establishment protocols Attack strategies and classic flaws : 45 Attack strategies and classic flaws Intruder-in-the-middle “man-in-the-middle” attack on unauthenticated DH Reflection attack Original protocol A ? B : rA B ? A : Ek(rA, rB) A ? B : rB Attack A ? E : rA E ? A : rA : Starting a new session A ? E : Ek(rA, rA’) : Reply of (2) E ? A : Ek(rA, rA’) : Reply of (1) A ? E : rA’ Can be prevented by using two different keys k1 and k2 for encryption Attack strategies and classic flaws : 46 Attack strategies and classic flaws Interleaving attacks Flawed protocol A ? B : rA B ? A : rB, SB(rB, rA, A) A ? B : rA’, SA(rA’, rB, B) Attack E ? B : rA B ? E : rB, SB(rB, rA, A) E ? A : rB A ? E : rA’, SA(rA’, rB, B) E ? B : rA’, SA(rA’, rB, B) Due to symmetric messages (2), (3) Analysis methods : 47 Analysis methods ad hoc and practical analysis (Provide heuristic security) convincing arguments that any successful attack requires resource level greater than the resources of the perceived adversary May uncover protocol flaws establishing that a protocol is bad Subtle flaws in protocols typically escape ad hoc analysis reducibility from hard problems proving that any successful protocol attack leads directly to the ability to solve a well-studied reference problem provably secure protocol A challenge is to establish that all possible attacks have been taken into account, and can be equated to solving the identified reference problems Analysis methods : 48 Analysis methods complexity-theoretic analysis Model of computation is defined, and adversaries are modeled as having polynomial power. Security proof relative to the model is then constructed The existence of underlying cryptographic primitives with specified properties is typically assumed. An objective is to design cryptographic protocols which require the fewest cryptographic primitives, or the weakest assumptions. Polynomial attacks which are feasible under such a model may in practice be computationally infeasible Despite these issues, complexity-theoretic analysis is invaluable for formulating fundamental principles and confirming intuition. Analysis methods : 49 Analysis methods information-theoretic analysis mathematical proofs involving entropy relationships to prove protocols are unconditionally secure Adversaries are modeled to have unbounded computing resources not applicable to most practical schemes for several reasons many schemes can at best be computationally secure typically involve keys of impractically large size, or can only be used once formal methods logics of authentication (BAN), term re-writing systems, expert systems, and other methods combining algebraic and state-transition techniques help in finding flaws and redundancies in protocols the “proofs” provided are proofs within the specified formal system, and cannot be interpreted as absolute proofs of security Absence of discovered flaws does not imply the absence of flaws : 50 Thank You!