Subject: [CFRG] Questions for the group from the HPKE presentation

From: Nick Sullivan <[email-masked]>
Date: Fri, 6 Aug 2021 18:30:38 -0400

Dear CFRG participants,

At IETF 111, Dan Harkins made a presentation
<https://datatracker.ietf.org/meeting/111/materials/slides-111-cfrg-new-kems-and-aeads-for-hpke-00>
with two proposals:
- a proposal to define new codepoints for HPKE representing new KEMs for
compressed NIST points
- a proposal to define new codepoints to support deterministic
authenticated encryption schemes that don't use a nonce. This is in service
of the use case of out-of-order delivery of ciphertexts. *In the
discussion, it was noted that HPKE uses a nonce to ensure that it never
leaks whether the same plaintext was encrypted twice and that this proposal
does not provide this security property.*

Also during the discussion, an alternative proposal was made to solve the
out-of-order use case: modify the API for HPKE to enable the user to reset
the nonce counter. This API would enable out-of-order delivery of
ciphertexts with existing HPKE AEADs.

The chairs would like to ask the group a few questions:
1) Does the research group support adding an API to HPKE for resetting the
nonce counter?
2) Is there interest in pursuing a work item to explore defining either of
the following:
- new codepoints for compressed curve points in HPKE?
- new codepoints for deterministic authenticated encryption in HPKE (given the
answer to (1) was no)?

Regards,
Nick (for the chairs)

---

From: Richard Barnes <[email-masked]>
Date: Fri, 6 Aug 2021 12:49:21 -1000

1. I don't think this question is well-formed.  HPKE isn't an API, it is a
construction.  In fact, the "API considerations" section of the HPKE spec
is there precisely because there might be different APIs to an HPKE
implementation.  Given all that, I would be in favor of no action here.
There are several existing ways for an HPKE-based protocol to deal with
out-of-order delivery.

2. Personally, I don't have a use case for either of these.

On Fri, Aug 6, 2021 at 12:31 PM Nick Sullivan <nick=
[email-masked]> wrote:

> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Christopher Patton <[email-masked]>
Date: Fri, 6 Aug 2021 16:55:08 -0700

1) I support solving Dan's use case, and I think adding an additional API
call is the right way to do it. However, I see Richard's point that there
might not be a need to extend the document beyond noting the use case and
how to solve it.

2) I support adding codepoints for compressed curve points. However, I
don't support adding deterministic AE, given the security implications of
having no nonce. That said, if we take 2) it might be worth considering
adding nonce-misuse resistant AE schemes, such as AES-GCM-SIV, as these
would provide some assurance in case the new API call is misused.

Best,
Chris P.

---

From: Dan Harkins <[email-masked]>
Date: Fri, 06 Aug 2021 16:56:27 -0700

On 8/6/21 3:49 PM, Richard Barnes wrote:
> 1. I don't think this question is well-formed.  HPKE isn't an API, it 
> is a construction.  In fact, the "API considerations" section of the 
> HPKE spec is there precisely because there might be different APIs to 
> an HPKE implementation.

   It may not be perfectly formed but its obvious what is being asked. 
My answer
to it is that once you find out that your contexts are out of sync it's 
too late.
I think it's more important to just be able to deal with out-of-order 
and lost
packets.

   Yes, it's "a construction"...that hides a datum from the user and 
makes the
construction fragile for some use cases. So I'd like to remove that 
fragility for
those use cases. The easiest and least intrusive, to the construction, 
way is
to just have Nn=0 for these new AEAD algorithms and not worry about the 
nonce.

   One thing I failed to mention during my presentation is that even if the
user adds a counter/nonce as AAD or a plaintext tweak (to hide whether 
the same
thing is encrypted twice) and screws it up, the DAE security guarantees
remain. SIV is the original misuse-resistant mode.

   Instead "resetting the nonce counter" we could do somethinganalogous 
