Yaksha, an improved system and method for securing communications using split private key asymmetric cryptography

Claims

What is claimed:

1. A method for securing communications over a system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion, said method for securing communications between at least a first and second of said plurality of users comprising the steps of:

generating, for the first user, a temporary asymmetric crypto-key having a first temporary key portion and an associated second temporary key portion;

encrypting said second temporary key portion with the first private key portion of a first user crypto-key associated with the first user to form a first encrypted message;

obtaining, for a third user, the second temporary key portion by applying the second private key portion of the first user crypto-key to the first encrypted message, thereby authenticating the first user to a third user;

further encrypting the first encrypted message with the second private key portion of the first user crypto-key to form a second encrypted message; and

obtaining, for the first user, the second temporary key portion by applying the public key portion of the first user crypto-key to decrypt the second encrypted message and thereby authenticating the third user to the first user.

2. A method for securing communications according to claim 1, further comprising the steps of:

encrypting a first message from the third user to the second user and a first symmetric session crypto-key with the second private key portion of a second user crypto-key associated with the second user to form a third encrypted message;

encrypting the first symmetric session crypto-key with the second temporary key portion to form a forth encrypted message,

obtaining, for the first user, the first symmetric session crypto-key by applying the first temporary key portion to the decrypt the fourth encrypted message;

encrypting the third encrypted message with the first temporary key portion to form a fifth encrypted message; and

obtaining, for the second user, the first message and the first symmetric session crypto-key by applying the second temporary key portion and the first private key portion of the second user crypto-key to decrypt the fifth encrypted message, thereby authenticating the first user and the third user to the second user.

3. A method for securing communications according to claim 1, further comprising the step of obtaining, for the second user, the second temporary key portion by applying the public key portion of the first user crypto-key to decrypt the second encrypted message, thereby authenticating the first and third users to the second user.

4. A method for securing communications according to claim 2, wherein said third user is an authentication server and said second user is a ticket granting server which grants a ticket for service from a fourth user.

5. A method for securing communications according to claim 4, further comprising the step of encrypting a second message from the first user to the second user with the first symmetric session key to form a sixth encrypted message, wherein said first message is an instruction to grant said ticket and said second message is a time stamp.

6. A method for securing communications according to claim 4, further comprising the steps of:

encrypting a third message to the fourth user and a second symmetric session key with the second private key portion of a fourth user crypto-key associated with the fourth user to form a seventh encrypted message;

encrypting the third encrypted message with the first private key portion of the second user crypto-key to form an eight encrypted message;

encrypting the second symmetric session key with the first symmetric session key to form a ninth encrypted message;

obtaining, for the first user, the first message and the first symmetric session key by applying the public key portion of the second user crypto-key to the eight encrypted messages, thereby authenticating the second user to the first user;

obtaining, for the first user, the second symmetric session key by applying the first symmetric session key to the ninth encrypted message;

encrypting the seventh encrypted message with the first temporary key portion to form a tenth encrypted message; and

obtaining, for the fourth user, the third message and the second symmetric session crypto-key by applying the second temporary key portion and the first private key portion of the fourth user crypto-key to the tenth encrypted message and thereby authenticating the first and second users to the fourth user.

7. A method for securing communications according to claim 6, further comprising the steps of:

encrypting the seventh encrypted message with the first private key portion of the fourth user crypto-key to form a twelfth encrypted message; and

obtaining, for the first user, the third message and the second symmetric session key by applying the public key portion of the fourth user crypro-key to the twelfth encrypted message and thereby authenticating the fourth user to the first user.

8. A method for securing communications according to claim 6, further comprising the step of obtaining the second temporary key portion by applying the public key portion of the first user crypto-key to decrypt the second encrypted message, thereby authenticating the first and third users to the second user and the first and third users to the fourth user.

9. A method for securing communications according to claim 6, further comprising the step of encrypting a fourth message from the first user to the fourth user with the second symmetric session key to form a eleventh encrypted message, wherein said third message to the fourth user is a ticket instructing the fourth user to provide a service and said fourth message to the fourth user is a time stamp.

10. A method for securing communications according to claim 6, wherein:

the first encrypted message includes a first random number string concatenated with the second temporary key portion;

the fourth encrypted message includes a second random number string concatenated with the first symmetric session crypto-key; and

the ninth encrypted message includes a third random number string concatenated with the second symmetric session crypto-key.

