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

[Julia Len <[e-mail]>]

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