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

[Richard Barnes <[e-mail]>]

The GroupSecrets are not encrypted under a single key -- they're encrypted
to each joiner's init keys using HPKE.

Good point about the difference in guarantees; I had missed this about
#336.  In the terminology that's in the key schedule now, then, we would
derive the welcome_secret from the member_secret.

Syntically, I might prefer it be an extension as in Commit, but that's
outweighed by my desire not to have extensions in GroupSecrets.  So yeah,
`optional<PreSharedKeys>` seems right, where `PreSharedKeys` is whatever we
put in the Commit extension.

--Richard

On Thu, Jul 30, 2020 at 3:49 AM Konrad Kohbrok <[e-mail]>
wrote:

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