11. A method for securing communications according to claim 1, wherein said asymmetrical crypto-keys are applied using modular exponentiation.

12. A method for securing communications according to claim 1, wherein said temporary crypto-key has an associated expiration time.

13. A method for securing communications according to claim 1, further comprising the steps of:

encrypting a hash message with the first private key portion of the first user crypto-key to form a third encrypted message, thereby placing a signature of the first user on the hash message;

encrypting said third encrypted message with said first temporary key portion and with the first private key portion of the first user crypto-key to form a fourth encrypted message;

obtaining, for the third user, the third encrypted message by applying said second temporary key portion and the second private key portion of the first user crypto-key to the fourth encrypted message;

encrypting said third encrypted message with the second private key portion of the first user crypto-key to form a fifth encrypted message, thereby placing a signature of the third user on the hash message; and

obtaining, for the second user, the hash message by applying the public key portion of the first user crypto-key to the fifth encrypted message, thereby verifying the joint signatures of the first and third users on the hash message.

14. A method for securing communications according to claim 13, further comprising the step of encrypting said fifth encrypted message with said second temporary key portion.

15. A method for jointly signing communications over a system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion, said method for a first and second of said plurality of users jointly signing communications comprising the steps of:

generating, for the first user, a temporary asymmetric crypto-key having a first temporary key portion and an associated second temporary key portion;

encrypting said second temporary key portion with the first private key portion of a first user crypto-key associated with the first user to form a first encrypted message;

encrypting a hash message with the first private key portion of the first user crypto-key to form a second encrypted message, thereby placing a signature of the first user on the hash message;

encrypting said second encrypted message with said first temporary key portion to form a third encrypted message;

obtaining, for the second user, the second temporary key portion by applying the second private key portion of the first user crypto-key to the first encrypted message, thereby authenticating the first user to the second user;

obtaining, for the second user, the second encrypted message by applying said second temporary key portion to the third encrypted message;

encrypting said second encrypted message with the second private key portion of the first user crypto-key to form a fourth encrypted message, thereby placing a signature of the second user on the hash message; and

obtaining the hash message by applying the public key portion of the first user crypto-key to the fourth encrypted message, thereby verifying the joint signatures of the first and second users on the hash message.

16. A method for jointly signing communications according to claim 15, further comprising the steps of:

encrypting said fourth encrypted message with said second temporary key portion to form a fifth encrypted message;

encrypting said first encrypted message with the second private key portion of the first user crypto-key to form a sixth encrypted message;

obtaining, for a third user, said second temporary key portion by applying the public key portion of the first user crypto-key to the sixth encrypted message; and

obtaining, for the third user said hash message by applying the second temporary public key and the public key portion of the first user crypto-key to the fifth encrypted message;

wherein the third encrypted message includes a first random number string concatenated with the second encrypted message, and the fifth encrypted message includes a second random number string concatenated with the fourth encrypted message.

17. A method for jointly signing communications according to claim 15, wherein said asymmetrical crypto-keys are applied using modular exponentiation.

18. A method for securing communications over a system according to claim 15, wherein said temporary crypto-key has an associated expiration time.

19. A secure communications system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion, said system comprising:

a database having each said second private key portion stored therein;

a first processor connected to a communications network for (i) generating a temporary asymmetric crypto-key having a first temporary key portion and an associated second temporary key portion, (ii) encrypting said second temporary key portion with the first private key portion of a first user crypto-key associated with a first user to form a first encrypted message, and (iii) transmitting said first encrypted message over the communications network; and

a second processor connected to the database and to the communications network for (i) retrieving the second private key portion of the first user crypto-key from the database (ii) obtaining the second temporary key portion by applying the second private key portion of the first user crypto-key to the first encrypted message, thereby authenticating the first user, (iii) encrypting the first encrypted message with the second private key portion of the first user crypto-key to form a second encrypted message, and (iv) transmitting the second encrypted message over the communications network;

wherein the first processor obtains the second temporary key portion by applying the public key portion of the first user crypto-key to decrypt the second encrypted message and thereby authenticates a second user.

20. A secure communications system according to claim 19, wherein:

said second processor (i) retrieves the second private key portion of a third user crypto-key associated with a third user from the database, (ii) generates a first symmetric session crypto-key, (iii) encrypts a first message to the third user and the first symmetric session crypto-key with the second private key portion of the third user crypto-key to form a third encrypted message, (iv) encrypts the first symmetric session crypto-key with the second temporary key portion to form a forth encrypted message; and (v) transmits the third and fourth encrypted messages over the communications network; and

