Design Sketch for a Quantum-Safe Encrypted Filesystem

Almost all disk encryption systems today follow a similar design pattern.  Symmetric-key block ciphers are used, with the initialization vector being derived entirely from the block index to which the data is stored.  Often times, the disk is broken up into sections, each of which has its own key.  However, the point of this is that the key and IV are static across any number of writes.

This preserves the atomicity of writes and allows the design to work at the block layer as opposed to the filesystem layer.  However, it also restricts the modes of operation to those that are strong against reuse of IVs.  Typically, this means CBC mode.  This block-level design also makes it quite difficult to integrate a MAC.  Modes like AES-XTS go some distance to mitigating this, and the problem can be mitigated completely by using a filesystem with inherent corruption-resistance like ZFS.

The problem is that this scheme completely prohibits the use of stream ciphers such as ChaCha20 or modes of operation such as CTR or OFB that produce stream cipher-like behavior.  This would be a footnote but for recent results that demonstrate a quantum period-finding attack capable of breaking basically all modes other than CTR or OFB.  This suggests that to implement quantum-safe encrypted storage, we need to come up with a scheme capable of using stream ciphers.

The Problem of Disk Encryption

The fundamental problem with using stream ciphers for block-layer disk encryption stems from the fact that the initialization vector (and ideally the key) must be changed every time the block is written, and this key must be available at an arbitrarily later time in order to read.

In general, there are basically three ways to manage keys in the context of disk encryption:

1. Derive the key and IV from the block index
2. Store the keys in a separate location on disk, look this up when needed
3. Alter the interface for block IO to take a key as a parameter

Most current disk encryption schemes use option 1; however, this ends up reusing IVs, which prohibits the use of stream ciphers (and modes like CTR and OFB).  Option 2 guarantees that we have a unique IV (and key, if we want it) every time we write to a given block; we simply change keys and record this in our key storage.  The price we pay for this is atomicity: every incoming block write requires a write to two separate disk blocks.  This effectively undermines even atomic filesystems like ZFS.  The only example of this sort of scheme of which I am aware is FreeBSD’s older GBDE system.

Option 3 eschews the problem to someone else.  Of course, this means they have to solve the problem somehow.  The only way this ends up not being wholly equivalent to options 1 or 2 is if the consumer of the block-layer interface (the filesystem) somehow organizes itself in a way that a key and IV are always readily available whenever a read or write is about to take place.  This of course, requires addressing full-disk encryption in the filesystem itself.  It also places certain demands on the design of the filesystem.

Atomic Snapshot Filesystems

Atomic filesystems are designed in such a way that all I/O operations appear to be atomic.  With regard to writes, this means that the sort of filesystem corruption that necessitates tools like fsck cannot happen.  Either an operation takes place, or it does not.

Of course, a given write operation may actually perform many block writes; however, the filesystem’s on-disk data structures are carefully designed in such a way that one single write causes all of the operations that lead up to it to “take effect” at once.  Typically, this involves building up a number of “shadow” objects representing the new state, then switching over to them in a single write.

Note that in this approach, we effectively get snapshots for free.  We have a data structure consisting of a mutable spine that points to a complex but immutable set of data structures.  We never overwrite anything until the single operation that updates the mutable spine, causing the operation to take effect.

Atomic Key/IV Updates

The atomic snapshot filesystem design provides a way to effectively change the keys and IVs for every node of a filesystem data structure every time it is written.  Because we are creating a shadow data structure, then installing it with a single write, it is quite simple to generate new keys or IVs every time we create a node in this shadow structure.  Conversely, because the filesystem is atomic, and every node contains the keys and IVs for any node to which it points, anyone traversing the filesystem always has the information they need to decrypt any object they can reach.

This scheme has advantages over conventional disk or filesystem encryption.  Unlike conventional disk encryption, each filesystem object has its own key and IV, and these are uniquely generated every time a write takes place.  Nothing about the key and IV can be inferred by any attacker looking at an arbitrary disk block.  Unlike conventional filesystem encryption which typically only encrypts file contents, everything is encrypted.

Possible ZFS Extension

The ZFS filesystem is a highly advanced filesystem and volume management scheme that provides fully atomic operations and snapshots.  I am admittedly not familiar enough with its workings to know for absolute certain whether the scheme I describe above could be added to it, but I am fairly confident that it could.  I am also aware that ZFS provides an encryption system already, but I am also fairly confident that it is not equivalent to the scheme I describe above.

ZFS would also need to be extended to support a broader range of ciphers and modes of operation to take advantage of this scheme.  Support for CTR and OFB modes are absolutely essential, of course.  I would also recommend support for ciphers beyond AES.  Camellia and ChaCha20 would make good additions, among others.

Conclusion

Quantum-safe disk encryption is arguably not as critical to develop as quantum-safe encryption for network communications.  With network communications, it is reasonable to assume that all traffic is being recorded and will be subject to quantum attacks once those become available.  The same it not true of disk storage.  However, the technology does need to be developed, and the recent results about the period-finding attack on symmetric cipher modes demonstrate a workable attack against nearly all disk encryption schemes.

I would urge all filesystem projects to consider the scheme I’ve laid out and integrate concerns for quantum-safe encryption into their design.

As a final note, should anyone from Illumos run across this blog, I’d be more than willing to discuss more details of this scheme with them.