to what
IPsec does with a floating window that prevents replay but allows 
out-of-order
delivery modulo some limit (really late packets will just get dropped). 
But that
might require some changes to the API...err, the construction, so we'd 
be back
to a reformed question #1.

> Given all that, I would be in favor of no action here. There are 
> several existing ways for an HPKE-based protocol to deal with 
> out-of-order delivery.

   You mean like using deterministic authenticated encryption? If not 
that, then what
exactly are you referring to?

> 2. Personally, I don't have a use case for either of these.

   Well, will you admit that while these might not be your use cases 
that they are
legitimate nonetheless?

   Serialization should have never used SEC uncompressed format. There's 
no valid
reason to do that. I regret that I didn't bring this issue up until it was
officially "too late". But that can be rectified pretty easily and no 
one will force
you to use compact representation if you really don't want to.

   Dan.

> On Fri, Aug 6, 2021 at 12:31 PM Nick Sullivan 
> <nick=[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Dear CFRG participants,
>
>     - a proposal to define new codepoints for HPKE representing new
>     KEMs for compressed NIST points
>     authenticated encryption schemes that don't use a nonce. This is
>     in service of the use case of out-of-order delivery of
>     ciphertexts. /In the discussion, it was noted thatHPKE uses a
>     nonce to ensure that it never leaks whether the same plaintext was
>     encrypted twice and that this proposal does not provide this
>     security property./
>
>     Also during the discussion, an alternative proposal was made to
>     solve the out-of-order use case: modify the API for HPKE to enable
>     the user to reset the nonce counter. This API would enable
>     out-of-order delivery of ciphertexts with existing HPKE AEADs.
>
>     1) Does the research group support adding an API to HPKE for
>     resetting the nonce counter?
>     2) Is there interest in pursuing a work item to explore defining
>     either of the following:
>     - new codepoints for deterministic authenticated
>     encryption in HPKE (given the answer to (1) was no)?
>
>
>
>     Regards,
>     Nick (for the chairs)
>     [email-masked] <mailto:[email-masked]>
>     <https://www.irtf.org/mailman/listinfo/cfrg>
>

-- 
"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

---

From: Richard Barnes <[email-masked]>
Date: Sun, 8 Aug 2021 21:56:17 -1000

W.r.t. (1), the obvious solution to me would be a reordering window outside
of the HPKE implementation.  Even if the HPKE implementation required
in-order delivery, the application payloads containing HPKE ciphertexts
could have a sequence number indicating the order in which they were
produced, and the receiving application could use this to ensure that they
were fed to the HPKE implementation in order.

--RLB

On Fri, Aug 6, 2021 at 1:56 PM Dan Harkins <[email-masked]> wrote:

> implementation.
>   It may not be perfectly formed but its obvious what is being asked. My
> answer
> I think it's more important to just be able to deal with out-of-order and
> lost
> packets.
>
>   Yes, it's "a construction"...that hides a datum from the user and makes
> the
> those use cases. The easiest and least intrusive, to the construction, way
> is
> user adds a counter/nonce as AAD or a plaintext tweak (to hide whether the
> same
>   Instead "resetting the nonce counter" we could do something analogous
> to what
> might require some changes to the API...err, the construction, so we'd be
> back
> Given all that, I would be in favor of no action here.  There are several
> existing ways for an HPKE-based protocol to deal with out-of-order delivery.
>
>
>   You mean like using deterministic authenticated encryption? If not that,
> then what
>   Well, will you admit that while these might not be your use cases that
> they are
> legitimate nonetheless?
>
>   Serialization should have never used SEC uncompressed format. There's no
> valid
> officially "too late". But that can be rectified pretty easily and no one
> will force
>> 1) Does the research group support adding an API to HPKE for resetting
>> the nonce counter?
>> 2) Is there interest in pursuing a work item to explore defining either
>> of the following:

---

From: Dan Harkins <[email-masked]>
Date: Mon, 09 Aug 2021 01:36:05 -0700

