(This post currently requires client-side JS from capability.party. Sorry.)

A capability is an unforgeable communicable token of authority. Today, we’ll focus on what the unforgeability property means.

Unforgeable

First, what is unforgeability, and why is it important? If somebody had the ability to forge capabilities, then they would be able to assume authority which they were not granted. Capability-secure systems define rules for when authority can be granted. Taken together, a capability-secure system insists that authority can only be assumed by legitimate means within the system and that no technique exists for attempting to forge capabilities outside those means.

If this seems needlessly abstract, then consider memory-safe systems as an analogy. In a memory-safe system, it’s not possible to forge pointers; every pointer must refer to a valid region of memory. There are in-system techniques for acquiring new valid pointers, but not for hand-crafting possibly-out-of-range pointers. Similarly, in a capability-safe system, there are in-system techniques for acquiring new capabilities, but not for hand-crafting possibly-unauthorized capabilities.

Unguessable

Unguessability is less abstract. There are two common classes of unguessable capabilities to relate to: pointers and cryptographic secrets. In both cases, “unguessable” is actually a little misleading and “hard-to-guess” might be a better description. An unguessable capability can be guessed at, many times, but each guess has a low probability of succeeding.

The exact chance of success depends on the details of how the guesses can be made. Most unguessable systems can be reduced to the unguessability of a fixed-length bitstring. There are $2^k$ possible bitstrings with $k$ bits. One might expect a probability like $2^{-k}$ for each guess if the bitstring were assigned at random.

Unlike unforgeability, unguessability analysis depends crucially on what kinds of attacks the system will have to endure. A naïve implementation unaware of the dangers might choose to assign bitstrings sequentially, but this is a problem, because an attacker could turn one legally-granted capability into another illegally-guessed capability easily.

As an example, imagine assigning the sequence $1, 2, \ldots$ to capabilities. An attacker might receive $42$ as their capability legally. This suggests to them that $41, 40, \ldots$ might all be valid capabilities as well. For this reason, an unpredictable or chaotic function, like a CSPRNG, is often used to help generate unguessable bitstrings which are closer to that ideal $2^{-k}$ probability of a successful guess.

Relativity

We might now wonder why it is that both unforgeability and unguessability appear in capability theory. Additionally, one might wonder why we mentioned that pointers are both unforgeable and unguessable. Surely this isn’t clarifying the issue!

The answer is that unforgeability and unguessability are the same property. From inside a capability-safe system, capabilities appear unforgeable; from outside the system, however, capabilities are merely standard values and are subject to unguessability rules instead. Let’s explore several instances of this phenomenon, starting with pointers.

It’s no secret that capability-safe programming languages, like E, Monte, and Pony, use pointers under the hood at some level in their implementations. If one uses a debugger to examine or change the pointer values from outside a program, then one can alter the behavior of the objects inside the program. Nonetheless, from inside the program, this alteration isn’t possible. Therefore, these pointers are somehow both unforgeable and unguessable‽ But the answer, again, is that these are just two ways of looking at the same property from two different perspectives.

Another example relevant to capability-safe languages is the management of swissnums. A swissnum is clearly unguessable, but it is the best substitute that we have for unforgeability when doing communication via The Network, which only accepts bitstrings. Indeed, in the common case of TLS over TCP/IP, the privacy properties of TLS are all that stand between Eve and our swissnums.

Practical Proofs

Why does all of this matter? Well, remember that we prefer to talk about unforgeable capabilities. However, in the real world, capabilities are always unguessable if one stands back far enough and gets a sufficiently-encompassing perspective. Side-channel attacks, debuggers, impedance mismatches between capability-unsafe and capability-safe systems; all of these contribute to a general weakening of unforgeability to unguessability.

We would like to prove facts about our capability systems as if their capabilities were unguessable, and only worry about unguessability at the edges, where our systems must interface with The Filesystem, The Network, legacy tooling, and other nemeses. In each case, we say that a capability is only unguessable when it is exposed on one of these edges, but otherwise, capabilities which never leave a capability-safe system stay unforgeable, because they are never externally observed.

In particular, we can imagine a simple distributed system between Alice and Mallory.

As usual, Alice doesn’t trust Mallory, but she can model him as a black box which communicates using bitstrings over The Network. (Strings of octets, pedantically.) Then, Alice knows that her liability with Mallory is limited to the few capabilities which she grants via bitstrings over The Network, because although Mallory can try to guess as any capabilities as he likes, his range of guesses only covers a small domain of Alice’s capabilities; specifically, he can only guess at those capabilities which she will ever serialize into bitstrings.

This only-at-the-border reasoning lets us avoid more paranoid approaches, which we’ll call papers-please reasoning. Good examples are ARM pointer authentication and glibc encrypted pointers, which both work as advertised but at a speed penalty. Worse, they don’t prevent capability-guessing attacks, but merely raise the difficulty of guessing. Admittedly, in the scenarios in which these technologies are used, everybody involved understands the tradeoffs, and these tactics are part of defense-in-depth strategies. However, from a formal point of view, it’s nonetheless comforting to know that our formal methods are just as valid in terms of defense-in-depth and effectiveness.

Summary

In summary, a capability is often, in practice, an unguessable copyable token of authority, rather than an unforgeable communicable token, and there’s nothing wrong with that as long as we don’t forget what it means.