Kim-Kwang Raymond Choo
Affiliation: Information Security Institute
Security Proof for the Improved Ryu-Yoon-Yoo Identity-Based Key Agreement Protocol
Key agreement protocols are essential for secure communications in open and distributed environments. The protocol design is, however, extremely error-prone as evidenced by the iterative process of fixing discovered attacks on published protocols. We revisit an efficient identity-based (ID-based) key agreement protocol due to Ryu, Yoon and Yoo. The protocol is highly efficient and suitable for real-world applications despite offering no resilience against key-compromise impersonation (K-CI). We then show that the protocol is, in fact, insecure against reflection attacks. A slight modification to the protocol is proposed, which results in significant benefits for the security of the protocol without compromising on its efficiency. Finally, we prove the improved protocol secure in a widely accepted model.
Key Agreement from Signatures: Improved Protocols and Anonymous Extension
We exploit the relationships between signature schemes and key agreement protocols; and propose a high performance identity-based (ID-based) key agreement protocol based on strong pairing challenge-response signatures. The latter is the first of its kind in ID-based cryptography and is of interest in itself. Using the proof technique of signature unforgeability against adaptive chosen-message attack, our protocol fully supports Session-Key Reveal queries and partially supports Session-State Reveal queries (which leaks ephemeral secret and keying material for session key derivation), without gap assumption or any unrealistic restriction. We show how to incorporate KGC forward secrecy so the past session keys are not compromised even the adversary gets the master secret key of the Key Generation Center (and the private keys of all users). Both proposals are efficient and have the strongest security among other unbroken identity-based two-party two-message protocols. Inspired by ring signatures and motivated by the need for a better anonymous roaming mechanism, we extend our basic protocol to support key agreement among spontaneous anonymous groups (SAG). To the best of our knowledge, this is the first ID-based SAG key agreement protocol with bilateral privacy.
Perfect Forward Secure Identity-Based Authenticated Key Agreement Protocol in the Escrow Mode
There are several essential features in key agreement protocols such as key escrow (essential when confidentiality, audit trail and legal interception are required) and perfect forward secrecy (i.e., the security of a session key established between two or more entities is guaranteed even when the private keys of the entities are compromised). Majority of the existing escrowable identity-based key agreement protocols, however, only provide partial forward secrecy. Therefore, such protocols are unsuitable for real-word applications that require a stronger sense of forward secrecy --- perfect forward secrecy. In this paper, we propose an efficient perfect forward secure identity-based key agreement protocol in the escrow mode. We prove the security of our protocol in the random oracle model, assuming the intractability of the Gap Bilinear Diffie-Hellman (GBDH) problem. Security proofs are invaluable tools in assuring protocol implementers about the security properties of protocols. We note, however, that many existing security proofs of previously published identity-based protocols entail lengthy and complicated mathematical proofs. In this paper, our proof adopts a modular approach and, hence, simpler to follow.
New Identity-Based Authenticated Key Agreement Protocols from Pairings (without Random Oracles)
We present the first provably secure ID-based key agreement protocol, inspired by the ID-based encryption scheme of Gentry, in the standard (non-random-oracle) model. We show how this key agreement can be used in either escrowed or escrowless mode. We also give a protocol which enables users of separate private key generators to agree on a shared secret key. All our proposed protocols have comparable performance to all known protocols that are proven secure in the random oracle model.
Examining Indistinguishability-Based Proof Models for Key Establishment Protocols
We examine various indistinguishability-based proof models for key establishment protocols, namely the Bellare & Rogaway (1993, 1995), the Bellare, Pointcheval, & Rogaway (2000), and the Canetti & Krawczyk (2001) proof models. We then consider several variants of these proof models, identify several subtle differences between these variants and models, and compare the relative strengths of the notions of security between the models. For each of the pair of relations between the models (either an implication or a non-implication), we provide proofs or counter-examples to support the observed relations. We also reveal a drawback with the original formulation of the Bellare, Pointcheval, & Rogaway (2000) model, whereby the Corrupt query is not allowed. As a case study, we use the Abdalla & Pointcheval (2005) three-party password-based key exchange protocol (3PAKE), which carries a proof of security in the Bellare, Pointcheval, & Rogaway (2000) model. We reveal a previously unpublished flaw in the protocol, and demonstrate that this attack would not be captured in the model due to the omission of the Corrupt query.
Errors in Computational Complexity Proofs for Protocols
Proofs are invaluable tools in assuring protocol implementers about the security properties of protocols. However, several instances of undetected flaws in the proofs of protocols (resulting in flawed protocols) undermine the credibility of provably-secure protocols. In this work, we examine several protocols with claimed proofs of security by Boyd & Gonzalez Nieto (2003), Jakobsson & Pointcheval (2001), and Wong & Chan (2001), and an authenticator by Bellare, Canetti, & Krawczyk (1998). Using these protocols as case studies, we reveal previously unpublished flaws in these protocols and their proofs. We hope our analysis will enable similar mistakes to be avoided in the future.
Revisit Of McCullagh--Barreto Two-Party ID-Based Authenticated Key Agreement Protocols
The recently proposed two-party ID-based authenticated key agreement protocols (with and without escrow) and its variant resistant to key-compromise impersonation by McCullagh & Barreto are revisited. The protocol carries a proof of security in the Bellare & Rogaway (1993) model. In this paper, it is demonstrated that the protocols and its variant are not secure if the adversary is allowed to send a Reveal query to reveal non-partner players who had accepted the same session key.