Introduction

EscoDB is a document store designed for privacy and portability. It provides end-to-end encryption of all data and supports storing content on any object store with conditional writes. It principally targets read-heavy applications requiring storage of sensitive material, such as passwords, TOTP keys, API tokens, private keys and other credentials.

Here is a brief overview of its API:

let adapter = new FileAdapter({ path: 'path/to/store' })

let store = new Store(adapter, {
  key: { password: 'open sesame' }
})

let handle = await store.openOrCreate()

await Promise.all([
  handle.update('/contacts/alice', () => ({ email: 'alice@example.com' })),
  handle.update('/contacts/bob', () => ({ email: 'bob@example.com' }))
])

let contacts = await handle.list('/contacts/')
// -> ['alice', 'bob']

let alice = await handle.get('/contacts/alice')
// -> { email: 'alice@example.com' }

Its key features are:

Flexible and convenient data model: EscoDB’s interface is that of a key-value store, where the values are JSON-compatible documents, and keys resemble filesystem paths. This allows for grouping related items into directories, and efficiently listing and removing all the items within a directory.
End-to-end encryption of all content: All content – both keys and values – is encrypted at rest and is resistant to tampering. Document keys and directory structure are not readable to anyone who does not know the store password. An attacker cannot modify the stored data without being detected.
Bring your own storage: EscoDB is designed to run in a variety of environments and supports storing its data in any object store with conditional writes. This includes the local filesystem, cloud platforms like Amazon S3, Google Cloud Storage, or Dropbox, or self-hosted services like remoteStorage or Solid. Users can add support for any data store by implementing a small plugin API.
Safe concurrent access: By using the underlying data store’s conditional write API, EscoDB ensures that multiple clients can concurrently update the store without losing updates. It ensures the internal consistency of its data model in the presence of concurrent updates to the same files, and partial failure of a client workload.
Highly optimised batch updates: Being designed to interact with remote storage services with high latency, EscoDB transparently optimises document updates into as few requests as possible. It does this while preserving data consistency when clients perform concurrent updates to the same files.

Installation

EscoDB does not have a central server but rather operates as a library that you embed in your own applications. It is distributed as a JavaScript package installable via npm:

$ npm install @escodb/core

Once installed, it can be loaded via require() or import:

// CommonJS
const { Store, FileAdapter } = require('@escodb/core')

// ESM
import { Store, FileAdapter } from '@escodb/core'

Usage

The @escodb/core package exports a few different classes:

const { Store, FileAdapter } = require('@escodb/core')

The full set of exported classes is:

Store: The core class representing an EscoDB instance backed by a specific storage location. This is the main entry point for all interactions with a store.
FileAdapter, MemoryAdapter: These are covered under Storage adapters.

Creating and opening a store

All interaction with a store begins by creating a storage adapter, and then creating a Store instance with this adapter and the password needed to access it.

let adapter = new FileAdapter({ path: 'path/to/files' })

let store = new Store({
  key: { password: 'open sesame' }
})

The FileAdapter class takes the following options:

path (required): The pathname to the directory where the store’s files will be kept. The current process’s user must have permission to read and write in this directory.
fsync: Whether to call fsync(2) when writing to files. This is more robust but adds significant latency. For maximal safety, this is true by default and EscoDB optimises document updates into as few disk accesses as possible to minimise the latency impact. In some scenarios, for example when running unit tests, it may be desirable to disable fsync to reduce latency.

The Store class takes the following options:

key.password: The password that is used to encrypt the store’s root encryption keys. This should be a high-entropy unique password that cannot be guessed or brute-forced by an attacker.

EscoDB may support other types of access control in future, such as a raw symmetric encryption key or a user’s asymmetric key pair. For now, passwords are the only supported access method.

Creating a new store

If nothing has yet been written to the store, i.e. the target directory contains no files, then it must be created:

let handle = await store.create({
  password: { iterations: 1000000 },
  shards: { n: 2 }
})

This performs the initial setup for the store: generating a set of cryptographic keys and related configuration data, and writing this config to disk. The options are:

password.iterations: The number of rounds used to convert the password to an encryption key via PBKDF2-SHA-256. This currently defaults to 600,000.
shards.n: The number of shard files that the store will spread documents across. Increasing the number of shards allows the store to perform more concurrent data access and decreases the time to read and write shards as each file contains a smaller slice of the whole data set. However it also increases the number of disk accesses (or HTTP requests for remote stores) required to access multiple items. Setting the number of shards is a trade-off between these factors. The default number is 4.

If the store already exists, then Store.create() will throw an error.

Opening an existing store

If the store has already been initialised, then it needs to be opened:

let handle = await store.open()

This reads the config into memory and uses the password to decrypt the store’s root keys. This involves a slow hash of the store password but this only needs to be done once when the store is first opened, not when individual items are accessed.

If the store has not been initialised then Store.open() will throw an error.

As a convenience, EscoDB provides a method that will open the store if it exists, otherwise it will initialise it with the given options and then open it.

let handle = await store.openOrCreate({
  password: { iterations: 1000000 },
  shards: { n: 2 }
})

Note that if the store already exists, the options passed to openOrCreate() will have no effect; they will not be used to update the store’s settings and will simply be ignored.

Working with documents

Documents in EscoDB are indexed by a path, a string resembling an absolute filesystem path. Paths must begin with a slash, and may contain letters, digits, dashes, underscores and dots, and they may contain multiple segments separated by slashes. /info.txt, /phone-numbers and /bob/avatar.png are all valid document paths.

