Keyed-hashing based Rumpelstiltskin trees as singly attenuated decomposable authority

Keyed-hashing based Rumpelstiltskin trees as singly attenuated decomposable authority

Sparse capabilities are tokens of authority that both designate an object and contain the authority to either invoke methods on that object or send messages to it. If these are to remain persistent through system reboots, object serialization and confidentiality of the serialized data for persistent storage becomes a concern. Modeling authority as a Directional Acyclic Graph (DAG) is a useful way of reasoning about least authority design. In this article we discuss a keyed-hashing based tree structure approach to the implementation of a sparse capabilities based system with built-in facilities for secure persistent object serialization, that can be used in the composition of arbitrary DAG based authority graph setups.

A naive keyed-hashing based tree of raw storage objects.

The use of a keyed hashing algorithm such as HMAC-SHA2 or BLAKE2 allows for the creation of a simple decomposable tree of named objects, each with its own unique unguessable designation or sparse cap. If the root of the tree is designated with a high entropy sparse-cap, then any named child of this root node could have its own unique sparse cap through a keyed hashing operation that uses the parent sparse-cap as key and the child name as message. The same keyed hashing step may be used for child nodes of this child node, and than their child nodes, effectively creating a tree of named objects each with its own unguessable sparse capability designating it. As a keyed hashing operation has no reverse function, it should not possible to derive the parent sparse-cap from the child sparse-cap. This makes the tree of objects a directional graph. An entity (process, object) holding a sparse-cap to a node can decompose its authority using a number of keyed hashing operations to obtain a sparse-cap to a chunk of authority that it can then delegate to an other entity.

Directory listing objects.

Considering the directional tree defined above, someone with a sparse-cap to a node would still need to know or guess the names of the child nodes in order to access them. As names are supposed to be guessable designations within the name-space of the parent, there is little to no security in using secret child names. As such, it is suggested that each non-leave node either is or contains a list of the names of all of its child nodes.

Symbolic link objects.

While having one or multiple disjunct decomposable trees of authority has use cases and fits the definition of a DAG, there are many useful instances of DAGs that can not be described with disjunct directional trees. To extent the expressiveness of the authority model, we propose that the concept of a symbolic link node, akin to symbolic links in file-systems on UNIX based operating systems, can be used to overcome the expresivness limits of the tree based authority structures. A symbolic link node contains a sparse-cap of a node, that is not its direct decedent, in it’s serialization.

Confidential storage of object serialization.

We assume that nodes can have persistent storage facilities for its serialization. In the simples form because the nodes are actually file objects, and in a more complex form, because in-memory objects that have been in disuse for a long time might allow a server to page them out to persistent storage. There are two issues with respect to persistent storage that need attention. Storage location and storage confidentiality. For confidentiality, given that the node’s sparse-cap already provides full authority, we propose that the sparse-cap of the node can double as File Encryption Key (FEK). For the location of the data, we add an extra keyed hashing operation. For this operation we shall use a cloud secret as message and the sparse-cap of the node as key. The concept of the cloud secret provides the concept of a realm with a shared secret of what we shall discuss the utility when we discuss in the next section. The result from the second keyed hashing operation results in a hash that we can use as a key for storage in a database, or alternatively. That we may format in order to create a relatively shallow path within a file-system directory for storing our encrypted serialization as a file. The use of this construct has an interesting property. The sparse-cap to the node together with the cloud secret combine to an actual designation of the serialized object. If the combination designates nothing, then the sparse-cap is invalid.

Casting an attenuated shadow

So far, our tree of nodes only knows decomposition and composition (through sym-links). There is an other aspects of capability based security that is often useful, and that is attenuation. A prime form of attenuation that maps well to the way objects are used in programming, is the concept of const references to mutable objects. Or to say it in file-system terms, read only access. While attenuating only leave nodes could be useful, delegating attenuated access to whole sub-trees also has its utility. This however creates a challenge with respect to our keyed-hashing based tree structure in combination with different paths to what should be considered the same outcome.
We define a desirable property for the interaction between decomposition and attenuation:

Attenuation of a decomposition towards a child node should yield the same results as decomposition of an attenuation towards that same child node.

