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

[Chris Brzuska <[e-mail]>]

Right - so, I guess, I have another misunderstanding/confusion. I 
thought that the GroupSecrets, too, are only encrypted once under a 
single symmetric key, and then, this symmetric key is encrypted to all 
new members using HPKE. But I guess I misunderstood and this is not the 
case (why not?), because else, we could just use this same symmetric key 
to encrypt the GroupInfo, too.

Chris

On 26/07/2020 01:01, Richard Barnes wrote:

> Correct, it’s for efficiency.  It lets you encrypt one copy of the 
> GroupInfo and send it to many new joiners.  If the group is large and 
> the Welcome carries the tree, this is a significant savings, 
> especially if you’re adding multiple new members in the epoch.
>
>
> On Sat, Jul 25, 2020 at 17:36 Chris Brzuska <[e-mail] 
> <mailto:[e-mail]>> wrote:
>
>     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
>>>>>