A document path must not end with a trailing slash. A directory path does end with a trailing slash; such a path refers to the set of documents whose paths have it as a prefix. For example, the directory /bob/ contains the document /bob/avatar, while the directory / contains the document /index and the directory /bob/.

Directories are created implicitly when documents are updated; they do not need to be explicitly created. A directory is simply a cache of the document paths that begin with a certain prefix, which means the store can efficiently return a list of the directory’s children without scanning the whole store.

It is legal for a directory to have the same textual name as a document; /users and /users/ are distinct paths that refer to a document and a directory respectively. Thus it is legal to have documents named /users and /users/alice co-exist.

The store handle returned by Store.open() or Store.create() supports the following methods.

`handle.get(path)`

Returns the current content of the document at path, or null if the document does not exist.

await handle.get('/users/alice')
// -> null

await handle.update('/users/alice', () => ({ name: 'Alice' }))

await handle.get('/users/alice')
// -> { name: 'Alice' }

`handle.list(path)`

Returns the names of all the documents and subdirectories that are direct children of the directory at path, or null if the directory does not exist.

await handle.list('/users/')
// -> null

await handle.update('/users/alice', () => ({ name: 'Alice' }))
await handle.update('/users/bob/contacts', () => ({ email: 'bob@example.com' }))

await handle.list('/users/')
// -> ['alice', 'bob/']

`handle.find(path)`

Returns an async iterator containing the names of all the documents that are descendants of the directory at path.

await handle.update('/users/alice', () => ({ name: 'Alice' }))
await handle.update('/users/bob/contacts', () => ({ email: 'bob@example.com' }))

let paths = []

for await (let path of handle.find('/users/')) {
  paths.push(path)
}

// -> paths = ['alice', 'bob/contacts']

Note that find() enumerates only documents that reside under the given directory, it does not emit intermediate directory names. It returns an async iterator rather than a single Promise because it requires traversing multiple directory entries in the store, rather than reading the content of a single directory.

`handle.update(path, fn)`

Updates the document at path by applying the function fn to its current state.

// create a new doc, or ignore its current content

await handle.update('/users/alice', () => {
  return { emails: ['alice@example.com'] }
})

// update a doc based on its current state

let doc = await handle.update('/users/alice', (doc) => {
  let emails = [...doc.emails, 'work.address@example.org']
  return { ...doc, emails }
})

// -> doc = { emails: ['alice@example.com', 'work.address@example.org'] }

The update() method takes a function rather than a simple document value in order to support concurrency. If two clients try to update the same file at the same time, the storage layer will return an error to one of them and that client will retry. It does this by reloading the file containing the other client’s update, and then re-applying fn to the document.

This means that fn may be executed multiple times, but only its final output will be persisted. That is, once the storage backend accepts the client’s write, it will not apply the same update to the document again. For example, if three clients concurrently execute the function update('/counter', (doc) => ({ n: doc.n + 1 })), then the n field in the document /counter will be incremented by 3, even though each client may execute the update function multiple times as they all race to update the same file.

The same thing applies if the same client makes multiple concurrent updates of its own:

await handle.get('/counter')
// -> { n: 1 }

await Promise.all([
  handle.update('/counter', (doc) => ({ n: doc.n + 1 })),
  handle.update('/counter', (doc) => ({ n: doc.n + 1 })),
  handle.update('/counter', (doc) => ({ n: doc.n + 1 }))
])

await handle.get('/counter')
// -> { n: 4 }

update() returns a Promise that resolves with the new state of the document when the document has been successfully written to the storage backend. If writing to storage raises any error other than a conditional write conflict, the Promise is rejected with this error.

`handle.remove(path)`

Unconditionally removes the document from the store.

await handle.get('/users/alice')
// -> { name: 'Alice Smith' }

await handle.remove('/users/alice')

await handle.get('/users/alice')
// -> null

Like update(), the remove() method returns a Promise that resolves when its effect is successfully persisted, or rejects with an error if writing the update to storage fails.

`handle.prune(path)`

Recursively removes all the documents under the directory path.

await handle.get('/users/alice')          // -> { name: 'Alice' }
await handle.get('/users/bob/contacts')   // -> { email: 'bob@example.com' }
await handle.list('/users/')              // -> ['alice', 'bob/']

await handle.prune('/users/')

await handle.get('/users/alice')          // -> null
await handle.get('/users/bob/contacts')   // -> null
await handle.list('/users/')              // -> null

To remove all the documents in the store, call prune('/').

Performance optimisation

EscoDB has been designed to let applications keep their data in an arbitrary object store, including those available through cloud hosting platforms. Access to a remote service can involve significant latency, for example it is not uncommon to see response times of 1-2 seconds when using the Dropbox API even on a fast and stable internet connection. This can make it very expensive to access multiple items in a store, and so we provide a way to automatically batch operations together to massively reduce interaction with the storage layer.

Storage model

To make the best use of the API, it helps to understand its storage model. An EscoDB instance stores documents and directory information in a fixed number of shard files. Each document is assigned to a shard by hashing its path, producing a uniform and random distribution of documents across shards.

To execute a get() or list() call, the store needs to load the shard containing the requested path into memory, parse it, and then locate the requested path within it.

