Shade/docs/archive/V3.12-DESIGN.md

V3.12 — Key Transparency: Designnotat

Status: Done — implementert i @shade/key-transparency 0.4.0, frosset i 4.0 GA. Forfatter: Shade-teamet Reviewer-mål: ekstern crypto-orientert reviewer før produksjons-deploy. Implementasjons-target: @shade/key-transparency + utvidelser i @shade/server, @shade/transport, @shade/sdk.

---

1. Mål og ikke-mål

Mål

Bytt ut "blind tillit til prekey-server" med en verifiserbar append-only log. Når en klient mottar et prekey-bundle skal den ha kryptografisk bevis for at:

1. Bundlen er commit'et i en tidstemplet log (Signed Tree Head).
2. Den eksakte (adresse, identityKey, signedPreKey)-mappingen står i den loggen — eller den står ikke (fravær-bevis).
3. Loggen har ikke skrevet om historie siden forrige fetch (konsistens-bevis).
4. Andre klienter ser samme log (split-view-deteksjon via witness-gossip).

Dette er CT-style transparens (RFC 6962-prinsipper) tilpasset prekey-distribusjon.

Ikke-mål (eksplisitt ut)

• Federert log mellom flere prekey-servere. Hver Shade-deployment har én log (eller ingen). Multi-server gossip er V3.13+.
• Løse MITM-på-første-kontakt fullstendig. KT fanger split-view og re-write, men ikke det at en angriper publiserer en forfalsket identitet ved første registrering. Det er V3.3 (fingerprint-gate)
  • V3.10 (social recovery).
• Legal/compliance audit-log. Loggen er kryptografisk, ikke juridisk.
• Klient-styrt sletting. Append-only — DELETE skriver tombstone-entry, fjerner ikke historikk.

Beslutningskriterium for implementasjon

Når dette notatet er godkjent og alle åpne spørsmål under §11 har konkrete svar (ikke bare "vi finner ut av det senere"), kan kode skrives. Det notatet ligger på når §11 lukkes er det vi bygger.

---

2. Trusselmodell-tillegg

Eksisterende THREAT-MODEL.md dekker prekey-server som "honest-but-curious"

• tilstede TOFU. KT utvider modellen til fully-malicious server:

Angrep	Pre-V3.12	Post-V3.12
Server returnerer feil bundle for én klient	Uoppdaget til OOB-verifisering	Klient kan be om proof; mismatch oppdages
Server bytter en allerede registrert identityKey	TOFU-fingerprint endres → V3.3-gate slår inn (men brukerinitiert)	Loggen vil vise to entries med samme adresse → witness oppdager
Server gir alice ulike identityKeys til Bob og Charlie (split-view)	Uoppdaget til OOB	Witness-gossip avslører to ulike STH-er
Server skriver om historikk for å skjule tidligere svik	Mulig	Konsistens-proof feiler → klient varsler
Server nekter å publisere ny STH	Mulig	"Stale STH"-detekteres av friskhetsbevis (max age)
Server kompromitterer signing-key for STH	KT-trygghet brutt	Witness gossip om gammel STH-kjede; rotasjon krever ny genesis

KT løser ikke:

• Førstegangs-impersonering av en helt ny adresse (intet historisk bevismateriale).
• Kollusjon mellom server og alle witnesses.
• Klient som glemmer cached STH og må re-bootstrappe.

---

3. Datastruktur-valg

Vi velger RFC 6962-stil append-only Merkle log + ekstern adresse-index med commitment-bevis. Begrunnelse:

Vurderte alternativer

1. Pure CT-log (RFC 6962): Simple append-only Merkle tree. Inklusjonsbevis trivielle. Fravær-bevis ikke støttet nativt (må scanne hele loggen).
2. CONIKS-tre (sparse Merkle tree over adresser): Native fravær-bevis, men mye mer kompleks (epoch-baserte snapshots, prefix-trees, placeholder-nodes). Overkill for første iterasjon.
3. Hybrid (RFC 6962 log + side-index): Loggen er sannhetskilde, indexen er en commitment-mapping address → leaf_index. Server beviser inklusjon via leaf-path, fravær via "denne adressen er ikke i indexen ved tree_size T" + signert STH.

Valg: alternativ 3. Det gir CT-stil enkelthet, samt fravær-bevis nesten gratis (commitment til indexen er en del av hver STH).

Konkret format

Leaf