To achieve this property, some sacrifices need to be made with regards to the flexibility of the system as a whole. We define a trusted component, a server or an actual user-space file-system, that needs to be used in decomposition operations. This trusted component will also need to play a role in symbolic link dereferencing. That is, an attentuated access sparse-cap to a symbolic link should not allow the client access to the unattenuated access sparse-cap that is part of the sym-link serialization. In order to fit in attenuation, we introduce two extra keyed hashing operations. First, we define that the the attenuated access sparse-cap KEY2 is derivable client side using a keyed hashing operation, using the unattenuated access sparse-cap KEY1 as key and a static string "read-only::nosalt" as message. The storage designation KEY3 in turn is derived from the attenuated access sparse-cap KEY2 using the cloud secret as message. Now instead of using KEY1 for decomposition, we use KEY3 instead. As this last operation could lead to a situation where someone holding an attenuated access sparse-cap to a parent node might derive the unattenuated sparse-cap to the child node, this operation needs to be performed server side and needs to be performed in a way that uses a secret only known to the server. In order to accomplish this, we use the attenuated access sparse-cap KEY2 as key and a concatenation of the child node name and the server side secret as message. It is important to realize that the resulting decomposition result is the unattenuated access sparse-cap, so the server implementation must take care to perform an additional attenuation operation if the operation was invoked using an attenuated-access sparse-cap.

The result of this updated design is that we could say that we have a two equally shaped connected trees. You could say the attenuated access caps of the nodes form a kind of a shaddow of the tree defined by the unattenuated access sparse-caps.

Offloading the server; use of the cloud secret

While decomposition through the introduction of attenuation facilities has become a server side operation, access to the encrypted object serializations must not necessarily go through the central component. In fact, from a privilege separation point of view, it might even be desired that the component in charge of decomposition itself has no access to the persistent storage for object serialization. In some cases a sub-system with write access might be useful, where other cases are conceivable, especially when the objects stored are actual data files, where distributed read only access could improve scalability. As discussed earlier, the determination of the storage key is done using a cloud secret. This secret should be shared between entities that require access to the actual object serializations, yet not to other entities. Lack of knowledge of the cloud secret should disallow clients with a sparse-cap to infer the location of the serialization within the storage system. While this may be of little use with a hand full of serializations in the storage system, this decoupling should be a least authority measure once the amount of stored entities grows. That is, an attacker with an attenuated access sparse cap and write access to the storage subsystem would have to try to decrypt (and check if decryption worked) millions of encrypted files. If we take care as not to make success detection too trivial w.r.t. the non-encrypted serialization formats used, this facility should offer some protection against the threat of adversarial cloud storage parties.

The symlink attenuation problem

The scaling facilities provided by the cloud secret introduce a new problem. Deep attenuation in the presence of symbolic link. If a symbolic link contains a sparse capability for attenuated access, then in the setup described so far, an attenuated access sparse capability for the symbolic link would provide any holder of the cloud secret with access to the raw storage and with the ability to retrieve the raw encrypted serializations, will have the ability to access the stored unattenuated access sparse capability. This of course is an undesirable situation that requires fixing. So far we have defined the need for two secrets and holder entities: A decomposition service without access to serialized encrypted holding the decomposition secret and a data access functionality that requires the cloud secret. We shall now define a third secret and corresponding sub-system. We define an additional layer of encryption. Instead of storing the sparse capability directly, we ask a service to encrypt it. The additional encryption is done using an encryption key, K4 that is created using keyed hashing, using K2 as key and the symlink secret as message. If the service is requested to decrypt the sparse capability using an unattenuated access sparse capability, or if the stored capability already was an attenuated access capability then the decrypted sparse-cap will be returned. If however an attenuated access capability is used to request th symlink content, and the content is an unattenuated access capability, the service will return an attenuated version of the stored sparse capability.

Open issue: preserving the acyclic property

Where the symlink subsystem elevates the directional tree graph design to a generic directional graph design. The symlinks however by themselves do not guarantee the esential acyclic property of the graph. While it is possible to create a check and failure mechanism inside of a symlink subsystem that would make new symlink creation fail if the new symlink would end up violating the acyclic property, there are potential performance, denial of service and race condition concerns with any such mechanism. As such we must this issue to be unresolved and accept that adherence to the acyclic property is to be considered a voluntary best practice guideline.