Subject: [CFRG] Fixing the multi-shot API of HPKE

From: Dan Harkins <[email-masked]>
Date: Fri, 12 Feb 2021 15:29:21 -0800

Hello again,

   The HPKE spec defines a single shot API for doing things like 
key-wrapping.
You pass in the recipient's public key and some plaintext and get back a
ciphertext. And that's it. One and done.

   There is also (what I'll call for lack of a better word) a multi-shot 
API.
The idea here is that there's a single asymmetric crypto operation involving
the recipient's pubic key to derive some state that resides in an opaque 
HPKE
context and then multiple calls to encrypt distinct plaintexts. The state
created includes a base nonce and a sequence number (initialized to zero).
Each call to another encryption (decryption) increments the sequence number
which is xor'd with the base nonce and passed to the AEAD algorithm. The 
HPKE
APIs take a plaintext, and AAD, and produce a ciphertext, and vice versa.

   This multi-shot API is fine if your world is Guaranteed In Order Delivery
of Packets but that's not the world we all live in. As such, it'll only
be a matter of time before the sender and receiver are out of sync. The
HPKE draft alludes to this problem this way:

    "It is up to the application to ensure that encryptions and
     decryptions are done in the proper sequence, so that encryption
     and decryption nonces align."

Well that's a pain! One of the nice things about HPKE is that one doesn't
need to worry about the nitty gritty of crypto state management anymore,
it's all hidden. The API is nice and clean-- pass in a plaintext and get a
ciphertext, pass in a ciphertext and get a plaintext.

   If there was an AEAD mode that did not require a nonce it could be used
in HPKE's multi-shot API without need for the application to manage state
and guarantee the parties stay in sync. Thankfully there is such an AEAD
mode: AES-SIV (RFC 5297).

   When I brought this up earlier (and also on github) in the context of
misuse resistance the response was, there's an export-only API that will
give you a secret and you can go do any AEAD mode you feel like, including
AES-SIV, issue closed.

   While that is technically true, it applies equally to the AEAD functions
that HPKE already defines-- you can export a secret and do AES-GCM-256
outside of HPKE while managing the necessary state yourself. Yet HPKE
defines AEAD functions whose state resides in an opaque context so there
is obviously value in having that functionality. I just want to get that
value-- a clean, multi-shot API where I don't need to worry about managing
state or guaranteeing people remain in sync-- for people who don't live
in the world of Guaranteed In Order Delivery of Packets.

   So I'd like to ask the group whether they see value in having a 
nonce-less
AEAD mode in HPKE. If so I'll be happy to resurrect the text changes I
proposed and will be happy to contribute test vectors from my HPKE
implementation which already does AES-SIV.

   One issue is that there are different security properties for a
deterministic authenticated encryption scheme than for a probabilistic
scheme. This is discussed in [1] and the security considerations would
have to mention this. But I don't see that as a formidable problem.

   regards,

   Dan.

[1] Rogaway and Shrimpton, "Deterministic Authenticated Encryption",
     EUROCRYPT, 2006

-- 
"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: Karthikeyan Bhargavan <[email-masked]>
Date: Sat, 13 Feb 2021 12:10:38 +0100

Hi Dan,

I don’t fully understand the problem you are alluding to.

>     and decryption nonces align.”

The HPKE stateful API guarantees that nonces cannot be misused, even if you use AES-GCM or Chacha-Poly. (Of course, you could also add a SIV ciphersuite.)
Furthermore, it guarantees that the stream of plaintext messages received by the decryptor is a prefix of the stream of plaintext messages sent by the encryptor.

In the current design, if two ciphertexts are decrypted out-of-order, both decryptions will fail.
So the problem alluded to in the text above is one of functionality; the application has to ensure (using some meta-data) that it is calling decrypt in the right order.
The application usually has to do something like this anyway to put the plaintext stream together.

I do not see how using AES-GCM-SIV is going to solve the above issue; yes, it would allow you to decrypt the plaintext in any order, but  the HPKE receiver would not be able to authenticate the correct order.
Am I missing something?

-Karthik

> On 13 Feb 2021, at 00:29, Dan Harkins <[email-masked]> wrote:
> 
> 
>   Hello again,
> 
>   The HPKE spec defines a single shot API for doing things like key-wrapping.
>   There is also (what I'll call for lack of a better word) a multi-shot API.
> the recipient's pubic key to derive some state that resides in an opaque HPKE
> which is xor'd with the base nonce and passed to the AEAD algorithm. The HPKE
>   So I'd like to ask the group whether they see value in having a nonce-less
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Dan Harkins <[email-masked]>
Date: Sat, 13 Feb 2021 04:28:37 -0800

Hi Karthik,

> Furthermore, it guarantees that the stream of plaintext messages received by the decryptor is a prefix of the stream of plaintext messages sent by the encryptor.

   It's not an issue of misuse, it's an issue of the sender and
receiver contexts getting out of sync through entirely normal
network behavior and becoming unusable.

> I do not see how using AES-GCM-SIV is going to solve the above issue; yes, it would allow you to decrypt the plaintext in any order, but  the HPKE receiver would not be able to authenticate the cor…

   AES-GCM-SIV requires a nonce (although reuse is not tragic in the
way it is for GCM) so there still needs to be some guarantee that the
nonce plugged into the receiver is the same as the one plugged into
the sender when the ciphertext was created. This is a proposal for
AES-SIV (defined by Rogaway and Shrimpton) which can do deterministic
AEAD (it can also be passed a nonce to be more like a traditional AEAD
mode, albeit slower, but that's not what I'm proposing here). No nonce
so nothing to worry about getting out of order.

   Regarding the correct order, for a streaming application yes that's
true. The correct order would still be needed and whatever technique
you use to ensure that decrypted packets get ordered correctly could
probably be used to ensure that packets are decrypted in order. But
there are other interesting applications of HPKE that are not streaming
and each message can be thought of as self-contained. Imagine a sensor
obtaining some environmental data and then sending it off to a server
for correlation and processing every <time slice>. It would be quite
easy for such a sensor and server to get their HPKE contexts out of
sync and that would be a real PITA.

   regards,

   Dan.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Sun, 14 Feb 2021 01:53:37 +0000

Strictly speaking, AES-GCM-SIV does *not* need a nonce, given that the bounds (how many messages of what size are secured with the same key) are observed.

I found that a very useful property. Not everybody needs that, and not always - but it's like "you don't need it, until you *really* need it".
--
Regards,
Uri
 
There are two ways to design a system. One is to make is so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare

On 2/13/21, 07:29, "CFRG on behalf of Dan Harkins" <[email-masked] on behalf of [email-masked]> wrote:

       Hi Karthik,

       regards,

       Dan.

---

From: Richard Barnes <[email-masked]>
Date: Mon, 15 Feb 2021 11:31:36 -0500

Hi Dan,

HPKE is not intended to be a full network protocol; it is supposed to be
embedded in an application that assures properties such as those you
mention.  Section 8.6, "External Requirements / Non-Goals" [1] has some
text on this.  If you think we can be clearer in these disclaimers,
suggested text / PRs would be welcome.

--Richard

[1] https://tools.ietf.org/html/draft-irtf-cfrg-hpke-07#section-8.6

On Sat, Feb 13, 2021 at 7:29 AM Dan Harkins <[email-masked]> wrote:

> > The HPKE stateful API guarantees that nonces cannot be misused, even if
> you use AES-GCM or Chacha-Poly. (Of course, you could also add a SIV
> ciphersuite.)
> > Furthermore, it guarantees that the stream of plaintext messages
> received by the decryptor is a prefix of the stream of plaintext messages
> sent by the encryptor.
>
> > So the problem alluded to in the text above is one of functionality; the
> application has to ensure (using some meta-data) that it is calling decrypt
> in the right order.
> > I do not see how using AES-GCM-SIV is going to solve the above issue;
> yes, it would allow you to decrypt the plaintext in any order, but  the
> HPKE receiver would not be able to authenticate the correct order.
> > Am I missing something?
>

---

From: Dan Harkins <[email-masked]>
Date: Mon, 15 Feb 2021 10:33:14 -0800

Hi Richard,

On 2/15/21 8:31 AM, Richard Barnes wrote:
> Hi Dan,
>
> HPKE is not intended to be a full network protocol; it is supposed to 
> be embedded in an application that assures properties such as those 
> you mention.  Section 8.6, "External Requirements / Non-Goals" [1] has 
> some text on this.  If you think we can be clearer in these 
> disclaimers, suggested text / PRs would be welcome.

   Right, it's designed to be a fairly low-level primitive. Section 8.6 is
describing the non-goals of HPKE. It's basically, "if you want this feature
you need to handle this on your own", which is perfectly understandable. No
need to be clearer there.

   But this is the other way around. This is an expectation that HPKE places
on any high-level protocol that might want to use it. It might be nice to
have a (sub-)section formally devoted to this instead of burying the
requirement in a discussion of how the sequence number is managed inside of
an opaque HPKE context where its importance could easily be missed.

   Actually since this is an external requirement, you could make the 
title of
8.6 just be "External Requirements", make the current content of 8.6 be a
sub-section 8.6.1 entitled "Non-Goals" and then make an 8.6.2 entitled
"Requirements on Upper-Layer Protocol" that says this requirement formally:

     A high-level protocol that uses HPKE's stateful API MUST provide
     for guaranteed in-order delivery of packets to ensure that all
     ciphertexts are presented to ContextR.Open() in the order in which
     they were generated by ContextS.Seal().

     A high-level protocol MUST be able to detect packet loss and to
     abandon any HPKE state that becomes unsynchronized as a result of
     unrecoverable packet loss. Any packet number a high-level protocol
     assigns to an HPKE message SHOULD be (part of) the AAD passed to
     ContextS.Seal() and ContextR.Open() and it is the responsibility of
     the high-level protocol to specify how that is accomplished.

     A high-level protocol SHOULD provide a means of re-establishing
     synchronized state in the event that contexts get hopelessly out
     of sync. If this feature is provided it MUST NOT open the protocol
     up to any additional attack-- that is, the only way an attacker can
     induce parties to resynchronize is by dropping packets or otherwise
     denying service.

Something along those lines but in your voice.

   But I still maintain that adding AES-SIV is the way to go :-)

   regards,

   Dan.

> On Sat, Feb 13, 2021 at 7:29 AM Dan Harkins <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>
>        Hi Karthik,
>
>     > The HPKE stateful API guarantees that nonces cannot be misused,
>     even if you use AES-GCM or Chacha-Poly. (Of course, you could also
>     add a SIV ciphersuite.)
>     received by the decryptor is a prefix of the stream of plaintext
>     messages sent by the encryptor.
>
>     > In the current design, if two ciphertexts are decrypted
>     out-of-order, both decryptions will fail.
>     > So the problem alluded to in the text above is one of
>     functionality; the application has to ensure (using some
>     meta-data) that it is calling decrypt in the right order.
>     > I do not see how using AES-GCM-SIV is going to solve the above
>     issue; yes, it would allow you to decrypt the plaintext in any
>     order, but  the HPKE receiver would not be able to authenticate
>     the correct order.
>     > Am I missing something?
>
>     >> On 13 Feb 2021, at 00:29, Dan Harkins <[email-masked]
>     <mailto:[email-masked]>> wrote:
>     >>
>     >>
>     >>    Hello again,
>     >>
>     >> [email-masked] <mailto:[email-masked]>
>     [email-masked] <mailto:[email-masked]>

---

From: Richard Barnes <[email-masked]>
Date: Mon, 15 Feb 2021 15:33:07 -0500

Hi Dan,

Thanks for the suggested text.  I adapted it into the document in this PR:

https://github.com/cfrg/draft-irtf-cfrg-hpke/pull/209

Cheers,
--Richard

On Mon, Feb 15, 2021 at 1:33 PM Dan Harkins <[email-masked]> wrote:

>   Actually since this is an external requirement, you could make the title
> of
>> > So the problem alluded to in the text above is one of functionality;
>> the application has to ensure (using some meta-data) that it is calling
>> decrypt in the right order.