PQC in ZRTP (RFC6189)

Dear Saag and AvtCore,

as already discussed on Saag
( https://mailarchive.ietf.org/arch/msg/saag/HjxX-4QcqbgO6pshPsPozbhxTV0/ )
I'm working on introducing PQC in ZRTP. On Colin Perkins'
advice, I post this also on avtcore. I'm not yet ready to
publish an I-D, but eager to get external eyes on the solution
I figured to solve the problem of substituting DH with PQC-KEM
in ZRTP.

For those not familiar with ZRTP, it's a key
exchange protocol with authentication over a voice channel
using a Short-Authentication-String(SAS). Stripping it to the
very core of the key exchange it basically does:

Alice and Bob generates DH key pairs (Pka,
Ska) and (PKb, Skb).

1) Bob sends a Commit packet holding
hash(Pkb)

2) Alice sends DH1 packet holding Pka

3) Bob sends DH2 packet holding PKb

They both compute a shared secret DHab using
the peer's public key and their secret one. They then derive
s0 from DHab and a transcript of the exchange. From this, a
20bits hash is generated and turned into a human readable
string(the SAS) to be compared over a voice channel.

Bob sending hash(Pkb) prevent an attacker to
put himself in a position of choosing the final SAS(by
generating his key pair leading to the desired SAS) trying to
find a collision (on 20 bits it is not difficult) starting
from two different Pka.

Whole details in the RFC: https://datatracker.ietf.org/doc/html/rfc6189

In order to introduce PQC to this scheme, it
must be adapted to KEM interface:

Pk,Sk = KEM_keyGen()

Ct,Secret = KEM_encaps(Pk)

Secret = KEM_decaps(Ct, Sk)

This cannot be used directly in the current
ZRTP scheme: if Alice sends her Pk in DH1 packet, Bob can't
commit to Ct before receiving it.

Two solutions to solve this problem :

A - Both parties encapsulate a secret.

Alice and Bob both generate a key pair
(Pka,Ska) and (Pkb,Skb)

1) Bob sends Pkb

2) Alice generates Cta,Secreta =
KEM_encaps(Pkb) then sends Pka and hash(Cta)

3) Bob generates Ctb,Secretb =
KEM_encaps(Pka) then sends Ctb

4) Alice sends Cta

They both derive s0 using Secreta, Secretb
and a transcript of the exchange

In this version there is one additional
packet, Alice sending hash(Cta) plays the role of hash(Pkb)
from the original ZRTP.

B - Only Alice encapsulates a secret

1) Bob generates Pkb,Skb and a random nonce
then sends Pkb and hash(nonce) to Alice

2) Alice generate Ct, Secret =
KEM_encaps(Pkb) then sends Ct to Bob

3) Bob sends the nonce

They both derive s0 using Secret, nonce and
a transcript of the exchange. No extra packets, the exchange
is still safe against simple wiretapping thanks to the KEM and
no parties gets to choose the SAS after getting the other
party material involved in its generation: Alice doesn't have
the nonce when she generates Ct and Secret, Bob commits to use
the nonce before receiving Ct.

The second solution seems simpler and have
my preference. Anyone read this long email until here and have
comments on these schemes?

Note: Hybrid key exchange would be addressed
inside the KEM itself performing both a PQC-KEM and a DH-based
KEM.

Thanks

Johan