On the Origin of Kerberos

Kerberos is a cryptographic authentication and key distribution system developed by MIT Project Athena with the goal that a single login provide access to many different computing services. Kerberos is distributed as a component of most major operating systems, including Microsoft Windows, Apple OS/X and IOS, IBM z/OS, and many versions of Unix. It is also thoroughly documented both in professional papers and in tutorials. However, most descriptions (a typical example is the article in Wikipedia¹) begin the history of Kerberos by saying it is based on a protocol designed by Roger Needham and Michael Schroeder in 1978. It is not so well known that the Needham & Schroeder protocol is itself based on a 1967 invention by Howard Rosenblum of the United States National Security Agency (NSA) that for many years was classified.

THE KEY DISTRIBUTION PROBLEM

For encrypted communication to be useful, the recipient of a message must be in possession of the decryption key that corresponds to the encryption key used by the sender. In addition, potential adversaries must not be able to get a copy of the decryption key. Thus, cryptographic communication requires advance planning to choose encryption and decryption keys and to distribute those keys to the sender and receiver using a secure communication method. The remainder of this discussion assumes use of symmetric encryption, which means that the encryption and decryption keys are either identical or derivable one from the other, so the secure communication of the keys must assure both confidentiality and integrity.²

When in the 1960s the NSA developed a secure telephone system these requirements presented a problem: since anyone with a phone capable of encryption might place a call to any other such phone, it seemed that there had to be an advance arrangement to share a unique encryption key between every potential pair of telephones. For this reason, in the initial implementation, each phone stored a list of encryption keys, one for every other phone it might call or that might call it. Setting up and maintaining these lists presented a scaling problem. Creating a network of a half-dozen secure telephones might be feasible but to deploy thousands for use throughout the Defense Department would be a major challenge, especially since an element of cryptographic security doctrine is that encryption keys should be used only briefly, then changed, to reduce the amount of material encrypted under a single key that could be used for cryptanalysis or that would be exposed if the key were compromised.

For a second generation secure telephone system, Howard Rosenblum in 1967 proposed and patented a key distribution system that he called Bellfield.^3,4 The idea was that each phone would maintain just one encryption key, unique to that phone, and shared only with a key distribution center (KDC). To place a call from phone A to phone B, the first step would be for phone A to send an encrypted message to the KDC indicating an intent to hold an encrypted conversation with phone B. The KDC would fabricate a new encryption key, known as a "session key" and send two copies of that session key back to A, one encrypted under the key that it shares with A and the second encrypted under the key it shares with B. Phone A then forwards B's encrypted session key as part of the call setup. Once this flurry of messages has been delivered, A and B both possess copies of a session key for this conversation. In addition to allowing A and B to communicate securely without a specific prior arrangement between them, a feature of this technique is that every new telephone conversation could be encrypted with its own unique session key, thus helping satisfy the cryptographic security doctrine to minimize use of any one key.

The early 1970s saw growing interest in both computer security and computer communication networks. In addition to the NSA,⁵ several groups working in industry and academic environments were thinking about how to apply encryption to protect data transmitted between computers. A secure peer-to-peer computer network has a requirement...