To execute an update() or remove() call, it needs to load the shards containing the affected document and all its parent directories, update all of them in memory, and then write the updated shards back. These writes need to be performed in a particular order to preserve the internal consistency of the store’s data structures, so they cannot all be performed in parallel.

The storage backend implements compare-and-swap (CAS), wherein it will only accept a write if the client proves it has seen the latest version of the file. When clients try to apply concurrent updates to the same shard, some of these writes will be rejected and the whole update() or remove() workflow needs to be retried, all of which adds to the latency for successfully completing the operation.

EscoDB provides a way to reduce the cost of both reads and writes, by caching shards in memory and transparently batching multiple document updates into the same write to a shard file.

The Task interface

EscoDB provides an abstraction called a task for grouping multiple document accesses and reducing the communication overhead with the storage backend. To use it, perform the usual steps to open a store:

let adapter = new FileAdapter({ path: 'path/to/store' })
let store = new Store(adapter, { key: { password: 'open sesame' } })
let handle = await store.open()

Once you have a handle from Store.open(), calling task() on it will create and return a new task.

let task = handle.task()

Tasks have the same interface as the main store handle: get(), list(), find(), update(), remove() and prune() all work as they do normally. The difference is in how the task changes the interaction with the storage adapter:

All shard files are cached indefinitely. This means calls to get(), list() and find() will always return the same result for each document/directory, as updates made by other clients are not visible.
Concurrent calls to update(), remove() and prune() are optimised into a small number of writes to the backend, while preserving any ordering needed for internal consistency.

Document updates still obey CAS; if a write to a shard file is rejected due to concurrent writes by other clients/tasks, all updates targeting that shard will be retried. Since this causes the shard to be reloaded, this is the only way that changes from other clients become visible to a task.

Tasks vs transactions

Note that a task is not a transaction, it is a data access optimisation. Document updates performed through a task are still independent of one another, and it is possible for some to succeed while others fail.

The shard files are also independent objects and storage adapters do not offer transaction semantics across them. This means that if a task updates multiple documents, those updates are not atomic. Another client may observe some of these updates before the task has completed all its planned updates.

In terms of consistency phenomena, EscoDB prevents lost updates to a single document, but does not prevent write skew across documents. It also does not provide snapshot isolation; it caches each shard on first access but does not provide a consistent view across all shards at a single moment.

Optimisation patterns

For many workloads, simply using a handle.task() to access the store rather than the handle itself will make things faster. Any number of tasks can be created from the same handle, and so a task also functions as a way to scope cache lifetimes.

let task1 = handle.task()

await task1.get('/alice')
await task1.get('/bob')

let task2 = handle.task()

await task2.get('/carol')

In this example, the reads of /alice and /bob share the same cache, while the read to /carol uses its own cache. This lets you control when you’d like data accesses to take advantage of caching, versus when you’d prefer to see up-to-date content.

Concurrent updates

For sequential updates, the use of a task provides some benefit. In the following example, every update() has to read the affected shards from the backend and write them back again:

let handle = await store.open()

await handle.update('/alice', () => ({ email: 'alice@example.com' }))
await handle.update('/bob', () => ({ email: 'bob@example.com' }))
await handle.update('/carol', () => ({ email: 'carol@example.com' }))

If a task is used here, then each shard is only read into memory once, when it is first needed by any of the update() calls. But, each update() still makes exactly the same writes as it did before.

let handle = await store.open()
let task = handle.task()

await task.update('/alice', () => ({ email: 'alice@example.com' }))
await task.update('/bob', () => ({ email: 'bob@example.com' }))
await task.update('/carol', () => ({ email: 'carol@example.com' }))

A much more significant performance gain can be had by executing the updates concurrently using the task:

let handle = await store.open()
let task = handle.task()

await Promise.all([
  task.update('/alice', () => ({ email: 'alice@example.com' })),
  task.update('/bob', () => ({ email: 'bob@example.com' })),
  task.update('/carol', () => ({ email: 'carol@example.com' }))
])

When this is done, the updates also merge their changes into a small number of shard file writes. A task can quite comfortably merge 100,000 document updates together into a workload that reads each shard once and writes to each shard just a couple of times.

Note that if the set of concurrent update() calls in the above example were invoked on handle, rather than on task, they would actually be executed sequentially. When invoked through handle, each update() call acts independently with its own copy of the shard content. If they were allowed to execute concurrently, their writes to the backend would likely conflict with each other and cause a lot of retries before all of them eventually succeeded. To produce a more optimal outcome, each update() is instead executed one at a time.

To give an idea of the difference that task.update() makes, below is the result of a benchmark for updating 1,000 documents with randomised paths, stored across 4 shards, via FileAdapter with fsync turned off to reduce the write latency:

	Reads	Writes	Time (ms)
sequential `handle.update()`	2,618	2,618	1,163
sequential `task.update()`	4	2,632	980
concurrent `task.update()`	4	8	59

Your results will depend on the platform you’re running on and the latency properties of your storage adapter, but this illustrates how big a difference this optimisation can make. On remote storage systems with even higher latency this difference can be enormous.

Execution planning

In general, any update() or remove() executed by a task will be merged into whatever uncompleted work the task is already executing, to dynamically reduce the total number of writes made. If a shard file write fails due to a CAS violation, the retried operations are optimised in the same way.