But that won't work because even if an implementation is able to
use a reordering window, the existing HPKE "construction" uses a
nonce inside of the HPKE context that is unknowable to the user who
is managing the reordering window. A reordering window is only
useful when misorder is not tragic, and that is not the case with
the current HPKE specification.

   Any change to use a reordering window would require a change to
the API/construction such that it doesn't use an opaque sequence
number/nonce. And that is exactly what I'm proposing.

   Dan.

On 8/9/21 12:56 AM, Richard Barnes wrote:
> W.r.t. (1), the obvious solution to me would be a reordering window 
> outside of the HPKE implementation.  Even if the HPKE implementation 
> required in-order delivery, the application payloads containing HPKE 
> ciphertexts could have a sequence number indicating the order in which 
> they were produced, and the receiving application could use this to 
> ensure that they were fed to the HPKE implementation in order.
>
> --RLB
>
>
> On Fri, Aug 6, 2021 at 1:56 PM Dan Harkins <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>
>>     1. I don't think this question is well-formed. HPKE isn't an API,
>>     it is a construction.  In fact, the "API considerations" section
>>     of the HPKE spec is there precisely because there might be
>>     different APIs to an HPKE implementation.
>
>       It may not be perfectly formed but its obvious what is being
>     asked. My answer
>     to it is that once you find out that your contexts are out of sync
>     it's too late.
>     I think it's more important to just be able to deal with
>     out-of-order and lost
>     packets.
>
>       Yes, it's "a construction"...that hides a datum from the user
>     and makes the
>     construction fragile for some use cases. So I'd like to remove
>     that fragility for
>     those use cases. The easiest and least intrusive, to the
>     construction, way is
>     to just have Nn=0 for these new AEAD algorithms and not worry
>     about the nonce.
>
>     user adds a counter/nonce as AAD or a plaintext tweak (to hide
>     whether the same
>       Instead "resetting the nonce counter" we could do
>     somethinganalogous to what
>     delivery modulo some limit (really late packets will just get
>     dropped). But that
>     might require some changes to the API...err, the construction, so
>     we'd be back
>       You mean like using deterministic authenticated encryption? If
>     not that, then what
>       Well, will you admit that while these might not be your use
>     cases that they are
>     legitimate nonetheless?
>
>       Serialization should have never used SEC uncompressed format.
>     There's no valid
>     officially "too late". But that can be rectified pretty easily and
>     no one will force
>>         - a proposal to define new codepoints for HPKE representing
>>         new KEMs for compressed NIST points
>>         - a proposal to define new codepoints to support
>>         deterministic authenticated encryption schemes that don't use
>>         a nonce. This is in service of the use case of out-of-order
>>         delivery of ciphertexts. /In the discussion, it was noted
>>         thatHPKE uses a nonce to ensure that it never leaks whether
>>         the same plaintext was encrypted twice and that this proposal
>>         does not provide this security property./
>>
>>         Also during the discussion, an alternative proposal was made
>>         to solve the out-of-order use case: modify the API for HPKE
>>         to enable the user to reset the nonce counter. This API would
>>         enable out-of-order delivery of ciphertexts with existing
>>         HPKE AEADs.
>>
>>         2) Is there interest in pursuing a work item to explore
>>         defining either of the following:

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 09 Aug 2021 07:08:15 -0700

For what it's worth, I agree with Richard here. As I understand the situation, this is solvable by the application or wrapper protocol. TLS 1.3, for example, assumes the same sort of reliable, in-order delivery to keep per-record nonces in sync, and that seems to work just fine: https://datatracker.ietf.org/doc/html/rfc8446#section-5.3.

To answer the questions from the original post:

1) No (as per above), but also because adding this type of API seems really unsafe for AEADs that cannot survive nonce reuse.
2) Registering new compressed point format KEMs seems fine -- that's why we have the registry! I don't think we should add DAE ciphersuites given how they impact the security posture of HPKE. This seems to have the effect of making different application decisions regarding the AEAD yield different security outcomes, which I would claim is a regression.