Hver leaf representerer én registrering eller revoke:

leaf = SHA256(
  0x00 ||                        // leaf prefix (RFC 6962)
  uint64_be(timestamp_ms) ||
  byte(operation) ||             // 0x01 register, 0x02 replenish, 0x03 delete
  uint16_be(len(address)) || address_bytes ||
  uint16_be(len(bundle_hash)) || bundle_hash    // 32 bytes SHA-256 over canonical bundle
)

bundle_hash er deterministisk hash av:

canonical_bundle = SHA256(
  0x01 ||                        // bundle prefix
  identitySigningKey (32) ||
  identityDHKey (32) ||
  uint32_be(signedPreKey.keyId) ||
  signedPreKey.publicKey (32) ||
  signedPreKey.signature (64)
)

One-time prekeys er ikke med i bundle-hashen — de er ephemerale og ville lekket OTP-rotasjons-mønstre.

Tree

Merkle-tre over leaf-array, RFC 6962 §2.1:

• MTH(empty) = SHA256()
• MTH({d}) = SHA256(0x00 || d) (already hashed leaf)
• MTH(D[n]) = SHA256(0x01 || MTH(D[0:k]) || MTH(D[k:n])) der k er største 2-potens < n.

Signed Tree Head (STH)

sth = {
  tree_size: uint64,
  timestamp: uint64_ms,
  root_hash: bytes(32),
  index_root: bytes(32),         // commitment til adresse-index ved denne tree_size
  log_id: bytes(32),             // SHA-256 av server-public-key (stabil ID)
  signature: bytes(64)           // Ed25519 over canonical(rest)
}

canonical(sth) for signing:

0x02 ||                          // sth prefix
uint64_be(tree_size) ||
uint64_be(timestamp) ||
root_hash (32) ||
index_root (32) ||
log_id (32)

Inklusjons-bevis

Standard RFC 6962 audit-path: liste med søsken-hasher fra leaf til root, slik at klient re-beregner root og sammenligner med STH.

Konsistens-bevis

Standard RFC 6962 §2.1.2: bevis at tree med tree_size = N1 er prefix av tree med tree_size = N2 > N1. Klient bruker dette for å detektere re-write.

Fravær-bevis

Adresse-indexen er en sortert liste (address, leaf_index_of_latest) serialized og hashet. index_root i STH er commitment.

For å bevise fravær av adresse addr ved tree_size N:

• Server returnerer hele indexen ved tree_size N (sortert), eller
• (effektivt:) Returnerer naboparet (addr_prev, addr_next) der addr_prev < addr < addr_next lexikografisk, sammen med en Merkle-path i en sparse Merkle tree over indexen.

Første iterasjon: vi serialiserer hele indexen og lar klienten laste den (kompakt: <100 KB selv for 100k adresser). Senere optimaliserer vi til sparse Merkle tree hvis dataset vokser.

---

4. Friskhetsbevis (Signed Tree Heads)

Frekvens

• Min: Ny STH ved hver mutasjon (register/replenish/delete) — synkront i write-pathen.
• Maks-stale: Selv uten mutasjoner skal en STH publiseres minst hver 10. minutt ("heartbeat STH" — samme tree_size, oppdatert timestamp). Dette gir klienter mulighet til å detektere "død" log uten å bekymre seg om hvorvidt logen faktisk har endret seg.

Klient-akseptansevindue

Klient avviser STH eldre enn now - 24 timer (default, konfigurerbar). Dette beskytter mot replay av gamle STH-er som "skjuler" en mutasjon gjort i ettertid.

Stale-STH som soft-fail

Hvis STH er stale men gyldig signert: klient logger advarsel, returnerer bundle med proof.staleness = 'warn' (V1) eller blokkerer (V2 etter dogfooding). Vi starter med warn, eskalerer til block når witness-økosystem er etablert.

---

5. Klient-verifikasjonssteg

På hver fetchBundle(address):

1. Server returnerer { bundle, proof: { sth, leaf, audit_path, leaf_index, address_index_proof } }.
2. Klient verifiserer:
   • sth.signature mot kjent log_public_key (pinnet ved første bootstrap).
   • sth.timestamp >= now - max_age_ms (default 24t).
   • Re-beregner leaf_hash fra bundle og sammenligner med proof.leaf.
   • Re-beregner root_hash fra audit_path + leaf og sammenligner med sth.root_hash.
   • Verifiserer address_index_proof mot sth.index_root.