said first processor (i) obtains the first symmetric session crypto-key by applying the first temporary key portion to the decrypt the fourth encrypted message, and (ii) encrypts the third encrypted message with the first temporary key portion to form a fifth encrypted message, and (iii) transmits the fifth encrypted message over the communications network.

21. A secure communications system according to claim 20, further comprising:

a third processor connected to said communications network for obtaining the first message and the first symmetric session crypto-key by applying the second temporary key portion and the first private key portion of the second user crypto-key to decrypt the fifth encrypted message, thereby authenticating the first user and the second user.

22. A secure communications system according to claim 19, wherein:

said first processor (i) encrypts a hash message with the first private key portion of the first user crypto-key to form a third encrypted message, thereby placing a signature of the first user on the hash message, (ii) encrypts said third encrypted message with said first temporary key portion and with the first private key portion of the first user crypto-key to form a fourth encrypted message, and (iii) transmits said fourth encrypted messages over the network;

said second processor (i) obtains the third encrypted message by applying said second temporary key portion and the second private key portion of the first user crypro-key to the fourth encrypted message, (ii) encrypts said third encrypted message with the second private key portion of the first user crypto-key to form a sixth encrypted message, thereby placing a signature of the second user on the hash message.

23. A secure communications system according to claim 22, further comprising a third processor for obtaining the hash message by applying the public key portion of the first user crypto-key to the sixth encrypted message, thereby verifying the joint signatures of the first and second users.

24. A method for authenticating users of a system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion known only to a third party, said method for authenticating users comprising the steps of:

a first user encrypting a first message with the first private key portion of a first user crypto-key associated with the first user to form a first encrypted message;

the third party obtaining the first message by applying the second private key portion of the first user crypto-key to the first encrypted message, thereby authenticating the first user to the third party;

the third party encrypting the first encrypted message with the second private key portion of the first user crypto-key to form a second encrypted message; and

the first user, obtaining the first message by applying the public key portion of the first user crypto-key to decrypt the second encrypted message and thereby authenticating the third party to the first user.

25. A method for authenticating user of a system according to claim 24, wherein said third party is an authentication server.

26. A method for authenticating users of a system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion known only to a third party, said method for authenticating users comprising the steps of:

a first user encrypting a first message with the first private key portion of a first user crypto-key associated with the first user to form a first encrypted message;

the third party encrypting the first encrypted message with the second private key portion of the first user crypto-key to form a second encrypted message; and

a second user obtaining the first message by applying the public key portion of the first user crypto-key to decrypt the second encrypted message and thereby authenticating the first user to the second user.

27. A method for authenticating user of a system according to claim 26, wherein said step of said second user obtaining said first message verifies that the first message is signed by both the first user and the third party.

28. A method for authenticating user of a system according to claim 26, wherein said third party is an authentication server.

29. A method for authenticating users of a system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion known only to a third party, said method for authenticating users comprising the steps of:

the third party encrypting a first message with the second private key portion of a first user crypto-key associated with the first user to form a first encrypted message;

a first user encrypting the first encrypted message with the first private key portion of the first user crypto-key to form a second encrypted message;

a second user, obtaining the first message by applying the public key portion of the first user crypto-key to decrypt the second encrypted message and thereby authenticating the first user to the second user.

30. A method for authenticating user of a system according to claim 29, wherein said step of said second user obtaining said first message verifies that the first message is signed by both the first user and the third party.

31. A method for authenticating user of a system according to claim 29, wherein said third party is an authentication server.

32. A method for securing communications over a system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion known only to a third party, said method for securing communications between at least a first and second of said plurality of users comprising the steps of:

generating a temporary asymmetric crypto-key having a first temporary key portion and an associated second temporary key portion;

the first user encrypting said second temporary key portion with the first private key portion of a first user crypto-key associated with the first user to form a first encrypted message;

the third party encrypting the first encrypted message with the second private key portion of the first user crypto-key to form a second encrypted message;

the second user obtaining said second temporary key portion by applying the public key portion of the first user crypto-key; and

encrypting a communication between the first user and the second user with one of either said first temporary key portion or said second temporary key portion and decrypting said encrypted communication with the other of either said first temporary key portion or said second temporary key portion.

33. A method for authenticating user of a system according to claim 32, wherein said third party is an authentication server.