Best,
Chris

On Mon, Aug 9, 2021, at 12:56 AM, Richard Barnes wrote:
> >> 1. I don't think this question is well-formed.  HPKE isn't an API, it is a construction.  In fact, the "API considerations" section of the HPKE spec is there precisely because there might be different APIs to an HPKE implementation.  
> >  
> >   It may not be perfectly formed but its obvious what is being asked. My answer
> > to it is that once you find out that your contexts are out of sync it's too late.
> > I think it's more important to just be able to deal with out-of-order and lost
> > packets.
> > 
> >   Yes, it's "a construction"...that hides a datum from the user and makes the
> > construction fragile for some use cases. So I'd like to remove that fragility for
> > those use cases. The easiest and least intrusive, to the construction, way is
> > to just have Nn=0 for these new AEAD algorithms and not worry about the nonce.
> > 
> > user adds a counter/nonce as AAD or a plaintext tweak (to hide whether the same 
> >   Instead "resetting the nonce counter" we could do something analogous to what
> > IPsec does with a floating window that prevents replay but allows out-of-order
> > delivery modulo some limit (really late packets will just get dropped). But that
> > might require some changes to the API...err, the construction, so we'd be back
> >> Given all that, I would be in favor of no action here.  There are several existing ways for an HPKE-based protocol to deal with out-of-order delivery.
> >  
> >   You mean like using deterministic authenticated encryption? If not that, then what
> >   Well, will you admit that while these might not be your use cases that they are
> > legitimate nonetheless?
> > 
> >   Serialization should have never used SEC uncompressed format. There's no valid
> > officially "too late". But that can be rectified pretty easily and no one will force
> >> On Fri, Aug 6, 2021 at 12:31 PM Nick Sullivan <nick=[email-masked]> wrote:
> >>> Dear CFRG participants, 
> >>> 
> >>> At IETF 111, Dan Harkins made a presentation <https://datatracker.ietf.org/meeting/111/materials/slides-111-cfrg-new-kems-and-aeads-for-hpke-00> with two proposals:
> >>> - a proposal to define new codepoints for HPKE representing new KEMs for compressed NIST points
> >>> - a proposal to define new codepoints to support deterministic authenticated encryption schemes that don't use a nonce. This is in service of the use case of out-of-order delivery of ciphertexts. *In the discussion, it was noted that HPKE uses a nonce to ensure that it never leaks whether the same plaintext was encrypted twice and that this proposal does not provide this security property.*
> >>> 
> >>> Also during the discussion, an alternative proposal was made to solve the out-of-order use case: modify the API for HPKE to enable the user to reset the nonce counter. This API would enable out-of-order delivery of ciphertexts with existing HPKE AEADs.
> >>> 
> >>> 1) Does the research group support adding an API to HPKE for resetting the nonce counter?
> >>> 2) Is there interest in pursuing a work item to explore defining either of the following:
> >>> - new codepoints for deterministic authenticated encryption in HPKE (given the answer to (1) was no)?
> >>> 
> >>> 
> >>> 
> >>> Regards,
> >>> Nick (for the chairs)

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 9 Aug 2021 14:46:33 +0000

Semi-related. Am I the only one who became rather antagonistic to AEAD modes that can't survive nonce reuse/misuse?

I'd like to see only nonce misuse-resistant AEAD as we move forward.

Regards,
Uri

> On Aug 9, 2021, at 10:09, Christopher Wood <[email-masked]> wrote:
>

---

From: Natanael <[email-masked]>
Date: Mon, 9 Aug 2021 16:53:14 +0200

Den mån 9 aug. 2021 16:47Blumenthal, Uri - 0553 - MITLL <[email-masked]>
skrev:

> Semi-related. Am I the only one who became rather antagonistic to AEAD
> modes that can't survive nonce reuse/misuse?
>

FWIW I am also strongly in favor of MRAE modes (misuse resistant
authenticated encryption, like SIV modes). Robustness properties are only
becoming more important.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 9 Aug 2021 15:51:27 +0000

