Cryptography – Key management – Key distribution
Reexamination Certificate
2000-02-07
2001-04-10
Swann, Tod (Department: 2132)
Cryptography
Key management
Key distribution
C380S282000, C713S170000, C713S171000
Reexamination Certificate
active
06215878
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates generally to electronic communications and more particularly to communicating messages securely to an intended group.
2. Discussion of the Background Art
Transmitting secure messages from one party over public communication channels to another party poses several problems. The message transmitter and recipient often desire that a message be transmitted to and from the intended party and not be intercepted by a third party. Cryptography, including Diffie-Heliman exchanges, public/private key methodology, and other encryption techniques, provides different ways of message encryption and/or authentication which help solve this problem. Each party using a public/private key encryption technique has a public key K
pu
and a private key K
pr
. Public key K
pu
is made available so that any member of the public can use it to encrypt a message. Private key K
pr
is kept private to one party so that only he can use it to decrypt messages that were encrypted with public key K
pu
. Many communication applications, such as secure multicast transmissions and secure routing protocols, involve a group of more than two communicating parties, and require establishment of a common secret key for use by the group members. Diffie-Hellman exchanges can be extended to work with a group. However, an N-member group requires each party to perform N exponentiation operations, so as N increases the communication expense increases disproportionately. Further, adding a single new member requires all parties to take part in a new multiparty exchange, making this technique unsatisfactory, for example, for dynamic multicast groups.
Harney et al. in “Group Key Management Protocol” (GKMP), September 1994, provide a solution to specifically distribute a secret key to intended group members. In Harney each party first performs an authenticated Diffie-Hellman exchange with a key holder. The key holder then uses a session key generated from the Diffie-Hellman exchange to encrypt the secret key and sends the result to the requesting party.
Harney also is expensive because it requires a complete exchange with two costly exponentiations and at least two public key operations to authenticate the communication. Additionally, the secret key is directly encrypted with the Diffie-Hellman secret key using a symmetric cipher in which an encryption key can be calculated from a corresponding decryption key and vice versa. In many cases the encryption key and decryption key are identical and each party in the communication exchange must agree on the keys before they are used. Harney thus allows a third party seeking to steal the secret key to attack only the symmetric cipher.
U.S. Pat. No. 5,729,680 to Janson et al. discloses a method for distributing a key from a party B to a party A, which provides a basis for distributing the key in multi-party communications. However, Janson requires that parties A and B share a common key K
ab
prior to protocol execution. Additionally, Janson does not initially exchange identity stamps to be used in subsequent communication exchanges to provide liveness proof of each party A and party B during these communication exchanges. Liveness proof of party A proves to party B that party B received the subject information from party A, and not from a third party who could have recorded a previous communication from party A to party B and then replayed the communication to party B. Similarly, liveness proof of party B proves to party A that party A received the subject information from party B. Janson then discloses that party A, upon receiving the secret key from party B, sends receipt acknowledgement to party B. In addition, party A authenticates itself to party B, but not vice-versa. Party A thus does not have proof that party B is the actual key holder and not an imposter.
In light of the deficiencies of the prior art, what is needed is a technique to quickly, efficiently, and securely distribute a secret key to intended group members.
INVENTION SUMMARY
The invention provides a key distribution method in which a key holder H distributes a secret key K to only intended group members M. During the distribution process the invention assures that each party, a member M and the key holder H, can encrypt and decrypt exchanged information such that the encrypter knows that the decrypter will be the intended party. The invention preferably uses a public key/private key encryption technique in which, for example, a trusted Certificate Authority in a public key infrastructure signs the certificates to provide the public keys involved in the encryption. Alternatively, the invention, together with a symmetric cipher, uses a shared secret, established through an authenticated mechanism outside the information exchanges of the invention. Additionally, the invention uses a strong mixing function that takes several pieces of data as input and produces a pseudo-random authentication (or digest). Data inputs to the mixing function include identity stamps that are generated by each member M and key holder H. These inputs can be the identity of the stamp generator, such as a network address, port, or protocol, or can be a timestamp and/or a secret value that is known only to the stamp generator. The stamps include information to bind member M if generated by key holder H, and to bind key holder H if generated by member M. Consequently, the invention authenticates each communication exchange between member M and key holder H.
In accordance with the invention, a key requester, normally an intended group member M, chooses a random code R
m
, and uses encryption key K
me
to encrypt code R
m
and form encrypted code R
me
. Member M then sends encrypted code R
me
to key holder H. Key holder H uses decryption key K
hd
to decrypt the encrypted code R
me
and thereby acquire code R
m
. Key holder H then creates a coded secret of secret key K; he preferably takes the exclusive-OR of secret key K and code R
m
to generate a code R
h
. Key holder H then uses encryption key K
me
to encrypt code R
h
and sends it to member M. Member M then, using decryption key K
md
, decrypts the encrypted code R
h
and derives secret key K by performing the exclusive-OR of the two codes R
h
and R
m
. In addition, each party generates an identity stamp, which is a pseudo-random bit stream that is bound to his identity, and uses this stamp when needed as a liveness proof in communication exchanges. The invention also uses time stamps, mixing functions including hashing, and digital signatures for further security and authentication. Group members do not need to know one another, but must trust the encryption keys K
me
and K
he
. This can be accomplished by using a certificate authority.
Because the invention requires two encryptions in communication exchanges, attacking the invention's scheme for protecting secret key K requires breaking two difficult encryptions, especially when the preferred embodiment uses the public/private key encryption technique. Breaking each public/private key encryption is more difficult than breaking a single symmetric cipher as in Harney because breaking a public/private key encryption involves factoring a very large number, which may have over a thousand bits, into two smaller prime numbers while breaking a symmetric cipher requires breaking two codes. Further, the invention costs less because it incurs low overhead and does not involve expensive Diffie-Hellman exchanges. The invention, allowing efficient addition of new members, is also relatively simple, fast, scalable, and secure. In the preferred embodiment, where certificates in a public key infrastructure provide public encryption keys (key K
me
and key K
he
) for the public/private key encryption technique, the invention does not require bootstrapping, i.e., prior communication or configuration.
REFERENCES:
patent: 4956863 (1990-09-01), Goss
patent: 5729608 (1998-03-01), Janson et al.
patent: 5889865 (1999-03-01), Vanstone et al.
patent: 6038322 (2000-03-01), Harkins
patent:
Cisco Technology Inc.
Darrow Justin T.
Hickman Palermo & Truong & Becker LLP
Palermo Christopher J.
Swann Tod
LandOfFree
Group key distribution does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Group key distribution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Group key distribution will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2537974