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

Dan Brown <> Thu, 23 May 2019 17:09 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id D497C120043 for <>; Thu, 23 May 2019 10:09:52 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.611
X-Spam-Status: No, score=-0.611 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=1.989, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 5mpheCyBDKnc for <>; Thu, 23 May 2019 10:09:48 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 65FDF120099 for <>; Thu, 23 May 2019 10:09:36 -0700 (PDT)
Received: from ([]) by with ESMTP/TLS/DHE-RSA-AES256-SHA; 23 May 2019 13:09:28 -0400
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([fe80::b815:71ef:9f8f:e07c%16]) with mapi id 14.03.0415.000; Thu, 23 May 2019 13:09:27 -0400
From: Dan Brown <>
To: Hugo Krawczyk <>, Paterson Kenneth <>
CC: "" <>
Thread-Topic: [Cfrg] Adoption call for draft-barnes-cfrg-hpke
Thread-Index: AQHU/AdYoCx6qRbbHkW7ypFcKyh/6qZ2+LiAgAIX9oA=
Date: Thu, 23 May 2019 17:09:26 +0000
Message-ID: <>
References: <> <>
In-Reply-To: <>
Accept-Language: en-US, en-CA
Content-Language: en-US
x-originating-ip: []
Content-Type: multipart/alternative; boundary="_000_810C31990B57ED40B2062BA10D43FBF501DDDA86XMB116CNCrimnet_"
MIME-Version: 1.0
Archived-At: <>
Subject: Re: [Cfrg] Adoption call for draft-barnes-cfrg-hpke
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 23 May 2019 17:09:53 -0000

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
+1 (289) 261-4157

From: Cfrg <> 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<> 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?