Envelope encryption and data at rest

// Envelope encryption with Web Crypto: a fresh data key (DEK) for every record, wrapped with AES-GCM by a key-encryption
// key (KEK) that this code can use but not read. The record is bound to its row, the KEK is rotated by re-wrapping the
// DEKs, the AES key wrap of RFC 3394 is checked against its published vector, and a KEK is "destroyed". The KEK bytes
// are lab values; in production they live in a KMS or an HSM. Everything printed is true on every run, whatever the
// random keys and nonces.
const subtle = crypto.subtle;
const utf8 = new TextEncoder();
const hex = (buf) => Buffer.from(buf).toString('hex');
const same = (a, b) => Buffer.from(a).equals(Buffer.from(b));
const frame = (...parts) => Buffer.concat(parts.flatMap((p) => [Buffer.from([0, utf8.encode(p).length]), utf8.encode(p)]));

// A KEK is an AES-GCM key that is not extractable: this code can wrap and unwrap with it, and cannot export it.
const importKek = (bytes) => subtle.importKey('raw', bytes, 'AES-GCM', false, ['wrapKey', 'unwrapKey']);
const keks = new Map([['kek-1', await importKek(Uint8Array.from({ length: 32 }, (_, i) => i))]]);

// The data is bound to its row (table, column, id). The wrapped DEK is bound to the same row and to the KEK that wrapped
// it. The KEK's id is not in the data's associated data, so a rotation never has to touch the data.
const dataAad = (table, column, id) => frame('v1', 'data', table, column, id);
const wrapAad = (kekId, table, column, id) => frame('v1', 'wrap', kekId, table, column, id);

async function wrap(kekId, dek, table, column, id) {
  const iv = crypto.getRandomValues(new Uint8Array(12));
  const wrapped = await subtle.wrapKey('raw', dek, keks.get(kekId), { name: 'AES-GCM', iv, additionalData: wrapAad(kekId, table, column, id) });
  return { kekId, iv, wrapped };
}
async function unwrap(w, table, column, id, extractable) {
  return subtle.unwrapKey('raw', w.wrapped, keks.get(w.kekId), { name: 'AES-GCM', iv: w.iv, additionalData: wrapAad(w.kekId, table, column, id) }, { name: 'AES-GCM' }, extractable, ['encrypt', 'decrypt']);
}

async function seal(kekId, table, column, id, text) {
  const dek = await subtle.generateKey({ name: 'AES-GCM', length: 256 }, true, ['encrypt', 'decrypt']);
  const nonce = crypto.getRandomValues(new Uint8Array(12));
  const data = await subtle.encrypt({ name: 'AES-GCM', iv: nonce, additionalData: dataAad(table, column, id) }, dek, utf8.encode(text));
  return { w: await wrap(kekId, dek, table, column, id), nonce, data };
}
async function open(rec, table, column, id) {
  try {
    const dek = await unwrap(rec.w, table, column, id, false);
    return new TextDecoder().decode(await subtle.decrypt({ name: 'AES-GCM', iv: rec.nonce, additionalData: dataAad(table, column, id) }, dek, rec.data));
  } catch {
    return null;
  }
}

const phones = ['98450 11122', '99001 23456', '90350 77889'];
const rows = await Promise.all(phones.map((p, i) => seal('kek-1', 'customers', 'phone', String(4200 + i), p)));
const opened = await Promise.all(rows.map((r, i) => open(r, 'customers', 'phone', String(4200 + i))));
console.log(`3 records, a fresh DEK each, all open: ${opened.every((t, i) => t === phones[i])}`);
console.log(`sizes: wrapped DEK ${rows[0].w.wrapped.byteLength} bytes (32 key + 16 tag) and a ${rows[0].w.iv.length}-byte nonce, data ${rows[0].data.byteLength} bytes (${utf8.encode(phones[0]).length} + 16 tag)`);
console.log(`record 4200 opened as row 4201: ${await open(rows[0], 'customers', 'phone', '4201')}, as column email: ${await open(rows[0], 'customers', 'email', '4200')}`);
try {
  await subtle.exportKey('raw', keks.get('kek-1'));
} catch (e) {
  console.log(`export the KEK: ${e.name}`);
}