One caveat to be aware of is that this optimisation involves building an execution plan that is stored in memory. This plan increases in size with every pending operation, and with the number of shards in the store. At a certain number of pending updates, the cost of storing and updating this plan may become prohibitive, but this can be avoided by putting a limit on the number of updates put into a single batch.

let handle = store.open()

let docs = {
  '/alice': { email: 'alice@example.com' },
  '/bob': { email: 'alice@example.com' },
  // ...
}

let task = handle.task()
let updates = []
let limit = 1e5

for (let [path, doc] of Object.entries(docs)) {
  updates.push(task.update(path, () => doc))

  if (updates.length >= limit) {
    await Promise.all(updates)
    updates = []
  }
}

Note that you do not need to create a fresh task when the updates list is flushed. A task’s execution plan only retains pending operations in memory, so a single task can be used indefinitely as long as its set of pending operations does not get too large, and all pending operations eventually complete.

Storage adapters

EscoDB provides a number of storage adapters that can be passed to the Store class to handle persistence. Two such adapters are included in the @escodb/core package:

FileAdapter: Stores content on the local filesystem. Most current applications will use this adapter.
MemoryAdapter: Stores content in memory and does not write to any persistent store. This adapter is mainly used for testing; if your application uses a remote storage backend, it can be swapped out for this adapter and it will work identically.

Several other adapters are available via other packages:

@escodb/couchdb-adapter: Adapter for storing content in CouchDB.
@escodb/s3-adapter: Adapter for storing content in Amazon S3.

Custom adapters

Support for any other storage system can be accomplished by implementing the Storage Adapter API, which consists of the following methods:

read(id): Returns Promise<{ value, rev }> where value is a string representing the current content of the file or object named id. rev is a revision token that identifies the current version of the file, and can be any type of value that the write() method knows how to handle. If the file does not currently exist, returns Promise<null>.
write(id, value, rev): If rev matches the current revision of the file named id, then it writes the string value to the file and returns Promise<{ rev }> where rev is the new revision token. Otherwise, it returns a Promise rejected with an error with code = 'ERR_CONFLICT'. If the input rev is null then the write must only succeed if the file does not currently exist.

Any object implementing these two methods can be used as a storage adapter. To make sure that EscoDB’s concurrency control works correctly, these methods must obey the following constraints:

The first write(id, value, rev) call to succeed for a given id must have rev = null. That is, the client must believe it is creating the file for the first time. If the file does not exist then any non-null rev input should be rejected.
Any subsequent write(id, value, rev) call for that id must succeed only if rev is a revision token that has previously been returned by read(id) or write(id, ...). That is, some client must previously have been told that rev was the current revision token.
write(id, value, rev) must succeed at most once for each unique combination of id and rev, i.e. only one value is accepted for each version of a file.
The rev returned by a successful call to write(id, value, rev) must be different from any previously returned rev. EscoDB includes a small amount of random content each time it updates a file, so this requirement can be met by using a collision-resistant content hash.
After a write(id, value, rev) call succeeds, all subsequent calls to read(id) must return value until the next successful call to write(id, ...).
write(id, value, rev) must appear to be atomic to any external observer. That is, calls to read(id) must only ever return a value that was passed in some prior successful write(id, value, rev) call and must never return any intermediate or incomplete value.

Security considerations

The storage layer in EscoDB is deliberately minimal. It does not have any awareness of the data model built on top of it, the data access execution planner, or any of the cryptographic techniques used to secure the data. It is simply a place where blobs of data can be stored and retrieved.

Being an end-to-end encryption system, EscoDB places minimal trust in the storage layer and tries to guard against an attacker who has access to the storage server or to the communication channel between the client and the server.

That being said, it is still a good idea to secure the storage backend as much as you are able. The storage system should be protected by strong credentials that grant access only to authorised users, it should be logically or physically isolated from systems that do not require access to it, and all communication with it should use an encrypted and authenticated transport mechanism such as TLS or SSH.

Cryptography

EscoDB is a document store designed to keep its contents private. It achieves this via two key features: it lets the user choose where its contents are physically stored, and it encrypts everything input by the user, including document IDs (referred to as paths in the API).

It also aims to protect stored data from certain forms of tampering. While encryption prevents an attacker from being able to read the contents of your files, tamper resistance means they cannot deface data in certain ways, even if they are unable to decrypt it. They key thing that EscoDB prevents is the ability to move encrypted records inside a file so that a document becomes readable via a different ID than the one it was written to. This is achieved by appropriate use of authenticated encryption with associated data (AEAD).

EscoDB cannot protect you from arbitrary changes to its data files, including partial or total deletion of their content. You should still use appropriate measures to prevent unauthorised access to data in transit and at rest, and you should back up your data in case it is lost by the primary storage system.

The following pages describe how EscoDB uses cryptography in the data it stores, including why certain choices have been made.

Security goals

As an end-to-end encryption system, EscoDB performs all cryptographic operations in the client, and trusts the storage backend only to be able to return data that was previously written to it. It assumes that an attacker may have access to the storage server or the communication channel between the client and server, and aims to enforce these security goals under that assumption:

The contents of a store may only be read and modified by somebody in possession of the correct store password. It is assumed that the password is only distributed to intended authorised users; knowledge of the password conveys access to the store. In particular the password is never given to the storage adapter and so cannot be transmitted to the storage server.
An attacker is any person attempting to interact with the store without knowing the store password. We assume an attacker may be able to access the files on the storage server or in transit.
An attacker must not be able to recover any of the store’s encrypted content, which includes the root encryption and authentication keys in the config file, the shard keys in each shard file, or individual data items.
An attacker must not be able to learn the ID or path of any data item, nor reveal the directory structure of such paths.
An attacker may be able to tell roughly how many items are stored, along with the approximate byte length of each item.
Any attempt by an attacker to deface or tamper with the store’s content must be detectable by a legitimate user. Such tampering may include:
- alteration of a specific ciphertext
- substitution of an encrypted item for any subset of it
- moving of a ciphertext to a different logical location
- addition or removal of an encrypted item such as a shard key or document
- reordering of keys or documents
- changing any unencrypted stored value in a manner that undermines these goals
An attacker must not be able to cause the client to encrypt and store any material, nor to authenticate any material, under a key selected by the attacker.

Algorithms used

EscoDB makes use of the following cryptographic primitives and constructions:

AES-256-GCM
SHA-256
HMAC
PBKDF2

The implementation of all these algorithms is provided by the host platform; on Node.js we use the crypto module and in the browser we use the Subtle Crypto API.

Keys, initialisation vectors (IVs), salts, and other random values are produced in one of two ways. If the platform provides a dedicated generateKey() function for the relevant algorithm, then that function is used. Otherwise, the crypto.randomBytes() or crypto.getRandomValues() function is used.

Where buffers need to be compared for equality, a timing-safe comparison function provided by the host platform is used.

Building blocks

Throughout this documentation we will refer to a few common constructions that are used repeatedly in EscoDB’s design. This page lists all such constructions and provides a detailed description of their operation.

Canonical encoding

In a number of places, EscoDB needs to authenticate a collection of values, either as the additional data for authenticated encryption, or as plaintext that is authenticated using a MAC. Such collections are encoded in a particular way to make them resistant to canonicalisation attacks, and we refer to this as canonical encoding. It is based on the PAE encoding scheme in PASETO.

For example, when a stored item is encrypted, it is bound to the file it is stored in, the scope items, the item’s path (e.g. /doc) and the ID of the key used to encrypt it. This context is represented by the structure:

{ file: 'shard-0000-ffff', scope: 'items', path: '/doc', key: 1 }

To encode this value into a single buffer that can be passed to cryptographic algorithms, the following steps are followed:

Sort the key-value pairs in the context by their key
Flatten the pairs into a single array of the form [key1, value1, key2, value2, ...]
Convert each item in the array to a buffer; strings are converted to their UTF-8 encoding, and numbers are converted to big-endian unsigned 64-bit integers (u64)
Write the length of this array as a u64
For each item in the array, write its length as a u64, followed by the bytes of the item itself

For the example context above, sorting and converting to an array gives the following:

['file', 'shard-0000-ffff', 'key', 1, 'path', '/doc', 'scope', 'items']

Encoding this into buffers gives the following output:

00 00 00 00 00 00 00 08  00 00 00 00 00 00 00 04  |................|
66 69 6c 65 00 00 00 00  00 00 00 0f 73 68 61 72  |file........shar|
64 2d 30 30 30 30 2d 66  66 66 66 00 00 00 00 00  |d-0000-ffff.....|
00 00 03 6b 65 79 00 00  00 00 00 00 00 08 00 00  |...key..........|
00 00 00 00 00 01 00 00  00 00 00 00 00 04 70 61  |..............pa|
74 68 00 00 00 00 00 00  00 04 2f 64 6f 63 00 00  |th......../doc..|
00 00 00 00 00 05 73 63  6f 70 65 00 00 00 00 00  |......scope.....|
00 00 05 69 74 65 6d 73                           |...items|

Encryption

Whenever we talk about a value being encrypted, we mean that the following steps are taken:

The inputs are:
- Some 256-bit encryption key
- A plaintext, usually a JSON string or another key
- A binding context, a collection of key-value pairs that represent the identity of the encrypted value and the location where it is stored
Generate a random 96-bit initialisation vector (IV)
Compute the additional authenticated data (AAD) as the canonical encoding of the binding context
Apply AES-256-GCM to the key, the IV, the plaintext, and the AAD to produce a ciphertext and a 128-bit authentication tag
Return the concatenation of the IV, ciphertext and authentication tag

Decryption will fail unless the same binding context is provided to the decryption algorithm. This lets us prevent tampering of the ciphertext itself, as well as checking the ciphertext has not been moved between files or to a different location in the same file.

IV construction

We use random IVs with AES-GCM because the operation of EscoDB means that a deterministic IV construction would be highly likely to produce IV collisions. EscoDB has no central server, and lets any number of clients access the storage concurrently. If the IV was driven by, say, a counter in the stored files, it is very likely that two clients concurrently updating the same file would read the same counter value and therefore use the same IV for their next encryption.

Even though one of these clients would have their write rejected by the storage layer’s concurrency control, they would still both send their ciphertexts with identical IVs over the communication channel between the client and the storage media, and this would create an opportunity for anybody observing said channel to break the encryption.

Since IV reuse completely breaks the security of AES-GCM, a deterministic IV construction is not viable without some co-ordination between clients. We therefore use random IVs and ensure that key usage limits are not exceeded.

Usage limits

The security of AES-GCM relies on the IV being unique for each encryption under the same key. If an IV is ever repeated, this can allow an attacker to recover plaintext, and to forge their own ciphertexts with apparently valid authentication tags. To ensure the collision probability remains below 2^-32 for a random 96-bit IV, each key must be used for no more than 2³² encryptions.

