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)
<draft-rfced-info-kubo-00.txt>
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