// Rotation: unwrap each DEK with the old KEK and wrap it with the new one. The data and its nonce are not touched.
keks.set('kek-2', await importKek(Uint8Array.from({ length: 32 }, (_, i) => 255 - i)));
async function rewrap(rec, to, table, column, id) {
  const dek = await unwrap(rec.w, table, column, id, true);
  return { ...rec, w: await wrap(to, dek, table, column, id) };
}
const rotated = await Promise.all(rows.map((r, i) => rewrap(r, 'kek-2', 'customers', 'phone', String(4200 + i))));
const afterRotation = await Promise.all(rotated.map((r, i) => open(r, 'customers', 'phone', String(4200 + i))));
console.log(`\nrotation to kek-2: data bytes unchanged ${rotated.every((r, i) => same(r.data, rows[i].data))}, wrapped DEKs changed ${rotated.every((r, i) => !same(r.w.wrapped, rows[i].w.wrapped))}, all open under kek-2: ${afterRotation.every((t, i) => t === phones[i])}`);
const records = 10_000_000;
const size = 4096;
console.log(`10 million records of 4 KiB: re-encrypting touches ${((records * size) / 1e9).toFixed(1)} GB, re-wrapping touches ${((records * 60) / 1e6).toFixed(0)} MB of wrapped keys`);

// A KEK that leaked is a different case. Rotation changed the wrapping, not the DEKs: an old backup holds the old wrapped DEK,
// and with the leaked kek-1 it unwraps the very DEK that still protects today's data. Only fresh DEKs close that door.
const oldDek = await unwrap(rows[0].w, 'customers', 'phone', '4200', false);
const readWithOldDek = async (rec) => {
  try {
    return new TextDecoder().decode(await subtle.decrypt({ name: 'AES-GCM', iv: rec.nonce, additionalData: dataAad('customers', 'phone', '4200') }, oldDek, rec.data));
  } catch {
    return null;
  }
};
console.log(`after the rotation, the old wrapped DEK from a backup and the leaked kek-1 still read today's data: ${(await readWithOldDek(rotated[0])) === phones[0]}`);
const reencrypted = await seal('kek-2', 'customers', 'phone', '4200', phones[0]);
console.log(`after re-encrypting under a fresh DEK: ${(await readWithOldDek(reencrypted)) === phones[0]}, and the new record opens under kek-2: ${(await open(reencrypted, 'customers', 'phone', '4200')) === phones[0]}`);

// The AES key wrap of RFC 3394, section 4.1, which has no associated data and a fixed integrity value: 128-bit KEK, 128-bit key.
const rfcKek = await subtle.importKey('raw', Buffer.from('000102030405060708090A0B0C0D0E0F', 'hex'), 'AES-KW', false, ['wrapKey', 'unwrapKey']);
const rfcData = await subtle.importKey('raw', Buffer.from('00112233445566778899AABBCCDDEEFF', 'hex'), 'AES-GCM', true, ['encrypt']);
const rfcWrapped = hex(await subtle.wrapKey('raw', rfcData, rfcKek, 'AES-KW')).toUpperCase();
console.log(`\nRFC 3394 section 4.1: ${rfcWrapped.slice(0, 16)}…${rfcWrapped.slice(-8)}, ${rfcWrapped.length / 2} bytes for a 16-byte key, as published: ${rfcWrapped === '1FA68B0A8112B447AEF34BD8FB5A7B829D3E862371D2CFE5'}`);

// Destroying a KEK makes every DEK under it unusable, and so every record. A copy of the key store undoes that.
const backup = new Map(keks);
keks.delete('kek-2');
const afterDestroy = await Promise.all(rotated.map((r, i) => open(r, 'customers', 'phone', String(4200 + i)).catch(() => null)));
console.log(`\nkek-2 destroyed: ${afterDestroy.filter(Boolean).length} of 3 records open`);
keks.set('kek-2', backup.get('kek-2'));
const afterRestore = await Promise.all(rotated.map((r, i) => open(r, 'customers', 'phone', String(4200 + i))));
console.log(`the key store restored from a backup: ${afterRestore.filter(Boolean).length} of 3 records open again`);

// A lab record with fixed values, to open in the AES tool of this site: a key of the bytes 0 to 31, a nonce of twelve 0x0b
// bytes, and the row as associated data.
const labBytes = Uint8Array.from({ length: 32 }, (_, i) => i);
const labKey = await subtle.importKey('raw', labBytes, 'AES-GCM', false, ['encrypt']);
const labNonce = new Uint8Array(12).fill(0x0b);
const labAad = dataAad('customers', 'phone', '4200');
const labSealed = new Uint8Array(await subtle.encrypt({ name: 'AES-GCM', iv: labNonce, additionalData: labAad }, labKey, utf8.encode('98450 11122')));
console.log('\nlab record (AES-256-GCM, every value in hex):');
console.log(`  key        ${hex(labBytes)}`);
console.log(`  nonce      ${hex(labNonce)}`);
console.log(`  AAD        ${hex(labAad)}`);
console.log(`  ciphertext ${hex(labSealed.subarray(0, -16))}`);
console.log(`  tag        ${hex(labSealed.subarray(-16))}`);

