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

[Dan Brown <[e-mail]>]

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?