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

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 <karthik.bhargavan@gmail.com> 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 <jlen@cs.cornell.edu <mailto:jlen@cs.cornell.edu>> 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/ <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/crypto-panel/Ol1Mm8JUpmgapgq8ppnBQQSlEkE/>
>> > https://mailarchive.ietf.org/arch/msg/cfrg/7zhOHPFkCyZC00xLZnsEBT3o6ZU/ <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
>> > Cfrg@irtf.org <mailto:Cfrg@irtf.org>
>> > https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>_______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
>> https://www.irtf.org/mailman/listinfo/cfrg
> 