[saag] PQC in ZRTP (RFC6189)

[Johan Pascal <[e-mail]>]

Dear Saag and AvtCore,

as already discussed on Saag (https://mailarchive.ietf.org/arch/msg/saag/HjxX-4QcqbgO6pshPsPozbhxTV0/" rel="nofollow">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" rel="nofollow">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