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

[Konrad Kohbrok <[e-mail]>]

Hi Richard,

Is there a particular reason why the PSK has to be announced inside of the
GroupInfo object? This significantly weakens the authentication guarantees we
get from the PSK. A member that does not know the PSK can now decrypt the
GroupInfo object and learn, for example, about the group composition, group id,
epoch, etc.

Our original proposal in #336 was suggesting to put the PSKId into the
GroupSecrets object and I don't see what we gain by having it in the GroupInfo
object instead. From what I can see it only weakens security and makes the key
schedule design more awkward.

Regarding efficiency: As Chris remarked, the GroupSecrets object is encrypted
under a single symmetric key for all members just as the GroupInfo object, isn't it?

Cheers,
Konrad


On 25.07.20 23: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
>>>>
> 
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>