SECURE COMMUNICATION USING REMOTE PROCEDURE CALLS SECURE COMMUNICATION USING REMOTE PROCEDURE CALLS Secure Communication Using Remote Procedure Calls Andrew D. Birrell February 13, 1984 2:56 pm {Copyright notice goes here} Abstract: Research on encryption-based secure communication protocols has reached a stage where it is feasible to construct end-to-end secure protocols. This paper describes the design of such a protocol, built as part of a remote procedure call package. The paper describes the security abstraction presented to users of the package, the authentication mechanisms, and the protocol for encrypting and verifying remote calls. CR Categories and Subject Descriptors: Class No [Major Classification]: Classification Topic  Descriptors, Descriptors, ... Computing Reviews categories go here; General Terms: keywords, keywords The author's present address is: Digital Equipment Corporation, Computer Systems Research Laboratory, 130 Lytton, Palo Alto, CA 94301. The work described here was performed while employed by the Xerox Corporation. XEROX Xerox Corporation Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, California 94304 PRELIMINARY  Do not distribute without the author's permission 1. Introduction Many computing environments now exist where frequent and substantial parts of the activities involve communication amongst computers linked by open networks. A user may well spend most of his time at a personal computer, and use networks for transferring data to and from other personal computers, or shared server computers such as printers, file servers and mail servers. Most of the networks (and internetworks) used for these activities are open in the sense that they are readily vulnerable to eavesdropping and interference from unauthorized intruders. Such an architecture presents security problems much different from the ones traditionally faced in monolithic time sharing systems. In particular, it is clear that security must be based on the use of encryption in the communication protocols. Fundamentally, encryption permits the establishment of a data channel that is less open than the underlying internetwork, by arranging that only authorized parties can create, inspect and/or modify some or all of the data. Establishing, using and maintaining such a secure data channel requires the resolution of multiple problems. First, it is necessary to identify the authorized parties (traditionally called principals). Second, it is necessary to convince each principal that the others are indeed who they claim to be. (This step is traditionally termed authentication.) Third, it is necessary to transfer the actual data in a manner that is not vulnerable to the various threats. The second and third of these are inevitably interdependent, since a recipient may require convincing that each particular datum did indeed come from the asserted sender. There are several discussions in the public literature about designing communication protocols to achieve various forms and levels of security. Much of the published material is concerned with particular aspects of the overall problem, especially the design and improvement of authentication protocols [1,5,10]. There is less material available describing how to construct a complete secure communication protocol. A recent report by Voydock and Kent [11] gives a thorough description of one such design, including substantial description of the supporting arguments for their design. There are disappointingly few real implementations of secure protocols. The purpose of this paper is to describe the construction of such a protocol. It is possible to include secure communication at various levels in the communication protocol hierarchy. At the physical layer, security can be achieved by various non-cryptographic techniques that prevent tampering with the communication medium itself. At the network layer, it is possible to encrypt all traffic on each network using a code whose key is shared among all nodes directly connected to that network. This is termed link encryption; it protects against intruders from outside the community that shares that network, but does not distinguish principals within that community. When multiple networks are involved in a communication path, link encryption allows intrusion by members of the trusted community of every network traversed by the path. The lowest layer at which we can provide an end-to-end guarantee is the internetwork layer, where we introduce direct node-to-node addressing of packets. But in many communication architectures (including ours) it is not until the transport layer that end-to-end security is feasible. The transport layer is the lowest level at which enough state information is kept to establish the authenticity of incoming data in successive packets of an interaction. It is the transport layer where we are first concerned with the relationship between successive packets. Here we introduce code which handles packet sequencing, detects missing or repeated packets, and retransmits to recover from lost or malformed packets. These mechanisms are just what is need to implement a secure protocol, and so we have chosen to introduce secure communication as an aspect of the transport layer protocol. One could also introduce security facilities at higher levels. However, doing so would reproduce many of the mechanisms already extant in the transport layer. These mechanisms have always been difficult to design and implement, and often significantly reduce efficiency. Implementing them twice seems undesirable. It would also reduce the utility of the secure protocol, since the easiest way to communicate would likely be by using the transport layer directly. This is particularly true of remote procedure calls, where a major purpose is to simplify the task of communicating, by providing a single simple and widely shared mechanism: procedure calls. If security were something that required extra programming beyond the procedure invokation itself, then it would intrude on the aim of easy communication. Large parts of our security design are derived from previous work. A moderate understanding of previous work is needed for proper appreciation of the remainder of this paper; the report by Voydock and Kent [11,12] is a good introduction. As discussed in section 3, we use the federal data encryption standard (DES) for our encryption [4]. This choice is dictated largely by the availability of very fast (and cheap) hardware for DES. Hence, our schemes are based on the use of private keys (instead of public keys [8]). For our purposes it would be impracticable to have each pair of principals that want to communicate share a private key, so our scheme is based on the use of an authentication service (also known as a key distribution center). Thus each principal has a single private key known only to the principal and the authentication service. When two principals wish to communicate, they negotiate with the authentication service to obtain a shared conversation key. This conversation key is used to encrypt subequent communication between the two principals. The design presented here arose as part of a project to implement remote procedure calls (RPC) on the Xerox research internetwork. The overall design of this RPC package has been reported in an earlier paper [3]. Prior to the construction of this RPC package, there were no encryption based protocols in the internetwork. Previous protocols transmitted passwords as clear text whenever any authentication was desired. Part of the design of this RPC package included a new transport layer protocol, and this seemed like an ideal opportunity to include security features at the correct level in the protocol hierarchy. An additional factor that enabled the introduction of a secure protocol was that most software using the research internetwork had recently converted to using Grapevine [2] as the primary authority for naming and authenticating individuals and services. This allowed us to envisage using Grapevine as the mediator in the negotiation to establish the authenticity of the principals involved in secure communication. 2. The Security Abstraction Offered to Clients Clients of our RPC package interface to its security facilities by dealing in conversations. A conversation represents a communicating pair of security principals; during secure communication, one of these principals is an implementor of a remote procedure, the other is a caller on that procedure. A client can create a conversation by presenting the RPC runtime system with his name and private key, and the name of the other principal. Subsequently, if that conversation is an argument of a remote procedure call, the RPC runtime system ensures that the call is performed securely using a conversation key known only to those two principals. We guarantee to the caller and callee that they are the two principals nominated when the conversation was created. (More precisely, we guarantee that the caller and callee are each trusted by one of those principals, to the extent of having been told the conversation key by one of them.) When a server is invoked for an incoming call with a conversation as argument, the server may ask the RPC runtime system for the name of the other principal in the conversation. Thus, our clients never deal explicitly with encryption, but they get the appropriate guarantees. Creating a conversation involves an interaction between the principal who wishes to create it and the authentication service (as described in section 4). Using a conversation to make a remote call (described in section 5) involves only the two principals - the authentication service is not concerned with this. For example, if principal A wishes to communicate securely with principal B, then A's program would include a call on the RPC runtime system of the form: conv _ RPC.CreateConv[from: nameOfA, to: nameOfB, key: privateKeyOfA] Principal A could then make remote calls to a procedure P.Q implemented by B such as: x _ P.Q[thisConv: conv, arg: y] Inside the implementation of P.Q, principal B could find the identity of his caller by a call on the RPC runtime system of the form: caller _ RPC.GetCaller[thisConv]; This concept of conversations is orthogonal to the other abstractions involved in a call. Multiple processes can participate in a single conversation; there may be multiple simultaneous calls in a conversation; calls can be made through multiple remote interfaces but still be part of the same conversation. Calls may be made in either direction in a conversation, independent of which principal is the caller and which is the callee. Indeed, it would be consistent for many machines (with the same two principals) to participate in a single conversation, although we have not implemented this. Note that we restrict a secure conversation to a pair of principals. We do not directly support multi-party conversations (although they may be emulated by pairwise two-party conversations). Nor do we support third party operations. For example, if a user A calls a server B to perform some operation, the server B cannot communicate securely with a third principal C (on a third machine) to perform some action on behalf of A merely by providing the authentication information that B obtained from A. To support such interaction, it would be necessary for A to establish a conversation between himself and C, then give B enough information (particularly, the authenticator and conversation key) to allow B to participate in the conversation. Such interactions can be made securely, and are not ruled out by our package, but we provide little aid for them. When building a secure system of any sort, it is important to be clear about the threats that are being countered. We guarantee to the caller that his call will be performed only by a callee whose name the caller has nominated. We will tell the callee the true name of the caller. Calls cannot be observed in transit, to the extent that an intruder cannot determine which procedure is being called, nor any information about the arguments or results (except their length), Calls and results cannot be modified by an intruder while in transit. An intruder cannot cause a call to be invoked more than once. We do not attempt any protection against traffic analysis or against denial of service (although clearly a caller will notice if his remote call does not complete because of a denial of service attack). It is also important to be aware that these guarantees are not absolute. The best that can be offered is that we make it prohibitively expensive for an intruder to violate these guarantees. The aim is to make that expense greater than the value to the intruder. The communicating principals should trust these security guarantees only to the extent that they trust the authentication service, the encryption algorithm, and each other. 3. Encryption Algorithms As mentioned in section 1, we use the federal data encryption standard (DES) for our encryption. We made this choice primarily because DES is available in cheap, fast hardware (as fast as 14 megabits per second). There has been some controversy over the cryptographic strengths and weaknesses of DES, but these are not important to our design. The design would be unaffected by a choice of any other private key encryption algorithm. Our detailed packet formats allow for multiple encryption algorithms, and for key lengths up to 128 bits. Use of a public key system [8] would have a large impact on the authentication protocol. Basically, DES maps 64-bit blocks of plain-text into 64-bit blocks of cipher-text. That basic mapping hides the data, but does not hide patterns (such as repeated blocks of zeros) and does not detect modifications. The cipher block chaining, or CBC, mode of DES [6] hides the patterns, but still does not guarantee to detect modifications. We use the CBC mode with the addition of a 64-bit checksum encrypted at the end of the packet. This checksum is formed by accumulating the 64-bit exclusive-or of the plain text blocks (this is performed by hardware in parallel with the encryption). This technique reduces the probability of most undetected modifications to 2-64. This assertion is based on the observation that from the point of view of an intruder who does not know the conversation key, modifying a block of cipher text produces an unpredictable modification to two blocks of plain text when decrypted. It is fairly simple to show that a random modification to 64-bits of plain-text has probability 1-2-64 of changing the resulting checksum. An alternative modification to CBC mode has been proposed by Ehrsam, et al [7], which we rejected because the requisite extra hardware would be more complicated. Remember that an intruder has an a priori probability of 2-56 of guessing the conversation key at his first attempt. Unfortunately, Voydock and Kent have recently pointed out that both of these schemes for detecting modifications to cipher text are inadequate [12]. If an intruder swaps two adjacent cipher text blocks, the change might not be detected. We have not yet modified our protocols to repair this defect. We assume that users choose (or are issued) sufficiently random private keys [9]. Temporary keys, CBC initialization vectors, and conversation keys should be generated by the authentication servers using a hardware random number generator. In the descriptions in the following sections, we have omitted some details. These details are quite systematic, being the modifications needed for secure distribution of CBC initialization vectors, for avoidance of transmissions of cipher text for known plain text, and for minimizing the amount of data encrypted with long term keys. All these details are given in full in section 8. We use the notation {P}K to indicate the cipher text formed by encrypting plain text P using encryption key K. In each context, if P is an encryption key we intend straightforward single-block use of DES, and otherwise we intend encryption using the CBC mode with the checksum described above. 4. Authentication There is substantial literature on protocols for implementing this negotiation [1,5,10]. The protocol we use is based primarily on Needham and Schroeder's [10], modified slightly to improve some shortcomings, and rearranged to meet our efficiency goals. This protocol relies on the presence of a trusted authentication service. We use the Grapevine distributed system [2] as our authentication service. Grapevine provides a distributed replicated database indexed by strings known as RNames. Several values may be associated with an RName. One such value is used as the private key for security principals. Our authentication scheme creates an authenticator. An authenticator is encrypted data that one principal can use to assure the other of his identity. When principal A passes an authenticator to B, the assurance is based on B's observation that someone who knew B's private key (namely the authentication service) promises that the imbedded conversation key was given only to principal A. B may as well believe the assurance, because the only alternative is that B's private key has been compromised. The authenticator takes the form { CK, T, A }KB where CK is a conversation key, A is A's name, T is the time at which the authenticator was created, and KB is B's private key. T is used to limit the damage potentially caused by a compromised private key, by limiting the lifetime of an authenticator to a few hours. To obtain an authenticator, A calls the RPC runtime system on A's host, giving it A's name, B's name and A's private key. The RPC runtime system calls the authentication service remotely (without additional encryption) giving it [ A, B, X ] where A and B are the principal names and X is a non-repeating 64-bit number. (Alternatively, X may be chosen pseudo-randomly or randomly.) The authentication service returns { authenticator, X, B, CK }KA where KA is A's private key and CK is the conversation key, also imbedded in the authenticator. The RPC runtime system on A's host may now obtain the conversation key and authenticator, and is assured that it and CK were issued by the authentication service for communication between A and B. Additionally, the RPC runtime system generates a permanently unique identifier for the conversation. Later when A asks the RPC runtime system to make a remote call using this conversation, it has available the authenticator, the conversation key and the unique identifier. The first part of figure 2 shows the operation of creating a conversation. The permanently unique identifier of a conversation is created by concatenating the unique identifier of this processor with a sequence number. When the runtime system is first started, this sequence number is initialized from a one second real-time clock, and the values used for unique identifiers never exceed the current value of that clock. This restricts the rate of generation of new conversations on a single processor to a long term average of one per second, although the burst rate may occasionally exceed one per second. Note that in order to return the authenticator, the authentication service uses the private keys of both principals. Since the Grapevine database is distributed, both of these keys might not be known by any single Grapevine host. So to respond to the request a Grapevine host may need to communicate in a secure fashion with another Grapevine host. The Grapevine servers are capable of communicating securely amongst themselves, since they are themselves security principals registered in a part of the database that is replicated on every Grapevine host. It is important to remember that the entire security of this scheme depends on the security of the authentication service's database. Ultimately, this must depend on the physical protection of the hosts maintaining this database. 5. Making Secure Calls The structure employed for our RPC package (as we have described in the earlier paper [3]) is as follows. A caller initiates a remote call by making a local call to a specially constructed user stub module. This stub takes the arguments of the call and an identification of the desired procedure and places them in one or more packets which it passes to the RPC runtime system. The runtime system is responsible for transmitting the packets reliably to the remote host and waiting for a response. In the remote host, the packets are received and are passed to the appropriate server stub module (also specially constructed). The server stub unpacks the arguments and makes an ordinary local call to the appropriate procedure. When this local call returns, the server stub takes the results, places them in one or more packets, and the RPC runtime system communicates them back to the caller machine, where they are given to the user stub. The user stub then takes the results and returns from the original local call. This structure is depicted in figure 1, and is described in much more detail in the earlier paper [3]. The earlier paper also describes our binding mechanism, whereby a caller determines which host implements a desired remote procedure. <==