Additionally, it is important that the key stream generated by AES-GCM be indistinguishable from random data. The block counter in GCM is a 32-bit value, so as long as the IV is different for each encryption, and each plaintext does not exceed 2³² blocks (64 GiB) in length, then every block of input to the AES cipher under the same key will be unique. The AES block cipher is a pseudo-random permutation (PRP), rather than a pseudo-random function (PRF), so that means every output from the block cipher under the same key will also be unique.

Once a certain number of blocks have been encrypted under the same key, the fact that the output of the AES block cipher never repeats can be used to distinguish it from random data. With a block size of 128 bits, to keep the distinguishing advantage below 2^-32 each key must be used for no more than 2⁴⁸ total blocks of input (4 PiB, or 1 MiB per message on average). On top of the plaintext blocks, AES-GCM consumes one additional block to encrypt the authentication tag, and this counts towards the usage limit.

For additional safety with multiple clients operating independently, EscoDB lowers these limits to 2³¹ encryptions and 2⁴⁷ total blocks encrypted under each key, i.e. we reduce each limit by one-half. This provides a safety margin so that if a key has almost reached its usage limit, two concurrent clients can safely use it a few more times without exceeding the “true” limit.

The config file

Every EscoDB store contains a file named config that is populated when the store is first created. This file contains the keys necessary for various operations, all of which are encrypted under the user’s password. Any binary values such as keys and salts are encoded using base64. A normal config file looks like this:

{
  "version": 1,
  "password": {
    "salt": "nCAFvP5M5bZlLRWdc9M+3QnLkX9+uKtovGA7GVk6foU=",
    "iterations": 600000
  },
  "cipher": {
    "key": "bym4sON3aF8GXpLzqZqxEmHll1G5e5r0zCN7kqdsnYCT+lHpC30sgFJ5D5FNTigb6BS9aZe5EHIDt7M1"
  },
  "auth": {
    "key": "0mB/FwRdeYF+qhHumLlhlXQVo46hCWRwTOsz2F8FZnvUu8e89rjVBSpX8bHKQjXJG54LP/9d5UlAjeOFCkOfR41ulKeGxpZyzm2PorywRy35ZI0hagU7EgEbKUo="
  },
  "shards": {
    "key": "LPDgFUUovpp7c7kJTO8DJymUq21ugDEovrQTXcibUHQ1SzuFw4PmxSqhMaUukA3PxX7wgaDYSMfyBQbMhvo3nlMGOA0kd2rjtn+QxKGEyA3VOfB9edBTd7gKIsA=",
    "n": 4
  }
}

The meaning of the fields is as follows:

version: A value that tracks the schema version of the config file, currently the only valid value is 1.
password: Contains the 256-bit salt and iteration count that are used with PBKDF2-HMAC-SHA-256 to turn the password into the User Key; this key is then used to encrypt all the other keys in the config file.
cipher: Contains the 256-bit Root Key which is used to encrypt the Shard Keys that are used inside each storage file. This key is encrypted under the User Key, with the binding context { file: 'config', scope: 'keys.cipher' }.
auth: Contains the 512-bit Auth Key that is used with HMAC-SHA-256 to authenticate unencrypted metadata stored inside the storage files. This key is encrypted under the User Key, with the binding context { file: 'config', scope: 'keys.auth' }.
shards: Contains the number of shard files that the storage is divided into, and the 512-bit Routing Key that is used with HMAC-SHA-256 to hash item paths to determine which shard file they are stored in. This usage of HMAC is not really security-critical, it serves as a convenient pseudo-random function for distributing items across shards in a manner that is randomised between different stores. The Routing Key is also encrypted under the User Key, with the binding context { file: 'config', scope: 'keys.router' }.

All keys and salts contained in the config are independent random values. The User Key (derived from the user’s password) is only used to encrypt the keys in this file, when the store is first created.

Shard files

Items stored in EscoDB live in shard files. Each item is assigned to a shard by signing its path using HMAC-SHA-256 with the Routing Key. The first two bytes of the hash are used to determine which shard the item resides in. If the config file has shards.n set to 4, then there will be four shard files with names shard-0000-3fff, shard-4000-7fff, and so on.

The shard header

The first line of each shard file contains a JSON header that looks something like this:

{
  "version": 1,
  "tag": "XmpfJjKen/k=",
  "cipher": {
    "keys": [
      "AAAAASwT71X33d2HO8kgkb0eGq6qWzi0LZ+Pap7BavPafsL9oKIvD0/xXnkmcDKixEKdVQVSHoZQ4JwOLF7Up1UU",
      "AAAAAiFQ2Ua4RI97avOsaBfu6zSOdB7/Xk+PokDULYtQ/Tnmm9iaHIdeDYYqPai8Fa1IdBUYREbHSfDIYTvOclij",
      "AAAAAwF0vhvn5BaVM85sf+3QteUwP6hQc+JY9frsXO3XiVVMy0x8gdUEg0ujUlW1orLDD1KPteFHHx6U8ExkbaTG"
    ],
    "state": "AAAAAIAAAAAAAAABRxcqXwAAAACAAAAAAAAAAUcW8sMAAAAAFXlWnwAAAAA239Ma",
    "mac": "kvAtihYSiF0uD/kaTvI+feZQcfkWXRZ6J4pzjY1gtB4="
  }
}

