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

[Chris Brzuska <[e-mail]>]

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