Challenges in Key Exchange Protocols
Key exchange protocols play a crucial role in ensuring secure communication. This content explores the challenges faced in designing robust key exchange mechanisms, from vulnerabilities in existing protocols like Diffie-Hellman to the complexity of implementing authentication. Despite decades of research, the quest for secure and standardized solutions remains ongoing due to the relentless nature of security threats.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Robust Key Exchange Feng Hao Dependability Group Tech Chat 12 Feb, 2013 1
EPSRC First Grant The talk is based on the following grant: Bridging Theory and Practice in Key Exchange Protocols , PI (Feng Hao), EPSRC First Grant, 2012-2014. 2
Track record Cryptanalysis of the Dragonfly Key Exchange Protocol Dylan, Hao 13 Security Analysis of a Multi-Factor Authenticated Key Exchange Hao, Dylan, ACNS 12 On Robust Key Agreement Based on Public Key Authentication Hao, SCN 12 (BPA) On Small Subgroup Non-Confinement Attacks Hao, CIT 10 Password Authenticated Key Exchange by Juggling Hao, Ryan, SPW 08 Kish's Key Exchange Scheme Is insecure Hao, IET IF 06 3
Background on key exchange Alice Bob 4
1976 Breakthrough Diffie-Hellman key exchange protocol based on Discrete Logarithm 5
Ground-breaking, but vulnerable Diffie-Hellman protocol is vulnerable to man- in-the-middle attack Mallory Alice Bob (b) (a) (a , b ) ga' ga gb' gb Ka=gab Ka=gab Kb=ga b Kb=ga b 6
Fixing the flaw Harder than most people had thought Took nearly 40 years research Still an active area 7
The basic solution Authenticated Key Exchange Three ways to add authentication Something you know: password Some you have: token (private/public key) Something who you are: biometrics 8
A notoriously difficult task A vast amount of protocols proposed Nearly all have been found with security flaws Standardization was hoped to be the solution But several standard AKE protocols have been found flawed as well. 9
Why so difficult? The nature of security research Dealing with an unpredictable enemy It s like building a castle Attacker only needs to find one weak entry to break in 10
Our contributions Designed two AKE protocols J-PAKE (Hao, Ryan, SPW 08) YAK (Hao, FC 10) Meanwhile, we have broken several others protocols Not broken Not broken 11
Our design approach Simplicity principle Make it as simple as possible but not more Anderson-Needham 6thprinciple (1995) Do not assume that a message you receive has a particular form (such as gr for known r) unless you can check this Require using Zero Knowledge Proofs 12
Importance of Zero Knowledge Proof ZKP forces participants to strictly follow protocol specification Extremely important in multi/two-party secure computation problems Universally agreed by the security community But ZKP not used in past AKE protocols, why? Isn t key exchange a two-party secure computation problem ? 13
The devil of efficiency ZKP widely considered too expensive! Nearly all researchers have chosen to discard it to optimize efficiency Optimisation is the process of taking something that works and replacing it with something that almost works, but is cheaper - Roger Needham 14
Efficiency and Security Can Co-exit We don t discard ZKPs (we value the 6th P) Instead, we use novel techniques to minimize the number of ZKPs, so the protocol is still efficient overall. J-PAKE: password-based AKE Comparable to the most efficient but more robust YAK: public key based AKE Comparable to the most efficient but more robust 15
Whats next? J-PAKE and YAK are really the simplest we can achieve under the 6th principle Difficult to envision any improvement in this regard 16
The other half of story: formal analysis Aim: provable security Three components in provable security Formal security definition Formal adversarial model Formal security proofs Nowadays, almost every protocol claims to have been formally proven secure 18
Harsh reality Many provably secure protocols eventually prove to be insecure In fact we have broken a few ourselves What s going on? 19
The role of security proofs Do we need rigorous definition and proofs? Absolutely. This applies to any science and engineering discipline. But not good enough, the proofs must be constructed within a formal model OK, but which model? 20
Existing formal models Password-based AKE Bellare-Pointchevel-Rogaway Abdalla-Pointcheval Katz-Ostrovsky-Yung Jiang-Gong Gennaro-Lindell PKI-based AKE Cannetti-Kcrawczyk LaMacchia-Lauter-Mityagin Kcrawczyk Multi-factor based AKE Pointcheval-Zimmer Eurocrypt 00 RSA 05 Eurocrypt 01 SAC 04 Eurocrypt 03 Cited by 833 Cited by 144 Cited by 279 Cited by 37 Cited by 128 Eurocrypt 01 ProvSec 07 Crypto 05 Cited by 668 Cited by 170 Cited by 289 ACNS 08 Cited by 15 * Citation data from Google Scholar (8 July, 2012) 21
Which is the right model? A question first raised by two professors: Menezes and Koblitz See The uneasy relationship between mathematics and cryptography (AMS 07) Surprisingly, no answer even today Every model claims to be the right one. But that cannot be right. 22
Our criterion of truth Fortunately, each model comes with a concrete example of a practical protocol. Hence, We take practice as one and the only one criterion to evaluate the truth of a theory. 23
Basic intuition A right theoretical model should give right practical results. If not, the model may not be right . 24
Case study 1: Password based AKE Authenticated key exchange based on a shared password without any PKI Also known as PAKE The first PAKE protocol is called EKE Designed by Bellovin and Merrit in 1992. 25
Encrypted Key Exchange (1992) Bob (s) Alice (s) a, g, p b, g, p B = gb mod p A = ga mod p Es(A) K = Ab mod p = gab mod p K = Ba mod p = gab mod p Es(B) A known weakness: the exchanged items leak password info to a passive attacker (Jaspan 96) 26
However, EKE is provably secure Bellare-Pointcheval-Rogaway formally proved that EKE is provably secure (Eurocrypt 00) That conclusion clearly contradicts the known information leakage problem. What s going on? 27
Implicit assumption Bellare-Pointcheval-Rogaway define a formal ideal cipher model. The ideal cipher is assumed never to leak any info even when using a low-entropy key. What exactly is this cipher? (Boyd, 2003) Not defined in the [BPR00] paper. No one really knows. 28
Others examples Several PAKE protocols claim provably secure under standard models (no idealized functions) Katz-Ostrovsky-Yung (Eurocrpt 01) Gennaro-Lindell (Eurocrypt 03) Jiang-Gong (SAC 04) Abdalla-Poincheval (RSA 05) Provably secure without idealized functions Sounds perfect in theory How about in practice? 29
A realistic weakness In practice, none of these protocols have been implemented (to the best of my knowledge). All them require a trusted third party to define protocol parameters. How to realize such a trusted third party? 30
How to define protocol parameters? Katz-Ostrovsky-Yung s paper: use a trusted third party or a source of randomness But no concrete explanation of the source of randomness in the paper Jiang-Gong s paper: use a trusted third party or a threshold scheme But no concrete explanation of the threshold scheme in the paper Gennaro-Lindell s paper: choose a large organization as the trusted third party But that would fundamentally remove benefits of PAKE 31
Roadmap Password-based AKE Bellare-Pointchevel-Rogaway Abdalla-Pointcheval Katz-Ostrovsky-Yung Jiang-Gong Gennaro-Lindell PKI-based AKE Cannetti-Kcrawczyk LaMacchia-Lauter-Mityagin Kcrawczyk Multi-factor based AKE Pointcheval-Zimmer Eurocrypt 00 RSA 05 Eurocrypt 01 SAC 04 Eurocrypt 03 Cited by 833 Cited by 144 Cited by 279 Cited by 37 Cited by 128 Eurocrypt 01 ProvSec 07 Crypto 05 Cited by 668 Cited by 170 Cited by 289 ACNS 08 Cited by 15 * Citation data from Google Scholar (8 July, 2012) 32
Case study 2: PKI-based AKE Alice and Bob have authentic public keys of each other (through PKI). They establish a session key based on their respective private keys. Menezes-Qu-Vanstone protocol (MQV) is one of the most well-known examples Widely standardized (e.g., IEEE P1363) 33
Menezes-Qu-Vanstone (MQV) Alice (ga) Bob (gb) B = gy mod p A = gx mod p A B K = H( ) K = H( ) Two mandatory safeguards in the protocol: 1. Proof-of-possession during CA registration 2. Public key validation during key exchange 34
However, MQV has no proofs The original protocol was carefully designed by three prominent cryptographers in 1995 But still, it contains one flaw (Kaliski, 2001) Unknown Key Sharing attack if there is no key confirmation 35
What was wrong with MQV? Where should user identities be included? 1. During key exchange 2. During key confirmation MQV only include identities in stage 2. Lessons: MQV without key confirmation is not secure. MQV should have included identities in stage 1 (Menezes did exactly this change in Indocrypt 06) 36
HMQV protocol A hash variant of MQV (Kcrawczyk, Crypto 05) Formally proven secure in a variant of CK model, called HMQV model. Quickly included into IEEE P1362 draft the HMQV work represents a prime example of the success of theoretical cryptography (Kcrawczyk, AMS 07) 37
How does HMQV work? Similar to MQV, except the following changes: 1. Include identities in key exchange through hashing 2. Remove the required proof-of-possession during CA registration 3. Remove the required public key validation during key exchange flows The last two changes turn out to degrade security significantly (despite formal proofs) 38
Attacks on HMQV An attacker can compromise the user s private key (Menezes-Ustaoglu 06) Then, HMQV was revised in 2007 (IEEE P1363) However, the revised HMQV is still vulnerable (Hao, FC 10) Invalid public key attack (authentication failure) Wormhole attack (a variant of UKS attack) 39
The HMQV model Attacks reflect the deficiencies in the theoretical model in HMQV. It suggests that the HMQV model is not a right model. However about other formal models? 40
Canetti-Kcrawczyk (CK) model One of the most well-known models, due to Canetti-Kcrawczyk at Eurocrypt 01. As a concrete example, the authors apply the model to prove the SIG-DH protocol is secure. 41
SIG-DH protocol Alice (ga) Bob (gb) B = gy mod p A = gx mod p Sig(A, ) Sig(B, ) K = H( ) K = H( ) Basically, digitally sign the exchanged items. 42
Contradiction we will want to guarantee that the leakage of information specific to one session (such as the leakage of a session key or ephemeral state information) will have no effects on the security of other sessions ... Canetti-Kcrawczyk (Eurocrypt 01) However, if we use DSA, then the leakage of the randomization factor will leak the private key. 43
Where is the catch? The model (implicitly) assumes there is a discrete logarithm based signature scheme that is secure even when ephemeral secrets are revealed. However, the paper doesn t provide a concrete signature algorithm. The deficiency in the CK model then motivates defining a new model. 44
Extended CK (eCK) model A new model called extended CK (eCK) by LaMacchia, Lauter, Mityagin (2007) Claims to be stronger than the CK model because it explicitly captures the threat of leaking ephemeral secrets. Authors also present a NAXOS protocol They apply the model to formally prove NAXOS is secure. 45
NAXOS protocol Alice (ga) Bob (gb) B = gH(y,b) mod p A = gH(x,a) mod p A B K = H( ) K = H( ) The key part in the design: use H(x, a) instead of x on the exponent Known as the NAXOS trick. 46
Where is the catch? NAXOS claims secure if the attacker learns the ephemeral secret: H(x, a) (but not x) However, that s challengeable Both H(x, a) and x are ephemeral secrets Why attacker can only learn one, not the other? This is repeating the same deficiency in CK model excluding valid attacks by assumption 47
Roadmap Password-based AKE Bellare-Pointchevel-Rogaway Abdalla-Pointcheval Katz-Ostrovsky-Yung Jiang-Gong Gennaro-Lindell PKI-based AKE Cannetti-Kcrawczyk LaMacchia-Lauter-Mityagin Kcrawczyk Multi-factor based AKE Pointcheval-Zimmer Eurocrypt 00 RSA 05 Eurocrypt 01 SAC 04 Eurocrypt 03 Cited by 833 Cited by 144 Cited by 279 Cited by 37 Cited by 128 Eurocrypt 01 ProvSec 07 Crypto 05 Cited by 668 Cited by 170 Cited by 289 ACNS 08 Cited by 15 * Citation data from Google Scholar (8 July, 2012) 48
Case study 3: multi-factor based AKE Alice and Bob perform authenticated key exchange based on multiple factors Password Tamper-resistant token Biometrics Pointcheval-Zimmer protocol (ACNS 08) First protocol that combines all three factors Has a formal model and formal proofs 49
Attacks Two attacks on Pointcheval-Zimmer protocol (Hao, Dylan, ACNS 12) 1. With a stolen password, attacker can further steal biometrics 2. Based on the above attack, attacker can further steal a private key (similar to Menezes et al s attack on HMQV in 2006) Conclusion: the attacker only needs to break one password factor in order to break the entire three-factor scheme. 50