34. A method for securing communications over a system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion known only to a third party, said method for securing communications between at least a first and second of said plurality of users comprising the steps of:

generating a temporary asymmetric crypto-key having a first temporary key portion and an associated second temporary key portion;

the third party encrypting a symmetric session crypto-key with the second private key portion of a first user crypto-key associated with a first user to form a first encrypted message;

the third party encrypting the symmetric session crypto-key with the second temporary key portion to form a second encrypted message,

obtaining, for a second user, the symmetric session crypto-key by applying the first temporary key portion to decrypt the second encrypted message;

encrypting the first encrypted message with the first temporary key portion to form a third encrypted message;

obtaining, for the first user, the symmetric session crypto-key by applying the second temporary key portion and the first private key portion of the first user crypto-key to decrypt the third encrypted message; and

encrypting a communication between the first user and the second user with said symmetric session crypto-key.

35. A method for securing communications according to claim 34, further comprising the symmetric session crypto-key being disclosed, by the third party, to a third user for eavesdropping on said encrypted communication.

36. A method for securing communications over a system having a plurality of system users, each said user having an associated asymmetric crypto-key with a public key portion and a corresponding private key portion, each public key portion being accessible to the plurality of system users, each private key portion having a first private key portion known only to the associated user and a corresponding second private key portion known only to a third party, said method for securing communications between at least a first and second of said plurality of users comprising the steps of:

generating a temporary asymmetric crypto-key having a first temporary key portion and, an associated second temporary key portion;

the third party encrypting a first symmetric session key with the second private key portion of a first user crypto-key associated with a first user to form a first encrypted message;

the third party encrypting the first symmetric session key with a second symmetric session key to form a second encrypted message;

obtaining, for a second user, the first symmetric session key by applying the second symmetric session key to the second encrypted message;

the second user encrypting the first encrypted message with the first temporary key portion to form a third encrypted message; obtaining, for the first user, the second symmetric session crypro-key by applying the second temporary key portion and the first private key portion of the first user crypto-key to the third encrypted message; and

encrypting a communication between the first user and the second user with said second symmetric session crypto-key.

37. A method for securing communications according to claim 36, further comprising the second symmetric session crypto-key being disclosed, by the third party, to a third user for eavesdropping on said encrypted communication.

BACKGROUND OF INVENTION

1. Field Of The Invention

The present invention relates generally to securing communications using cryptography. More particularly, the present invention provides a method and system for enhancing the security of communications using asymmetric crypto-keys and is especially useful in enhancing communication security in conventional Kerberos authentication systems.

2. Description of the Related Art

Cryptosystems have been developed for maintaining the privacy of information transmitted across a communications channel. Often, a symmetric cryptosystem is used for this purpose. Symmetric cryptosystems, which utilize electronic keys, can be likened to a physical security system where a box has a single locking mechanism with a single key hole. One key holder uses his/her key to open the box, place a message in the box and relock the box. Only a second holder of the identical copy of the key can unlock the box and retrieve the message. The term symmetric reflects the fact that both users must have identical keys.

In more technical terms, a symmetric cryptosystem comprises an encryption function E, a decryption function D, and a shared secret-key, K. The key is a unique string of data bits to which the functions are applied. Two examples of encipherment/decipherment functions are the National Bureau of Standards Data Encryption Standard (DES) and the more recent Fast Encipherment Algorithm (FEAL). To transmit a message, M, in privacy, the sender computes C=E (M,K), where C is referred to as the ciphertext. Upon receipt of C, the recipient computes M =D (C,K), to recover the message M. An eavesdropper who copies C, but does not know K, will find it practically impossible to recover M. Typically, all details of the enciphering and deciphering functions, E and D, are well known, and the security of the system depends solely on maintaining the secrecy of key, K. Conventional symmetric cryptosystems are fairly efficient and can be used for encryption at fairly high data rates, especially if appropriate hardware implementations are used.

Asymmetric cryptosystems, often referred to as public key cryptosystems, provide another means of encrypting information. Such systems differ from symmetric systems in that, in terms of physical analogue, the box has one lock with two non-identical keys associated with it. For example, in an RSA system, either key can be used to unlock the box to retrieve a message which has been locked in the box by the other key. However, the system could be limited to using the keys in a particular sequence, such that the box can only be locked with the one key and unlocked with the other key.

