Mixing KEM into Noise

This is a draft. It’s a notepad for me to jot things down for fun. It might disappear anytime.

I am not a cryptographer. Expect severe bugs.

Purpose

No PQ authentication for now.

The primary threat as of this date is harvest-now decrypt-later. While PQ authentication is desirable, the consensus is that we’re relatively far away from active quantum-capable MITMs; KEMs are not a good fit for Noise for auth, and those with commutative group actions such as CSIDH are slow and too novel. Thus, the goal here is to have PQ contribution to the shared secret.

KEM selection

• ML-KEM (Kyber) should work fine
• Classic McEliece is a much more battle-tested choice, but would not fit into Noise’s and other length limits.
• Does not apply to CSIDH or other NIKE-capable algorithms; those would integrate much more elegantly into Noise, and auth would be trivial too. But none are standardized, SIDH/SIKE is broken, and they are way too CPU intensive.
• Perhaps except for McEliece, as Ori said: we’re in the RC4 era of PQ.

Tokens

• The ke receiver must be the kem sender; the kem receiver must be the ke sender.
• KEM keys and secrets are ephemeral and single-use.
• Each ephemeral KEM keypair is single-use.
• Each ke should be consumed by max one kem (exactly one unless connection breaks).
• After a kem consumes a ke, delete kempk and kemsk on both sides, and delete kemss immediately after MixKey, etc.

ke sender

• KemPair() -> (kempk, kemsk), store kemsk
• Send kempk
• MixHash(kempk)

ke receiver

• Get and store kempk
• MixHash(kempk)

kem sender

• KemEncaps(kempk) -> (kemct, kemss)
• Send kemct
• MixHash(kemct)
• MixKey(kemss)

kem receiver

• Get kemct
• KemDecaps(kemsk, kemct) -> kemss
• MixHash(kemct)
• MixKey(kemss)

Some handshake patterns

Pefer kem before s. (Obviously doesn’t apply to pre-knowledge s.)

These are the four that I’m familiar with (as part of Murshy’s design).

NX

-> e, ke
<- e, ee, kem, s, es

XX

-> e, ke
<- e, ee, kem, s, es
-> s, se

NK

<- s
...
-> e, es, ke
<- e, ee, kem

XK

<- s
...
-> e, es, ke
<- e, ee, kem
-> s, se

Formal verification?

Well, I’ll look into applied $\pi$-calculus when I finish my school exams.