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

[Julia Len <[e-mail]>]

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