Protocol

Conventions: byte strings are base64url (no padding) unless stated otherwise.

This document defines the wire protocol, envelope format, and cryptography used by Prelay. It is the single source of truth for implementing interoperable clients. It intentionally contains no custom cryptography (PRD §9); it composes audited primitives.

1. Overview

Prelay delivers a notification from a sender to an Android device:

Sender ──► Prelay Server ──► FCM (transport) ──► Android app ──► Notification

Everything FCM carries is a single encrypted envelope. The server may or may not be able to read the notification, depending on the mode (§5).

There are two supported modes:

• Mode A — server-assisted encryption. The sender posts plaintext; the server encrypts for the target device. Simple API. Default for self-hosted.
• Mode B — sender-encrypted (zero-knowledge). The sender encrypts with the device's public key; the server only routes and forwards. The only mode the SaaS (Phase B) accepts.

Both modes use the same envelope format and the same primitives. The only difference is who performs the encryption.

2. Cryptographic primitives

Key derivation (v2, §12.5): the AEAD key is never the raw ECDH output. key = HKDF-SHA256(ikm = X25519 shared secret, salt = SHA-256(sender_key ‖ device_public_key), info = "prelay-envelope-v2", L = 32). The salt binds the key to the exact key pair; the info label provides protocol domain separation.

Rationale:

• X25519 is fast, side-channel-resistant, and available in crypto/ecdh (Go stdlib), libsodium, BouncyCastle, and Android Keystore (API 33+).
• ChaCha20-Poly1305 (RFC 8439) is available in golang.org/x/crypto/chacha20poly1305, libsodium, and BouncyCastle (ChaCha20Poly1305). XChaCha20 was considered but dropped: BouncyCastle does not provide it, and its 24-byte nonce robustness is unnecessary because every message uses a fresh ephemeral key — a random 12-byte nonce with a per-message key is always safe (decision record §12.1).
• Using a random nonce per message means no nonce-reuse bookkeeping per key.
• UUIDv7 is used for both message and device ids (decision record §12): it is an IETF standard (RFC 9562), is natively time-ordered (index-friendly), stores as canonical lowercase text in both SQLite and the SaaS's PostgreSQL, and has first-class support across every target language (Go, Kotlin, Python, Node).

3. Device keys

• The Android app generates an X25519 keypair on first run.
• The private key never leaves the device (PRD §7.1). It is sealed using Android Keystore (§7 of this doc) and is never transmitted, logged, or backed up by the server.
• The public key is registered with the server at device registration.

Device identity is a server-issued UUIDv7 (device_id). The public key is immutable at rest; rotation replaces it and bumps key_version (§9).

4. Envelope

Every message delivered to a device is one envelope:

{
  "version": 2,
  "message_id": "0193f8e2-6b4a-7b9e-a2c1-000000000001",
  "device_id": "0193f8e2-6b4a-7b9e-a2c1-000000000002",
  "key_version": 1,
  "algorithm": "X25519-ChaCha20-Poly1305",
  "sender_key": "<base64url 32-byte ephemeral public key>",
  "nonce": "<base64url 12 bytes>",
  "ciphertext": "<base64url>",
  "created_at": 1710000000,
  "ttl": 3600,
  "priority": "high"
}

The FCM data payload is a single JSON object containing the envelope at key env:

{
  "env": "<the envelope object above>"
}

4.1 Associated data (v2)

Every header field except sender_key and nonce is authenticated as AEAD associated data. sender_key and nonce are excluded because they are already authenticated as direct inputs of the key derivation and the AEAD itself. The AAD is a fixed-order, newline-joined string — identical on every platform, no JSON canonicalization:

"prelay-env-v2" \n
version \n message_id \n device_id \n key_version \n algorithm \n
created_at \n ttl \n priority

Integers are decimal; ttl is 0 and priority is the empty string when absent on the wire. Any party rewriting an authenticated header field — e.g. a relay server refreshing message_id or created_at — breaks the Poly1305 tag and the message is discarded on the device. This is what makes the replay protection of §8 hold against an untrusted server.

No plaintext title, message, URL, or metadata is ever placed in the FCM payload (PRD §11).

5. Encryption flows

5.1 Mode A — server-assisted (self-hosted default)