3 records, a fresh DEK each, all open: true
sizes: wrapped DEK 48 bytes (32 key + 16 tag) and a 12-byte nonce, data 27 bytes (11 + 16 tag)
record 4200 opened as row 4201: null, as column email: null
export the KEK: InvalidAccessError

rotation to kek-2: data bytes unchanged true, wrapped DEKs changed true, all open under kek-2: true
10 million records of 4 KiB: re-encrypting touches 41.0 GB, re-wrapping touches 600 MB of wrapped keys
after the rotation, the old wrapped DEK from a backup and the leaked kek-1 still read today's data: true
after re-encrypting under a fresh DEK: false, and the new record opens under kek-2: true

RFC 3394 section 4.1: 1FA68B0A8112B447…71D2CFE5, 24 bytes for a 16-byte key, as published: true

kek-2 destroyed: 0 of 3 records open
the key store restored from a backup: 3 of 3 records open again

lab record (AES-256-GCM, every value in hex):
  key        000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
  nonce      0b0b0b0b0b0b0b0b0b0b0b0b
  AAD        000276310004646174610009637573746f6d657273000570686f6e65000434323030
  ciphertext 91b62694bf4cbc98eafb29
  tag        c555809b2764b937391069bee14681d6

"""Blind indexes for searching encrypted fields: an HMAC of the normalised value, under a key of its own for each column.
The program shows what a reader of the table learns from an index (the frequency table of the column), what shortening
the index costs in extra matches, and why the value is normalised first. The key and the 2,000 rows are lab values."""
import hmac
import random
import unicodedata
from collections import Counter

ROOT_KEY = bytes(range(32))  # a lab key; real keys live in a KMS and never in code


def column_key(column: str) -> bytes:
    """One key for each column: HKDF-Expand with a label, so the same text in two columns gives two indexes."""
    return hmac.digest(ROOT_KEY, b"blind-index v1 " + column.encode() + b"\x01", "sha256")


def normalise(value: str) -> str:
    return unicodedata.normalize("NFKC", value).strip().casefold()


def blind_index(column: str, value: str, bits: int = 256) -> str:
    """The first `bits` bits of HMAC-SHA-256(column key, normalised value), as hex."""
    tag = int.from_bytes(hmac.digest(column_key(column), normalise(value).encode(), "sha256"), "big")
    return f"{tag >> (256 - bits):0{(bits + 3) // 4}x}"


rng = random.Random(7)
STATES = ["Maharashtra", "Karnataka", "Tamil Nadu", "Delhi", "Gujarat", "Kerala", "Punjab", "Assam"]
WEIGHTS = [30, 22, 16, 12, 9, 6, 3, 2]
ROWS = [(f"user{n}.{rng.randrange(1000, 9999)}@example.com", rng.choices(STATES, WEIGHTS)[0]) for n in range(2000)]
EMAILS = [r[0] for r in ROWS]
STATE_COLUMN = [r[1] for r in ROWS]

# 1. Normalising before indexing, so that a search finds what was stored.
stored = blind_index("email", "priya.sharma@example.com")
typed = "  Priya.Sharma@Example.COM "
print(f"typed {typed!r}: matches the stored index after normalising: {blind_index('email', typed) == stored}")
raw = hmac.digest(column_key("email"), typed.encode(), "sha256").hex()
print(f"the same text hashed as typed, without normalising, matches: {raw == stored}")
print(f"the same text in the phone column gives another index: {blind_index('phone', 'priya.sharma@example.com') != stored}")

# 2. What the index column shows a reader of the table: the plaintext column's frequency table.
index_counts = Counter(blind_index("state", s) for s in STATE_COLUMN)
plain_counts = Counter(STATE_COLUMN)
print(f"\nstate column: {len(plain_counts)} different values, {len(index_counts)} different indexes")
print(f"the largest groups of the index hold {[c for _, c in index_counts.most_common(3)]} rows; of the plain column, {[c for _, c in plain_counts.most_common(3)]}")
print(f"email column: {len(set(blind_index('email', e) for e in EMAILS))} different indexes for {len(set(EMAILS))} different emails, every group has one row")

# 3. Shortening the index: fewer bits put more rows in each group, so a search returns extras that the application drops.
print("\nindex bits   rows a lookup returns (mean)   groups")
for bits in (256, 32, 16, 8):
    groups = Counter(blind_index("email", e, bits) for e in EMAILS)
    mean = sum(c * c for c in groups.values()) / len(EMAILS)
    print(f"{bits:>10}   {mean:>27.2f}   {len(groups):>6}")
