Home > News & Events > MITRE Publications > The Edge >

Most people think of cryptography, the science of transforming messages using keys, as a way to keep secrets. When the transformed message gives little or no information about the original contents, and when an enormous number of potential keys must be tried before finding the correct one, then cryptography achieves the goal of keeping secrets, also called confidentiality. Historically, confidentiality has been the prime goal of cryptography, and undermining it has been the goal of cryptanalysis.

What is less well known is that cryptography can also be used to achieve authenticity, which means that the message came from the intended source and has not been altered in transit. When a secret key is used, in combination with the contents of a message, to construct a value that the recipient can check, then cryptography achieves authentication. Cryptography is central to modern information security because it can provide either confidentiality or authenticity, and can also combine them in many useful ways.

In some cases, authentication is the crucial service of cryptography. For instance, MITRE engineer Mark Shelor faced a remote management problem: to allow a central network management workstation to manage distant sensors. Standards for secure network management exist, but are complicated, so that vendors resist implementing them. Shelor identified authenticity as the prime goal for his program. When a message tells a sensor to turn off (for example), the sensor must authenticate the message as coming from the management workstation, rather than from an adversary who would like the system not to detect a planned infraction. Shelor slightly modified a widely-used, non-secure network management protocol to incorporate message authentication. As a consequence, the program's contractors could easily and cheaply implement his solution, providing exactly the service that matters. There was also one fine point: it was necessary to provide each message with a sequence number, as part of the authenticated contents of the message. Each message is prepared with a sequence number greater than the numbers used previously. This lets the device ensure that a newly received message was sent recently by the management workstation, rather than having been recorded by an adversary and re-used long afterward. Authentication keys must be changed (manually in this example) before the system runs out of sequence numbers and needs to re-start at 0.

This example illustrates three key lessons in the use of cryptography:

1) Start by determining exactly what cryptographic services are needed--authentication, in this case.

2) Determine the simplest way to provide just those services--in this case, by incorporating message authentication into a widely accepted protocol.

3) Check whether message replay can create problems, and use sequence numbers to prevent them.

Simple, clean choices create easily implemented cryptographic protocols. They reliably meet the security goals. Vendors are then cooperative about implementing those cryptographic protocols, as we found in the remote sensor management case.

In reality, many uses of cryptography require that several goals be met simultaneously. For example, some aspects of a conversation must remain confidential, whereas a different set (usually an overlapping set) are authenticated. In an extreme case, such as the Secure Electronic Transaction protocol designed for credit card transactions, some data (such as purchase price) must be shared among the customer, merchant, and bank, while some values must be hidden from each participant (for instance, the card number should not be disclosed to the merchant), and others must be authenticated (for instance, the bank approval must be authenticated to the merchant). The complexity of both functional goals and security goals, however, has led to a protocol that has not yet been put into use, although the design was completed in the early 1990s. This is unfortunate because a protocol of this kind would make a far better basis for electronic retail commerce than the current approach based on Secure Sockets Layer.

Many cryptographic protocols aim to distribute a fresh cryptographic session key by means of a long-term key used only for this purpose. Then the session key must remain confidential, while the participants in the exchange are authenticated to each other. Key distribution is an important problem for two reasons. First, no key should be used for more than a given amount of data (or length of time) to reduce the risk of an attacker discovering the key. Second, methods such as public key cryptography that are convenient for distributing a small amount of data, such as a session key, are too computationally demanding to allow a full conversation to be encrypted.

In protocols of any complexity, the cryptographic operations can interact in ways that are hard to foresee, so that an attacker can sometimes force a system to behave in ways that undermine its goals. Indeed, this is possible even if the cryptographic operations themselves are strong or even perfect. Therefore, cryptographic protocols must be examined carefully to discover any harmful interplay an attacker might cause.

The attacker may capture messages off a network or insert messages onto it; an attacker may combine portions of captured messages, and may apply cryptographic operations using keys known to himself or previously extracted from legitimate messages. In addition, an attacker may start a session with an honest participant, or wait until an honest participant starts a particular session. These threats make it hard to ensure the confidentiality or authenticity of particular data.