Yes, SIV is what naturally comes to mind (though I'm not "married" to SIV - it's just what appears readily available and reasonably-well tested).

Shouldn't CFRG make a statement to IESG, mentioning the concerns with nonce misuse, and recommending that only resistant modes are adopted?

Thanks

Regards,
Uri

> On Aug 9, 2021, at 10:54, Natanael <[email-masked]> wrote:
> 
> 
> 
> Den mån 9 aug. 2021 16:47Blumenthal, Uri - 0553 - MITLL <[email-masked]> skrev:
> FWIW I am also strongly in favor of MRAE modes (misuse resistant authenticated encryption, like SIV modes). Robustness properties are only becoming more important. 
> 
>

---

From: Dan Harkins <[email-masked]>
Date: Mon, 09 Aug 2021 09:57:23 -0700

> 1) No (as per above), but also because adding this type of API seems really unsafe for AEADs that cannot survive nonce reuse.

   But SIV *can* survive nonce reuse. It is the original misuse-resistant
AEAD mode. The existing AEAD modes cannot survive nonce reuse and they would
be unchanged in my proposal.

   Dan.

---

From: "Martin Thomson" <[email-masked]>
Date: Tue, 10 Aug 2021 11:03:36 +1000

On Mon, Aug 9, 2021, at 17:56, Richard Barnes wrote:
> outside of the HPKE implementation.  

That doesn't work if there are gaps that never get filled.

I don't see a problem with defining something new (Windowed-HPKE, say) that allows for a) an explicit counter, b) more flexible anti-replay and c) tolerance of gaps.  This is what we do in DTLS relative to TLS, which has nearly identical properties at the record layer as this.

The authors/editors of HPKE are justifiably defending the ability of HPKE to progress.  Please, let it proceed to publication.  Let this work proceed independently.  (The technique isn't exactly novel, so it's not like this would be CFRG work either.  Take it to SECDISPATCH.)

Interestingly, none of that approach would depend on use of nonce-misuse resistant modes.

---

From: Dan Harkins <[email-masked]>
Date: Mon, 09 Aug 2021 22:57:39 -0700

On 8/9/21 6:03 PM, Martin Thomson wrote:
> The authors/editors of HPKE are justifiably defending the ability of HPKE to progress.  Please, let it proceed to publication.

   I'm sorry but what are you talking about? No one has suggested preventing
the progress of HPKE or holding it up in any way. Please don't suggest
otherwise.

   Dan.

---

From: "Martin Thomson" <[email-masked]>
Date: Tue, 10 Aug 2021 17:43:06 +1000

> the progress of HPKE or holding it up in any way. Please don't suggest

Sorry Dan, I wasn't attributing any particular intent to you.  You have a problem and are looking for a solution and doing everything right in doing so. I never got the impression that you wanted to stall HPKE progress (the opposite in fact).

But I can't read Nick's email as anything other than a question about modifying HPKE.  I am reading Richard's response as a reaction to that.  I'm curious as to whether the same reaction would apply to a derivative work that added unreliable or unordered receipt.

---

From: Loup Vaillant-David <[email-masked]>
Date: Tue, 10 Aug 2021 14:42:17 +0200

Blumenthal, Uri wrote:
> Semi-related. Am I the only one who became rather antagonistic to
> AEAD modes that can't survive nonce reuse/misuse?
> 

Designing actual protocols convinced me that AEAD is not enough. We
need to go all the way to actual wire protocols, or file formats.

First, we need to establish a session key. It's pretty easy in some
cases (password based key derivation, and done), but key exchange is
generally more problematic (just look at Noise to get an idea of what
it takes to actually exchange keys).

In some cases (such as file encryption), it may be more practical to
have a random (and therefore unique) key for each instance. In this
case, we don't even need a nonce, and we could fix it at zero. (Let's
ignore the likes of AES-CBC).

