Post-quantum protection depends on address secrecy; proposal: ephemeral ML-KEM-768 in the meow bootstrap for a per-connection PSK #133

Activity

1. bradfitz commented on Sep 26, 2026

   

   bradfitz

   on Sep 26, 2026

   Member

   More actions

   Thanks for writing this up. I like the proposal. Couple misc thoughts:

   • yes, 1.25 KB setup packets over shared DERP relays are fine
   • ML-KEM-768 seems like the direction we're going with Tailscale itself. No need for 1024.
   • We are working on PQ stuff in Tailscale proper at the moment (probably doing ML-KEM-768 blended in during the handshake), which might mean Tailcat picks that all up for free and can just drop its PSKs from its addresses entirely.
   • Backwards compat: yes, it'd be nice to have at least one tagged release that understands some "needs new protocol" bit and fails with "I can't do that" and have that out for bit in advance, so when the new PQ stuff comes, the interop story is less chaotic. Maybe we instead send a capability version integer like Tailscale does.

   But the one requirement I didn't see you address:

   • As the operator of the shared DERP relays, we don't want to have access to know WireGuard public keys that then let us do a MEOW to servers and connect to them. They shouldn't have such power. The PSK let them be dumber in that they only knew the Wireguard part but couldn't then MEOW to the servers without the PSK. So if we do ML-KEM during MEOW, we lose that property and the shared relays again become a juicy target. So I think we still need some non-WireGuard-public-key shared secret in the address that we blend in to the PSK, even if ML-KEM does the heavy lifting. This is the part we'd still want even if Tailscale's PQ handshake changes land soon. In which case, our tailcat might need no changes at all: the PSK becomes the protection-from-shared-relay-operators part, and the ML-KEM bit from Tailscale itself becomes the PQ part.

   Thoughts?
2. XavierXIEXIN commented on Sep 27, 2026

   

   XavierXIEXIN

   on Sep 27, 2026

   Author

   More actions

   Thanks for the quick and thorough reply, and for the clear answers on packet size and ML-KEM-768. Taking your points in turn, with the goal of leaving this in a state where you don't need to come back to it until you want to.

   The shared-relay-operator property is kept, I just buried it

   The address PSK is not dropped in the proposal. It stays in the address and is the HKDF salt:

   psk_peer = HKDF-SHA256(ikm = kem_ss, salt = addr_psk,
                          info = "tailcat pq psk v1" || kem_id || server_pub || client_pub || H(ek) || H(ct))
   

   So the KEM does the post-quantum work and the address PSK does exactly the job you describe: a relay operator who knows the server's WireGuard public key can send a meow, can even complete the ML-KEM exchange and learn kem_ss, but without addr_psk they derive a different psk_peer and the Noise handshake fails. That is the same outcome they get today, where the meow succeeds and only the handshake fails. Nothing the operator sees on the wire (ek, ct, both node keys) helps, because addr_psk never leaves the address.

   If you want the property to hold one layer earlier, so the operator can't even get a meowed or make the server do KEM work and allocate peer state, a 32-byte tag on the PQ ping does it: HMAC-SHA256(addr_psk, client_pub || ek), checked against the DERP source key before anything else. Pings from anyone who doesn't know the address PSK are dropped before encapsulation. The server would still accept --psk=false addresses without a tag, as today. I'd include that; it's cheap and it makes the "relays should be dumb" argument hold at every step rather than only at the handshake.

   For addresses that are deliberately published (TXT record + --allow), the PSK is public and the relay-operator property is gone regardless of mechanism, which matches your answer in #105: at that point --allow is the access control. The KEM still gives those deployments the HNDL protection they currently lack, which was the original motivation.

   Tailscale's in-handshake ML-KEM

   If wireguard-go gets ML-KEM-768 blended into the handshake, I agree that's the better end state and tailcat should just inherit it: the PSK becomes the anti-relay-operator part, the handshake becomes the PQ part, and the meow-level KEM in this proposal becomes unnecessary. I don't think tailcat should ship two PQ mechanisms. So I'd treat the meow-KEM design as the standalone fallback in case the handshake work is far off, and otherwise leave it on the shelf; the writeup is here if it's ever useful.

   One small follow-up that applies either way: the current README "Key Management" text and the --psk help say the address PSK provides post-quantum protection. That's true for secret addresses and false for published ones; once the handshake change lands it becomes simply true. Might be worth a one-line qualification in the meantime.

   Capability version, and what I'd ship now regardless

   Fully agree on getting a "needs newer protocol" signal out ahead of time, and a capability integer is better than a bit. Concretely:

   • Address: a new CBOR field carrying the minimum client capability version the server requires. fxamacker/cbor's default decode mode ignores unknown struct fields (ExtraDecErrorUnknownField is opt-in), so today's clients parse such an address fine and then fail later with a timeout; that's unavoidable for already-shipped builds. The prep release adds the check and fails immediately with something like this address requires tailcat protocol v2; this build supports v1, please upgrade. tailcat parse prints it.
   • Meow ping: a new ping type that carries the client's capability version (and, later, whatever the PQ mechanism needs). The address field doubles as the negotiation signal: if the address carries a version, the server understands the new ping; if it doesn't, the client sends today's ping. That removes the "send v2, then alternate with v1" fallback dance from my proposal entirely.
   • Server side: a --min-client-version (or fold it into --pq=require later) so operators can refuse old clients once they choose to, with a log line saying which client was refused and why.

   That prep change is independent of which PQ mechanism eventually lands and is small (wire field, parse-time check, one meow type, help text, tests). I'm happy to send it as a PR if that's welcome; if you'd rather do it in-house alongside the Tailscale handshake work, the notes above should be enough and no reply is needed on my side.

   Thanks again for engaging with this so carefully.
3. bradfitz commented on Nov 4, 2026

   

   bradfitz

   on Nov 4, 2026

   Member

   More actions

   @XavierXIEXIN, see #160. Thoughts?