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

From: "Hale, Britta (CIV)" <[email-masked]>
Date: Tue, 7 Jul 2020 02:41:54 +0000

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 <[email-masked]> on behalf of Chris Brzuska <[email-masked]>
Date: Tuesday, June 9, 2020 at 10:32 AM
To: "[email-masked]" <[email-masked]>
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.

---

From: Chris Brzuska <[email-masked]>
Date: Tue, 7 Jul 2020 12:29:36 +0300

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
>
> [3] Bellare and Lysyanskaya. Symmetric and Dual PRFs from Standard 
> Assumptions: A Generic Validation of an HMAC Assumption.
>
> *From: *MLS <[email-masked]> on behalf of Chris Brzuska 
> <[email-masked]>
> *Date: *Tuesday, June 9, 2020 at 10:32 AM
> *To: *"[email-masked]" <[email-masked]>
> *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.
>
> [1] Pull Request:https://github.com/mlswg/mls-protocol/pull/337 
> <https://github.com/mlswg/mls-protocol/pull/337>
>
> *--------------------------------------------------------------------------------------------------------------------*
>
> *Summary of main points:*
>
> The current key schedule
> - 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:
> - 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.
>
> - 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
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Richard Barnes <[email-masked]>
Date: Fri, 24 Jul 2020 13:53:38 -0400

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 <[email-masked]> 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
>
>
>
>
>
>
>
> *From: *MLS <[email-masked]> <[email-masked]> on behalf of
> Chris Brzuska <[email-masked]> <[email-masked]>
> *To: *"[email-masked]" <[email-masked]> <[email-masked]> <[email-masked]>
> 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.
>
> - The suggested construction has higher parallel efficiency. It increases
> the overall number of HMAC evaluations by 1.
>
> Assumptions:
> - 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.
> - 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.
>
> operation for the psk. For other input keys, it does not seem needed, since
> they were returned from Expand.
> MLS mailing [email-masked]://www.ietf.org/mailman/listinfo/mls
>

---

From: Chris Brzuska <[email-masked]>
Date: Fri, 24 Jul 2020 21:31:53 +0300

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:
> 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.
>
> 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
>
>
> On Tue, Jul 7, 2020 at 5:30 AM Chris Brzuska <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     >>> 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
>
>>     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).
>>
>>     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
>>
>>     [3] Bellare and Lysyanskaya. Symmetric and Dual PRFs from
>>     Standard Assumptions: A Generic Validation of an HMAC Assumption.
>>
>>     *From: *MLS <[email-masked]> <mailto:[email-masked]>
>>     on behalf of Chris Brzuska <[email-masked]>
>>     <mailto:[email-masked]>
>>     *To: *"[email-masked]" <mailto:[email-masked]> <[email-masked]>
>>     <mailto:[email-masked]>
>>     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.
>>
>>     - 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:
>>     - 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.
>>     - 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.
>>
>>     - 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.
>>
>>
>>     [email-masked]  <mailto:[email-masked]>
>     [email-masked] <mailto:[email-masked]>

---

From: Richard Barnes <[email-masked]>
Date: Fri, 24 Jul 2020 14:47:46 -0400

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 <[email-masked]>
wrote:

> because you want new joiners to put in the PSK, but you don't want them to
> have to know the commit secret.
>
> 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
>> This is worth noting from an assurance standpoint: there was discussion
>> at the virtual interims with respect to the current formulation of MLS key
>> (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.
>>
>> security reduction for the design principle here [2]. I include a summary
>> of the main points in the end of this eMail.
>>

---

From: Chris Brzuska <[email-masked]>
Date: Fri, 24 Jul 2020 22:18:03 +0300

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.
>
> (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 <[email-masked] 
>     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.
>
>     "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
>>     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.
>>
>>     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.
>>
>>     On Tue, Jul 7, 2020 at 5:30 AM Chris Brzuska
>>     <[email-masked] <mailto:[email-masked]>> wrote:
>>
>>         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
>>>         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).
>>>
>>>         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.
>>>
>>>         resistance [4], and some discussion on relation to that
>>>         would be nice to see.
>>>
>>>         Britta
>>>
>>>         *From: *MLS <[email-masked]>
>>>         <mailto:[email-masked]> on behalf of Chris Brzuska
>>>         <[email-masked]> <mailto:[email-masked]>
>>>         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
>>>         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.
>>>
>>>         [1] Pull
>>>         Request:https://github.com/mlswg/mls-protocol/pull/337
>>>         - 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
>>>         - 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:
>>>         - 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.
>>>         - 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.
>>>
>>>         - 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.
>>>
>>>

---

From: Chris Brzuska <[email-masked]>
Date: Sat, 25 Jul 2020 23:09:19 +0300

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:

> how to best combine two, three keys and more keys, remains, now with 
> an additional requirement to combine two keys separately first.
>
>> thing you're coalescing with nPRF would be the latter two 
>> HKDF-Extract calls.
>>
>> Hope that helps,
>> --Richard
>>
>>
>>
>>     *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
>>>     construction, I'm inclined to just stick with HKDF and merge
>>>     #362 instead of #336.
>>>
>>>     --Richard
>>>
>>>
>>>         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
>>>
>>>>         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
>>>>         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 suggested construction has higher parallel
>>>>         efficiency. It increases the overall number of HMAC
>>>>         evaluations by 1.
>>>>
>>>>         Assumptions:
>>>>         unique value. I.e., NameNPRF is secure in the same
>>>>         scenarios as DPRF: Keys only repeat if the input keys

---

From: Richard Barnes <[email-masked]>
Date: Sat, 25 Jul 2020 17:14:20 -0400

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 <[email-masked]>
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
>
> 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
>>> 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.
>>> 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.
>>>

---

From: Chris Brzuska <[email-masked]>
Date: Sun, 26 Jul 2020 00:36:44 +0300

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:
> 1. Decrypt the EncryptedGroupSecrets (including the joiner_secret) 
> using the relevant HPKE private key
> On Sat, Jul 25, 2020 at 4:09 PM Chris Brzuska <[email-masked] 
>     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
>
>>     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.
>>
>>>     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.
>>>
>>>     (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
>>>         thank you for looking into this. I think, I need more
>>>         explanation to understand the following point:
>>>
>>>         operation, because you want new joiners to put in the PSK,
>>>         but you don't want them to have to know the commit secret.
>>>
>>>         "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
>>>>         I was looking again at the key schedule as I was drafting
>>>>         #362 [1].  A couple of things occurred to me:
>>>>
>>>>         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.
>>>>
>>>>         construction, I'm inclined to just stick with HKDF and
>>>>         merge #362 instead of #336.
>>>>
>>>>         --Richard
>>>>
>>>>
>>>>             >>> 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
>>>>
>>>>>             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
>>>>>
>>>>>             [3] Bellare and Lysyanskaya. Symmetric and Dual PRFs
>>>>>             from Standard Assumptions: A Generic Validation of an
>>>>>             HMAC Assumption.
>>>>>
>>>>>             <mailto:[email-masked]> on behalf of Chris
>>>>>             Brzuska <[email-masked]>
>>>>>             *To: *"[email-masked]" <mailto:[email-masked]>
>>>>>             <[email-masked]> <mailto:[email-masked]>
>>>>>             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
>>>>>             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.
>>>>>
>>>>>             discussion and security reduction for the design
>>>>>             principle here [2]. I include a summary of the main
>>>>>             points in the end of this eMail.
>>>>>
>>>>>             - uses Extract as a dual pseudorandom function and
>>>>>             assumes that HMAC is a dual pseudorandom function
>>>>>             - 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:
>>>>>             - 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.
>>>>>
>>>>>             - 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.

---

From: Richard Barnes <[email-masked]>
Date: Sat, 25 Jul 2020 18:01:06 -0400

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 <[email-masked]> wrote:

> 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
>
>>> us.  It's not saving us any HMAC calls, and relative to #362, it would only
>>> it seems like you could add a layer, computing a synthetic PSK from the
>>>> That's an excellent point. In addition to pseudorandomness, we prove
>>>> the collision-resistance of our construction. I.e., assuming that no unique

---

From: Chris Brzuska <[email-masked]>
Date: Sun, 26 Jul 2020 02:01:01 +0300

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:

> 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 <[email-masked] 
>     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
>
>>     1. Decrypt the EncryptedGroupSecrets (including the
>>     joiner_secret) using the relevant HPKE private key
>>     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
>>         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
>>
>>>         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.
>>>
>>>>         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.
>>>>
>>>>         (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
>>>>
>>>>
>>>>
>>>>             >>>  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.
>>>>
>>>>             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."
>>>>
>>>>             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
>>>>>             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.
>>>>>
>>>>>             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
>>>>>
>>>>>
>>>>>                 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
>>>>>>                 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.
>>>>>>
>>>>>>                 [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?
>>>>>>
>>>>>>                 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
>>>>>>                 - 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
>>>>>>                 - 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:
>>>>>>                 efficiency. It increases the overall number of
>>>>>>                 HMAC evaluations by 1.
>>>>>>
>>>>>>                 Assumptions:
>>>>>>                 - 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:
>>>>>>                 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.
>>>>>>
>>>>>>                 - 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
>>>>>>                 - Wood: Can we replace HMAC by arbitrary PRF?
>>>>>>                 Yes. For uniqueness of output keys, the PRF needs
>>>>>>                 to be collision-resistant, too.
>>>>>>
>>>>>>

---

From: Konrad Kohbrok <[email-masked]>
Date: Thu, 30 Jul 2020 09:49:09 +0200

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:
> 1. Decrypt the EncryptedGroupSecrets (including the joiner_secret) using the
> relevant HPKE private key
> 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
>>>     epoch secret should verify that *all members of the current epoch* know
>>>     the PSK, not just the ones inherited from the last epoch.
>>>
>>>     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
>>>
>>>
>>>
>>>         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."
>>>
>>>         epoch_secret (from which the welcome_secret is derived). Where did I
>>>         go wrong?
>>>
>>>         Thanks!
>>>
>>>         Chris
>>>
>>>                        init_secret_[n-1] (or 0)
>>>                              |
>>>                              V
>>>>         I was looking again at the key schedule as I was drafting #362 [1]. 
>>>>         A couple of things occurred to me:
>>>>
>>>>         us.  It's not saving us any HMAC calls, and relative to #362, it
>>>>         would only coalesce two DPRF calls into one nPRF call.
>>>>
>>>>         then, it seems like you could add a layer, computing a synthetic PSK
>>>>         from the multiple ones, and keeping the main key schedule simple.
>>>>
>>>>             prove the collision-resistance of our construction. I.e.,
>>>>             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
>>>>
>>>>>             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
>>>>>             formulation of MLS key derivation, which has a “TLS
>>>>>             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
>>>>>             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.
>>>>>
>>>>>             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.
>>>>>
>>>>>             extract operation for the psk. For other input keys, it does
>>>>>             not seem needed, since they were returned from Expand.

---

From: Chris Brzuska <[email-masked]>
Date: Fri, 31 Jul 2020 10:22:10 +0300

Hi Richard,

I came to the conclusion that none of the concerns you brought up 
affects the nPRF suggestion at its core. The issue of the welcome secret 
is unnecessary (see separate eMail which I just sent since I think that 
the use/generation of the welcome_secret is of independent interest). 
The other interface mismatch which you identified is that the key needs 
to be partially shared before, but this is not a problem: You can share 
the xor of the two input keys or the concatenation of the two keys to be 
xored.

An additional advantage of the updated nPRF construction (in addition to 
better assumptions and parallel computation) is that it combines entropy 
additively, i.e., if several secrets have low entropy, but together, 
they have enough entropy, then extracting from the concatenation of all 
of them will yield a good key although neither of the secret was good. 
This is useful regardless of the number of keys we combine.

Chris