version specifies the schema version of the file, including this header. tag is a random 64-bit value that is updated each time the file is written. This ensures that storage backends that use a content hash as the file’s “revision” will report the file as changed even if none of its items were actually modified. This is important for enforcing EscoDB’s consistency properties.

The cipher section contains the following elements:

keys: A list of base64-encoded Shard Keys, each containing the following elements:
- A 32-bit sequential integer key ID. This uniquely identifies the key and is unencrypted.
- A 16-bit integer specifying the encryption algorithm the key belongs to. Currently AES-256-GCM is the only supported algorithm.
- A 256-bit encryption key.
The algorithm ID and the key itself are encrypted under the Root Key with the binding context { file, scope: 'keys', key } where file is the name of the shard file (e.g. shard-8000-bfff) and key is the key ID. This makes sure that key material genuinely corresponds to the unencrypted key ID, and the ID has not been tampered.
state: A base64-encoded buffer containing several 64-bit counters. Each Shard Key has two counters in this buffer, one for the number of plaintexts it has encrypted, and one for the total number of blocks. These are updated whenever a value inside the shard is encrypted just before being written to storage. When either counter reaches a configured usage limit, a new Shard Key is generated with the next sequential key ID, and it is added to the keys list.
mac: The HMAC-SHA-256 signature of the key IDs and usage counters. This is computed as follows:
- Let keys be the concatenation of all the Shard Key IDs in the order they appear in the header. For example if there are three keys in the header, this would be the buffer <00 00 00 01 00 00 00 02 00 00 00 03>.
- Let state be the base64-decoded state buffer.
- Let context be { file, scope: 'keys', keys, state } where file is the name of the shard file.
- Then mac is the HMAC-SHA-256 signature of the canonical encoding of context using the Auth Key.

The signature ensures the integrity of those parts of the header that are stored in plaintext. It makes sure the key IDs have not been modified and that no keys have been added or removed, and it makes sure the counter state is genuine. This is critical for the safe usage of the AES-GCM cipher.

Key rotation rationale

Although we do not expect that in normal usage any shard would ever receive more than 2³² item updates, benchmarks indicate it is physically possible to hit this limit in a matter of hours by spamming a store with document updates. This could potentially be exploited by an attacker to force the victim’s store to reuse an IV and thereby break its encryption, and so we implement key rotation to defend against this.

The Root Key is only used to encrypt newly generated Shard Keys, and so would need to be rotated if more than 2³² Shard Keys were created. If we make a generous assumption about performance and assume that one can use up a Shard Key in one hour, it would take around 490,000 years to run through 2³² of them. Therefore usage-based key rotation is currently not implemented on the Root Key, as this also might complicate the future implementation of multi-user store access.

HMAC signatures are secure as long as there is negligible chance of a collision on the hash output. With a 256-bit hash, keeping the collision probability to less than 2^-32 allows a maximum of 2¹¹² signatures under the same key. This is equivalent to updating a shard file ten million times per nanosecond for the lifetime of the known universe, so we also do not implement usage-based rotation of the Auth Key.

The key IDs and counter state are not encrypted because it would be impossible or impractical to do so. The key IDs are used to identify which Shard Key was used to encrypt each stored item, which would not work if the IDs were themselves encrypted under that Shard Key. We could encrypt them under the Root Key, but that would mean that the Root Key would be used every time a new item was encrypted, and would therefore be used up at the same rate as Shard Keys. Therefore we would have to implement rotation of the Root Key which simply moves the problem to somewhere else.

Encrypting the counter state would add complexity. We cannot encrypt them under the Root Key for the reason just given, and encrypting them under a Shard Key would mean that the act of encrypting them would also change their state and possibly require minting a fresh key. This is not impossible to work around but would add unwarranted complexity. We don’t regard the information about how many items have been encrypted as secret, as it can be estimated by anyone with read access to the file, even if they cannot decrypt any of its content.

Concurrency control

EscoDB’s consistency model is based around multiple clients interacting concurrently with an object store implementing compare-and-swap. Reading a file from storage returns a { data, revision } pair, where revision may be a sequential version number, a content hash, or anything else that uniquely identifies the current version of the file. Writing to storage only succeeds if the client supplies a revision value matching the current stored version of the file.

Under this model, if two clients want to update the same item, they will both read the same shard file from storage and receive the file’s current content and revision. They will each update their copy of the shard in memory, encrypting the item’s new content under the latest Shard Key. But when writing their updated shard back to storage, only one of these writes will be accepted, and the other will be rejected, as the first accepted write updated the stored file’s revision.

Client: Alice                      Storage                       Client: Bob
      |                               |                               |
      |            read()             |                               |
      | ----------------------------> |                               |
      | <---------------------------- |                               |
      |      { data: D, rev: X }      |                               |
      |                               |            read()             |
      |                               | <---------------------------- |
      |                               | ----------------------------> |
      |                               |      { data: D, rev: X }      |
      |     write(data: A, rev: X)    |                               |
      | ----------------------------> |                               |
      | <---------------------------- |                               |
      |         { ok, rev: Y }        |                               |
      |                               |     write(data: B, rev: X)    |
      |                               | <---------------------------- |
      |                               | ----------------------------> |
      |                               |             error             |

When this happens, the client whose write was rejected will reload the shard from storage and attempt to re-apply its desired changes atop the updated state.