3. Hvis klient har en cached forrige STH: sjekk konsistens-proof mellom forrige og denne. Server publiserer dette i GET /v1/kt/consistency?from=<size>&to=<size>.
4. Hvis klient har en cached STH for samme tree_size med ulik root_hash → split-view alarm.

Probabilistisk vs. obligatorisk verifisering

Vi velger obligatorisk ved hver bundle-fetch. Bundle-fetch er sjelden (per ny peer, ikke per melding) — kostnaden er <100ms. Probabilistisk verifisering ville la klienter bli lurt av "én dårlig fetch" uten deteksjon.

Bootstrap

Første gang en klient møter en log: pinner log_public_key etter å ha hentet det fra et ut-av-bånd-pinningendepunkt eller fra Shade.config (operatør sender den med klient-config). Etterfølgende rotasjon krever ny genesis-STH med eksplisitt break-event signert av forrige nøkkel.

---

6. Witness/auditor-rolle

Hva en witness gjør

• Periodisk poll: GET /v1/kt/sth (hent siste STH).
• Lagrer alle observerte STH-er i append-only lokal store.
• Eksponerer GET /witness/sth?log_id=...&tree_size=... slik at andre klienter kan sammenligne hva denne witnessen har sett.
• Verifiserer konsistens mellom hver ny STH og forrige.

Klient-witness-gossip

Klient-bibliotek kan operere i tre moduser:

1. Observe-only: verifiserer kun bundle den selv henter, ingen gossip.
2. Light-witness: poller STH hver Xt og lagrer lokalt; sammenligner med STH levert ved bundle-fetch.
3. Full-witness: publiserer signerte STH-observasjoner til en konfigurert peer-liste eller offentlig endpoint.

V1 leverer 1 og 2. Mode 3 (full-witness publication-protocol) er V2 hvis økosystem trenger det.

Hvem kjører witnesses?

• Shade-prosjektet kjører referanse-witness på offentlig endpoint (separate-from-prekey-server).
• Power-users / operatører kan kjøre egne via @shade/key-transparency/witness- API.
• Tredjeparts auditors (typisk security-research) er invitert.

Vi krever ikke federation/konsensus mellom witnesses i V1 — gossip er rent "har du sett samme STH som meg?".

---

7. Operatørkost

Lagring

• Per leaf: 32 bytes (hash) + ~80 bytes adresse-index entry = ~112 bytes.
• 100k adresser, 1 rotasjon/år, 1 replenish/uke: ~5.4M leaves = ~600 MB log. Tre-strukturen er beregnet on-demand, ikke lagret.
• Index: ~100k × 80B = 8 MB i minne (cacheable).

CPU

• STH-signing: 1 Ed25519-signering per mutasjon + heartbeat = <1k/dag for små deployments. Trivielt.
• Audit-path-beregning: O(log N) ved fetch. <1ms.
• Konsistens-proof: O(log N).

Backup

Logen MÅ aldri miste data — sletting eller corruption ødelegger integritet permanent. Strategi:

• Loggen lagres som append-only tabell shade_kt_log (PG) med (leaf_index, leaf_hash, leaf_data_json).
• Backup hver time + WAL-shipping anbefalt.
• Ved corruption: se §10 Recovery.

STH-signing-key

• Genereres ved første KT-aktivering, lagres i operatør-styrt secret (env, KMS, eller på disk for hjemme-server).
• Rotasjon: breaking event — krever ny genesis-STH der ny key signerer melding "rotated from ${old_key}" med gammel key. Klient må eksplisitt akseptere rotasjonen.

---

8. Migrasjon

Server-side

KT er opt-in på operatør-nivå. createPrekeyServer({ keyTransparency: { enabled, store, signingKey } }). Når slått på:

1. Server skriver alle eksisterende identiteter inn som genesis-leaves ved boot.
2. Første STH publiseres med tree_size = N der N er antall eksisterende adresser.
3. Klient som henter bundle får proof; klient som ikke støtter KT ignorerer proof-felt (forward-compatible).

Klient-side

@shade/sdk-config:

createShade({
  keyTransparency: {
    mode: 'observe' | 'light-witness' | 'off',
    logPublicKey: '<base64>',
    maxStaleMs: 86_400_000,
  },
  // ...
})

mode: 'off' (default for backward-compat første release) — ignorerer proof. Ny SDK med mode: 'observe' verifiserer men feiler ikke harde hvis proof mangler. mode: 'observe-strict' (senere) krever proof.

