C++ Rumpelstiltskin tree-graph library
RumpelTree++ is a C++11 implementation of the Rumpelstiltskin Tree-graph sparsecap algorithm. This algorithm allows any decomposable singly-attenuable Directional Acyclic Graph (DAG) structured authority graph to use sparse capabilities as tokens of authority for potentially singly-attenuated sub-graphs.The algorithm imposes storage and encryption keys to be used for the serialisation of DAG nodes. While the RumpelTree++ was written primarily for use in the upcoming RumpelstiltskinFS, a sparse friendly encrypted rewrite of one of the core MinorFS user-space file systems. The prima advantage of this algorithm for RumpelstiltskinFS is that it removes the need of any lookup table like the sqlite database used in the earlier MinorFS solution. The library and the algorithm were both written and designed with RumpelstiltskinFS in mind, but they should be usable in a much wider range of situations, including as basis for capability URLs.
Before installing, please make sure you have Crypto++, cmake and either a recent version of the GNU C++ compiler or Clang installed on your system. If you are running Linux, each of these should be available in your standard repository. After having taken care of these prerequisites, do the following:
$ git clone https://github.com/pibara/Rumpeltreepp.git
$ cd Rumpeltreepp
$ mkdir build
$ cd build
$ cmake ..
$ make
$ make test
$ sudo make install
If any of the steps before 'sudo make install' fails, please contact the author.
Currently RumpelTree++ is a one-man project, and while the author has over a decade of experience with secure coding practices, recent events like heartbleed have shown the importance of peer review of security sensitive code. The author of RumpelTree++ is currently looking for anyone with knowledge on at least two of the following subjects to contribute a peer review to this project:
In order to use RumpelTree++ in your code, you should include the Rumpelstiltskin header file to your C++ code.
#include <rumpelstiltskin.hpp>
Next to this, you will need to inform your build system about the fact that your application needs to be linked against the rumpeltree++ library. If you are using CMake, this should be done something like:
target_link_libraries(yourapp rumpeltree++)
RumpleTree++ deals with sparse caps. These sparse caps are basically strings that potentially hold tremendous authority. Given that its best to minimize the risks of holding this authority, RumpelTree++ comes with its own string class rumpelstiltskin::string that should be close to a drop-in replacement for std::string. The rumpelstiltskin::string class is basically a RAIIish like wrapper for std::string that clears the content of the wrapped string prior to destruction. By doing this, the lifetime of the spare caps in process memory is limited to the logical lifetime of the strings in your program. This while when using std::string for such strings, the spare caps may linger in process memory for quite some time, and may end up in uninitialized memory allocated to other parts of your program, what from a least authority perspective is a bad idea. It is strongly suggested that when your programs handles sparse caps outside of the direct RumpelTree++ context, it use rumpelstiltskin::string to store them.
Mostly when using RumpelTree++ you won't have to concern yourself about the difference between rumpelstiltskin::string and std::string. The use of the C++11 auto keyword should hide this from you for the most part, and the interface of rumpelstiltskin::string is sufficiently similar to that of std::string so that you should hardly notice it in >90% of cases.
Next to rumpelstiltskin::string, RumpelTree++ also comes with a convenience function for wiping 32 byte long representations of encryption keys (that we shall discuss later). If for some reason you need to copy an encryption key out of a RumpelTree++ object, its suggested you wrap this key inh a RAII object and invoke this convenience function from its destructor.
YourClass::~YourClass() {
rumpelstiltskin::memclear32(mKey);
}
The Rumpelstiltskin Tree-graph sparsecap algorithm supports some operations to only be performed on the server side, while other operations may for scalability and performance reasons also be done on the client side. If you are building a server or a file-system you may opt to ignore the whole concept of client side operations, or you may build in facilities that allow a select set of operations to also be performed client side. The following sections describe the RumpelTree++ operations for the server side.
The server itself needs one or two secrets:
auto secret=rumpelstiltskin::randomsecret();
This function should only be used at first use of your server or during installation. This secret should be stored in a place where only your server of file-system is able to access it with strict access control allowing your server and only your server to access it during normal system operations. Whenever the server is restarted, the secret should be retrieved from this tightly protected file. We can now create a base server object for our server implementation to use:
auto server=rumpelstiltskin::create_server(secret);
auto server=rumpelstiltskin::create_server(secret,cloudsecret);
One of the core concepts of the Rumpelstiltskin Tree-graph sparsecap algorithm is the unattenuated root sparsecap. The fun thing is, we can have many roots and in order to create a new root, we can either just make one up, or generate one from a password.
auto randomrootcap=rumpelstiltskin::randomrootcap();
auto personalrootcap=rumpelstiltskin::pass2rootcap("KnockKnockItsMeAg41n");
Once we have a root cap or any cap for that matter, we can get to one of the node's of our tree.
auto rootnode=server[personalrootcap];
Once we have a node object, its possible to get at any of its child nodes using the locally unique name of the child. A node could have one child named 'bob' and another child named 'allice', but no two children named 'bob'. After we get at the child node named 'bob' we can request the sparsecap to designate that node.
auto childnode=rootnode["bob"];
auto childcap=childnode.cap();
It is essential to note that decomposition is purely a server side operation. While other operations like attenuation and decryption may be done client side, the algorithm used by RumpleTree++ does not allow for client side decomposition.
Next to decomposition and getting at the sparse caps for child nodes, we can also use single attenuation. Its important to note that this single attenuation is deep attenuation. You can use an attenuated authority sparse cap for a parent to gain access to an attenuated authority sparse cap for any of its children. Its also important to note that attenuation of decomposition yields the exact same sparse caps as decomposition of attenuation does. Getting an attenuated authority sparsecap is done like:
auto attenuatedrootnode=rootnode.attenuated();
auto attenuatedrootcap=attenuatedrootnode.cap();
While we could just make up root node sparse caps or generate them from a password, the actual node's in the DAG need to be persistently stored somewhere, and this storage should probably be done encrypted. For this, RumpelTree++ has the concept of storage objects. Each node can be mapped to a storage object, and this storage object holds both a storage key designating some kind of location for the encrypted storage of the serialization of the node, and an encryption key that is to be used for encryption and decryption of the serialized node's. Its important to note that neither encryption nor storage are part of the RumpelTree++ functionality. Its up to the application implementing the actual server or file-system to take care of storage and encryption. RumpelTree++ simply provides node encryption keys and file-system friendly storage keys.
auto rootstorage=rootnode.storage() ;
auto rawstorage=rumpelstiltskin::string("/var/rumpelstilskinfs/rawdata/") + rootstorage.storage();
auto cryptokey =rootstorage.crypto_key();
While its completely possible to only ever use server side operations, there might be scalability issues with doing all operations on a single server. To unload the server, there are some operations that can be performed on the client side instead. Attenuation is always possible on the client side, while enabling decryption is a possibility that a system designer may opt for. To do client side operation, we need to create a client side object first. If the server side uses a cloud secret, and if we want to support client side decryption, we shall also need this cloud secret, otherwise we may simply forget about it.
auto client=rumpelstiltskin::create_client(cloudsecret);
Client side attenuation knows no concept of node's. The client can simply directly convert unattenuated authority caps to attenuated authority caps.
auto attenuatedcap=client.attenuate(unattenuatedcap);
If the system designer wishes it, she could allow the clients read-only access to encrypted node-serialization storage, and using the client side default or pre-shared cloud secret, client side decryption could be implemented. Just like with attenuation, we have no node concept on the client side, just direct translation of sparse caps to storage objects.
auto nodestorage=client.storage(cap);
auto rawstorage=rumpelstiltskin::string("/export/servernetworkshare/") + rootstorage.storage();
auto cryptokey =rootstorage.crypto_key();