Subject: [CFRG] Bart: a deniable key exchange using HPKE

From: Dan Harkins <[email-masked]>
Date: Wed, 20 Jan 2021 12:25:29 -0800

Hello,

   IKEv1 had an "encrypted nonce" mode of authentication that was, sadly,
left out of IKEv2. This exchange was based on the SHARE and EXCH modes
of SKEME [1]. The HPKE draft has created the opportunity to robustly and
straightforwardly do something similar, where two honest participants can
get strong mutual authentication but have plausible deniability that the
exchange actually took place by running HPKE twice. Call it Bart [2].

   HPKE is used in BASE mode only, and only with the one-shot API (the HPKE
context is destroyed after doing a single encryption and exporting a single
secret). [Note: I'm taking liberties with the HPKE APIs defined in the draft
somewhat but it should be obvious what I'm doing].

   Sa/Sb is the static identity key of Alice/Bob respectively (private 
analog is
sa/sb). Ea/Eb is ephemeral key of Alice/Bob respectively, Ka/Kb is 
secret exported
from Alice's and Bob's HPKE context, respectively. Ca/Cb is ciphertext 
from Alice
and Bob, respectively. Basically Bart does two static-ephemeral DH 
exchanges to
encrypt nonces and extract secrets, and then HKDFs the nonces as salt 
and the
secrets as keying material to produce authenticated and secret outputs.

   1. Alice and Bob already trust each other's static DH (identity) key, 
Sb/Sa.
   2. Alice and Bob create random nonces, Na and Nb respectively, and 
use HPKE to
       create contexts, ctxa/ctxb, encrypt the random nonce in the 
peer's public key,
       they both extract secrets, Ka and Kb, from the respective HPKE 
contexts:

     Na <-- Rand()
     ctxa = HPKE-setup(Sb)
     Ea, Ca = HPKE-encap(ctxa, Na)
     Ka = HPKE-export(ctxa, "some label")

                    Ea, Ca --------->
                                              ctxa = HPKE-setup(Ea, sb)
                                              Na = HPKE-decap(ctxa, Ca)
                                              Ka = HPKE-export(ctxa, 
"some label")

                                              Nb <-- Rand()
                                              ctxb = HPKE-setup(Sa)
                                              Eb, Cb = HPKE-encap(ctxb, Nb)
                                              Kb = HPKE-export(ctxb, 
"some label")

                            <----------   Eb, Cb

     ctxb = HPKE-setup(Eb, sa)
     Nb = HPKE-decap(ctxb, Cb)
     Kb = HPKE-export(ctxb, "some label")

    3. HKDF-Extract is then passed a concatenation of the two decrypted 
nonces as
(an authenticated) salt and a concatenation of the extracted secrets as 
IKM to
produce a secret:

     secret = HKDF-Extract(Na | Nb, Ka | Kb)

The secret can then be used with HKDF-Expand() to derive a key used to MAC a
transcript of the exchange (and authenticate Bart) and a key to export to an
upper-layer application.

   The nice thing is that in this exchange the key is authenticated, not 
just the
exchange. And it's completely deniable. Chas can produce a simulated 
exchange
between Alice and Bob that neither party took part in. This fact can be 
used by
both Alice and Bob to plausibly deny that they ever took part in a 
legitimate
exchange, useful for whistleblowing and muckraking use cases.

   regards,

   Dan.

[1] https://www.ndss-symposium.org/wp-content/uploads/2017/09/krawczyk.ps
[2] Bart Simpson: "I didn't do it. Nobody saw me do it. You can't prove
     anything."

-- 
"The object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." -- Marcus Aurelius