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

[Chris Brzuska <[e-mail]>]

Hi Richard,

I came to the conclusion that none of the concerns you brought up 
affects the nPRF suggestion at its core. The issue of the welcome secret 
is unnecessary (see separate eMail which I just sent since I think that 
the use/generation of the welcome_secret is of independent interest). 
The other interface mismatch which you identified is that the key needs 
to be partially shared before, but this is not a problem: You can share 
the xor of the two input keys or the concatenation of the two keys to be 
xored.

An additional advantage of the updated nPRF construction (in addition to 
better assumptions and parallel computation) is that it combines entropy 
additively, i.e., if several secrets have low entropy, but together, 
they have enough entropy, then extracting from the concatenation of all 
of them will yield a good key although neither of the secret was good. 
This is useful regardless of the number of keys we combine.

Chris

On 24/07/2020 20:53, Richard Barnes wrote:
> Hey Chris,
>
> I was looking again at the key schedule as I was drafting #362 [1].  A 
> couple of things occurred to me:
>
> 1. You can't add the commit secret and PSKs in the same operation, 
> because you want new joiners to put in the PSK, but you don't want 
> them to have to know the commit secret.
>
> 2. The nPRF construction you propose has the same number of HMAC 
> invocations as the chained-HKDF-Extract stuff that's in the current 
> draft / 362.
>
> Given those observations, I wonder how much an nPRF is really buying 
> us.  It's not saving us any HMAC calls, and relative to #362, it would 
> only coalesce two DPRF calls into one nPRF call.
>
> Maybe there's some benefit if there are multiple PSKs?  But even then, 
> it seems like you could add a layer, computing a synthetic PSK from 
> the multiple ones, and keeping the main key schedule simple.
>
> At this point, given the above and the novelty of the nPRF 
> construction, I'm inclined to just stick with HKDF and merge #362 
> instead of #336.
>
> --Richard
>
>
> [1] https://github.com/mlswg/mls-protocol/pull/362
>
> On Tue, Jul 7, 2020 at 5:30 AM Chris Brzuska <[e-mail] 
> <mailto:[e-mail]>> wrote:
>
>     Thank you for the pointer to Carter-Wegman MACs.
>
>     >>> This style of combing hash outputs does affect collision
>     resistance [4], and some discussion on relation to that would be
>     nice to see.
>
>     That's an excellent point. In addition to pseudorandomness, we
>     prove the collision-resistance of our construction. I.e., assuming
>     that no unique value is used twice and assuming that HMAC is
>     collision-resistance, then the final Expand operation guarantees
>     unique outputs. I.e., by including the unique value into the final
>     Expand operation after the xor, the construction recovers from any
>     collisions incurred by the xor.
>
>     Chris
>
>     On 07/07/2020 05:41, Hale, Britta (CIV) wrote:
>>
>>     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]> <mailto:[e-mail]>
>>     on behalf of Chris Brzuska <[e-mail]>
>>     <mailto:[e-mail]>
>>     *Date: *Tuesday, June 9, 2020 at 10:32 AM
>>     *To: *"[e-mail]" <mailto:[e-mail]> <[e-mail]>
>>     <mailto:[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
>>     <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.
>>
>>
>>     _______________________________________________
>>     MLS mailing list
>>     [e-mail]  <mailto:[e-mail]>
>>     https://www.ietf.org/mailman/listinfo/mls
>     _______________________________________________
>     MLS mailing list
>     [e-mail] <mailto:[e-mail]>
>     https://www.ietf.org/mailman/listinfo/mls
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls