Distributed Capabilities with Symmetric keys

We have seen a close connection between public key crypto and capabilities. We now look at the earlier practice of symmetric key crypto and note that many of the same problems may be solved with symmetric keys as well. Symmetric keys cost less to use but the protocols may be more complex. Unibus is a proposed protocol much along these lines.

There is here at best a germ of a good idea. See some issues, however, that I see with this scheme.

A pair of sites can communicate using a shared secret symmetric cypher key. This provides secrecy and authenticates each site to the other. (But see these pitfalls to using symmetric crypto for authentication.) We call this a symmetric connection here. Indeed this is just classic encryption.

If we have a symmetric connection then I can verify that you sent a particular message because only you and I know a secret, and I know that I did not create the message. I cannot convince a third party, however, that the message is from you for I would have to reveal our shared secret, and even then there would be only my word that I had not created the message. Public key crypto solves this “repudiation” problem elegantly!

A site with symmetric connections to two other sites can introduce those other sites to each other, providing them with a symmetric connection, so that they can communicate directly. This is done by choosing a new key to be shared by those two other sites. This key must be securely transmitted to both other sites before either can send a message to the other. Alternatively a site might store pending messages for which it has not yet received a key. Of course the introducer also knows the secret key of the new symmetric connection. We discuss that situation here.

A symmetric connection between X and Y is in some regards like X holding a capability to Y, but here are these differences:

Y must devote storage to the secret key of the symmetric connection.
Y can identify the sources of messages sent over symmetric connections.

In short, with symmetric connections, Y may be, and must be aware of each of its correspondents—those who may send it messages. By contrast, public keys, or capabilities arrange for secure reception of messages from senders previously unknown to C. As with symmetric connections, the authority to contact C may be limited by limiting the distribution of public keys or capabilities.

Before public keys were invented Needham & Schroeder suggested a scheme for arranging symmetric connections more in the style of capabilities or public keys. The Kerberos protocols use this scheme.

Suppose that site A, which has symmetric connections to sites B and C, wants to enable B to securely contact C. Let S_xy represent the key shared by sites x and y and S_xy(Z) represent the message Z enciphered by that key. When A learns that B will need to contact C then A chooses a random S_BC and sends the following to B:

[S_AB(S_BC), S_AC(S_BC)]

Some such information is found in the Kerberos ticket which also includes validity duration and routing information. It may seem strange to send something to B that only C can decipher but B has the correct incentive to hold S_AC(S_BC) until B needs to convey to C, B’s authority to contact C. When B needs to contact C it sends to C, [A,S_AC(S_BC),S_BC(business matters)]. The initial “A” is so that C need not guess which key to use to decipher S_AC(S_BC).

Several scenarios make this pattern useful:

C is a server that is not equipped to maintain symmetric connections to its potential clients.
There is no way for C to know how long its end of the symmetric connection should be maintained, (when to throw away the shared secret),
C does not yet exist when A chooses S_BC,
Communication between A and C is not possible when A chooses S_BC,
C should not learn of the arrangement until it is time for B to contact C.

Schneier ascribes this pattern to Needham & Schroeder.

This scheme seems a bit like A delivering C’s public key to B. There are important differences:

The message to B can be used only by B because only B knows S_AB.
C must associate C’s introduction to B with A in order to decipher S_BC.
The message from B to C serves as an introduction by A of B to C.

I think that SSL v3 combines the advantages of these two schemes. The central site, to which there are many capabilities, need keep no state that is relevant to most of those capabilities. For recent accessors it maintains a secret key and thus avoids the cost of frequently recomputing a new symmetric key. (This raises a denial of service vulnerability in the form of too many bogus requests to reestablish temporary symmetric keys. Each request requires to much work to reject as bogus.)

Problems

Unfortunately in the above scenario the communication between B and C is available to A. Now this is presumably not serious as B and C are supposedly discussing things that they would have had no reason to discuss except for having been introduced to each other by A. Further B and C may each regard the other as a figment of A’s imagination—merely a deputy of A.

Suppose, however, that D communicates also with both B and C. D might like to introduce B to C to carry out D’s business without A being able to intercept the traffic. It would seem that B and C would have to keep these two pieces of traffic apart. This impairs scale economies in communications between B and C, for B and C must use different symmetric keys for different traffic.

Diffie-Hellman seems to solve these problems as described here.

On the other hand it may be necessary for B and C to continue to discriminate which traffic between them relates to A and which to D, lest B or C become a confused deputy. This is a critical issue when B or C are stateful objects. There are other questions that impact the design: “Do B and C have secrets to keep from A or D?”, “Are B and C vulnerable to corruption of their communications, by either A or D?”.

These issues can be abstracted by asking when, after A introduces B to C, do B and C no longer trust A with their communications about A.

I feel a notion of ‘relationship’ struggling to emerge. A relationship is between to objects, and is symmetric. It is what is enabled by symmetric cryptography and a shared secret key. For a pair of objects there may be zero, one or more relationships. It is not always necessary for an object in two relationships to know whether they are with the same other object. In fact it may be for the relationship to be reflexive so that an object is in a relationship with itself. The relationship might be an alternative primitive notion.