Subject: Re: [Cfrg] Second RGLC on draft-irtf-cfrg-hpke

From: Julia Len <[email-masked]>
Date: Tue, 1 Sep 2020 18:07:24 -0400

The HPKE PSK-based sender authentication scheme could be vulnerable to what
we call a partitioning oracle (PO) attack (the paper [LGR20] is in
preparation -- drafts are available upon request).

Partitioning oracle attacks against HPKE target authenticated encryption
with associated data (AEAD) schemes that are non-committing, meaning
attackers can construct ciphertexts that decrypt without error under more
than one key. HPKE only supports GCM and ChaCha20/Poly1305 for AEAD, both
of which are non-committing.

If decryption failures are observable to the sender of an HPKE ciphertext,
a partitioning oracle attack can recover the PSK from a set of possible
keys S as follows. An attacker can split S into two sets S0 and S1. It can
then run the KEM with the receiver’s public key to get the DH shared
secret, and then derive the set of AEAD keys K for each key in S0. A
ciphertext can be computed so that it decrypts correctly for all keys in K.
The attacker must then be able to determine whether decryption succeeds. If
the ciphertext is decrypted correctly, the correct PSK must be in S0, and
if the ciphertext does not decrypt, the correct PSK must be in S1. The
attacker can then repeat the above steps, setting S appropriately to S0 or
S1, until it finds the correct PSK. This attack enables the adversary to
recover the PSK in time logarithmic in the size of the original set S.

The draft anticipates a decryption oracle being used to attempt to learn
the PSK. The authors observe that with “access to an oracle that allows to
distinguish between a good and a wrong PSK, [the sender] can perform a
dictionary attack on the PSK”. However, because the AEADs are
non-committing, a PO attack can potentially give an exponential speed-up
over a naive dictionary attack, making remote PSK recovery more feasible.
Furthermore, while the scheme specifies it is not suitable for use with
passwords, it does permit short PSKs. (Section 8.4 currently says ‘Using a
PSK shorter than "Nh" bytes is permitted.’, where Nh is the output size of
the key derivation function.)

Our recommended mitigation is changing the HPKE PSK sender auth
construction to use a committing AEAD scheme. For example,
Encrypt-then-HMAC type schemes can be made committing. Unfortunately we are
unaware of any standard that specifies a committing AEAD scheme. A less
disruptive mitigation is to strengthen the language in the HPKE
specification, warning about partitioning oracle attacks and requiring PSKs
to have sufficient min-entropy (say, 128 bits) to make PSK extraction via
partitioning oracle infeasible. Example text for consideration is below:

The second paragraph of Section 8.4 could be modified to say the following:

HPKE is specified to use HKDF as key derivation function. HKDF is not
> designed to slow down dictionary attacks, see [RFC5869
> <https://www.ietf.org/id/draft-irtf-cfrg-hpke-05.html#RFC5869>]. Thus,
> HPKE's PSK mechanism is not suitable for use with a low-entropy password as
> the PSK: in scenarios in which the adversary knows the KEM shared secret
> shared_secret and has access to an oracle that allows to distinguish
> between a good and a wrong PSK, it can perform PSK-recovering attacks. This
> oracle can be the decryption operation on a captured HPKE ciphertext or any
> other recipient behavior which is observably different when using a wrong
> PSK. The adversary knows the KEM shared secret shared_secret if it knows
> all KEM private keys of one participant. In the PSK mode this is trivially
> the case if the adversary acts as sender.

> To recover a lower entropy PSK, an attacker in this scenario can trivially
> perform a dictionary attack. Given a set S of possible PSK values, the
> attacker generates an HPKE ciphertext using each value in S, and submits
> the resulting ciphertexts to the oracle to learn which PSK is being used by
> the receiver. Further, because HPKE uses AEAD schemes that are not
> key-committing, an attacker can mount a partitioning oracle attack [LGR20]
> which can recover the PSK from a set of S possible PSK values, with |S| =
> m*k, in roughly m + log k queries to the oracle using ciphertexts of length
> proportional to k, the maximum message length in blocks. The PSK must
> therefore be chosen with sufficient entropy so that m + log k is
> prohibitive for attackers (e.g., 2^128).

[LGR20] Len, J., Grubbs, P., Ristenpart, T. Partitioning Oracle Attacks. In
preparation, 2020.

Regards,

Julia Len, Paul Grubbs, and Tom Ristenpart

> > Dear CFRG participants,
> >
> > This message starts a second 2-week RGLC on "Hybrid Public Key
> > Encryption" (draft-irtf-cfrg-hpke-05), that will end on August 31st. See
> > https://datatracker.ietf.org/doc/draft-irtf-cfrg-hpke/ for the latest
> > version of the draft.
> >
> > We are having the second RGLC because we didn't have much feedback during
> > the first RGLC and because we have obtained two new Crypto Panel reviews:
> >
> >
> https://mailarchive.ietf.org/arch/msg/crypto-panel/Ol1Mm8JUpmgapgq8ppnBQQSlEkE/
> > https://mailarchive.ietf.org/arch/msg/cfrg/7zhOHPFkCyZC00xLZnsEBT3o6ZU/
> >
> > Please send your comments, as well as expression of support to publish as
> > an RFC (or possible reasons for not doing so) in reply to this message or
> > directly to CFRG chairs.
> >
> >
>
> > Regards,
> > Stanislav, Nick and Alexey
> > _______________________________________________
> > Cfrg mailing list
> > [email-masked]
> > https://www.irtf.org/mailman/listinfo/cfrg

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Thu, 10 Sep 2020 03:31:23 +0200

Hello Julia,

Thanks for this email.

Could you share a draft of [LGR20] so we can study the issue?

-Karthik

> On 2 Sep 2020, at 00:07, Julia Len <[email-masked]> wrote:
> 
> The HPKE PSK-based sender authentication scheme could be vulnerable to what we call a partitioning oracle (PO) attack (the paper [LGR20] is in preparation -- drafts are available upon request). 
> 
> Partitioning oracle attacks against HPKE target authenticated encryption with associated data (AEAD) schemes that are non-committing, meaning attackers can construct ciphertexts that decrypt without error under more than one key. HPKE only supports GCM and ChaCha20/Poly1305 for AEAD, both of which are non-committing.
> 
> If decryption failures are observable to the sender of an HPKE ciphertext, a partitioning oracle attack can recover the PSK from a set of possible keys S as follows. An attacker can split S into two sets S0 and S1. It can then run the KEM with the receiver’s public key to get the DH shared secret, and then derive the set of AEAD keys K for each key in S0. A ciphertext can be computed so that it decrypts correctly for all keys in K. The attacker must then be able to determine whether decryption succeeds. If the ciphertext is decrypted correctly, the correct PSK must be in S0, and if the ciphertext does not decrypt, the correct PSK must be in S1. The attacker can then repeat the above steps, setting S appropriately to S0 or S1, until it finds the correct PSK. This attack enables the adversary to recover the PSK in time logarithmic in the size of the original set S. 
> 
> The draft anticipates a decryption oracle being used to attempt to learn the PSK. The authors observe that with “access to an oracle that allows to distinguish between a good and a wrong PSK, [the sender] can perform a dictionary attack on the PSK”. However, because the AEADs are non-committing, a PO attack can potentially give an exponential speed-up over a naive dictionary attack, making remote PSK recovery more feasible. Furthermore, while the scheme specifies it is not suitable for use with passwords, it does permit short PSKs. (Section 8.4 currently says ‘Using a PSK shorter than "Nh" bytes is permitted.’, where Nh is the output size of the key derivation function.)
> 
> Our recommended mitigation is changing the HPKE PSK sender auth construction to use a committing AEAD scheme. For example, Encrypt-then-HMAC type schemes can be made committing. Unfortunately we are unaware of any standard that specifies a committing AEAD scheme. A less disruptive mitigation is to strengthen the language in the HPKE specification, warning about partitioning oracle attacks and requiring PSKs to have sufficient min-entropy (say, 128 bits) to make PSK extraction via partitioning oracle infeasible. Example text for consideration is below:
> 
> HPKE is specified to use HKDF as key derivation function. HKDF is not designed to slow down dictionary attacks, see [RFC5869 <https://www.ietf.org/id/draft-irtf-cfrg-hpke-05.html#RFC5869>]. Thus, HPKE's PSK mechanism is not suitable for use with a low-entropy password as the PSK: in scenarios in which the adversary knows the KEM shared secret shared_secret and has access to an oracle that allows to distinguish between a good and a wrong PSK, it can perform PSK-recovering attacks. This oracle can be the decryption operation on a captured HPKE ciphertext or any other recipient behavior which is observably different when using a wrong PSK. The adversary knows the KEM shared secret shared_secret if it knows all KEM private keys of one participant. In the PSK mode this is trivially the case if the adversary acts as sender.  
> 
> To recover a lower entropy PSK, an attacker in this scenario can trivially perform a dictionary attack. Given a set S of possible PSK values, the attacker generates an HPKE ciphertext using each value in S, and submits the resulting ciphertexts to the oracle to learn which PSK is being used by the receiver. Further, because HPKE uses AEAD schemes that are not key-committing, an attacker can mount a partitioning oracle attack [LGR20] which can recover the PSK from a set of S possible PSK values, with |S| = m*k, in roughly m + log k queries to the oracle using ciphertexts of length proportional to k, the maximum message length in blocks. The PSK must therefore be chosen with sufficient entropy so that m + log k is prohibitive for attackers (e.g., 2^128).
> 
> [LGR20] Len, J., Grubbs, P., Ristenpart, T. Partitioning Oracle Attacks. In preparation, 2020.
> 
> Regards,
> > https://datatracker.ietf.org/doc/draft-irtf-cfrg-hpke/ <https://datatracker.ietf.org/doc/draft-irtf-cfrg-hpke/> for the latest
> > version of the draft.
> >
> > https://mailarchive.ietf.org/arch/msg/crypto-panel/Ol1Mm8JUpmgapgq8ppnBQQSlEkE/ <https://mailarchive.ietf.org/arch/msg/crypto-panel/Ol1Mm8JUpmgapgq8ppnBQQSlEkE/>
> > https://mailarchive.ietf.org/arch/msg/cfrg/7zhOHPFkCyZC00xLZnsEBT3o6ZU/ <https://mailarchive.ietf.org/arch/msg/cfrg/7zhOHPFkCyZC00xLZnsEBT3o6ZU/>
> >
> > [email-masked] <mailto:[email-masked]>
> > https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>_______________________________________________
> Cfrg mailing list
> [email-masked]

---

From: Julia Len <[email-masked]>
Date: Thu, 10 Sep 2020 12:29:42 -0400

Karthik, I've sent you a draft separately.

The paper isn't ready currently for public distribution, so if anyone else
is interested we can send a draft to you directly.

Thanks,
Julia

On Wed, Sep 9, 2020 at 9:31 PM Karthikeyan Bhargavan <
[email-masked]> wrote:

> The HPKE PSK-based sender authentication scheme could be vulnerable to
> what we call a partitioning oracle (PO) attack (the paper [LGR20] is in
>> To recover a lower entropy PSK, an attacker in this scenario can
>> trivially perform a dictionary attack. Given a set S of possible PSK
>> values, the attacker generates an HPKE ciphertext using each value in S,
>> and submits the resulting ciphertexts to the oracle to learn which PSK is
>> being used by the receiver. Further, because HPKE uses AEAD schemes that
>> are not key-committing, an attacker can mount a partitioning oracle attack
>> [LGR20] which can recover the PSK from a set of S possible PSK values, with
>> |S| = m*k, in roughly m + log k queries to the oracle using ciphertexts of
>> length proportional to k, the maximum message length in blocks. The PSK
>> must therefore be chosen with sufficient entropy so that m + log k is

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Mon, 14 Sep 2020 14:03:32 +0200

Hi Julia,

After going through the paper, we better understand the attack.

One of your proposed countermeasures was to require that the PSK should be a random value with sufficient entropy.
If we were to change the wording in the spec to require that the PSK must be (at least) a 32 byte random value,
that would sufficiently reduce the advantage in the PO attack, yes?

Best regards,
Karthik

> On 10 Sep 2020, at 03:31, Karthikeyan Bhargavan <[email-masked]> wrote:
> 
> Hello Julia,
> 
> Thanks for this email.
> 
>> On 2 Sep 2020, at 00:07, Julia Len <[email-masked] <mailto:[email-masked]>> wrote:
>>

---

From: Julia Len <[email-masked]>
Date: Mon, 14 Sep 2020 15:02:45 -0400

Hi Karthik,

Changing the wording in the spec to require the PSK to be at least a 32
byte random value would be sufficient to prevent the PO attack. It might
also be beneficial to readers for the spec to include why they can't use
low entropy PSKs.

Sincerely,
Julia