Finally, we have other considerations, such as key rotation (ratchet)
for forward secrecy, various limits such as chunk length, number of
message per session, replay attack resistance, DoS resistance…

---

Simply put, AEAD, even with nonce-misuse resistance, is not enough.
Application writers need full blown protocols, ideally with some
reference implementation, and a test suite that tests various attacks
that might occur from specific implementation errors… such as nonce
misuse.

At that point, AEAD is just a (crucial) building block for protocol
designers. I believe it is reasonable to assume that protocol designers
(as opposed to application developers), will not design protocols that
reuse nonces. Just like it's reasonable to assume that AEAD designers
aren't going to misuse Poly1305.

So, just like we've been telling application developers to use
authenticated encryption instead of combining AES/GHASH (or
Chacha20/Poly1305) manually, we probably want to give them the
protocols they need, and tell them to use those.

If we do this, nonce-misuse sensitive AEAD such as RFC 8439 should be
much less of a problem. In this context, I believe the security
increase provided by a nonce-misuse resistance is minimal. Possibly not
enough to justify any perceivable decrease in performance.

For me, if we can get application writers to use high-level protocol
implementations, nonce-misuse resistance is just a nice to have.

Loup.

---

From: Dan Harkins <[email-masked]>
Date: Tue, 10 Aug 2021 13:58:18 -0700

An alternative proposal for using HPKE on lossy or unreliable networks...

   1000 pardons for the pseudo-python (which undoubtedly has some semantic
issues) but that's what HPKE uses so I'm trying to align with that.

   The idea here is that there is a new API for Seal and Open called 
DSeal and DOpen.
They are passed an additional datum which is used to construct the nonce 
used by
the AEAD algorithm (it no longer uses self.seq to construct the nonce). 
Senders
ensure this is a monotonically increasing number and receivers check 
whether they've
seen this number before in a sliding window of acceptable 
reordering/dropping.
For these APIs I've repurposed seq to be the sender's last sent number 
and the edge
of the receiver's window (seq can be used the old fashioned way when 
calling Seal()
and Open(), I'm not proposing a change to them). The receiver does an 
immediate
droppage check upon receipt and if it passes tries to open the message. 
If opening
succeeds the receiver window is updated to indicate this number has been 
seen.
This is analogous to the floating receiver window that IPsec uses [1] 
which was
written by James Hughes and Harry Varnis, all errors are mine.

def ContextS.DSeal(aad, num, pt):
   if num <= self.seq
       raise SealError
   ct = Seal(self.key, self.ComputeNonce(num), aad, pt)
   self.seq = num
   return ct

def ContextR.DOpen(aad, num, ct):
   if CheckSeq(num) == Bad
     raise OpenReplay
   pt = Open(self.key, self.ComputeNonce(num), aad, ct)
   if pt == OpenError:
     raise OpenError
   else
     UpdateWindow(num)
   return pt

where CheckSeq() and UpdateWindow() are as follows:

windowSize = 32 (or whatever)

def CheckSeq(num)
   if num == 0
      return Bad
   if num > self.seq
      return Good
   diff = self.seq - num
   if diff > windowSize
      return Bad
   if and(self.window, (1 << diff)) == 0
      return Good
   else
      return Bad

def UpdateWindow(num)
   if (num > self.seq)
       diff = num - self.seq
       if diff < windowSize
          self.window <<= diff
          self.window = or(self.window, 1)
       else
          self.window = 1
       self.seq = num
   else
       diff = self.seq - num
       self.window = or(self.window, (1 << diff))
   return

This does not require deterministic authenticated encryption modes but 
can, instead,
use the existing AEAD cipher modes so there is no worry about getting 
DAE instead
of IND-CCA2 when you're dealing with loss and reordering.

   Bouquets? Brickbats? If this seems like a better way to go I can 
write it up
in an -01 of my draft.

   regards,

   Dan.

[1] https://datatracker.ietf.org/doc/html/rfc2401#appendix-C