Use Merkle-tree-based storage

[v6ak]

Why?

• Backups can be authenticated as whole, not just individual VMs (at best).
• Atomicity: When computer crashes during backup, partial backup does not cause problems.
• It can obscure what file belongs to what VM. (But data usage patterns can still leak it, at least to some degree.)
• Allows buffering volumes. (Better performance, can potentially obscure data access patterns when upload is reordered.)
• Allow some data checks on remote. It can check hashes, because they are keys.

BackupStorageVM<->dom0 interface

Rather a simple key-value interface:

• get/set KDF params (operates with unauthenticated plaintext and simple KDF params format)
• getRoot – returns signed root with timestamp
• setRoot (or maybe compareAndSetRoot) – atomically stores a new signed root
• getBlob – returns an encrypted blob by ciphertext hash
• putBlob – uploads a new blob
• deleteBlob – removes blob

dom0 <-> BDVM interface

The interface should be very similar to BackupStorageVM<->dom0, but dom0 has to verify the permissions and maybe handle encryption.

Directory structure

Directory structure would be implemented on top of the mentioned key-value storage as Merkle tree.

What to decide

• How to handle permissions to particular files without leaking any data?
• How to buffer files in the target VM without leaking any data when maliciously modified? (When buffering, one has to send unauthenticated chunks.) Do we want this at all?
• How to handle garbage collection? Maybe it will require parsing and traversing directory structure in dom0. OTOH, it should be a rather simple format.
• When user removes a VM and creates a VM with the same name, should they be related in any way?

[v6ak]

First draft:

All items of Merkle tree are encrypted and somehow linked to the particular VM. TODO: describe details.

MAC is not needed for any node except the root one, because other node's ciphertext are authenticated by hash stored in a node that is already authenticated.

Root item

• creation date
• link to previous root item?
• root directory

Directory structure

List of directory item descriptions ordered by name.

Directory item description

• ASCII filename with limited set of characters
• item type (file or directory)
• creation date (?)
• size
• hash(es) of ciphertext (also this is identifier under which it will be references)

File

Just content of the file.