INTERNET DRAFT EXPIRES JAN 1999 INTERNET DRAFT Network Working Group T. Nishioka and T. Kubo INTERNET DRAFT Info. and Comm. Biz. Div. Category: Informational ADVANCE Co., Ltd. June 1998 The ID-based Key Management System (IDKMS) Status of This Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Distribution of this document is unlimited. Abstract This informational document describes some cryptographic protocols on an ID-based system called Key Predistribution System (KPS). Table of Contents 1. Introduction and preliminary remarks............................2 2. Setup...........................................................3 2.1. PAGS Setup...............................................3 2.2. User Setup...............................................3 3. Cryptographic Protocols.........................................4 3.1. Confidential Communication...............................4 3.2. Entity Authentication....................................5 3.3. Mutual Authentication....................................6 3.4. Message Authentication...................................8 3.5. Digital Signature........................................9 3.6. Key Recovery............................................10 4. Security Considerations and One Implementation of KPS..........12 Acknowledgment....................................................14 References........................................................14 Authors' Address..................................................14 Nishioka & Kubo Informational [Page 1] The ID-based Key Management System (IDKMS) July 1998 1. Introduction and preliminary remarks Cryptography is one of the fundamental tools to make the Internet a more secure network. It guards the Internet against various malicious attacks like eavesdropping, masquerading, falsifying, and so on. Although cryptography has powerful abilities in this area, it has also an Achilles' heel in key management. If key management were insecure, any system using cryptography would be totally defenseless, no matter how strong the cryptography is. The construction of a public -key infrastructure is one important point of the key management. In this memo we propose a different type of key management, which is based on an ID-based cryptography[1] called Key Predistribution System (KPS)[2,3]. The simplest KPS consists of one center and unspecified entities (users). It is assumed that each unspecified entity has his own broad-sense "name" represented by an ID, which may be something like, for example, a mail-address in the internet. The center called "KPS center" generates a center-algorithm represented by G. The center-algorithm G is confidential and nobody except the KPS center must know its content. The algorithm G outputs a secret algorithm if an ID is input into G. The secret algorithm is confidentially and securely distributed to an entity having the corresponding ID. The secret algorithm has the capability to generate a common key. If the owner inputs an ID into his secret algorithm, the secret algorithm outputs a common key between the owner and the entity having the corresponding ID. Therefore any common key has already been pre-distributed to an entity when the entity received his own secret algorithm. Using the above KPS, we introduce some interesting cryptographic protocols on the internet. The following protocols are mainly discussed on the application layer. It is expected that the reader is familiar with the basics of cryptography and linear algebra. Due to the ASCII representation of this memo, the following style is chosen for mathematical purposes: - a^{b} means the exponentiation of a to the power of b, which is always used within a modulo context. - a^[b] means a with an upper index of b. - a_[b] means a with a lower index or subscription of b. - a_[b,c] means a with lower indices or subscription of b and c. - a=b means equality or congruency within a modulo context. - E_{k}(M) means encryption of message M by key k. - D_{k}(C) means decryption of cipher C by key k. Nishioka & Kubo Informational [Page 2] The ID-based Key Management System (IDKMS) July 1998 2. Setup 2.1. PAGS Set up "Private Algorithm Generation System (PAGS)" represents both the KPS center and its center-algorithm: G( , ) for the internet. PAGS first generates the center-algorithm, G and stores it secretly. 2.2. User Set up An entity A applies for his own private ID to PAGS, where a private ID represents the secret-algorithm for the internet. 1. The entity A proposes his own "public ID": ID_[A] to PAGS, where public ID means usual the ID for the internet in contrast to the private ID. 2. Receiving A's application and his public ID, PAGS authenticates A and the correctness of ID_[A]. 3. If the application has no problem, PAGS generates the private ID: X_[A] using the center-algorithm G; X_[A]( )= G(ID_[A], )=G( ,ID_[A]). where G having two inputs is symmetric mapping the two inputs. If the application has a problem, PAGS notifies the applicant of the result and does not generate the corresponding private ID. 4. PAGS confidentially distributes the private ID, X_[A] to the entity A through a more secure channel than the internet. 5. Receiving the private ID, the entity A stores the private ID: X_[A] secretly. The entity A is able to share each different common key with any other entity B non-interactively using his own private ID, X_[A]. The entity A inputs B's public ID: ID_[B] into X_[A] and then A gets the common key: k_[AB]; k_[AB] = X_[A](ID_[B]) = G(ID_[A],ID_[B]). Independently and in the same way, the entity B can generate the common key with his private ID: X_[B]; k_[BA] = X_[B](ID_[A]) = G(ID_[B],ID_[A]), = G(ID_[A],ID_[B]), = k_[AB]. Nishioka & Kubo Informational [Page 3] The ID-based Key Management System (IDKMS) July 1998 3. Cryptographic Protocols Some interesting cryptographic protocols are presented in this section. They are based on some powerful features of KPS. 3.1. Confidential Communication We deal with confidential communication by common-key cryptography. It is critical to think about how to distribute a session key: k to a correct receiver B, where the session key is cryptographic and used to encrypt the main message: M. The ciphertext C is given by, E_{k}(M). We exhibit the key sharing between a sender A and a receiver B and the confidential communication protocol in the following; 3.1.1. Sender side 3.1.1.1. Common key generation The sender A generates a common key using his private ID and B's public ID; k_[AB] = X_[A](ID_[B]). 3.1.1.2. Session key generation The sender A generates a session key: k, using some appropriate random generator. 3.1.1.3. Message encryption Message M is encrypted with the session key into ciphertext C; C = E_{k}(M). 3.1.1.4. Session key encryption The session key is encrypted with the common key; E_{k_[AB]}(k). 3.1.1.5. Sending ciphertext The sender A sends the following data; ID_[A]aE_{k_[AB]}(k)aC, to the receiver B where the symbol "a"means concatenation. Note: The sender's public ID, ID_[A] needs not to be sent explicitly if the receiver recovers ID_[A] from other protocols. Nishioka & Kubo Informational [Page 4] The ID-based Key Management System (IDKMS) July 1998 3.1.2. Receiver side 3.1.2.1. Extraction of public ID Receiving the ciphered data, the receiver B extracts the sender's public ID: ID_[A], from them. 3.1.2.2. Common key generation The sender B generates a common key using his private ID and A's public ID; k_[AB] = X_[B](ID_[A]). 3.1.2.3. Session key decryption The session key is decrypted with the common key; k = D_{k_[AB]}(E_{k_[AB]}(k)). 3.1.2.4. Message decryption The Message is decrypted with the session key; M = D_{k}(C). 3.2. Entity Authentication Owing to KPS, any two entities share each own common key non -interactively. Using such a feature, a challenger C can authenticate a responder V. We introduce an authentication protocol in the following. It is assumed that the challenger C and the responder V have already known each public ID: ID_[C], ID_[V]. 3.2.1. Challenger side 3.2.1.1. Challenge word generation The challenger C generates a challenge word: R. It is preferred that the word R is a one-time word and usually generated from a random number generator. 3.2.1.2. Sending the challenge word The challenger C sends the word R to the responder V. Nishioka & Kubo Informational [Page 5] The ID-based Key Management System (IDKMS) July 1998 3.2.2. Responder side 3.2.2.1. Common key generation The responder V generates a common key: k_[CV] with the challenger C using V's private ID: X_[V] and C's public ID; k_[CV] = X_[V](ID_[C]). 3.2.2.2. Challenge word encryption Receiving the challenge word R, the responder V encrypts R with the common key; R' = E_{k_[CV]}(R). 3.2.2.3. Challenge response The responder V returns the response R' back to the challenger C. 3.2.3. Challenger side 3.2.3.1. Common key generation The challenger C generates a common key: k_[CV] using V's private ID: X_[C] and V's public ID; k_[CV] = X_[C](ID_[V]). 3.2.3.2. Response decryption Receiving the response, the challenger C decrypts the response with the common key; R'' = D_{k_[CV]}(R'). 3.2.3.3 Comparison The challenger C compares R'' with R. If R'' = R, the authentication is acknowledged. Otherwise the authentication is denied. 3.3. Mutual Authentication We can do mutual authentication using the entity authentication protocol in duplicate. It is, however, possible to save communicational cost by dealing with the duplicate protocols as a whole. We exhibit such a protocol in this section. We assume that an entity A with ID_[A] and an entity B with ID_[B] mutually authenticate and that both entities have already known each public ID. Nishioka & Kubo Informational [Page 6] The ID-based Key Management System (IDKMS) July 1998 3.3.1. Entity A side 3.3.1.1. Common key generation The entity A generates a common key: k_[AB]; k_[AB] = X_[A](ID_[B]). 3.3.1.2. Challenge word generation The entity A generates a challenge word: R_[A]. It is preferred that R_[A] is a random number. 3.3.1.3. Sending the challenge word The entity A sends the word R_[A] to the entity B. 3.3.2. Entity B side 3.3.2.1. Common key generation The entity B generates a common key: k_[AB]; k_[AB] = X_[B](ID_[A]). 3.3.2.2. Challenge word encryption Receiving the word R_[A], the entity B encrypts R_[A] with the common key k_[AB]; R'_[A] = E_{k_[AB]}(R_[A]). 3.3.2.3. Challenge word generation The entity B also generates a challenge word: R_[B]. It is preferred that R_[B] is a random number. 3.3.2.4. Sending the challenge and response word The entity B sends the word R'_[A] and R_[B] to the entity A; R'_[A]aR_[B]. 3.3.3. Entity A side 3.3.3.1. Response decryption Receiving the response R'_[A], the entity A decrypts it with the common key; R''_[A] = D_{k_[AB]}(R'_[A]). 3.3.3.2. Comparison The entity A compares R''_[A] with R_[A]. If R''_[A]=R_[A], the authentication of A to B is acknowledged. Otherwise the authentication is a denied. Nishioka & Kubo Informational [Page 7] The ID-based Key Management System (IDKMS) July 1998 3.3.3.3. Challenge word encryption The entity A encrypts the challenge word R_[B] with the common key; R'_[B] = E_{k_[AB]}(R_[B]). 3.3.3.4 Sending the response word The entity A sends the word R'_[B] to the entity B. 3.3.4. Entity B side 3.3.4.1. Response decryption Receiving the response R'_[B], the entity B decrypts it with the common key; R''_[B] = D_{k_[AB]}(R'_[B]). 3.3.4.2. Comparison The entity B compares R''_[B] with R_[B]. If R''_[B]=R_[B], authentication of B to A is acknowledged. Otherwise the authentication is a denied. 3.4. Message Authentication It is possible for a receiver to authenticate a message using key sharing based on KPS. Message authentication in this memo means that a receiver can confirm that a message is not falsified and that the identification of its sender is correct. We introduce a message authentication protocol in the following. It is assumed that a sender A sends a message M to a receiver B and that the sender A has already known the receiver B's public ID: ID_[B]. One of remarkable features of our protocol is the fact that it is not interactive. 3.4.1. Sender side 3.4.1.1. Common key generation The sender A generates a common key: k_[AB] from his private ID and the receiver's public ID in the following, k_[AB] = X_[A](ID_[B]). 3.4.1.2. Message hashing The sender A hashes a message M and the result is H(M), where H is a predefined hash function. Nishioka & Kubo Informational [Page 8] The ID-based Key Management System (IDKMS) July 1998 3.4.1.3. MAC generation Message authentication code (MAC) is generated from the hash value and the common key; MAC = E_{k_[AB]}(H(M)). 3.4.1.4. Message with MAC sending The sender A sends his own public ID, the message and the corresponding MAC: ID_[A]aMaMAC, to the receiver B. 3.4.2. Receiver side 3.4.2.1. Common key generation Receiving the message with MAC, the receiver B extracts the sender's public ID: ID_[A] from it. Then he generates the common key from the public ID and his own private ID; k_[AB] = X_[B](ID_[A]). 3.4.2.2. Message hashing The receiver B separates the message: M' itself from the message with MAC and then hashes the M'; H(M') 3.4.2.3. MAC decryption The receiver B decrypts the MAC with the common key; H(M)' = D_{k_[AB]}(MAC). 3.4.2.4. Comparison The receiver B compares the hashed message H(M') with the decrypted MAC H(M)'. If H(M')=H(M)', the authentication is acknowledged. Otherwise the authentication is denied. 3.5. Digital Signature In KPS, all related common keys have been already pre-distributed into each private ID. This feature enables us to construct some digital signature schemes. We introduce a digital signature scheme based on KPS using a one-way homomorphism in this section. The following signature scheme is an ID-based signature scheme and has no public key. Any entities with their own private ID can, however, authenticate any signature non-interactively. We assume that a signer A with ID_[A] signs a message M and a verifier B authenticates the message M of the signer A. Nishioka & Kubo Informational [Page 9] The ID-based Key Management System (IDKMS) July 1998 3.5.1. Signer side 3.5.1.1. Signing The signer A signs the message M with his own private ID using a keyed one-way homomorphism: F; Sign_[M,A]( ) = F_{M}(X_[A]( )) where the algebraic structure of X_[A] is succeeded into Sign_[M,A] by the homomorphism. However, the private ID itself cannot be derived from the signature by one-wayness of F. 3.5.1.2. Message sending or opening The signer A opens or sends the message, his public ID and the signature: ID_[A]aMaSign_[M,A], to the verifier B. 3.5.2. Verifier side 3.5.2.1. Authenticator_1 generation Receiving the message and the signer's public ID, the verifier B generates an authenticator_1: Auth_1, using his own private ID X_[B]; Auth_1 = F_{M}(X_[B](ID_[A])), = F_{M}(k_[AB]). 3.5.2.2. Authenticator_2 generation The verifier B generates an authenticator_2: Auth_2, from the signature itself and his public ID ID_[B]; Auth_2 = Sign_[M,A](ID_[B]), = F_{M}(X_[A](ID_[B])), = F_{M}(k_[AB]). 3.5.2.3. Comparison The verifier B compares Auth_1 with Auth_2. If Auth_1=Auth_2, the authentication is acknowledged. Otherwise the authentication is denied. 3.6. Key Recovery Strictly speaking, key recovery[4] may not be protocol. Nevertheless, it is a topic which cannot be neglected in the key management system. In this section, we introduce a key recovery scheme based on KPS[5]. Nishioka & Kubo Informational [Page 10] The ID-based Key Management System (IDKMS) July 1998 Although many Key Recovery Systems have been proposed recently, our KPS is particularly strong in the areas of Key Recovery System (KRS) with Data Recovery Field (DRF)[6]. In our scheme, PAGS further plays a role of Key Recovery Agent (KRA) and DRF is given by the encrypted session key itself: E_{k_[AB]}(k), in 3.1. (Confidential Communication). We then exhibit a key recovery protocol between Data Recovery Agency (DRA) and PAGS(KRA). It is assumed that the DRA has already got the ciphertext including the encrypted session key: ID_[A]aE_{k_[AB]}(k)aC, between the entity A and B in 3.1. (Confidential Communication) and the DRA knows also receiver's public ID, ID_B. 3.6.1. DRA side 3.6.1.1. DRF extraction DRA extracts the encrypted session key as DRF from the ciphertext to be recovered; DRF = E_{k_[AB]}(k). 3.6.1.2. Key Recovery Application DRA sends an application for the key recovery with the sender's public ID, the receiver's public ID and the DRF to PAGS; ID_[A]aID_[B]aDRF. 3.6.2. PAGS side 3.6.2.1. Key Recovery Authentication PAGS authenticates the application. If it is acceptable, PAGS takes the next step. Otherwise PAGS notifies DRA of the result. 3.6.2.2. Common key generation PAGS generates the common key from the center-algorithm using the two public IDs; k_[AB] = G(ID_[A],ID_[B]). 3.6.2.3. Session key recovery PAGS decrypts the DRF with the common key; k = D_{k_[AB]}(DRF). Nishioka & Kubo Informational [Page 11] The ID-based Key Management System (IDKMS) July 1998 3.6.2.4. Session key return back PAGS returns the session key k back to DRA. 3.6.3. DRA side 3.6.3.1. Message recovery Receiving the session key k, DRA decrypts the ciphertext with it; M = D_{k}(C). 4. Security Considerations and One Implementation of KPS The security of the above proposed protocols mainly depends on the security of KPS, though the security of cryptographic encryption algorithm, hash function, and random generator is also not negligible. There have been, however, many implementations proposed on KPS and the security of KPS depends on its implementation. We then recommend linear scheme KPS as the implementation of KPS. This KPS is based on information-theoretic security and has prominent simplicity and efficiency. We then briefly introduce a linear scheme KPS; 1. Center-algorithm The center-algorithm is represented by G_[i,j], where G is a (m,m) 2nd rank symmetric covariant tensor and its component is a random number belonging to GF(q) where q is a prime number. 2. Effective ID ID, for example ID_[A], is transferred to "effective ID": x_[A]^[i]; x_[A]^[i] = f^[i](ID_[A]), where f is a pre-defined one-way function. The effective ID is a contra-variant vector and its component also belongs to GF(q). 3. Secret algorithm The secret algorithm is generated from the center algorithm and the corresponding ID, for example, the entity A's secret-algorithm is given by, X_[A,i] = G_[i,j]f^[j](ID_[A]) mod q, = G_[i,j]x_[A]^[j] mod q, where Einstein's contraction is done on the overlapping index j. The secret-algorithm is then a covariant vector and its component also belongs to GF(q). Nishioka & Kubo Informational [Page 12] The ID-based Key Management System (IDKMS) July 1998 4. Common key Any common key is generated from secret-algorithm and ID, for example, the generation of the common key between A and B is as follows; k_[AB] = X_[A,i]f^[i](ID_[B]) mod q (A side), = X_[B,j]f^[j](ID_[A]) mod q (B side), = G_[i,j]x_[A]^[j]x_[B]^[i] mod q. In this way, the main calculation of the linear scheme KPS is simple. Moreover, an attacker needs at least m different secret algorithms to break the system completely. Such features suggest that the linear scheme KPS is a pragmatic one. We, however, recommend that each secret algorithm is stored in each tamper resistant module like an IC card. As one example of one-way homomorphism used in the digital signature, a homomorphism based on discrete log problem is proposed; 1. Signature Signature is given by, Sig_[M,A,i] = h^{X_[A,i]} mod p, where p is a large prime which satisfies q|p-1, and h is a specific value determined with the message M and the signer's ID_[A]: h = h(M, ID_[A]), where the order of the cyclic group generated by h on modulo p must be sufficient large. 2. Authenticator_2 Authenticator_1 is easily calculated in this implementation. Authentictor_2 is calculated in the following way; Auth_2= prod_[i=1]^[i=m] Sig_[M,A,i]^{f^[i](ID_[B])}mod p, = prod_[i=1]^[i=m] Sig_[M,A,i]^{x_[B]^[i]} mod p. where "prod" means that the following terms are multiplied from i=1 to i=m. The security of the signature scheme depends on both computational complex and information-theoretic security. Nishioka & Kubo Informational [Page 13] The ID-based Key Management System (IDKMS) July 1998 Acknowledgements One of the authors thanks to Prof. Imai and Imailab members for useful advises on some topics. References 1. A. Shamir, "Identity-Based Cryptosystems and Signature Schemes," Advances in Cryptology: Proc. of CRYPTO'84, Springer LNCS 196, pp.47-53, 1985 2. T. Matsumoto and H. Imai, "On the KEY PREDISTRIBUTION SYSTEM: A Practical Solution to the Key Distribution Problem," Advances in Cryptology: Proc. of CRYPTO'87, Springer LNCS 293, pp.185-193, 1987. 3. T. Matsumoto and H. Imai, "Applying the key predistribution systems to electronic mails and signatures," Proc. of SITA'87, pp.101-106, 1987. 4. D. E. Denning and D. K. Branstad, "A Taxonomy for Key Recovery Encryption System,"(URL:http://www.cosc.georgetown.edu/~denning /crypto/taxonom.html),May 11, 1997. D. E. Denning and D. K. Branstad, "A Taxonomy for Key Escrow Encryption System," Communication of the ACM, Vol.39, No,3, pp.34-40, March 1996. 5. T. Kubo, "Key Pre-distribution System as a Key Recovery system," Proc. of PKS'97, April 1997. 6. T. Nishioka, K. Matsuura, Y. Zheng, and H. Imai, "A Proposal for Authenticated Key Recovery System," Proc. JW-ISC'97,pp.189-196, October 1997 Authors' Address Tsuyoshi Nishioka, Ph.D. IT Laboratory Taka Kubo, Ph.D. Information & Communication Business Division ADVANCE Co., Ltd. 5-7, Nihonbashi-Kobunacho Chuo-ku, Tokyo 103-8354 Japan Phone: ++81 3 3667 6148 Fax: ++81 3 3664 4387 E-mail: nishioka@advance.co.jp, kubo@advance.co.jp WWW: http://www.advance.co.jp INTERNET DRAFT EXPIRES JAN 1999 INTERNET DRAFT