In public key electronic cryptosystems, each entity, has a private key, d, which is known only to the entity, and a public key, eN, which is publicly known. Once a message is encrypted with a user's public-key, it can only be decrypted using that user's private-key, and conversely, if a message is encrypted with a user's private-key, it can only be decrypted using that user's public-key. It will be understood by those familiar with the art that although the terms "encrypt" and "decrypt" and derivations thereof are used herein in describing the use of public and private keys in an asymmetric public key cryptosystem, the term "transform" is commonly used in the art interchangeably with the term "encrypt" and the term "invert" is commonly used in the art interchangeably with the term "decrypt". Accordingly, as used herein in describing the use of public and private keys, the term "transform" could be substituted for the term "encrypt" and the term "invert" could be substituted for the term "decrypt".

If sender x wishes to send a message to receiver y, then x, "looks-up" y's public key eN, and computes M=E(C,e.sub.y) and sends it to y. User y can recover M using its private-key d.sub.y, by computing C=D(M,d.sub.y). An adversary who makes a copy of C, but does not have d.sub.y, cannot recover M. However, public-key cryptosystems are inefficient for large messages.

Public-key cryptosystems are quite useful for digital signatures. The signer, x, computes S=E(M,d.sub.x) and sends [M,S] to y. User y "looks-up" x's public-key e.sub.x, and then checks to see if M=D(S,e.sub.x). If it does, then y can be confident that x signed the message, since computing S, such that M=D(S,e.sub.x), requires knowledge of d.sub.x, x's private key, which only x knows.

Public-key cryptography also provides a convenient way of performing session key exchange, after which the key that was exchanged can be used for encrypting messages during the course of a particular communications session and then destroyed, though this can vary depending on the application.

One public key cryptographic system is the Rivest, Shamir, Adleman (RSA) system, as described in Rivest, Shamir and Adleman, "A Method of Obtaining Digital Signatures and Public Key Cryptosystems", CACM, Vol 21, pp 120-126, February 1978. RSA is a public-key based cryptosystem that is believed to be very difficult to break. In the RSA system the pair (e.sub.i N.sub.i), is user i's public-key and d.sub.i is the user's private key. Here N.sub.i =pq, where p and q are large primes. Here also e.sub.i d.sub.i =1mod.phi.(N.sub.i), where .phi.(N.sub.i)=(p-1)(q-1) which is the Euler Toitient function which returns the number of positive numbers less than N.sub.i, that are relatively prime to N.sub.i. A Carmichael function is sometime is used in lieu of a Euler Toitient function.

To encrypt a message being sent to user j, user i will compute C=M.sup.(e.sbsp.j.sup.) modN.sub.j and send C to user j. User j can then perform M=C.sup.(d.sbsp.j.sup.) modN.sub.j to recover M. User i could also send the message using his signature. The RSA based signature of user i on the message, M, is M.sup.d.sbsp.i modN.sub.i. The recipient of the message, user j, can perform (M.sup.(d.sbsp.i.sup.) modN.sub.i).sup.(e.sbsp.i.sup.) modN.sub.i, to verify the signature of i on M.

In a typical mode of operation, i sends j, M.sup.(d.sbsp.i.sup.) modN.sub.i along with M and a certificate C=(i,e.sub.i N.sub.i)(.sup.d.sbsp.CA)modN.sub.CA, where C is generated by a Certificate Authority (CA) which serves as a trusted off-line intermediary. User j can recover i's public key from C, by performing C.sup.(e.sbsp.CA.sup.) modN.sub.CA, as e.sub.CA and N.sub.CA are universally known. It should also be noted that in an RSA system the encryption and signatures can be combined.

Modifications to RSA systems have been proposed to enable multi-signatures to be implemented. Such an approach is described in "Digital Multisignature", C. Boyd, Proceedings of the Inst. of Math, and its Appl. on Cryptography and Coding, 15-17 Dec. 1986. The proposed approach extends the RSA system by dividing or splitting the user private key d into two or more portions, say d.sub.a and d.sub.b, where d.sub.a *d.sub.b =d.