Consider the Needham-Schroeder protocol as an example. It uses public key cryptography. Public key cryptography provides a way that anyone can lock a message inside a metaphorical box, which only a single principal can unlock to discover the contents. Public Key Infrastructure (see "Securing Enterprise Resources with PKIs" ) may be used to ensure that only the intended principal can unlock the contents, assuming that the principal has carefully guarded a secret called his private key. If the message consists of a sequence of values X Y Z, for instance, then we will write [X Y Z]A for the result of locking those values so that only principal A can recover the contents.

The Needham-Schroeder protocol allows two network participants to agree on a pair of values. If the protocol ensures the confidentiality of these values and their authenticity (that each has come from the expected partner), then the participants can combine them to produce a new secret key for a session encrypted using symmetric cryptography.

In this protocol (see Intended Run diagram), the initiator A creates a new, random string of bits N_a. He sends N_a together with his name boxed as [N_a A]B to be readable only by intended partner, B. B, when he receives this message, assuming he wants a session with A, creates another new, random string of bits N_b. He sends N_a and N_b back to A in the form [N_a N_b]A. When A receives this message, he can infer that B has received N_a, because no one else can extract it from [N_a A]B. A then repackages N_b as [N_b]B; when B receives this, he can infer that A has received N_b. Thus, each has authenticated the other's possession of both numbers.

This elegant protocol, published in 1978 in a famous article, was discovered in 1995 to have a basic flaw (see diagram). Namely, if A starts a session with a dishonest principal P, then P can impersonate A to any B of P's choice, for instance A's bank. Neither A nor B can determine that this has happened.

A large literature of technical articles, developed over the past decade or more, is devoted to ways either to ensure that a protocol cannot fail or find failures if they exist. A series of articles by MITRE's Jonathan Herzog, Javier Thayer, and myself has led to a simple and reliable way to solve this problem. There are two ingredients.

The first ingredient is a method to find flaws when they are present. A protocol may unwittingly offer unintended services to an attacker. For instance, in the Needham-Schroeder protocol, the initiator A, when he starts a run with P using Na, offers to translate any future value [N_a N]A from this form (which P cannot read) to [N]P (from which P can learn N). The protocol requires A to perform this service, despite the fact that A cannot be sure that [N_a N]A came from P. This is the reason why the Needham-Schroeder protocol does not achieve its security goals. The protocol may be fixed by adding another element to the box, the name of the sender. Then, when A receives [N_a N B]A, A can be sure that P did not send this value, and can refuse to continue the protocol run. Many protocol flaws may be found quite quickly by looking for unintended services, in which an honest principal is required by the protocol to perform some cryptographic translation that may be used by an attacker.

The second ingredient in our work is a method to prove that a protocol is correct, when no flaws have been observed using the unintended services method. The essence of the method is to take the point of view of an individual participant. We will illustrate the idea using the corrected version, in which the second message [N_a N_b B]A includes the name of the sender B.

When B creates a new value N_b and sends it to A in the locked form [N_a N_b B] A, he is effectively making a challenge. The challenge defines what another principal has to do to convince B that this principal is A, and that this principal intended to start a conversation with B. The challenge is to extract the locked value N_b from [N_a N_b B]A. Anyone who can meet this challenge can then apply B's public key and return [N_b]B to B. However, assuming that A has kept his private key safe, only A can meet the challenge. Thus, if B ever does receive [N_b]B, then surely A has received the challenge term and transformed it. We call a pair of events an authentication test if a principal first sends a value (such as [N_a N_b B]A) and then receives a newly generated part back in a cryptographically altered form (such as [N_b]B). The authentication test allows one principal to test whether another principal is actively playing the game, rather than being impersonated by an attacker.

Thus, the authentication test method allows a protocol analyst to determine quickly and unambiguously exactly what one principal can tell about another, given the protocol behavior. This method has been made quite rigorous, and justified by mathematical proofs. Because the method is also compatible with the way protocol designers tend to think about their problems, unsound protocols are likely to become a thing of the past.

---

For more information, please contact Joshua Guttman using the employee directory.

---