Eksisterende deployments

Operatør kan rulle KT inn på live server uten klient-update:

1. Skru på KT i server-config → server begynner å produsere proofs.
2. Gamle klienter ignorerer proof-felt (de er additive i bundle-respons).
3. Nye klienter med mode: 'observe' begynner å verifisere.
4. Når operatør har testet og publisert log-public-key OOB, kan brukere skifte til 'light-witness'.

---

9. Akseptansekriterier

• @shade/key-transparency pakke leverer:
  • Merkle log core (RFC 6962 hash-funksjoner).
  • STH-signing/verifikasjon.
  • Inklusjons-bevis generering + verifisering.
  • Konsistens-bevis generering + verifisering.
  • Adresse-index med commitment.
  • Witness-light klient.
  • Cross-platform (TS-only, ingen native deps).
• @shade/server integrasjon:
  • KTLogStore-interface (memory + postgres).
  • Routes: GET /v1/kt/sth, GET /v1/kt/sth/:tree_size, GET /v1/kt/consistency, GET /v1/kt/inclusion/:address.
  • Bundle-fetch returnerer { bundle, proof } når KT aktivert.
  • Heartbeat-STH-publisering hver 10. minutt (configurable).
• @shade/transport ShadeFetchTransport:
  • Aksepterer optional keyTransparency-verifier.
  • fetchBundle() returnerer { bundle, proof?: KTProof }.
• @shade/sdk Shade:
  • keyTransparency-config.
  • Verifiserer proof ved hver bundle-fetch når aktivert.
  • Cacher STH for split-view-deteksjon.
• End-to-end test: split-view detection.
  • Test-server gir Bob bundle X, Charlie bundle Y for samme adresse alice.
  • Bob+Charlie kjører som light-witness, gossiper STH-er.
  • Test asserter at mismatch detekteres innen N polls.
• End-to-end test: log re-write detection.
  • Server skriver om historie (test-only API).
  • Konsistens-proof feiler på neste fetch.
• Operatør-doc dekker recovery-strategi.
• CHANGELOG, README, ROADMAP oppdatert.
• Cross-platform vector-test for Merkle hash + STH (Android/TS paritet, samme som V3.5-tradisjonen).

---

10. Recovery

Log corruption

Hvis log-data tapes (disk-feil før backup): kan ikke gjenopprettes uten å miste integritet — det er hele poenget.

Recovery-prosedyre:

1. Operatør publiserer "log-restart" event signert med STH-keyen.
2. Genesis-STH genereres på nytt med ny log_id (= ny offentlig nøkkel eller eksplisitt versjon).
3. Klienter som har cached STH-er fra gammel log varsles via eksplisitt diskrepans i log_id.
4. Brukere som er bekymret må OOB-verifisere identiteter (V3.3-gate trigges automatisk for fingerprint-rotasjon).

Stale signing-key

Hvis STH-keyen lekkes: rotasjon krever break-event (§7). Inntil brukerne aksepterer ny key, oppfører cient-bibliotek seg som om STH mangler (soft-fail i observe-mode, blokkerer i observe-strict).

---

11. Åpne spørsmål (lukket før kode)

Spørsmål	Svar
Hvordan distribueres log_public_key til klient første gang?	Operatør embedder i Shade.config ved app-init. OOB-pinning er fallback.
Skal one-time prekeys være med i bundle-hash?	Nei — ephemerale, og deres rotasjon ville støy-fylle loggen.
Konflikt: STH ved hver mutasjon vs. batched STH?	Per mutasjon. Heartbeat hver 10 min uansett. Batching vurderes som optimalisering hvis throughput blir et problem (ikke nå).
Hva skjer ved replenish (kun OTP-tilført)?	Skriver ikke til log (bundle-hash uendret). Heartbeat-STH dekker friskhet.
Hva med DELETE?	Skriver tombstone-leaf med operation = 0x03. Identiteten i indexen markeres som "deleted at tree_size N".
Sparse Merkle tree for index-proof?	Senere — V1 bruker hele indexen i fravær-proof. <100 KB ved 100k adresser er akseptabelt.
Klient-cache eviction-policy for STH?	LRU på log_id, last-N (default 100). Klient holder alltid siste sett STH.
Witness-publication-protokoll?	V1 har poll-only (GET /witness/sth); push-publication er V2.