"A Secure Joint Signature and Key Exchange System", Bellcore Technical Document see also U.S. patent application Ser. No. 08/277,808, which is also assigned to the assignee of the present application, modified Boyd's system, and made four significant additional points regarding split private key asymmetric cryptosystems. Although specifically applied to the two party case, the findings can be utilized more generally. The first point is that, assuming all operations are modulo N, breaking the joint signature system is equivalent to breaking RSA. This is true whether the attacker is an active or passive eavesdropper or one of the system users. It is assumed that key generation is conducted by a trusted third party, for example a tamper proof chip, and the factors of the RSA modulus N and .phi.(N) are discarded after key generation and not known to any of the system users. The second point is the description of the following key exchange protocol: User 1 sends c.sub.1 =m.sub.1.sup.d.sbsp.1 to User 2. User 2 recovers m.sub.1 =c.sub.1.sup.2.sbsp.2.sup.e. Similarly User 2 transmits m.sub.2 to User 1. Each user then computes m=.function.(m.sub.1, m.sub.2), where .function. is a function like XOR. Page and Plant prove mathematically that breaking this scheme is equivalent to breaking RSA. Again this is true whether the attacker is an active or passive eavesdropper or one of the system users. The third point is the introduction of the concept that one of the two users is a central server which maintains one portion of every user's RSA private key. In order to sign a message the user must interact with this server which, it is shown, cannot impersonate the user. Having to interact with such a central server has several important practical advantages, including instant revocation without difficult to maintain Certificate Revocation Lists (CRL), Kent, S., "Privacy Enhancement for Internet Electronic Mail: Part II: certificate Based Key Management", INTERNET RFC 1422, February 1993, a central point for audit and, as discussed below, a method of providing for digital signatures in an era where smart cards are not yet ubiquitous. Finally, the paper also proves mathematically that even if one of the two portions, d.sub.1, and d.sub.2, of the private key, d is short, say 64 bits, an eavesdropper will have equal difficulty breaking the split key system as would be experienced in breaking RSA. As a consequence, a digital signature infrastructure can be built where users who remember short (8-9 characters) passwords, can interact with the central server to create RSA signatures which are indistinguishable from those created using a full size private key stored on a smart card.

One symmetric cryptosystem is the Kerberos authentication system, Kohl, J. T. and B. C. Neuman, "The Kerberos Network Authentication Service", INTERNET RFC 1510, September 1993, which is based on the classic Needham-Schroeder authentication protocols, Needham, R. M. and Schroeder M. D., "Using Encryption for Authentication in Large Networks of Computers", Communications of the ACM, v. 21, n. 12, December 1978, with extensions by Denning-Sacco, D. E. Denning and G. M. Sacco, "Timestamps in Key Distribution Protocols," Communications of the ACM, v. 24, n. 8, August 81, pp. 553-536. The system uses a trusted third party model to perform authentication and key exchange between entities in a networked environment, for example, over a local or wide area network. Kerberos uses symmetric key cryptosystems as a primitive, and initial implementations use the Data Encryption Standard (DES) as an interoperability standard, though any other symmetric encryption standard can be used. After close to a decade of effort, the Kerberos authentication system is now a fairly mature system whose security properties have held up fairly well to intense scrutiny. Further, vendors are now delivering Kerberos as a supported product. Kerberos has also been adopted as the basis for the security service by the Open Software Foundation's (OSF) Distributed Computing Environment (DCE). Consequently, Kerberos can be expected to be among the most widespread security systems used in distributed environments over the next several years.

For the sake of clarity, a "simplified" version of the Kerberos protocol described by Neuman and Ts'o in Neuman, B. C. and Ts'o, T., "Kerberos: An Authentication Service for Computer Networks", IEEE Communications, September 1994, will be discussed below. The complete protocol is described in Kohl, J. T. and Neuman, B. C., "The Kerberos Network Authentication Service", INTERNET RFC 1510, September 1993. Further, the following discussion is based on Neuman, B. C. and Ts'o, T., "Kerberos: An Authentication Service for Computer Networks", IEEE Communications, September 1994, and for the sake of consistency uses almost the same notation. The fundamental message exchanges are shown in FIG. 1. In message 1 the user uses a personal computer or workstation 10 to request a ticket granting ticket (TGT) from an authentication server (AS) 20. The server 20 creates such a ticket TGT, looks up the user's password from the Kerberos database 30, encrypts the TGT with the password and sends it to the user via the computer 10 in message 2. The user decrypts the TGT with her password using computer 10, and stores the TGT on computer 10, for example on a hard disk or in the random access memory (RAM). Then, when the user desires to access a service, she sends message 3, which contains the TGT to the ticket granting server 40. The server 40 verifies the TGT and sends back, in message 4, a service ticket to access the service server 50, and a session key, encrypted with the user's password retrieved from database 30. In message 5 the user presents via computer 10 the service ticket to the server 50, which verif