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

[Chris Brzuska <[e-mail]>]

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] 
>> <mailto:[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] <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
>>>>
>>>>         [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
>>>