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 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 noncompromised keys We also show that timestamps can replace the handshake 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 timestamps are valuable in public key systems to ensure the integrity o f keys Public key systems also provide an alternate method of exchanging communication keys for single key data encryption As before timestamps protect against replays o f previously compromised communication keys No protocol is secure if users private keys are compromised We conclude with a brief discussion o f the threats to private keys in both types of systems II Single Key Systems I Introduction A Distribution of Communication Keys Secure communication between two users on a computer network is possible using either single key conventional 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 b y 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 specificpermission Former editor of Operating Systemsdepartment of which Anita K Jones is the current editor This research was supported in part by NSF Grant MCS77 04835 Authors present address Computer SciencesDept Purdue Univ W Lafayette IN 47907 1981ACM 0001 0782 81 0800 0533 00 75 533 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 AS A 1 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 o f 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 of the ACM August Volume 24 Number 8 B A IB cr 4 4 B f I B c r 5 where In is an identifier chosen by B A signals his intention to use CK by returning an agreed f u n c t i o n f 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 communication keys and private keys have not been compromised 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 communication 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 Note however that A can still communicate safely with B by initiating a new conversation assuming A s attempts are not blocked by C and that B can communicate safely with other users Of course C cannot impersonate A s response to B in the handshake without knowing the handshake function f But the problem of securing secret handshake functions is as difficult as the problem of securing communication keys Users must either privately exchange and remember permanent handshake functions or they must obtain them