Technical Note Operating Systems R. Stockton Gaines* Editor Timestamps in Key Distribution Protocols Dorothy E. Denning and Giovanni Maria Sacco Purdue University The distribution of keys in a computer network using single key or public key encryption is discussed. We consider the possibility that communication keys may be compromised, and show that key distribution protocols with timestamps prevent replays of compromised keys. The timestamps have the additional benefit of replacing a two-step handshake. Key Words and Phrases: encryption, encryption keys, key distribution, communications, security, timestamps. CR Categories: 3.81, 4.39 I. Introduction Secure communication between two users on a com- puter network is possible using either single key (con- ventional) encryption or public key encryption. In both systems, key distribution protocols are needed so the users can acquire keys to establish a secure channel. In single key systems, the users must acquire a shared communication key; in public-key systems [2], the users must acquire each others' public keys. Needham and Schroeder propose key distribution protocols for both single key and public key systems based on a centralized key distribution facility called an Authentication Server (AS) [6]. Their protocol for a single key system assumes that the AS is responsible for generating and distributing all communication keys, and that each user has registered a private (secret) key with the AS. The AS uses the private keys to protect (by encryption) the communication keys transmitted to the users. If communication keys and private keys are never compromised (as Needham and Schroeder assume), the Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. * Former editor of Operating Systems department, of which Anita K. Jones is the current editor. This research was supported in part by NSF Grant MCS77-04835. Authors' present address: Computer Sciences Dept., Purdue Univ., W. Lafayette, IN 47907. © 1981 ACM 0001-0782/81/0800-0533 $00.75 533 protocol is secure (i.e., can be used to establish a secure channel). We will show that the protocol is not secure when communication keys are compromised, and propose a solution Using timestamps. Although the likelihood of such a compromise may be small, the timestamps are useful for another reason: they can replace a two-step handshake designed to prevent replays of (noncomprom- ised) keys. We also show that timestamps can replace the hand- shake in the Needham and Schroeder protocol for public key systems. Here the AS is responsible for distributing users' public keys; it does not require access to their private keys. Because there are no secret communication keys, their compromise is not an issue. However, time- stamps are valuable in public key systems to ensure the integrity of keys. Public key systems also provide an alternate method of exchanging communication keys for single-key data encryption. As before, timestamps protect against replays of previously compromised communication keys. No protocol is secure if users' private keys are com- promised. We conclude with a brief discussion of the threats to private keys in both types of systems. II. Single Key Systems A. Distribution of Communication Keys Needham and Schroeder assume that each user A has a private (secret) key KA which is known only to A and AS. If two users wish secure communication, one of them obtains a secret communication key CK from AS and gives a copy to the other. If a new key is obtained for each conversation, a user need not keep a list of secret communication keys for all his correspondents. The key distribution protocol is as follows. Let (x} r denote the message x enciphered under key K. For a user A to acquire a key CK to share with another user B, these steps are taken: A ~ AS: A, B, IA (1) AS ~ A : {Ia, B, CK, Y} KA (2) where Ia is an identifier chosen by A and used only once, and Y = {CK, A} KR. Because Ia is returned by AS, enciphered under A's secret key, A can be sure that the response (2) is not a replay of a previous response. A then sends to B the message Y, which contains a copy of CK enciphered under B's private key: A ~ B: Y. (3) B. The Handshake After step (3), A can be sure that the key CK is safe to use. However, B cannot be sure that the enciphered message Y and subsequent messages supposedly sent from A are not replays of previous messages. To protect against replays, a handshake between B and A follows: Communications August. of Volume 24 the ACM Number 8B --* A: {IB} cr (4) .4 .-, B: (f(IB)) cr (5) where In is an identifier chosen by B. A signals his intention to use CK by returning an agreed functionf of IB; f could be something simple like f(I) = I - 1. The complete sequence of steps 0)-(5) establishes a secure channel between A and B as long as previous commu- nication keys and private keys have not been compro- mised. C. Compromises of Communication Keys If the encryption algorithms are strong and keys random, it is unlikely that communication keys will be compromised by cryptanalysis. We are more concerned with the communication key's direct exposure due to negligence or a design flaw in the system, i.e., an intruder may be able to break into the AS or into A's or B's computer and steal a key. Let us suppose that a third party C has intercepted and recorded all the messages between A and B in steps (3)-(5), and that C has obtained a copy of the commu- nication key CK. C can then later trick B into using the CK as follows: First C replays the message Y to B: C-* B: (CK, A} KB. Thinking that A has initiated a new conversation, B requests a handshake from A : B-.-* A: {I'n) oK. C intercepts the message, deciphers it, and impersonates A's response: A .-~ B: (f(I'n)} cK. Thereafter, C can send bogus messages to B that appear to be from A, intercepting and deciphering B's replies.