Re: [Cfrg] Adoption call for draft-barnes-cfrg-hpke

[Hugo Krawczyk <[e-mail]>]

Oops. Rushing  mistake...
You are absolutely right: HOMQV does not provide KCI (I should read my own
papers).
Thank you for catching this.
Using a signature of the sender seems indeed the only mechanism to secure
the authenticated KEM against KCI - at the expense of deniability as you
point out.

Hugo


On Thu, May 23, 2019 at 1:09 PM Dan Brown <[e-mail]> wrote:

> I think deniability is valuable in a one-pass peer-to-peer message
> authentication (or authenticated encryption) scheme, and it seems that
> resisting KCI (key compromise impersonation) interferes with that, though I
> could be wrong.
>
>
>
> Therefore, I would favor not adding KCI to one-pass peer-to-peer message
> authentication scheme.  Rather, to avoid KCI, just use a digital signature
> on the message.
>
>
>
> Details below.  (Sorry for any formatting issues)
>
> ​​​​​
>
> Dan Brown
>
> BlackBerry, Security in Motion
>
> [phone]
>
>
>
> *From:* Cfrg <[e-mail]> *On Behalf Of * Hugo Krawczyk
>
>
>
> - My only technical comment from my superficial reading is that the
> "Authentication using an Asymmetric Key" when implemented with the DH
> mechanism "zz = DH(skE, pkR) + DH(skI, pkR)"  is open to a KCI attack. If
> I learn R's private key not only I can read data sent to him (unavoidable
> in this setting) but I can also impersonate other parties to R, namely, I
> can send data to R as coming from any originator I choose. This is not a
> nice property of an authenticated KEM. Two solutions that address this
> issue are:
>
> 1) The KEM/DEM data is signed by the sender and identities input into the
> key derivation (this requires some care)
>
>
>
> *[DB] A sender signature hinders sender basic deniability.   The recipient
> can now prove to the 3rd parties that at least message was sent, albeit
> perhaps at the cost of exposing the recipient secret key.*
>
>
>
> *More generally, I would naively think that KCI resistance and full
> deniability are incompatible.  *
>
>
>
> *Informally, if Bob reveals his secret key to Charlene, he can convince
> Charline that it was Alice who authenticated the message, arguing as
> follows.  If KCI resistance is believed by Charlene, then Charlene will be
> convinced that Bob could not have generated the authenticated tag.  If the
> authentication security is believed by Charlene, then nobody else, other
> than Alice, could have a generated the message.  *
>
>
>
> *A little more formally, suppose that a pair of functions [Aut,Che] is an
> asymmetric authentication scheme in the sense, where Alice and Bob have
> secret keys a and b, and public key A and B (respectively), and
> Che(b,A,Aut(a,B,M))=1.  A KCI attack is a function Kci such that
> Che(b,A,Kci(b,A,M)) = 1, i.e. the function Kci can used to authenticate a
> message to Bob, using Bob’s secret instead of Alice’s.*
>
>
>
> *Convert [Aut,Che] into a pair of functions [Sig,Ver], a signature scheme,
> defined by Sig(a,M) = Aut(a,B,M) and Ver(M,S) = Che(b,A,M,S).  Then clearly
> Ver(A,M,Sig(a,M)) = 1.  These functions include Bob’s secret b as built-in
> parameter, but work for the set of Alice’s key pairs [a,A] as the
> asymmetric authentication scheme.  A simple forger would be a function For
> such that Ver(A,M,For(A,M))=1.  This function replicates what Sig does
> except it uses a instead A.  (This is a universal-message, key-only,
> forger).  Then a Kci function implies a function For.  So, a no Kci
> functions implies no For functions.  Therefore [Sig,Ver] is at least weakly
> secure as a signature scheme.  *
>
>
>
> *Maybe there is subtlety here that recovers plausible deniabiltiy by
> having [Sig,Ver] very weak, i.e. vulnerable to existential or chosen
> message attacks.  Maybe this is what designed-verifier signatures are?  I
> doubt this though, because it seems to that such a weakness would in turn
> imply interactive KCI attacks.*
>
>
>
> *In doing this, Bob reveals his secret key b, which is a high price.  But
> perhaps there are off-the-shelf zero-knowledge methods that Bob could use
> to avoid revealing b to Charlene, yet still convincing Charlene that Alice
> signed the message.*
>
>
>
> *If I am right, meaning deniability is the price of KCI resistance, then
> one might as well use a proper signature on the message, and then wrap the
> message plus signature inside asymmetric encryption scheme (with integrity
> protection, etc.) *
>
>
>
> *I am in favor of having the option of a basically deniable authenticated
> scheme.  This gives Alice two options for non-interactive authenticating a
> message to Bob: a signature, and a deniable authenticated message.
> (Combining these two options reduces down to the signature case.)*
>
>
>
> *By the way, I am not referring above to stronger notions of deniability,
> in which there is a bogus cover message.*
>
>
>
> 2) Use One-Pass HMQV as described in https://eprint.iacr.org/2010/638.pdf
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__eprint.iacr.org_2010_638.pdf&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=mf6j6fOClApRsArWE9wqI1rEGUVkfxZ0aXWmn35nK_c&m=g2W3XR6LRfqmZLpp2cHvD4I--HfrV95Ml0rceifxHsA&s=GTIQhWGOXycNM5LiwsyWMkSUWj4DVUivVAE3H2rAPe8&e=> as
> it gives optimal performance.
>
> Since HMQV has a patent one may want to replace it with some other
> somewhat-less-efficient implicitly-authenticated mechanism. I think Signal
> is doing something like that (but I am not sure about the details).
>
>
>
> *[DB] I am confused here, because that paper discusses HOMQV, and seems to
> say that 2-pass or 3-pass HMQV is needed for KCI resistance. Are you
> proposing an interactive 2-way communication?*
>
>
>
>
>