Chaining cryptographic algorithms

Let’s first take a look at some scenarios you might already know, in order to explain the far more complex crypto-chaining used by subshare:

1. When encrypting data using public-key cryptography, it is normal to not encrypt the payload data directly with the asymmetric algorithm. Instead, a random symmetric key is generated and encrypted with the public-key algorithm. The actual payload is then encrypted symmetrically.

   Payload-ciphertext and encrypted symmetric key are then sent together to the recipient. The recipient decrypts first the symmetric key using his private (asymmetric) key and then symmetrically decrypts the actual payload. This approach is called a hybrid cryptosystem.

2. In order to protect the private key, OpenPGP and other tools encrypt it using a symmetric crypto algorithm with the owner’s passphrase as symmetric key (more precisely: the symmetric key is derived from the passphrase).

3. Password-managers encrypt dozens of passwords with a single master-password (again with key derivation, of course).

As illustrated by these 3 examples, it is common to link multiple cryptographic operations (with multiple different keys) together in a chain.

From directory/file tree to cryptographic tree

Given the habitualness of chaining cryptographic keys and operations, subshare of course uses the same approach to join the encryption operations needed to encrypt an entire file system with many nested directories containing other directories and files.

When we started working on subshare, we stumbled over the paper Cryptree: A Folder Tree Structure for Cryptographic File Systems (original link broken) which described pretty much exactly what we needed. This saved us quite some work as we didn’t need to start planning the crypto-link-structure from scratch.

Therefore, big thanks to the authors of this paper!

However, we didn’t implement it as described:

First, we use the “Cryptree” solely for read permissions, i.e. for the encryption of meta- and payload-data. The “write access Cryptree” proved to be far too slow, because it requires too many public/private-key-pairs. Generating a key-pair is very expensive — it usually takes around 10 seconds and it may even take longer than a minute (depending on algorithm, key size and CPU power).

The average repository has hundreds of directories with thousands of files (and symlinks). Generating 4096-bit-RSA key-pairs for only 500 directories would already consume more than one hour — on fast hardware! You can totally forget this approach on a smart phone!

Hence we do not use it for write permissions. Instead, we decided to use a permission system based on signed delegations (another chaining — this time chained signatures).

Second, we extended the “read access Cryptree” described in the paper to support grant permissions (which were not yet mentioned in the paper). This extension required us to switch from a symmetric to an asymmetric “subfolder key” whenever grant permission was granted to a directory’s child directory. For performance reasons, we still continue to use symmetric “subfolder keys” as long as this is possible (i.e. in 99.999% of the cases).