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

[Chris Brzuska <[e-mail]>]

Thanks!

Another clarification question: I am confused about why GroupInfo and 
GroupSecrets are not encrypted using the same key? Since the 
welcome_secret can be derived from the GroupSecrets, the use of the 
welcome_secret does not seem to add security. Is this an efficiency 
optimization?

Chris

On 26/07/2020 00:14, Richard Barnes wrote:
> 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] 
> <mailto:[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] <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
>>>>