Subject: [CFRG] Dual-PRF, following IETF 113

From: Nimrod Aviram <[email-masked]>
Date: Mon, 28 Mar 2022 12:56:36 +0300

Hi Everyone,

Thank you for your questions and interest in our construction. You may find
our paper here: https://eprint.iacr.org/2022/065.

Following the meeting, we thought we’d summarize a few points that came up.
We’d be happy to continue the discussion here on the list, and answer
further questions.

The construction can accommodate as many keys as desired. The output key is
indistinguishable from random, even if all but one key is adversarially
chosen. Section 5.4 of the paper elaborates, and we’d be happy to elaborate
further here.

Frederic Jacobs brought up the potential use for MLS: Thank you! We will
contact the MLS WG.

Regarding KMAC: I think people were asking if we can replace HMAC in our
construction with KMAC. We rely on HMAC to supply several properties, both
a PRF and an extractor, so it depends whether KMAC also meets them. KMAC is
claimed to be a PRF in [3], without a proof. There is also some literature
on this, e.g. [5], but in a brief search I could not find specific
PRF-security claims for KMAC. So at a very cursory glance, it looks like
KMAC is a PRF, and then it’d be a question whether it’s also an extractor.
It’d be great if folks could please point us towards concrete analysis, and
then we could give more precise answers.

How we think of existing analysis of TLS 1.3 and other protocols: To be
clear, we are not aware of any error in a proof in this area. However, we
think the starting assumptions for the proofs warrant a close look. For TLS
1.3, the assumptions related to the existing KDFs are usually the PRF-ODH
family of assumptions. These assumptions don’t deal with a single
cryptographic building block, but rather with the combination of HKDF and
Diffie-Hellman. The assumption “basically says that the function value
PRF(g^(uv) , x*) for a DH key g^(uv) looks random, even if given g^u and
g^v and if seeing related values PRF(S^u, x) and/or PRF(T^v , x) for chosen
values S, T, and x”. Brendel et al. [2] showed that the strongest variant
of the PRF-ODH assumption family is achievable in the random oracle model,
but it is implausible to prove even the weaker variants in the standard
model (via algebraic black-box reductions to common cryptographic problems).

@Chris Wood, you wrote: “we seemingly rely quite heavily on this property,
and I would like to understand the implications on past analyses if the
claims do not hold. In particular, can the proofs be recovered?” At first
glance, the answer seems to be negative. Brendel et al. [4] write (Section
5.2, page 27; slightly edited for clarity; note this is different from the
first Brendel et al. reference [2]) “We cannot hope for breakdown
resilience for the … pseudorandomness of HKDF, as non-pseudorandom output
may enable an adversary to distinguish the session key from a random
string”. They write this when discussing the ECDHE-only handshake, where
HKDF feeds the ECDHE shared secret into the data input of HMAC, implying we
hope HMAC is a dual-PRF.

To summarize, existing analysis of TLS 1.3 (e.g. [1]) does not reduce
(only) to assumptions regarding the hash function as a primitive, but
requires assumptions on the combination of DH and HKDF. Section 2 of the
paper (bottom half of page 5) summarizes our findings in this area, and
Section 6 elaborates; Section 7 describes the similar situation with
analysis of Signal.

Best wishes,

Nimrod

[1] Dowling, B., Fischlin, M., Gunther, F., Stebila, D.: A cryptographic
analysis of the TLS 1.3 handshake protocol. Journal of Cryptology 34(4),
1–69 (2021).

[2] Brendel, Jacqueline, et al. "PRF-ODH: Relations, Instantiations, and
Impossibility Results." Cryptology ePrint Archive (2017).

[3] Kelsey, John, Shu-jen Chang, and Ray Perlner. "SHA-3 derived functions:
cSHAKE, KMAC, TupleHash and ParallelHash." NIST special publication 800
(2016): 185.
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf

[4] Brendel, Jacqueline, Marc Fischlin, and Felix Günther. "Breakdown
resilience of key exchange protocols: NewHope, TLS 1.3, and Hybrids."
European Symposium on Research in Computer Security. Springer, Cham, 2019.
https://eprint.iacr.org/2017/1252.pdf

[5] Gaži, Peter, Krzysztof Pietrzak, and Stefano Tessaro. "The exact PRF
security of truncation: Tight bounds for keyed sponges and truncated CBC."
Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2015.
https://link.springer.com/content/pdf/10.1007%2F978-3-662-47989-6_18.pdf

---

From: Gilles VAN ASSCHE <[email-masked]>
Date: Thu, 31 Mar 2022 15:59:35 +0000

Dear Nimrod,

Regarding KMAC: I think people were asking if we can replace HMAC in our construction with KMAC. We rely on HMAC to supply several properties, both a PRF and an extractor, so it depends whether KMAC also meets them. KMAC is claimed to be a PRF in [3], without a proof. There is also some literature on this, e.g. [5], but in a brief search I could not find specific PRF-security claims for KMAC. So at a very cursory glance, it looks like KMAC is a PRF, and then it’d be a question whether it’s also an extractor. It’d be great if folks could please point us towards concrete analysis, and then we could give more precise answers.

Up to its claimed security (see Claim 1 in [6]) and impossibility results, we can reason about KMAC/Keccak as seen as a random oracle and thereby convince ourselves that it is a PRF and an extractor. The validity of this claim is supported by the indifferentiabilty proof of the sponge construction [7] and a substantial amount of cryptanalysis.

Kind regards,
Gilles

[6] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, The Keccak reference, 2011, https://keccak.team/files/Keccak-reference-3.0.pdf
[7] idem, On the Indifferentiability of the Sponge Construction, EUROCRYPT 2008