Relationship Integrity

[jzelinskie]

Problem Statement

SpiceDB does not support a threat-model where the storage for the datastore is untrusted.
Today it is not possible to determine if relationships came from the SpiceDB API or were modified by a human with Datastore access. This is perfectly valid for those that fully trust the vendor providing services powering their SpiceDB Datastore. However, there are users that require additional integrity guarantees: proof that there has not been tampering with any data being consumed by SpiceDB.

For example, a customer support engineer for any one of the possible service providers for SpiceDB datastores could inadvertently modify data in the underlying storage causing changes to access being granted/revoked and downstream consumers of the Watch API from being inconsistency.

Solution Brainstorm

Overview

Relationship Integrity is to be provided by including MAC checking into the SpiceDB datastore itself. When enabled, reading any relationship from the datastore will require checking the validity of a MAC of the relationship. If a relationship fails verification, an error is returned failing the entire request.

Implementation

SpiceDB supports a pattern for implementing supersets of behavior for Datastore implementations by performing interface assertions. Today this is used to implement extensions to the Datastore interface for datastores that require running background processes or repairing any internal values after a major event such as failover or migration.

In order to progressively add Relationship Integrity support to the various datastores, it makes sense to introduce this feature as an extension. Datastores can optionally implement the interface to support the behavior; our first choice is CockroachDB as this vendor is not yet as ubiquitously trusted as cloud providers offering services for our other datastore implementations.

Logic for enforcing MAC checks will be implemented as a Datastore proxy. Today, Datastore proxies are used in order to implement common behavior to all Datastores including collecting metrics, enforcing read-only access, hedging datastore access, and deduplicating datastore access.

MACs are to be stored alongside relationships; for datastores powered by relational databases, this implementation should be an additional column added to table storing relationships. Keys are provided similarly to any other secret in SpiceDB -- via the environment/flag system. AuthZed's managed products will manage keys using cloud providers' KMS services with the option to have this key be owned by customers.

MACs will use the best practices in HMAC cryptography such as using the SHA256-HMAC algorithm and canonicalizing input. Canonicalization of the relationship along with its revision will put this data into a format that is reproducible and cannot suffer injections (e.g. overflowing relationship data into the revision field). A constant time comparison, provided by the Go standard library, will be performed to validate MACs on read. MACs themselves can be truncated for storage efficiency while still maintaining guarantees against collisions. Buffers used to compute MACs can be reset and reused in a pool in order to eliminate heap allocations that would increase any garbage collection pressure.

A Proof of Concept sketched out in the Go Playground of the MAC verification flow can be found here: https://go.dev/play/p/6KajspiVzlh

Key rotation is an uncommon, but necessary action that must be accounted for. In order to accommodate transitions between keys, SpiceDB should be configurable with multiple keys at a given time. If a MAC verifies with any of these keys, then the relationship is considered valid. Some users will be fine running in this state indefinitely and others can use this state only while asynchronously replacing existing relationships' MACs with MACs using the newest key.

Alternatives

After reviewing proposals for enhancements to auditing functionality that could notify upon detection of tampering, it was determined that users interested in this behavior prefer a fail-closed solution rather than the fail-open approach that retroactive notification would provide. Improving auditability of operations performed against production systems is an orthogonal feature that will be developed on a different timeline and considered out of scope for the rest of this document.