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

[Richard Barnes <[e-mail]>]

Think about the order of operations a new joiner goes through:

1. Decrypt the EncryptedGroupSecrets (including the joiner_secret) using
the relevant HPKE private key
2. Compute the welcome_secret, welcome_key, and welcome_nonce
3. Decrypt the GroupInfo using the welcome_key and welcome_nonce

My presumption is that the joiner will only know that it needs the PSK
after step 3, when it can read the GroupInfo extensions.  (See
https://github.com/mlswg/mls-protocol/issues/367)  That means that the
welcome_secret can't depend on the PSK.

On Sat, Jul 25, 2020 at 4:09 PM Chris Brzuska <[e-mail]>
wrote:

> Hi Richard,
>
> I have a quick question: An additional change in your key schedule is that
> the welcome_secret is now derived *before* including the PSK. What is the
> motivation behind this?
>
> Thanks!
>
> Chris
>
> On 24/07/2020 22:18, Chris Brzuska wrote:
>
> I see, thanks for clarifying. Obviously, with these requirements, pull
> request #336 does not work as is. I think that the conceptual issue of how
> to best combine two, three keys and more keys, remains, now with an
> additional requirement to combine two keys separately first.
>
> Will think about it, thanks for clarifying the requirements!
> Chris
>
> On 24/07/2020 21:47, Richard Barnes wrote:
>
> Your confusion is understandable -- the document is wrong right now!  You
> are correct that the current design prohibits new joiners from
> participating in the PSK proof, but that's a bug, not a feature.  The epoch
> secret should verify that *all members of the current epoch* know the PSK,
> not just the ones inherited from the last epoch.
>
> That's why #362 rearranges the key schedule as follows:
>
>                   init_secret_[n-1] (or 0)
>                         |
>                         V
>    commit_secret -> HKDF-Extract = joiner_secret
>                         |
>                         +--> Derive-Secret(., "welcome")
>                         |    = welcome_secret
>                         |
>                         V
>       PSK (or 0) -> HKDF-Extract = member_secret
>                         |
>                         V
> GroupContext_[n] -> HKDF-Extract = epoch_secret
>
> (I also promoted the GroupContext to the main key schedule.)  That's the
> context for my earlier comments.  With that picture, the only thing you're
> coalescing with nPRF would be the latter two HKDF-Extract calls.
>
> Hope that helps,
> --Richard
>
>
>
> On Fri, Jul 24, 2020 at 2:32 PM Chris Brzuska <[e-mail]>
> wrote:
>
>> Hey Richard,
>>
>> thank you for looking into this. I think, I need more explanation to
>> understand the following point:
>> >>>  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.
>>
>> The current draft sais the following about the PSK:
>> "Groups which already have an out-of-band mechanism to generate *shared*
>> group secrets can inject those in the MLS key schedule to seed the MLS
>> group secrets computations by this external entropy. At any epoch,
>> including the initial state, an application can decide to synchronize the
>> injection of a PSK into the MLS key schedule. This mechanism can be used to
>> improve security in the cases where having a full run of updates across
>> members is too expensive or in the case where the external group key
>> establishment mechanism provides stronger security against classical or
>> quantum adversaries."
>>
>> As I understand this paragraph, the PSK is known by all group members and
>> not related to new joiners. Maybe, the requirements and/or design changed
>> in the meanwhile, and I am not aware of it. I interpreted the paragraph
>> this way, since the current construction (posted below for convenience)
>> also requires to know the commit_secret to derive the epoch_secret (from
>> which the welcome_secret is derived). Where did I go wrong?
>>
>> Thanks!
>>
>> Chris
>>
>>                init_secret_[n-1] (or 0)
>>                      |
>>                      V
>>     PSK (or 0) -> HKDF-Extract = early_secret
>>                      |
>>                Derive-Secret(., "derived", "")
>>                      |
>>                      V
>> commit_secret -> HKDF-Extract = epoch_secret
>>
>>
>> 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]>
>> 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]> <[e-mail]> on behalf of
>>> Chris Brzuska <[e-mail]> <[e-mail]>
>>> *Date: *Tuesday, June 9, 2020 at 10:32 AM
>>> *To: *"[e-mail]" <[e-mail]> <[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.
>>>
>>> _______________________________________________
>>> MLS mailing [e-mail]://www.ietf.org/mailman/listinfo/mls
>>>
>>> _______________________________________________
>>> MLS mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/mls
>>>
>>