1. Sender → POST /v1/notify with {title, message, priority, channel?, device?, ttl?, actions?}.
2. Server looks up the target device's public key and current key_version.
3. Server generates a fresh ephemeral X25519 keypair for this message.
4. shared_secret = X25519(ephemeral_sk, device_pub).
5. nonce = random(12).
6. key = HKDF-SHA256(shared_secret, salt = SHA-256(ephemeral_pub ‖ device_pub), info = "prelay-envelope-v2").
7. ciphertext = ChaCha20-Poly1305.encrypt(key, nonce, plaintext, aad = §4.1 header string).
8. Envelope is built with sender_key = ephemeral_pub and key_version = device.key_version (always the current version).
9. Envelope → FCM data message → Android → decrypt (§5.3).

The server has the plaintext in memory briefly; it never persists it (PRD §13).

5.2 Mode B — sender-encrypted (zero-knowledge)

1. Sender fetches the device's public key and current key_version (GET /v1/devices/:id/public-key, or locally cached).
2. Sender performs exactly the same steps 3–8 as Mode A on its own machine, stamping the envelope with the fetched key_version.
3. Sender → POST /v1/notify with {device, encrypted: true, payload: <envelope>}.
4. Server validates the envelope (version, message_id, created_at, key_version, size) and routes it to the device. A key_version mismatch → 409 with code stale_key so the sender can refresh. The server never has the plaintext or the shared secret, and cannot decrypt.

Mode B is what the SaaS enforces (PRD §30.3).

5.3 Decryption (Android)

1. Parse envelope; reject unsupported version or algorithm.
2. Check message_id against local dedup cache and created_at freshness.
3. shared_secret = X25519(device_sk, envelope.sender_key).
4. key = HKDF-SHA256(shared_secret, salt = SHA-256(sender_key ‖ device_pub), info = "prelay-envelope-v2").
5. plaintext = ChaCha20-Poly1305.decrypt(key, nonce, ciphertext, aad = §4.1 header string). Authentication failure — including any rewritten header field — ⇒ discard silently (never show untrusted content).
6. Plaintext is the notification JSON (§6); build the Android notification.

5.4 Security properties

Deliberately absent: delivery acknowledgements (read receipts). Confirming receipt back to the sender would require the device to report behavior through the server, creating a behavioral trail — who opened what, when — that contradicts the zero-knowledge and data-minimization model. Delivery records (accepted/pushed) exist only for routing, expire automatically, and are never surfaced as read receipts to senders.

6. Notification plaintext format

The plaintext encrypted inside the envelope is JSON:

{
  "title": "Deployment failed",
  "message": "Production deployment failed.",
  "priority": "high",
  "channel": "deploy",
  "version": 1
}

The app ignores unknown actions and unknown fields (forward compatible).

7. Android key storage