Client: Alice                      Storage                       Client: Bob
      |                               |                               |
      |                               |            read()             |
      |                               | <---------------------------- |
      |                               | ----------------------------> |
      |                               |      { data: A, rev: Y }      |
      |                               |                               |
      |                               |                               |
      |                               |     write(data: C, rev: Y)    |
      |                               | <---------------------------- |
      |                               | ----------------------------> |
      |                               |         { ok: rev: Z }        |

Although Bob had his write rejected, we still count the encryptions that were done in that write even though they were never persisted. If a ciphertext is sent over the channel between the client and storage, it may be observed by an attacker and should still count towards the key’s usage limit. Therefore, when Bob reloads the shard from storage and re-applies his changes on top of the new state, he also merges the state of his key counters with the ones retrieved from storage.

For example, imagine the shard in storage currently has a key that has been used to encrypt 10 items. When Alice and Bob participate in this race to update the shard, the following happens:

Alice reads the shard from storage at revision X and observes its key usage counter has value 10.
Bob reads the shard from storage, also at revision X, and also sees the counter value of 10.
Alice updates two items and encrypts them both before the shard is written back to storage. She updates the counter to 12 to reflect this.
Bob updates three items and attempts to write the shard back. But since his revision is now stale, the write is rejected.
Bob reloads the shard from storage at revision Y and sees the key counter set to 12. He re-applies his increment of 3 from the failed write, bringing the value up to 15.
Bob re-applies his changes to the three items and increases the counter value to 18.
Bob writes his copy of the shard back to storage, this time successfully.

These steps are illustrated in the following sequence diagram.

Client: Alice                      Storage                       Client: Bob
      |                               |                               |
      |            read()             |                               |
      | ----------------------------> |                               |
      | <---------------------------- |                               |
      |     { rev: X, count: 10 }     |                               |
      |                               |            read()             |
      |                               | <---------------------------- |
      |                               | ----------------------------> |
      |                               |     { rev: X, count: 10 }     |
      |    write(rev: X, count: 12)   |                               |
      | ----------------------------> |                               |
      | <---------------------------- |                               |
      |         { ok, rev: Y }        |                               |
      |                               |    write(rev: X, count: 13)   |
      |                               | <---------------------------- |
      |                               | ----------------------------> |
      |                               |             error             |
      |                               |                               |
      |                               |                               |
      |                               |            read()             |
      |                               | <---------------------------- |
      |                               | ----------------------------> |
      |                               |     { rev: Y, count: 12 }     |
      |                               |                               |
      |                               |                               |
      |                               |    write(rev: Y, count: 18)   |
      |                               | <---------------------------- |
      |                               | ----------------------------> |
      |                               |         { ok: rev: Z }        |

This mechanism makes sure that encryptions done when clients are concurrently updating the same shard are recorded in the usage count. If a client’s write is rejected by the storage for any other reason, for example due to an authorisation error, their changes to the counter cannot be persisted.

Index and items

Following the header, the rest of the lines in a shard file are the index and the items. This data will typically look something like this:

AAAAAUYncFOOgsluuk0fI2JJWmLY2GASZCrHNTNJXPAk2/fv2NhGBUl6LS6+Yj60LdwNgpHlWAYkI2HfPo0=
AAAAAXPs+6XpqmWnCUHsgVFm49ZYrC5zdMBxQ6YXdORhpDVZi8RRIIUzdJC5uFx0aG5xi22skw==
AAAAAWaeds4hrRQ36HvOxu0ZvtnIkUcrmkZRnp7r6PDXTs09woIu1tZXNzulusggks7pYY+giXwBrft7o1ycg9UJb7Q=
AAAAAYsnsxumiH44cNLL6/I98cQS5+yzpNU0EFEN7ZoQ6a8luwBFHiN2K8lQlygqZWZGVtQViTTcbuuCwlVV
AAAAAfFchyrM1DHQ+0YFR2qA2X4CK88tiClaTM+Uk7TPcTf6Ui/VhEo+RBkUM43xdxr9TF1gK4hJBbN/u8I6SQ==

Each line consists of a base64-encoded buffer containing an unencrypted 32-bit key ID and the encrypted content of the item. The key ID identifies which of the keys in the header cipher.keys list the item is encrypted with.

The index is a sorted list of the paths of all the items in the shard. It exists so that EscoDB can locate an item by its path without having to decrypt all the items themselves. It is encrypted with the binding context { file, scope: 'index', key } where file is the name of the shard file and key is the key ID at the start of the line.

The items are the documents added to the store via calls to store.update(), and the directory indexes that list the names of all items that appear in each directory. Each one is encrypted with the binding context { file, scope: 'items', path, key } where path is the item’s path and key is the ID of the encryption key.

The binding of items prevents confused deputy attacks wherein an attacker cannot decrypt any content, but can swap the order of ciphertexts in the file or move ciphertexts between files. For example, if EscoDB is used as the backend for a password manager, this would allow an attacker to swap the victim’s passwords for two different services, and thereby trick them into disclosing their email password to a different website. Including the item’s path in the binding context ensures that the item only decrypts if it is genuinely the document for the requested path.

The index is decrypted every time the shard is loaded from storage, while specific items are only decrypted when a client accesses them via a get(), list() or find() call. The index and items are freshly encrypted just before the shard is written back to storage, if their value has been changed.

Keyboard shortcuts

EscoDB documentation