feat(protocol): optional encrypted UserKey backup with a base58 recovery key

[hartsock]

Motivation

The UserKey is the single durable secret in agent-mesh — the ed25519 root of trust that certifies every AgentKey, signs every GitHubBinding, and anchors the auto-team handshake. Today there is exactly one copy of it, the PKCS#8 PEM that UserKey::save writes to disk at mode 0600. There is no backup, no recovery, and no sanctioned cross-host portability path:

• Lose the file (disk failure, reimaged laptop, fat-fingered rm) and the identity is gone permanently — every cert chain rooted at that key is now unrecoverable, and you must re-enroll a fresh UserKey and re-cross-sign your GitHub binding from scratch.
• Move to a second host and you either insecurely scp the raw PEM (exactly the "scp'd tokens" the README's tagline rejects) or you mint a different identity, breaking --same-user discovery and the auto-team rule.

matrix-rust-sdk solved the analogous problem — "the user's root secret must survive device loss without a plaintext copy sitting around" — with a secret-storage mechanism keyed by a human-portable base58 recovery key (or passphrase). We can borrow that mechanism wholesale while staying broker-less: no escrow server, no homeserver, the wrapped blob lives wherever the user wants it and the recovery key lives in the user's head / password manager.

This is an optional, opt-in, backward-compatible addition. Default behavior is unchanged: no backup is written unless the user runs the backup command.

Current state

Verified against origin/main (agent-mesh-protocol):

• agent-mesh-protocol/src/user_key.rs — UserKey wraps a single ed25519_dalek::SigningKey. Its only persistence surface is:
  • UserKey::save(&self, path) (user_key.rs:67) — writes PKCS#8 PEM, refuses to overwrite an existing file, chmod 0600 on Unix, creates parent dirs. (origin/main additionally hardened this against a TOCTOU / dangling-symlink window via fix(protocol): #17 — create UserKey 0600 atomically (close TOCTOU window) #34.)
  • UserKey::load(path) (user_key.rs:109) — reads the PEM back.
  • Drop (user_key.rs:108) zeroizes the in-memory key bytes; Debug deliberately omits the private half.
  • There is no export_seed / from_seed / backup / recovery accessor. The only raw-bytes call is self.signing.to_bytes() inside Drop, used solely to scrub the copy. Confirmed: grep for backup|recover|export over user_key.rs on origin/main finds nothing but save/load and test names.
• agent-mesh-protocol/src/github_binding.rs — GitHubBinding::sign (github_binding.rs:53) signs BINDING_TAG || user_pubkey_bytes with the user's GitHub SSH ed25519 key. The binding embeds user_pubkey: UserPublic, so a restored UserKey with the same key bytes produces a binding that still verifies — restore must re-assert (or re-export) this binding, but does not need fresh SSH access if the original binding artifact was backed up alongside.
• Envelopes are signed only, never payload-encrypted: SignedEnvelope (envelope.rs:44) carries an ed25519 agent_sig over ENVELOPE_TAG || recipient || nonce || sequence || payload_cid plus a BLAKE3 payload_cid; payload is opaque ByteBuf in the clear. Confidentiality on the wire rides entirely on the iroh QUIC/TLS transport session (README "Transport (Phase 2)"). A UserKey backup is therefore an at-rest confidentiality problem (a wrapped seed blob), independent of the wire layer — the project has no AEAD-of-secrets primitive yet, so this issue introduces the first one.
• Non-exportable-key path already exists on origin/main (correcting the seed framing, which implied feat(protocol): external-pubkey delegation + MeshSigner seam (phone enrollment gate) #27/feat(transport): external-signer seam for the QUIC handshake (no owned seed) #28 were still pending): feat(protocol): external-pubkey delegation + MeshSigner seam (phone enrollment gate) #27 landed MeshSigner (signer.rs:36, a Send + Sync trait with verifying_key() + sign()), AgentKey::delegate_external (agent_key.rs:146, now requiring proof-of-possession per fix(protocol): require proof-of-possession to certify an external pubkey (§9.2) #40), and SignedEnvelope::new_with_signer (envelope.rs:83). signer.rs's module doc is explicit that a platform keystore (Android Keystore / iOS Secure Enclave) "will sign on your behalf but will never export the raw seed." feat(transport): external-signer seam for the QUIC handshake (no owned seed) #28 (closing the iroh transport-handshake seam for the same external signer) is still open. This is the carve-out that a backup feature must respect: non-exportable keys cannot be backed up, by construction.

Proposed design

An optional encrypted backup of the software-seed UserKey, with a base58 recovery key for restore. New module agent-mesh-protocol/src/user_key_backup.rs (name TBD), no new workspace dependency beyond an AEAD + a KDF + base58 (all already pulled transitively; pick crates that keep the dep graph lean).

1. Recovery-key derivation

• Generate a 32-byte random recovery key from the OS RNG. Render it to the user as a grouped base58 string (the matrix UX: bitcoin-alphabet base58 with a fixed 2-byte version prefix + a parity byte, formatted in space-separated 4-char groups). This is the artifact the user writes down / stores in a password manager. It is shown once.
• Alternatively, accept a user passphrase and stretch it to 32 bytes via a memory-hard or iterated KDF with a random salt stored in the backup envelope (matrix uses PBKDF2-HMAC-SHA512 with a high iteration count; argon2id is the stronger modern choice — decide in the PR and document).
• Either way the output is a 32-byte symmetric key. No plaintext seed and no plaintext recovery key is ever written to disk.

2. Wrap (backup)

• Serialize the UserKey's 32-byte ed25519 seed.
• Derive an AEAD key from the recovery key (domain-separated, e.g. HKDF with an agent-mesh-userkey-backup-v1 info tag so this key can never be confused with a transport or envelope key).
• Encrypt the seed with an AEAD (XChaCha20-Poly1305 or AES-GCM) under a random nonce. Authenticate the version tag and salt as associated data.
• Emit a self-describing, versioned, serde-serializable UserKeyBackup { version, kdf_params, salt, nonce, ciphertext, user_fingerprint }. The user_fingerprint (BLAKE3 of the public key) lets a user identify which identity a backup blob holds without decrypting it. Write it to a user-chosen path; it is safe to store anywhere (cloud, USB, repo-adjacent) because it is opaque without the recovery key.
• New API on UserKey, gated so it cannot be reached for a non-software key (see §4): fn backup(&self, recovery: &RecoveryKey) -> UserKeyBackup and a constructor RecoveryKey::generate() -> (RecoveryKey, String /* base58 to show once */) and RecoveryKey::from_base58(&str) / RecoveryKey::from_passphrase(&str, &KdfParams).

3. Restore

• On a new host: UserKey::restore(&UserKeyBackup, &RecoveryKey) -> Result<UserKey>. Re-derive the AEAD key, verify the Poly1305/GCM tag (wrong recovery key → authenticated decryption fails with a clear "recovery key did not match" error, not a panic), reconstruct the seed, rebuild the SigningKey, and UserKey::save it to the standard 0600 path. Because the seed is identical, the restored key's fingerprint equals the original's — --same-user discovery and the auto-team rule keep working transparently.
• Optionally bundle the GitHubBinding artifact into (or alongside) the backup so restore can re-publish the existing binding without re-touching the SSH key. If it is not bundled, restore prints guidance to re-run amesh bind github (the binding re-asserts trivially since the user_pubkey is unchanged — github_binding.rs:53).

4. Non-exportable-key carve-out (hard requirement)

• Backup is only valid for the software-seed path. A MeshSigner backed by Android Keystore / iOS Secure Enclave (signer.rs) has no exportable seed — there is nothing to wrap. The API must make this a compile-time or fail-closed distinction: backup() lives on UserKey (which owns a seed), and must not be expressible for an external/keystore-held identity. Document explicitly that non-exportable identities achieve continuity through the multi-host cross-signing / delegation path (AgentKey::delegate_external, agent_key.rs:146), not through seed export — you enroll the new device as its own keystore-held identity and certify it, rather than copying a secret that, by design, cannot leave the secure element.

5. CLI surface (separate follow-up PR)

amesh key backup --out <path> (prints the recovery key once), amesh key restore --in <path> (prompts for the recovery key / passphrase). Keep crypto in the library; the CLI is a thin wrapper. Out of scope for the protocol-crate PR.

Invariants

• No plaintext seed or plaintext recovery key ever touches disk.
• Opt-in: absent an explicit backup command, behavior is byte-for-byte unchanged.
• Broker-less: no escrow service, no network call; the user holds the recovery key and chooses where the blob lives.
• Backup format is versioned and self-describing so the KDF/AEAD can be rotated later without breaking old blobs.

Reference: matrix-rust-sdk

Read as a reference implementation, not as a dependency:

• crates/matrix-sdk-crypto/src/secret_storage.rs — SecretStorageKey is exactly the mechanism to borrow. It derives a 32-byte key from either a passphrase (PBKDF2-HMAC-SHA512, random salt, high iteration count — new_from_passphrase, line ~330) or a random key, and serializes it for the user as a base58 recovery key: to_base58() (line ~480) prepends a 2-byte version prefix [0x8b, 0x01], appends an XOR parity byte, base58-encodes with the bitcoin alphabet, and groups the output into 4-char chunks; from_account_data() / parse_base58_key() (lines ~370/421) reverse it, validating prefix + parity before use. It encrypts secrets with AES-CTR + HMAC-SHA-256 (encrypt/decrypt, lines ~531/547) and validates a candidate key via a zero-message MAC check (check_zero_message, line ~256) so a wrong recovery key is rejected before any secret is touched. We borrow the recovery-key derivation + base58 UX + verify-before-decrypt shape; our wrap can use a single modern AEAD (XChaCha20-Poly1305 / AES-GCM) rather than the spec's separate CTR+HMAC.
• crates/matrix-sdk/src/encryption/recovery/mod.rs (module doc, lines ~15-28) — confirms that in their unified "recovery" view, the recovery key is the secret-storage key. This is the UX abstraction we want: one human-portable string that reconstitutes the root secret.
• crates/matrix-sdk-crypto/src/backups/mod.rs (module doc, lines ~15-22) — the part NOT to borrow. Their server-side megolm key-backup algorithm (m.megolm_backup.v1.curve25519-aes-sha2) is documented in-tree as having "various flaws," "not recommended," and "only provided for backwards compatibility," with deprecated methods (line ~605). We take the secret-storage mechanism and the recovery-key UX; we explicitly do not replicate the megolm server-backup design (and we have no server to back up to anyway — we are broker-less).

Acceptance criteria

• An ADR / design note records the backup format (version, KDF choice + params, AEAD choice, base58 recovery-key encoding) and the software-seed-only scope.
• RecoveryKey::generate() returns a 32-byte key plus a grouped base58 string shown once; from_base58 round-trips it and rejects bad prefix/parity/length with typed errors (mirroring matrix's DecodeError).
• RecoveryKey::from_passphrase() stretches a passphrase with a salted KDF; salt + params are carried in the backup envelope.
• UserKey::backup() produces a versioned, serde-serializable UserKeyBackup whose seed is AEAD-encrypted under a domain-separated key derived from the recovery key; the blob carries the user_fingerprint and is safe to store anywhere.
• UserKey::restore() reconstitutes a UserKey whose fingerprint equals the original's; a wrong recovery key fails with a clear authenticated-decryption error (no panic, no partial write).
• No plaintext seed or recovery key is ever written to disk; restored keys land at the standard 0600 path via save.
• The default path is unchanged and fully backward compatible — no backup is created unless explicitly requested; existing save/load behavior and all current tests are untouched.
• Restore re-asserts the GitHubBinding (bundled in the backup, or by guiding the user to re-run amesh bind github); a round-trip test shows the restored identity's binding still verifies.
• The non-exportable-key carve-out is enforced and documented: backup() is unreachable for a keystore/MeshSigner-held identity, and the docs point such users at the delegate_external cross-signing path instead.
• Tests cover: backup→restore fingerprint equality, wrong-recovery-key rejection, passphrase and base58 paths, base58 parity/prefix corruption, and serde round-trip of UserKeyBackup. SSH/test keys are generated in-memory per CLAUDE.md (no fixtures, no wall-clock).
• just check and just cov-ci (75% floor) pass; zero clippy warnings.

Relationships

• Related feat(protocol): cross-signing trust graph + identity pinning for multi-host agents #44 — for multi-host, cross-signing a fresh host key is an alternative to backing up/exporting the seed.
• Related feat(transport): external-signer seam for the QUIC handshake (no owned seed) #28 — Secure-Enclave / non-exportable keys (the feat(protocol): external-pubkey delegation + MeshSigner seam (phone enrollment gate) #27 MeshSigner seam, feat(transport): external-signer seam for the QUIC handshake (no owned seed) #28 transport seam) cannot be exported — documented carve-out.

---

Meta · risk: high (per repo CLAUDE.md) · follow-up from the matrix-rust-sdk ↔ agent-mesh architectural comparison (matrix-rust-sdk is a reference implementation, not a dependency).

File/line references were drafted against a recent checkout; line numbers are indicative — symbols are authoritative (grep by name). Substance verified against origin/main @ f63c55f.

🤖 Generated with Claude Code