for rows in (2_000, 10_000_000):
    print(f"at 16 bits, {rows:>10,} rows: about {1 + (rows - 1) / 2**16:.1f} rows come back for a lookup")

typed '  Priya.Sharma@Example.COM ': matches the stored index after normalising: True
the same text hashed as typed, without normalising, matches: False
the same text in the phone column gives another index: True

state column: 8 different values, 8 different indexes
the largest groups of the index hold [610, 429, 323] rows; of the plain column, [610, 429, 323]
email column: 2000 different indexes for 2000 different emails, every group has one row

index bits   rows a lookup returns (mean)   groups
       256                          1.00     2000
        32                          1.00     2000
        16                          1.03     1969
         8                          8.72      256
at 16 bits,      2,000 rows: about 1.0 rows come back for a lookup
at 16 bits, 10,000,000 rows: about 153.6 rows come back for a lookup

// One phone number kept three ways: encrypted with AES-256-GCM, masked, and replaced by a vault token. For each the
// program prints what survives, who can undo it, and what a copy of the application database alone shows. The key and the
// numbers are lab values; everything printed is true on every run, whatever the random bytes.
import { createCipheriv, createDecipheriv, randomBytes } from 'node:crypto';

const phone = '98450 11122';
const numbers = [phone, ...Array.from({ length: 999 }, (_, i) => `9${String(8000 + ((i * 7919) % 2000)).padStart(4, '0')} ${String(10000 + ((i * 104729) % 90000))}`)];

// Encryption: reversible with the key, different every time, and as long as the value.
const key = Buffer.alloc(32, 7);
function seal(text) {
  const nonce = randomBytes(12);
  const c = createCipheriv('aes-256-gcm', key, nonce);
  return Buffer.concat([nonce, c.update(text, 'utf8'), c.final(), c.getAuthTag()]);
}
function unseal(blob) {
  const d = createDecipheriv('aes-256-gcm', key, blob.subarray(0, 12));
  d.setAuthTag(blob.subarray(-16));
  return Buffer.concat([d.update(blob.subarray(12, -16)), d.final()]).toString('utf8');
}
const a = seal(phone);
const b = seal(phone);
console.log(`encryption: ${a.length} bytes for a ${phone.length}-character value, opens with the key: ${unseal(a) === phone}, two encryptions of the same value differ: ${!a.equals(b)}`);

// Masking: part of the value is thrown away for good. Many numbers share a mask.
const mask = (p) => p.replace(/\d(?=.*\d{2}$)/g, 'X');
const masks = new Map();
for (const n of numbers) masks.set(mask(n), (masks.get(mask(n)) ?? 0) + 1);
console.log(`masking: ${phone} becomes ${mask(phone)}, of which 2 of 10 digits survive; ${numbers.length} numbers made ${masks.size} masks, up to ${Math.max(...masks.values())} numbers share one`);

// Tokenisation: the value goes into a vault and a random token takes its place; the token has no relation to the value.
const vault = new Map();
const byValue = new Map();
function tokenise(value) {
  if (byValue.has(value)) return byValue.get(value);
  const token = randomBytes(8).toString('hex');
  vault.set(token, value);
  byValue.set(value, token);
  return token;
}
const t1 = tokenise(phone);
console.log(`tokenisation: ${phone} becomes a ${t1.length}-character random token, the vault gives the value back: ${vault.get(t1) === phone}, the same number gets the same token again: ${tokenise(phone) === t1}`);

console.log('\nwhat a copy of the application database shows, without the key or the vault:');
console.log(`  encryption  the length of each value, and nothing about equal values (every blob differs)`);
console.log(`  masking     the last 2 digits of every number, ${numbers.length} numbers in ${masks.size} groups`);
console.log(`  token       nothing about the number, but equal numbers have equal tokens (${new Set(numbers.map(tokenise)).size} tokens for ${new Set(numbers).size} numbers)`);

encryption: 39 bytes for a 11-character value, opens with the key: true, two encryptions of the same value differ: true
masking: 98450 11122 becomes XXXXX XXX22, of which 2 of 10 digits survive; 1000 numbers made 100 masks, up to 11 numbers share one
tokenisation: 98450 11122 becomes a 16-character random token, the vault gives the value back: true, the same number gets the same token again: true

what a copy of the application database shows, without the key or the vault:
  encryption  the length of each value, and nothing about equal values (every blob differs)
  masking     the last 2 digits of every number, 1000 numbers in 100 groups
  token       nothing about the number, but equal numbers have equal tokens (1000 tokens for 1000 numbers)