Bandwidth-Optimized ML-KEM via Speculative Decapsulation

Abstract

ML-KEM-768 public keys are 1184 bytes, which is regrettable for UDP-based protocols at the IPv6 MTU floor of 1232 bytes of payload.

We present BOMSD, a technique that saves $k$ bytes on the initial public-key transmission by truncating the public key and having the receiver speculatively maintain $2^{8k}$ parallel protocol branches until downstream AEAD authentication disambiguates which branch corresponds to the true public key. We identify ML-KEM’s implicit-rejection property, normally regarded as a security feature, as an exciting opportunity for the legitimate parties to treat themselves as adversaries. We benchmark $k=1$ and confidently extrapolate this to any $k \le 1184$.

Introduction

A naive observer might suppose that implicit rejection makes our task harder, since the decapsulation primitive provides no local oracle for “wrong public key”. We, however, now embrace this. By deferring disambiguation to the AEAD layer, BOMSD exhibits temporal locality of cryptographic doubt™: the receiver simply does not know which shared secret is real, and proceeds anyway, in the spirit of branch prediction. We note that modern CPUs have demonstrated speculative execution to be both performant and entirely free of security consequences.

Construction

The sender transmits $\mathsf{pk}[0 : 1184-k]$, omitting the final $k$ bytes. The receiver enumerates all $2^{8k}$ completions and runs decap on each, obtaining $2^{8k}$ candidate shared secrets $\{\mathsf{ss}_0, \mathsf{ss}_1, \ldots\}$, each of which is, by ML-KEM’s definition, a perfectly valid pseudorandom string indistinguishable from any other.

The receiver then maintains $2^{8k}$ parallel instances of the remainder of the protocol, transmitting each subsequent outbound message $2^{8k}$ times, once under each candidate-derived AEAD key, and accepting inbound messages by trial-decrypting under all candidate keys. Upon the first successful AEAD verification, the receiver prunes the $2^{8k}-1$ losing branches. We call this eventually consistent handshakes.

Security Analysis

We argue BOMSD inherits the IND-CCA security of ML-KEM-768 in the measure-theoretic sense. The receiver’s commitment to all branches simultaneously means a passive adversary observing the wire sees $2^{8k}$ AEAD ciphertexts per outbound message, of which exactly one is real and the others are encrypted under keys uncorrelated with anything. We claim, without proof, that the additional $2^{8k}-1$ ciphertexts leak no information, on the grounds that they are encrypted under keys themselves indistinguishable from random.

A Tamarin proof was attempted but tamarin-prover emitted Egreg: ken has left the building, indicating the protocol’s security.

Bandwidth Analysis

The savings on the initial message are exactly $k$ bytes. The cost on each subsequent message of length $L$ is $(2^{8k}-1) \cdot L$ bytes. For $k=1$, this is a 1-byte saving on handshake initiation in exchange for 255 times bandwidth amplification on every subsequent message until disambiguation, which we argue is a meaningful improvement as subsequent messages are typically expected to be significantly smaller than the initial ML-KEM-768 encapsulation key.

Implementation Notes

Our reference implementation maintains $2^{8k}$ concurrent protocol state machines using Go goroutines, on the theory that goroutines are cheap. We have observed that this is true up to approximately $2^{16}$ goroutines, after which the Go runtime experiences a condition called “out of memory”, which we do not understand and are unable to mitigate. We thus recommend $k \le 2$.

Comparison to Prior Work

A reviewer suggested that a simpler approach would be to not truncate the public key.

This is out of scope, as we would like our initial message to be stateless.

Future Work

We plan to investigate BOMSD-YIPEE, in which the implicit-rejection property is inherited transitively across multiple protocol layers, such that disambiguation of the handshake is deferred until application-layer semantics are observed. For example, in HTTPS, the receiver would speculatively serve $2^{8k}$ distinct websites until the user clicks a link, at which point the click reveals which branch was real.

If you haven’t figured yet, this is a joke.

Seriously though, if you have a solution for UDP protocols where the initial messages want to be mostly stateless but the keys are too large please email me@runxiyu.org or runxiyu@umich.edu.