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

From: Marek Jankowski <[email-masked]>
Date: Tue, 30 Apr 2019 19:44:15 +0200

I also support the adoption of this draft.

Marek.

On Tue, Apr 30, 2019 at 5:28 PM mcgrew <[email-masked]> wrote:

> Hi Kenny and Richard,
>
> I support the adoption of draft-barnes-cfrg-hpke, and I have some comments
> below.
>
> I like the goal of an RFC that provides a self-contained normative
> description of "hybrid public key encryption."
>
> It should be an explicit goal that an implementation can conform to this
> RFC and also conform to [keyagreement], for the NIST approved algorithms,
> because NIST validation is important in the industry.  I suggest adding a
> subsection somewhere that details how this conformance is possible.
> Please note that I’m not asking that every possible option/ciphersuite in
> this document be in the NIST-approved category; rather, I’m asking that for
> the NIST-approved algorithms, the details such as key generation, domain
> parameters, and symmetric key derivation don’t have any incompatibilities.
>
> I suggest changing the name from hybrid public key encryption to something
> from the existing literature.   According to Boyd and Mathuria, for
> instance, this is a key transport scheme, and the term “hybrid” has a
> different meaning.   Something like "Key Transport for AEAD Using Discrete
> Log Cryptography” seems accurate, since this draft only covers DL, there is
> no need to have a name that would be generic to RSA and McEliece.
>  “Asymmetric Key Transport for AEAD” would be appropriate if there is a
> need to be more generic.
>
> The phrase "Hybrid public-key encryption (HPKE) is a substantially more
> efficient solution than traditional public key encryption techniques such
> as those based on RSA or ElGamal” is confusing, because combined
> asymmetric/symmetric crypto systems have been the preferred solution since
> Kohnfelder’s 1978 thesis.   Someone without domain expertise might
> mistakenly think that this draft is claiming to be an improvement over
> current public key algorithms.   I suggest motivating this draft with
> something like “While there are well accepted standards for public key
> encryption [RFC7748][keyagreement], in several scenarios these techniques
> must be combined with symmetric authenticated encryption."
>
> There should be some discussion about replay attacks and their
> prevention.
>
> If there is not a strong mechanism protecting against replays, would it
> make sense to use an AEAD that is robust against nonce misuse, like
> GCM-SIV?
>
> "A given context SHOULD be used either only for encryption or only for
> decryption.”   Why not a MUST?
>
> It seems that there is no citation given for P-256 and P-521.
>
> A nit: KEM is used before it is defined.
>
> thanks
>
> David
>
>
> > On Apr 26, 2019, at 4:09 AM, Paterson Kenneth <
> [email-masked]> wrote:
> >
> > Dear CFRG,
> >
> > (This is the first of two adoption calls today.)
> >
> > This email starts a 2-week adoption call for:
> >
> > https://tools.ietf.org/html/draft-barnes-cfrg-hpke-01
> >
> > Hybrid Public Key Encryption
> >
> > Please give your views on whether this document should be adopted as a
> CFRG draft, and if so, whether you'd be willing to help work on it/review
> it.
> >
> > Thanks,
> >
> > Kenny (for the chairs)
> >
> >
> > _______________________________________________
> > Cfrg mailing list
> > [email-masked]
> > https://www.irtf.org/mailman/listinfo/cfrg
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Jim Schaad <[email-masked]>
Date: Tue, 14 May 2019 13:58:14 -0700

I cannot be either pro or anti on this document.  I just don't understand
what it is trying to do.  I have read through the document on three separate
occasions but the goal is just eluding me.

Jim

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Paterson Kenneth
> Sent: Friday, April 26, 2019 1:09 AM
> To: [email-masked]
> Subject: [Cfrg] Adoption call for draft-barnes-cfrg-hpke
> 
> Dear CFRG,
> 
it.

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 22 May 2019 00:28:53 -0400

I support adoption of this document.

I wanted to read the draft in more detail but it is not happening so just a
few remarks.

- I too think that "hybrid" has too many meanings (I believe this was
called hybrid because it mixes public key with symmetric key). This
mechanism is also known as the "envelope method". My preferred name would
be "Encapsulated Public Key Encryption". It goes well with the terminology
KEM/DEM (for "key encapsulation mechanisms" and "data encapsulation
mechanism") as introduced by Shoup and quite common in current crypto
literature.

-  I would have liked to see the KEM/DEM terminology not only used but the
sections of the paper titled like that (namely, a section on key
encapsulation and a section of data encapsulation). The draft is
essentially presenting things in equivalent ways but I would like the
terminology and the section separation to be clearer. It would reflect more
clearly the separation and independence between these mechanisms.

- 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)
2) Use One-Pass HMQV as described in https://eprint.iacr.org/2010/638.pdf 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).

- The draft does not discuss forward secrecy. Clearly security cannot be
achieved in case of the compromise of the recipient's private key. However,
in the authenticated scenario where the sender has a private key forward
secrecy is achieved (with the DH-based solution) for the sender - i.e., the
encapsulated key remains secure even in the case that the sender's private
key is compromised. This, however, is only forward secure against
eavesdroppers (called "weak forward secrecy"). If one also adds the DEM
part with authenticated encryption then one achieves full forward secrecy,
i.e., security against active attacks. This is discussed in the above paper
and the references within.

Hugo

---

From: Dan Brown <[email-masked]>
Date: Thu, 23 May 2019 17:09:26 +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 <[email-masked]> 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?

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 23 May 2019 14:04:08 -0400

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 <[email-masked]> 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.
>
>
>
> *From:* Cfrg <[email-masked]> *On Behalf Of * Hugo Krawczyk
>
>
>
> 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:
>
> *[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
> *[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?*
>
>
>
>
>

---

From: Natanael <[email-masked]>
Date: Fri, 24 May 2019 11:06:21 +0200

On Thu, May 23, 2019 at 7:10 PM Dan Brown <[email-masked]> wrote:

>From what I've read on the topic (full disclosure, I'm just a hobbyist),
the solution to maintaining KCI resistance + deniability is essentially to
very carefully apply the concept of provenance to the outputs of the
cryptographic primitives. Standard deniability already works on a limited
concept of provenance as far as I an tell (especially Signal's 3DH), but to
maintain KCI resistance but now you still have to handle the problem of how
you can generate a fake conversation that fools others even if your key
leaks but still not be fooled by others if they steal your key. So how do
we do that?

At least for online interactive protocols I can imagine some options. The
first one: design a deniable key exchange where the key exchange is quick
and efficient if both parties' private keys are known by respective side
(standard key exchange between honest parties) - but where it is slow (as
in takes at least minutes to compute a full challenge-response transcript)
if only one side's keys are known. By applying a timeout rule to the
protocol, an adversary that only has your private key can't impersonate the
other party *fast enough* to fool you.