Alle åpne spørsmål har konkrete svar. Implementasjon kan starte.

---

12. Pakke-struktur

packages/shade-key-transparency/
├── package.json                 # @shade/key-transparency, v0.4.0
├── src/
│   ├── index.ts                 # Public exports
│   ├── hashes.ts                # RFC 6962 leaf/node hashing
│   ├── log.ts                   # MerkleLog (in-memory) + audit-path
│   ├── consistency.ts           # Consistency-proof gen/verify
│   ├── sth.ts                   # STH sign / verify / canonical bytes
│   ├── index-tree.ts            # Address index commitment
│   ├── proof.ts                 # KTProof type + bundle-proof verifier
│   ├── store.ts                 # KTLogStore interface (server-side)
│   ├── memory-store.ts          # In-memory KTLogStore
│   ├── witness.ts               # Light-witness client
│   └── errors.ts                # KT-specific error types
└── tests/
    ├── hashes.test.ts
    ├── log.test.ts              # RFC 6962 test vectors
    ├── consistency.test.ts
    ├── sth.test.ts
    ├── index-tree.test.ts
    ├── proof.test.ts
    └── split-view.test.ts       # End-to-end split-view detection

Server-integrasjon i @shade/server:

packages/shade-server/src/
├── kt-routes.ts                 # /v1/kt/* routes
├── kt-integration.ts            # Hook bundle-fetch + register/delete to log
└── ...

Postgres-implementasjon i @shade/storage-postgres:

packages/shade-storage-postgres/src/
├── postgres-kt-store.ts         # KTLogStore on PG
└── ...

Klient-integrasjon i @shade/transport + @shade/sdk:

packages/shade-transport/src/
├── kt-verifier.ts               # Proof-verifier for fetchBundle
└── ...

packages/shade-sdk/src/
├── kt.ts                        # Shade.keyTransparency config + cache
└── ...

---

13. Test-strategi

1. RFC 6962 test-vektorer: importer kjente vektorer fra https://datatracker.ietf.org/doc/html/rfc6962#appendix-A.
2. Property-tests (fast-check): for hver tree_size N og hvert leaf-index i: verify(audit_path(i, N), leaf, sth) === true.
3. Konsistens-bevis property-tests: for N1 < N2: verify_consistency(proof, sth1, sth2) === true.
4. Split-view e2e: to klienter, ondsinnet test-server, witness gossip oppdager mismatch.
5. Re-write-detection e2e: server muterer log-historie, klient neste fetch får konsistens-proof som feiler.
6. Cross-platform: Android (Kotlin) + TS gir samme leaf-hash for samme bundle (V3.5-paritet er forutsetning, så dette må også gå gjennom kotlin-port; for V3.12 første release dekker vi TS — Android port er V3.13).
7. Stale STH: klient avviser STH > max_age.
8. Bootstrap-pinning: klient feiler hvis log_public_key ikke matcher.

---

14. Sikkerhetsvurdering

• Falsk trygghet hvis halvveis: Avhjelpes ved at default-mode er 'off', bare eksplisitt aktivert KT gir hardere garantier. Dokumentasjon fremhever at 'observe' er observasjon, ikke obstruksjon, til økosystemet er etablert.
• Server-side mutability av historie: Avhjelpes ved at KTLogStore kun har append() — ingen update()/delete() på historiske leaves. PG-tabellen har CHECK constraint og BEFORE-triggers for ekstra defense in depth (se §7).
• STH-key compromise: dokumentert §10. Operatør-ansvar.
• DoS via massive index-proofs: index-proof er i V1 hele indexen. 100 KB per fetch er overkommelig; rate-limiteren dekker excess.
• Replay av gammel proof: STH-timestamp + max_age beskytter.

---

15. Approval

Når dette notatet er reviewed (in-tree review er nok for å kommitte første implementasjon; ekstern crypto-review er pre-deploy-krav per V3.12 §"Pre-requisite designnotat"), kan implementasjon starte.

Implementasjon-rekkefølge (alle commits i samme branch):

1. @shade/key-transparency core (Merkle log, STH, proofs).
2. Server-integrasjon (@shade/server + memory/postgres KTLogStore).
3. Klient-integrasjon (@shade/transport verifier + @shade/sdk config).
4. Witness-light + e2e split-view-test.
5. Operatør-doc + CHANGELOG + README + ROADMAP.

— end of design —