Synergy

Aqua Regia is a mixture of nitric acid and hydrochloric acid. Neither of these two reagents will dissolve gold. Aqua regia dissolves gold.

Synergy is a general pattern in capability systems. It takes several forms: rights amplification, sibling communication and sealing.

Synergy is a phenomenon where a program that holds two capabilities can do something by bringing these two capabilities together that it cannot do with them separately. In the systems we know the only way to bring capabilities together is to send one to the other in a message, or alternatively to send both to the some other object, but then that other object must either send one to the other or send both to a yet more fundamental object. By “fundamental” I mean older in the sense described here.

We consider first an example of rights amplification in Keykos. (See this for a more generic introduction to amplification.) A domain service key to a particular domain D is stronger than a start key to D. (Here is all you need to know about domains to understand this note.) This is because there is an order on the domain service key that yields the start key to the same domain and there are things that you can do with the domain service key that you can’t do with the start key. By invoking the domain creator that made the domain one can retrieve the domain service key from the start key. This operation is an example of rights amplification; given the start key we have amplified those rights to include the rights conveyed by the domain service key (to the same domain!). (The synergy is between the domain creator key and the start key.) Most programs can not perform this amplification for they lack a key to this domain creator.

There are two important questions to answer:

why is this a good design?
how is it accomplished?

Why is rights amplification a good idea?

This in turn breaks down into two questions:

is it harmful?
is it useful?

Harm from some feature may occur when some program is able to do something that it would not be able to do without the feature. That this is harmful is the peculiar perspective of the design of secure systems. The argument that rights amplification is harmless is subtle. Without loss of generality we take the domain example above. An exclusive holder of a domain creator key may choose to retain each domain service key ever returned by the creator. With this collection the holder can perform the amplification function without synergy as follows:

Accept a start key,
For each retained domain service key, produce all 256 possible start keys,
Compare each of these with the given start key for equality,
Return the domain service key that produced the matching start key.

We have thus shown how the amplification can be done without the feature. There is thus no harm in the feature if comparing keys for equality is possible.

The reader may have seen an important flaw in the above argument. Without the amplification feature two holders of the same domain creator key are unable to amplify start keys for domains from the other holder. This may be important if the two do not trust each other. The presence of the amplification feature in the domain creator means the domain creators should not be shared across trust boundaries. There are other reasons for this policy however and it is not expensive. This is generally the case with rights amplification.

Some will see another flaw here: “How do you compare keys for equality?”. Such an operation sends two keys to a primitive comparator (via a key to the comparator). Indeed this is a form of synergy. Capability system designers in good standing differ on how widely access to a comparator should be spread. Here is a description of a solution for a large class of synergy problems without EQ?.

As to whether synergy is useful there are several uses. Here are two:

If a domain obeys a program with a bug it may be important to be able to debug the program starting from the state of the broken domain. This requires the domain service key to the domain. The start key is likely to be available but the domain service key is generally not required after domain launch. With rights amplification the domain creator together with the start key can produce the required domain service key at less cost than always keeping the domain service key.
It is often required that an object be able to communicate with siblings in ways that others cannot. One example is money objects. Mondex cards use a combination of obscurity and crypto to communicate between themselves to prevent counterfeiting Mondex money. Capability systems with synergy can do the same without crypto. Here is a sample design in Keykos. Another example of sibling communication is to optimize computation by taking advantage of state representation. It might indeed be more than an optimization such as proprietary data formats.

How is synergy accomplished?

How does the domain creator produce the domain service key upon the rights-amplification order more easily than the above procedure?

The domain creator holds the domain tool which is a one-of-a kind object implemented by the kernel. An order on the domain tool takes a start key and another key x. If x matches the key in slot 0 of the node, D, designated by the start key, then the domain tool returns the node key to D. The domain creator then produces, again, the domain service key that designates D, which is returned to the caller of the domain creator.

In summary the domain creator performs synergy by invoking a synergy function of a more primitive object. In general this pattern continues until an object, such as a kernel object, is reached that is not constrained by capability discipline. Such programs are generally entrusted to enforce such discipline.

Sibling Communication

In Keykos, if someone asks you to do some work he may pass you access to a space-bank B which will provide for working storage for the job. You may want assurance that this bank plays by the rules of space banks. You should already have a bank T that you trust and of whom you can ask about B. To do this you invoke T sending B. If B is a real bank T will be able to determine this in which case you can trust that B will behave as T except for allocating storage on your customer’s nickel, but storage that your customer cannot see.

To do this the bank retains from birth a key to its creator. When asked to vouch for a sibling it asks its creator to whom the question is merely a matter of rights amplification. The creator may return a special start key to the sibling bank so that inter bank messages can pass efficiently with the recipient knowing that the message is from a true sibling. Banks can then engage in bank-talk.

C++ code of some class can directly access members of another object of the same class. This provides efficient primitive sibling communication.

Seals

The first hint of synergy that I know in the literature is sealing in James H. Morris’ “Protection in Programming Languages”, CACM, 16(1):15-21, 1973. That paper suggested that language scope rules could solve real security problems. In particular Morris introduced a pair of matched functions, seal and unseal. These were created by matched pairs by a commonly available service. If S and U are a matched pair then for all x, U(S(x)) = x. S(x), on the other hand, is useless to anyone without access to U. It is much like public key crypto without all of the arithmetic. It is a particularly simple primitive upon which many other synergy functions can be based.

See how to define types of synergy in Scheme starting from “eq?”.