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

[Julia Len <[e-mail]>]

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

On Mon, Sep 14, 2020 at 8:03 AM Karthikeyan Bhargavan <
[e-mail]> wrote:

> 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 <
> [e-mail]> wrote:
>
> 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 <[e-mail]> 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:
>
> 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
>> > [e-mail]
>> > https://www.irtf.org/mailman/listinfo/cfrg
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>