Re: [MLS] Key Schedule: Replace DPRF with multi-input PRF (NPRF)

["Hale, Britta (CIV)" <[e-mail]>]

This is an interesting proposal. It is closely related at a high level to Carter-Wegman MACs (i.e. for random seed r, MAC((k1, k2), m) =  PRF(k1, r) XOR MAC(k2, m)). Quite a few MACs fall into this category in practice. Considering the use of a MAC-based KDF and the proofs of [3] on DPRFs, there is an overlap between NPRFs and extrapolation of the above (based on iteration of the PRF guarantees).

This is worth noting from an assurance standpoint: there was discussion at the virtual interims with respect to the current formulation of MLS key derivation, which has a “TLS precedence”, yet this proposal is not without precedence itself. Ergo, such a change should not necessarily be concerning based on differing from current practice.

This style of combing hash outputs does affect collision resistance [4], and some discussion on relation to that would be nice to see.

Britta



[1] Carter, Wegman. Universal classes of hash functions.
[2] Carter, Wegman. New hash functions and their use in authentication and set equality.
[3] Bellare and Lysyanskaya. Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of an HMAC Assumption.
[4] Bernstein. What output size resists collisions in a xor of independent expansions?



From: MLS <[e-mail]> on behalf of Chris Brzuska <[e-mail]>
Date: Tuesday, June 9, 2020 at 10:32 AM
To: "[e-mail]" <[e-mail]>
Subject: [MLS] Key Schedule: Replace DPRF with multi-input PRF (NPRF)


Hi all,

I would like to open a discussion on a suggestion for a change in the key schedule. In the current draft, we use the Extract function twice as a dual pseudorandom function (DPRF) when combining 3 keys (*) and interleave them with an Expand call.

The suggestion [1] is to replace these 3 calls by a multi-input PRF (NPRF) which is especially designed to return a pseudorandom key when at least one of the input keys is pseudorandom. The new suggestion relies on standard PRF security rather than DPRF-security of Extract.

You can find the accompanying paper with pictures, discussion and security reduction for the design principle here [2]. I include a summary of the main points in the end of this eMail.

Please comment/share your opinion. Thanks!

Chris

(*) commit_secret, PSK and init_secret

[1] Pull Request: https://github.com/mlswg/mls-protocol/pull/337

[2] Paper: http://chrisbrzuska.de/2020-NPRF.html

--------------------------------------------------------------------------------------------------------------------

Summary of main points:

The current key schedule
- uses Extract as a dual pseudorandom function and assumes that HMAC is a dual pseudorandom function
- applies Extract after Expand, i.e., after applying a function which generates a pseudorandom value
- iterates Extract-then-Expand sequentially to combine more than 2 keys

The pull request suggests to
- replace the ad-hoc assumption that Extract is a dual pseudorandom function
- remove Extract steps when applied after Expand
- use a provably secure NPRF construction which allows to combine more than 2 keys and is based on a standard PRF assumption and statistical properties of xor.

Efficiency:
- The suggested construction has higher parallel efficiency. It increases the overall number of HMAC evaluations by 1.

Assumptions:
- HMAC is a standard PRF.
- Relies on a unique value, the group_context was suggested.

Construction:
(1) Use unique value to expand each key and xor the result
(2) expand resulting key, including unique value into the context again

Security argument:
- Pseudorandomness: unique value ensures that each outcome of Expand in (1) is used only once in a xor combination, thus allowing on one-time pad argument of xor.
- Uniqueness of resulting keys: (2) ensures that if HMAC is collision-resistent, then the result is collision-resistent.

Variants:
- It is possible to use an NPRF variant called NameNPRF [2] which has 3 HMAC evaluations more and relies less on the unique value. I.e., NameNPRF is secure in the same scenarios as DPRF: Keys only repeat if the input keys repeat *and* the group context repeats.

Questions/Comments that came up:
- Barnes, MacMillion suggested group_context as unique value
- MacMillion wondered about removal of Extract: One can add an extract operation for the psk. For other input keys, it does not seem needed, since they were returned from Expand.
- Wood: Can we replace HMAC by arbitrary PRF? Yes. For uniqueness of output keys, the PRF needs to be collision-resistant, too.