• The X25519 keypair is generated with BouncyCastle and the private key is wrapped in an Android Keystore AES-GCM key using KeyGenParameterSpec (PURPOSE_ENCRYPT | PURPOSE_DECRYPT, ENCRYPTION_PADDING_NONE, GCM). The wrapped key bytes can live in app-private storage; they are meaningless without the Keystore key.
• Keystore-native X25519 key agreement is not used; the wrapped-key approach is the only path on every supported API level (the app's minSdk is 26).
• On device loss, the user revokes the device; rotation is the recovery path (PRD §22 "Stolen Android device").

8. Replay protection & freshness

• Server (Mode B): keeps a bounded, TTL'd set of message_id values in a dedicated replay_keys store (janitor deletes expired rows). Re-submitting a seen message_id → 409 Conflict. This applies to Mode B only: the server mints a fresh message_id for every Mode A request, so there is no sender-supplied id to replay. The replay window is the envelope's full ttl — max(ttl, PRELAY_DELIVERY_TTL), up to the 7-day envelope maximum — so it always covers the time the message remains deliverable. Delivery records are metadata only (routing status) and keep their own retention: PRELAY_DELIVERY_TTL (24 h default); their expiry no longer shortens the replay guarantee. One edge remains fail-closed: a message_id reused after its window lapses may still get 409 until the janitor purges the stale delivery record or lapsed key — the insert's primary key does not know the window has ended (issue #88). A key is also rolled back if the request it gated fails, so a transient error never poisons an undelivered id.
• Server (Mode B): rejects created_at outside a configurable skew window. Default ±300 s (5 min), configurable per deployment via PRELAY_CLOCK_SKEW; bounded replay of old envelopes (§12.3).
• Server (Mode B): rejects envelopes whose key_version does not match the device's current key_version → 409 with code stale_key (§9).
• Android: keeps a small local dedup cache of recent message_ids and ignores stale envelopes. Freshness follows the envelope's own ttl (AEAD-bound, so it cannot be extended by an attacker), matching the transport delivery window — the server sends FCM messages with that same TTL (default 24 h) — floored at ±300 s, with far-future timestamps capped for clock drift. An id is reserved atomically before decrypting and committed only after the message is fully handled, so forged envelopes cannot poison the cache and concurrent deliveries cannot both proceed; the seen-set persists across restarts. Entries carry their accept timestamps and are swept after a fixed 24 h (ReplayGuard.SEEN_TTL_SEC, independent of a larger envelope ttl), so the cache stays bounded by time as well as count and bursts cannot evict replay-relevant ids.

9. Key rotation

Rotation requires proof of possession of the device's current private key (§12.6), so a stolen device:manage token alone cannot redirect future messages to an attacker key:

1. POST /v1/devices/:id/rotate/challenge (scope device:manage) returns {challenge_id, challenge_key} — the public half of a fresh ephemeral X25519 keypair. One outstanding challenge per device (issuing a new one invalidates the previous); TTL 5 minutes; single-use; kept in memory only.

2. POST /v1/devices/:id/rotate with {public_key, challenge_id, proof}, where

   proof = base64url( HKDF-SHA256(
       ikm  = X25519(current_private_key, challenge_key),
       salt = SHA-256(new_public_key ‖ device_id),   // raw key bytes ‖ UTF-8 id
       info = "prelay-rotate-proof-v1",
       L    = 32 ) )

   The server verifies symmetrically with X25519(challenge_private_key, current_public_key) and a constant-time compare. Any failure — unknown, expired, or already-used challenge, wrong proof — is 403 + {"code":"proof_invalid"}; the challenge is consumed on every attempt.

• Rotation notification: on a successful rotation the server best-effort delivers a high-priority notification (channel security) sealed to the old key and old key_version, telling the device its key was rotated and showing the new fingerprint. The app additionally compares the server's key_fingerprint/key_version for its own device on every refresh and warns prominently on a mismatch.
• No force path: if the current private key is lost, the device cannot be rotated to a new key; recovery is revoke + re-onboard (new device id).
• Server-side stale-key guard: any Mode B envelope whose key_version doesn't equal the device's current version is rejected with 409 + {"code":"stale_key"}. The sender fetches the fresh key + version and re-encrypts. This prevents pushing undecryptable messages after a rotation.
• Old envelopes encrypted to the previous key fail to decrypt on the device and are discarded; only new messages use the new key.
• The app displays key_fingerprint (unformatted) and the key version. The fingerprint is hex(SHA-256(public_key)[:16]); the rotation notification shows it grouped, 1a2b:3c4d:5e6f:7a8b:9c0d:1e2f:3a4b:5c6d.

10. Versioning & migration

• envelope.version and the plaintext version are independent. Bumping the plaintext format never requires a server change; bumping the envelope version is a coordinated protocol change.
• Unknown envelope version ⇒ server rejects; Android silently ignores.
• Unknown plaintext fields ⇒ ignored (forward compatible).
• The algorithm string is the single source of truth for crypto; do not infer from version.

11. Transport abstraction

The server core operates only on envelopes; delivery is behind an interface (PRD §29):

type Transport interface {
    Push(ctx context.Context, device Device, env *crypto.Envelope) error
}

• FCM driver (v1): sends a data message {"env": envelope} honoring priority and TTL. Data messages only — never notification messages (PRD §10).
• Future drivers: UnifiedPush, direct transports. They receive the same envelope; no protocol change required.

12. Decision record

All protocol decisions are resolved (v1 decisions in §12.1–§12.4, the v2 change in §12.5, the rotation proof in §12.6).

12.1 Nonce generation — CSPRNG per message, ChaCha20-Poly1305

• nonce = 12 bytes from crypto/rand (Go) / SecureRandom (Android), per message.
• Algorithm decision: standard ChaCha20-Poly1305 (RFC 8439), not XChaCha20. Each message uses a fresh ephemeral sender key, so a random 12-byte nonce is always safe (nonce collisions between different keys are harmless). This keeps the construction audited and available everywhere: x/crypto on Go, crypto_aead_chacha20poly1305_ietf in libsodium, and BouncyCastle's native ChaCha20Poly1305 on Android. Implementers must not reuse a nonce with the same derived key.

12.2 ID format — UUIDv7

• message_id and device_id are UUIDv7 (RFC 9562), canonical lowercase hyphenated text form.
• Time-ordered (index-friendly in SQLite and Postgres); stored as canonical lowercase text in both dialects; first-class support in Go (github.com/google/uuid v7), Kotlin, Python, and Node.
• message_id is sender-generated; device_id is server-issued at registration.

12.3 Clock-skew window — default ±300 s, configurable

• Default 300 seconds, overridable via PRELAY_CLOCK_SKEW (per-deployment config, applied only to Mode B created_at validation).
• Generous enough to absorb NTP/clock drift; replay is still bounded primarily by the message_id seen-set (§8), so skew is a secondary defense-in-depth.

12.4 key_version in the envelope — included in v1

• Required field on every envelope (§4).
• Mode A: server stamps it with the device's current version.
• Mode B: sender stamps it with the version fetched alongside the public key; server rejects mismatches with 409 + stale_key (§9).
• Implemented in v1 (not deferred to v1.1) because nothing is released yet and the stale-key guard prevents silently delivering undecryptable messages after a rotation.

12.5 Protocol v2 — AEAD-associated header + HKDF key derivation

• Problem (v1): the envelope header (message_id, created_at, ttl, priority, …) was not authenticated. A relay server or on-path attacker could rewrite message_id and created_at on a captured envelope and defeat every server-side replay check (§8) — the tag still verified because the ciphertext was untouched. The raw X25519 shared secret was also used directly as the AEAD key, with no KDF and no domain separation.
• Fix: v2 derives the AEAD key with HKDF-SHA256 (§2) and binds the header as associated data (§4.1). Replay now requires breaking ChaCha20-Poly1305.
• sender_key and nonce are excluded from the AAD: they are authenticated as direct inputs of the key derivation and the AEAD, so binding them would be redundant (and circular for the encryptor).
• No backward compatibility: v1 was never released (no users, no shipped envelopes); the server, CLI, and app all reject version != 2.
• AAD is a fixed-order, newline-joined string rather than canonicalized JSON: JSON canonicalization differs across platforms (field order, number formatting) and would be a compatibility hazard; the joined-string form is byte-identical everywhere. Both implementations pin it with cross-platform known-answer tests (crypto_test.go, PrelayCryptoTest.kt).

12.6 Key rotation proof-of-possession — challenge/response with the current key

• Problem: POST /v1/devices/:id/rotate accepted any 32-byte public key with only a device:manage token. A stolen token (e.g. read off a rooted device) could silently redirect future traffic to an attacker key — loss of future confidentiality — while the legitimate device silently stopped decrypting and never learned why. A signature by the new key would not help: an attacker possesses their own new key. Proof must be of the current private key, which is Keystore-sealed and never leaves the device.
• Fix: an ephemeral X25519 challenge (5-minute TTL, one outstanding per device, single-use, in-memory) answered with the HKDF-SHA256 transcript of §9 — only existing primitives (X25519 + HKDF-SHA256), mirroring the v2 envelope derivation style. The salt binds the proof to the exact new key and device, so a captured proof is useless for any other rotation.
• Recovery without the old key is revoke + re-onboard, deliberately: an admin force-rotate would reintroduce exactly the path this closes.
• Device awareness: the server seals a security-channel notification to the old key at rotation time, and the app compares fingerprints on every refresh — so even a device that missed the push learns of the change.
• Both derivations are pinned byte-for-byte by shared known-answer vectors (crypto_test.go TestRotateProofKAT, RotationProofTest.kt).