improving backwards-compatibility for future protocols

The Problem: How can we introduce new PAKE protocols and retain some measure of compatibility with existing implementations?

I've been making a plan to update Magic-Wormhole's PAKE setup algorithm with something that can prevent the "Harvest Now, Decrypt Later" ("HNDL") attack which becomes possible once cryptographically-relevant quantum computers come into existence (see ticket #TBD).

I have design for a new protocol, and I'm investigating how I can integrate it into magic-wormhole without causing problems with old clients that don't understand the new messages. The new protocol requires an additional phase between the existing PAKE and VERSION messages, probably named PAKE-1 or PAKE-2.

Let's call the existing SPAKE2-only protocol "v1". What I want is for a v1+v2 -capable client, when speaking to a v1-only client, to degrade smoothly to use v1. But a v1+v2-capable client speaking to another v1+v2-capable client should use v2 instead, and we'll observe PAKE and PAKE-2 and VERSION messages, whereas a v1 setup only sees PAKE and VERSION.

The v2 protocol will probably re-use the SPAKE2 exchange, but will need to perform an additional exchange using a protocol named ML-KEM (which is quantum-safe but unauthenticated). ML-KEM is a KEM (Key Encapsulation Mechanism), rather than a key-agreement protocol, and involves two messages (vs SPAKE2's single message).

I'm also anticipating yet another protocol, which we'll call v3, which should be safe against an active quantum-capable attacker, whose quantum computer can run in realtime. The v2 protocol is not safe against such an attacker, but cryptographers are working on protocols that are. The changes we make to support v2 should also smoothly support a v3 once such a protocol is ready. Our best guess about the v3 protocol is that it will use neither SPAKE2 nor ML-KEM, but like ML-KEM should only need two messages.

Problems with our current v1 protocol

In addition to not being safe against quantum HNDL attacks, the v1 protocol does not provide any sort of "what versions am I capable of speaking" fields to implement this sort of v1-vs-v2 negotiation. So we'll have to sneak them into somewhere that existing clients will ignore, so they won't get confused.

It is standard cryptographic engineering practice to record a transcript of the messages that travel between two clients, especially these "what am I capable of" fields, and hash all of them into the session key. This way, an active adversary who modifies the messages to remove or reduce these announcements (a "protocol downgrade attack") has less flexibility. If both Alice and Bob are v1+v2-capable, but Mallory edits Alice's negotiation message to make it look like she's v1-only, then Alice's session key will include her "v1+v2" message, whereas Bob's will include the modified "v1-only" message that he received, and their session keys will differ, preventing them from making a connection under the old protocol.

The magic-wormhole v1 protocol does not create a transcript of the key setup messages. It uses the SPAKE2 output directly as the primary session key. So any v1-capable client is vulnerable to a downgrade attack.

We can't fix this, but we can make sure that v2 is not similarly vulnerable.

Problems with our original upgrade plan

Our client-protocol.md docs, since the beginning, have stated that "Clients will ignore any phase they do not recognize.". The spec says that named phases are for the library, and numbered phases are for the application. So ideally we should be able to add a pake-2 phase and have older (v1-only) clients ignore them.

However, an AI-assisted survey of all the known implementations of the magic-wormhole protocol revealed that none of them would really survive the introduction of new phases.

The Python implementation gets the closest. pake is handled by _order.py and _key.py, and then _boss.py got_message() recognizes version and dilate-\d+ as library-owned phases. It sends numeric phases to the application, and has code to log.err anything else (which emits a complaint into the log but does not interrupt execution). However, the code in _receive.py attempts to use the session key to decrypt all phases after pake. So v1 clients would attempt to decrypt a new pake-2 phase, which would fail, and this would flunk the connection as "scary": treated the same as if the session key did not match, which normally indicates a failed MitM attack. It is fair to say the Python implementation will ignore unrecognized encrypted phases, but that does not help us add new phases to set up the session key.

The other implementations (Go, Haskell, Rust) do not have the flexible state-machine -based architecture of the Python client. Unrecognized phases will trigger an unrecognized-phase connection-closing error in Go (mood=errory), a failed decryption in Rust (scary), and won't even parse successfully in Haskell (crashes the whole client).

As is usually the case, extension mechanisms don't really work unless you use them, and of course if you already knew what the extension was going to be during v1, you'd have included it in v1. The best of intentions are compromised by inflexibility unless exercised frequently. The designers of TLS v1.3 discovered this as their attempts to use fully-specified extension points failed due to middleboxes rejecting the new values, because the designers of those middleboxes had based their logic from observed session behavior more than the full specification. To reduce the chances of this in the future, TLS v1.3 now specifies a "grease" mechanism RFC8701, in which advertisements are encouraged to include various reserved values, so that compatibility problems can be discovered early. We might consider adding something like this.

Fortunately, all four implementations will correctly ignore extra properties in the pake phase message body. A convenient consequence of using JSON for these bodies is that it encourages the use of stdlib JSON parsers, and even in strongly-typed languages, these usually default to ignoring unknown keys (Rust has #[serde(deny_unknown_fields)] but it's not the default). So we can inject new data here, where modern clients can see it, but older clients will be blissfully unaware.

The New Plan

We define a "key setup version" to be a short string of ASCII printable characters, like "v1" or "v2" or "frog". Mainstream versions will use v1/v2/vNN, but temporary experimental versions can deviate from this pattern. Version strings are limited to 128 characters.

We say that each client may be capable of speaking assorted versions ("v1-capable", "v1+v2 -capable"), forming its capability set. The clients will "negotiate" a specific version out of the intersection of their capability sets. "negotiate" is in scare quotes because in fact there is no back-and-forth, rather both sides independently run an algorithm on the pair of capability sets and they must both come to the same conclusion for a connection to work.

(This is in contrast with how Dilation negotiates versions, because that has a Leader and a Follower, and the Leader makes the one decision about which version to use, using the Follower's capability set as input. It doesn't matter what algorithm the Dilation Follower uses, whereas for key setup it is imperative that the two undifferentiated sides produce the same output)

We define the "key setup" stage of the magic-wormhole protocol to be two or more messages, starting with pake, ending with version, but including some moderate number of pake-NN phases in between those two. The v1 key setup stage has only pake and version, and new clients must not send any other phases until they see evidence that their peer is capable of speaking v2 or newer.

We also say each client is optimistic about a specific version, e.g. "v1+v2 -capable but v2-optimistic". The fastest/cheapest connection will be established when both clients are optimistic about the negotiated version. If the negotiated version is not the optimistic one, one or both clients may do unnecessary computational work (e.g. create an ML-KEM keypair that gets discarded), or require an extra roundtrip to send all the data that is needed

We add a new abilities property to the pake phase, to indicate which key-establishment protocols this client is capable of doing. If the abilities key is missing, new clients treat it as ["v1"]:

{ "phase": "pake", "abilities": ["v1", "v2"], "spake_v1": ... }

Clients have a hard-coded negotiation table: v2 wins over v1. Clients ignore any version string in abilities that are invalid or which they do not recognize.

Our planned v2 protocol calls for a mlkem_v2_pk value to be sent to the peer, and then a mlkem_v2_ct value to be received. This will be symmetric, just like the spake_v1 is sent in both directions.

A v2-optimistic client will send their mlkem_v2_pk value in the pake phase:

{ "phase": "pake", "abilities": ["v1", "v2"], "spake_v1": ..., "mlkem_v2_pk": ... }

This value might get ignored by a v1-only peer, but it won't harm them. The client will also include "v2" in the abilities to signal their willingness to speak v2. If a v1+v2-capable client sees "v2" in the peer's abilities, it will commit to using v2, which gives them permission to send additional pake-NN phases. Assuming it has the _pk value, our client will then send:

{ "phase": "pake-2", "mlkem_v2_ct": ... }

When our client receives the peer's mklem_v2_ct as well, it can compute the full session key (combining both the SPAKE2 and the ML-KEM keys), which enables it to finally send the version phase and finish the key-setup stage.

Values can appear in arbitrary key-setup phases

A v2-capable but v1-optimisic client will refrain from doing the ML-KEM work until it sees evidence that the peer can use it. This client's first message will advertise its v2-capability, but only include the v1 SPAKE2 value:

{ "phase": "pake", "abilities": ["v1", "v2"], "spake_v1": ... }

If the peer's abilities results in v2 being selected, our client will then send their _pk in the pake-2 phase. It might also be able to send a _ct in that phase, if the peer was v2-optimistic, or otherwise decided to send the value early enough:

{ "phase": "pake-2", "mlkem_v2_pk": ... }
or
{ "phase": "pake-2", "mlkem_v2_pk": ..., "mlkem_v2_ct": ... }

If the peer wasn't optimistic, our client may need an additional phase to get all the messages out:

{ "phase": "pake-3", "mlkem_v2_ct": ... }

The key-setup stage should be treated as a message pipe of arbitrary length, each message conveying some number of values (possibly zero!) as specifically-named properties inside the phase messages. The exact phase number in which the property arrives does not matter.

The cryptographic side of the v2 or v3 protocol will specify some rules about which values must be received before transmitting other values. Sometimes this is mandated by the way the values are generated, for example in ML-KEM, the ct ("ciphertext") value we send is the output of an Encaps() function that takes the pk ("public key") value that we receive from the peer. So it's simply impossible to send ct before receiving pk. In other cases (perhaps in the future v3 protocol) the value might be available early, but security requires that we not reveal it until the peer has committed to some earlier value.

Optimism vs Waste

Being optimistic about the wrong protocol produces waste but still establishes a valid connection. We can change the optimistic target over time as we get more deployment of the newer versions. I expect the sequence to be:

• v1-only (the current release)
• v1+v2-capable v1-optimistic
• v1+v2-capable v2-optimistic
• v1+v2+v3-capable v2-optimistic
• v1+v2+v3-capable v3-optimistic
• (maybe) v2+v3-capable v3-optimistic
• (mayber) v3-capable v3-optimistic

but of course we might skip some steps.

A v1+v2+v3-capable v2-optimistic client would start with:

{ "phase": "pake", "abilities": ["v1", "v2", "v3"], "spake_v1": ..., "mlkem_v2_pk": ... }

and then, upon realizing we are doing v3, send:

{ "phase": "pake-2", "new_v3_thing": ... }
{ "phase": "pake-3", "new_v3_thing2": ... }
{ "phase": "version", ... }

The mis-optimism will result in wasting CPU and channel space for both the SPAKE2 and the MLKEM values, and will take three messages to get to VERSION. The SPAKE2 waste is unavoidable if we want to retain the ability to speak v1.

A v1+v2+v3-capable v3-optimistic client would start with:

{ "phase": "pake", "abilities": ["v1", "v2", "v3"], "spake_v1": ..., "new_v3_thing": ... }

and then do:

{ "phase": "pake-2", "new_v3_thing2": ... }
{ "phase": "version", ... }

wasting only the SPAKE2 CPU.

Also note that all v1/v2/v3 protocols must ensure that revealing the first (optimistic) message does not compromise the password or give a quantum-capable attacker additional guesses. I believe the SPAKE2 first message has this property: the randomly-selected scalar effectively blinds the password, even if the attacker can get the discrete log of the public value. As long as the client discards the half-complete SPAKE2 protocol instance, it should not contribute to a quantum attack. Clients must discard any received messages that do not correspond to the negotiated protocol: a v3 session that somehow includes the SPAKE2 session key could reveal the password and compromise the session, even if the v3 cryptography was fully quantum-safe.

Transcript Hash

All post-v1 protocols must record the raw contents (pre-json.decode) of all key-setup phases (pake and pake-NN) in a "transcript". This includes all messages sent and received. The transcript must be hashed together with the PAKE/ML-KEM/v3/etc -generated key, and the negotiated protocol version, and this transcript hash will be used as the primary session key.

To do this consistently, on both sides, we must define how these values are sorted and concatenated. Each side has a side, which was formerly used only to distinguish the peer's messages from echoes of our own outbound messages. With this new approach, we also use side to sort the messages:

assert len(struct.pack(">l", 1)) == 4 # guard against weird word size
def withlen(x):
    # prepend a four-byte big-endian length prefix
    if len(x) >= 2**32:
        raise ValueError("too big")
    return struct.pack(">l", x) + x
def encode(side, phase, body):
  return withlen(side) + withlen(phase) + withlen(body)

We then encode() all key setup messages (pake and pake-NN for all received NN), sort the resulting bytestrings lexicographically, append the cryptographically-generated key (SPAKE2/etc), prepend the negotiated version (as a string like "v2" with a newline), concatenate them all, and SHA256-hash the concatenation to get the session key.

negotiated_version = "v2"
sorted_encoded_phases = sorted([encode(*md) for md in setup_messages])
session_key = sha256(
 negotiated_version + "\n"
 sorted_encoded_phases[0] +
 sorted_encoded_phases[1] +
 sorted_encoded_phases[2] +
 ..
 sorted_encoded_phases[-1] +
 pake_key
).digest()

The negotiated v1/v2/etc protocol will determine which properties must be received before we have enough data to compute the session key. The first sequentially-numbered phase which completes this set will end the key-setup stage and trigger computation of the session key. There should be no uncertainty about exactly when this happens (i.e. the client will know precisely which phase-NN is the last one).

Note that the phase-NN messages might not necessarily arrive in-order. If the peer is capable of generating two different fields at different times, it might combine them in a single phase-NN message, or spread them over two different ones, and the mailbox server might relay those messages in either order. Receivers should buffer and re-order received phase-NN messages into numeric order (noting that phase-9 should be delivered before phase-10 even though lexicographically "phase-9" > "phase-10"). The receiver should use a state machine that accumulates data until it has enough to build the session key.

If version or any non-key-setup message arrives before our side has established a session key, it should be buffered and processed after we have a session key, because we won't be able to decrypt such messages until that point.

Bikesheddables

• should the current (SPAKE2-only) protocol be retroactively named "v1" or "v0"?
• should we expand the protocol version names to distinguish between e.g. key setup, dilation, the client->server protocol endpoint URL?
  • e.g. "v2-setup" to distinguish from "v2-dilation"
• should the new (second) key-setup phase be called "pake-1" or "pake-2"? Equivalently, should be existing (first) key-setup phase (named pake) be treated as pake-0 or pake-1?
• msgs['pake'].abilities: name it differently? "capabilities"? "versions"? "can-do"?
• names of the new properties: mlkem_v2_pk/etc

Start with client-protocol.md and trace the Python implementation through _order.py, _key.py, _boss.py, and _receive.py; compare how the Go, Haskell, and Rust implementations handle unknown phases. Review the proposed abilities and pake-NN message flow, then determine the compatibility and negotiation behavior that must be documented or implemented for v1, v2, and future versions.