Cryptograhics file system

% Remco Bloemen % 2014-05-07

The only difficult right is reading. Any mutable operation can be implemented by a function

bool isValidChange(Change change, Authorization auth);

Where change represents the operation to be applied (for example a file delete) and auth is any collection of signatures or other data to proof the authorization for that change.

The function isValidChange returns true when the change conforms to all the rules.

This is similar to how the BitCoin blockchain validates transactions. Here every outgoing entry in a transaction contains a small script in a domain specific non Turing complete programming language. Give some authorization information, the script will return either true or false indicating if the authorization allows the money to be spend or not. This system has allowed BitCoin to be flexible beyond its original scope, but still there are uses for an even more flexible Turing complete language. This has some safety concerns however.

Some concepts

Once someone has a received the keys to access a file for reading, it is difficult to revoke.

If the user had access to the plaintext they could have made an out-of-system copy of the file’s plaintext. This is outside the scope of the system, unless it would implement draconian measures as scanning all the users systems for copies of possibly revoked files. The problem gets even more complicated by removable and read-only media such as optical disks or simply printed paper.

Assuming the user did not store the plaintext.


Lazy revocation

In lazy revocation the file’s key is updated the next time the file is changed. The old key will remain valid for the old file, but can not be used anymore for new changes, which will be encrypted with a new key.

The old key is marked dirty and the process of decrypting with the old key and reencrypting with the new key is called cleaning.

Key Rotation

Plutus: Scalable secure file sharing on untrusted storage Kallahalla, Riedel, Swaminathan, Wang and Fu

$$ \begin{aligned} K_{n+1} &= E_{private}(K_n) & K_{n-1} &= E_{public}(K_n) \end{aligned} $$

Key regression

Suppose key $K_1$ is updated to $K_2$, but some files are still dirty and encrypted with $K_1$. Key regression allows the $K_1$ to be derived from $K_2$ so that no history of keys needs to be maintained.

Rate limits (idea)

It would be nice to have a rate limiting service. A means of recognizing when rights are used in a suspicious manner. For example by exhaustively using all the read access rights to create an unencrypted copy of all the files.

One time pads (idea)

Tens of gigabytes of random key material can easily be stored on postmark sized microSD cards. Why not use this technology to obtain the perfect encryption that comes with it?

$$ K_1 → K_2 $$

There is some information $K_2'$ such that

$$ K_2 = D(K_1, K_2') $$

$$ K_1 \rightharpoonup K_2 $$

There is some information $K_2'$ such that

$$ K_2 = D( $$

Stored information isn’t dead

Least authority file system

Inserting a file

  1. File is encrypted
  2. The result is segmented
  3. Redundant data is added
  4. Hashes are computed
  5. Peers are selected
  6. Data is send to selected peers

The result is an ‘capability uri’ for downloading the file.

Donwloading a file

  1. Collect sufficient segments

  2. Validate their hashes

  3. Combine the segments

  4. Decrypt the segments


URI:CHK:(key):(hash):(needed-shares):(total-shares):(size) key is the 16-byte AES encryption key encoded in Base32 encoding, hash is the SHA265d hash of the URI Extension Block, needed-shares is the number of shares needed to reconstruct the file, total-shares is the number of total-shares distributed in the grid for that file, size is the size of the file in bytes.


URI:CHK-Verifier:(storageindex):(hash):(needed-shares):(total-shares):(size) storageindex is the SHA265d hash of the encryption key truncated to 16-byte.

literals (used for files smaller than 55 bytes)

URI:LIT:(data) data is the file hashed using SHA265d and encoded in base32 encoding.


Wuala uses Cryptree

"Because of the design of the Cryptree key management system used by Wuala, it is possible for Wuala (and possibly other attackers, but I’m not sure about that) to identify which files you have modified. This sounds like a minor point, but it is a potential problem: For example, when people decide to update their CVs / resumes, they would often prefer that their current employer not find out."

See also

Remco Bloemen
Math & Engineering