Skip to content
Tenura docs

Recipe 25: Encrypted Key-Value Store With Automatic Key Retirement

Situation

You need encrypted storage where encryption keys have bounded lifetimes. When a key epoch expires, data encrypted under that epoch becomes permanently unreadable — not by policy, but by cryptographic enforcement. Traditional KMS systems require manual key rotation schedules and hope that operators remember to follow them.

The lease model gives you a mechanical guarantee: each key epoch is backed by a lease with a TTL. When the TTL expires, the key material is zeroed. No rotation schedule to configure. No “remember to revoke” checklist. The key is gone because the lease is gone.

What You Build

An encrypted key-value store where:

  • KeyEpochManager manages key epochs, each backed by a lease TTL
  • EncryptedBlobStore encrypts data under the active epoch’s key
  • FabricKvStore provides the outer index (key name -> blob ID)
  • Rotation creates a new epoch; the old epoch enters Rotating status (both keys usable during overlap)
  • When the old epoch’s lease expires, EncryptedBlobStore::get() for old-epoch blobs fails closed
  • RenewalManager drives TTL-based renewal of the active epoch’s backing lease

Building Blocks

  • grafos_securestore::{KeyEpochManager, EncryptedBlobStore, EpochStatus, EpochId, BlobId} — source
  • grafos_securestore::MockCryptoBackend — XOR-based test backend (NOT secure; use AesGcmBackend in production) — source
  • grafos_kv::{KvBuilder, FabricKvStore} — source
  • grafos_leasekit::{RenewalManager, RenewalPolicy} — source

Design

Epoch Lifecycle

Each key epoch progresses through three states:

  1. Active — new writes encrypt under this epoch’s key
  2. Rotating — a newer epoch is active; this key is still available for decryption but not used for new writes
  3. Expired — key material has been zeroed via zeroize; decryption is impossible

create_epoch(now, ttl_secs) generates a fresh key, records a MemRegionLocator for the key material, and transitions any previously active epoch to Rotating. expire_old(now) checks expires_at and zeroes expired keys.

Two-Layer Architecture

The outer layer is a FabricKvStore that maps application-level keys (e.g., b"user:42:ssn") to BlobId values. The inner layer is an EncryptedBlobStore that maps BlobId to ciphertext + epoch metadata.

This separation means the KV index survives key rotation. Only the blob store needs to know about epochs.

Renewal and Expiry

RenewalManager tracks the active epoch’s TTL. Calling tick(now) at regular intervals renews the lease while the application intends the key to remain usable. Stopping renewal causes the epoch to expire on schedule. RenewalSummary.near_expiry provides early warning.

Walkthrough (Implementation Sketch)

1. Initialize the Encrypted Store

use grafos_securestore::{KeyEpochManager, EncryptedBlobStore, MockCryptoBackend, BlobId};
use grafos_kv::{KvBuilder, FabricKvStore};
use grafos_leasekit::{RenewalManager, RenewalPolicy};


// Create the key epoch manager with a crypto backend
let mut key_mgr = KeyEpochManager::new(Box::new(MockCryptoBackend::new()));


// Create the first epoch with a 1-hour TTL
let now = 1_000_000u64;
let epoch_id = key_mgr.create_epoch(now, 3600)?;


// Wrap in an encrypted blob store
let mut blob_store = EncryptedBlobStore::new(key_mgr);


// Create the outer KV index
let mut kv: FabricKvStore = KvBuilder::new()
    .hot_buckets(64)
    .default_ttl_secs(7200) // index lives longer than keys
    .build()?;

2. Store Encrypted Data

// Encrypt and store a secret
let blob_id = BlobId(1);
let blob_info = blob_store.put(blob_id, b"SSN: 123-45-6789")?;


// Record the blob ID in the KV index
kv.put_struct(b"user:42:ssn", &blob_id)?;

3. Retrieve While Key Is Active

// Look up the blob ID from the KV index
let blob_id: BlobId = kv.get_struct(b"user:42:ssn")?.unwrap();


// Decrypt — succeeds because the epoch is still Active
let plaintext = blob_store.get(&blob_info)?;
assert_eq!(plaintext, b"SSN: 123-45-6789");

4. Rotate Keys

// Rotate: creates a new Active epoch, old becomes Rotating
let new_epoch = blob_store.key_manager_mut().rotate(now + 1800, 3600)?;


// New writes encrypt under the new epoch
let blob_id_2 = BlobId(2);
let blob_info_2 = blob_store.put(blob_id_2, b"SSN: 987-65-4321")?;
kv.put_struct(b"user:99:ssn", &blob_id_2)?;


// Old data is still readable (old epoch is Rotating, not Expired)
let old_plaintext = blob_store.get(&blob_info)?;
assert_eq!(old_plaintext, b"SSN: 123-45-6789");

5. Old Epoch Expires — Fail Closed

// Time passes beyond the old epoch's TTL
let later = now + 4000; // past the original 3600s TTL
blob_store.key_manager_mut().expire_old(later);


// Old data is now permanently unreadable
let result = blob_store.get(&blob_info);
assert!(result.is_err()); // EpochExpired — key material zeroed


// New data is still readable (new epoch is still Active)
let new_plaintext = blob_store.get(&blob_info_2)?;
assert_eq!(new_plaintext, b"SSN: 987-65-4321");

6. Drive Renewal for the Active Epoch

let mut renewals = RenewalManager::new();
let policy = RenewalPolicy::default().with_threshold(0.3);
renewals.register(new_epoch.0, now + 1800 + 3600, policy);


// Periodic tick keeps the active epoch alive
let summary = renewals.tick(now + 3000);
if !summary.near_expiry.is_empty() {
    // Warn: active key epoch is close to expiry
}

Failure Modes

  • Active epoch expires unexpectedly: all new writes fail with NoActiveEpoch. All existing data under that epoch becomes permanently unreadable. This is the correct fail-closed behavior — create a new epoch to resume writes.
  • Rotation during write burst: brief window where old and new epochs are both usable. Reads work for both. No data loss during the overlap window.
  • Process crash before rotation completes: data under the old epoch is still decryptable until its TTL expires. No partial state — each epoch is independent.
  • KV index outlives all epochs: blob IDs in the index point to blobs whose keys are expired. Reads return EpochExpired. The index entry is harmless metadata; the secret is cryptographically dead.

Observability

  • Epoch creation/rotation/expiry events (from KeyEpochManager)
  • Active epoch TTL remaining (from RenewalManager)
  • Decrypt failures due to expired epochs (count these — a spike means rotation policy is too aggressive)
  • KV index size vs. active blob count (divergence indicates stale index entries)

Variations

  • Rewrap on rotation: when a new epoch is created, iterate all blobs encrypted under the old epoch, decrypt with old key, re-encrypt with new key. This prevents data loss at the cost of a migration window.
  • Multi-tenant isolation: separate KeyEpochManager per tenant, each with independent rotation cadence.
  • Compliance retention: keep ciphertext in block storage after epoch expiry for audit trails. The data is cryptographically inert but proves what was stored and when.
  • Hardware-backed crypto: replace MockCryptoBackend with AesGcmBackend (feature crypto-aes-gcm) for real AES-256-GCM encryption.