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

Konrad Kohbrok <konrad.kohbrok@datashrine.de> Thu, 30 July 2020 07:49 UTC

Return-Path: <konrad.kohbrok@datashrine.de>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BE5AF3A0F66 for <mls@ietfa.amsl.com>; Thu, 30 Jul 2020 00:49:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Level:
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id mcl3RiTDsy8h for <mls@ietfa.amsl.com>; Thu, 30 Jul 2020 00:49:18 -0700 (PDT)
Received: from mout-p-201.mailbox.org (mout-p-201.mailbox.org [IPv6:2001:67c:2050::465:201]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 765FB3A0F62 for <mls@ietf.org>; Thu, 30 Jul 2020 00:49:17 -0700 (PDT)
Received: from smtp2.mailbox.org (smtp2.mailbox.org [IPv6:2001:67c:2050:105:465:1:2:0]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by mout-p-201.mailbox.org (Postfix) with ESMTPS id 4BHMxR3ZMhzQlWK for <mls@ietf.org>; Thu, 30 Jul 2020 09:49:15 +0200 (CEST)
X-Virus-Scanned: amavisd-new at heinlein-support.de
Received: from smtp2.mailbox.org ([80.241.60.241]) by spamfilter01.heinlein-hosting.de (spamfilter01.heinlein-hosting.de [80.241.56.115]) (amavisd-new, port 10030) with ESMTP id DwXGjDVjH2Y4 for <mls@ietf.org>; Thu, 30 Jul 2020 09:49:10 +0200 (CEST)
To: mls@ietf.org
References: <682de0fe-41c2-9b96-067b-6cb4b08e1e7c@aalto.fi> <7028_1594089739_5F03E109_7028_154_1_B0D017EB-1A15-4C96-84C8-1E202A5A51EF@nps.edu> <4ceb1790-ef66-0113-0f59-023ab1e713e7@aalto.fi> <CAL02cgTLkZrUBAD3LLKtgwfg+eNZKWMn0qEJ7=H98pRM=gzYxQ@mail.gmail.com> <5754afd7-f05f-2844-5656-4f4572b49fab@aalto.fi> <CAL02cgTQonKgoh4trxpQxY9ONVvM_b6U+hFif+9Tahf7or9rmg@mail.gmail.com> <0c22bb51-6ef2-a55c-0c3a-14e0b590d7c7@aalto.fi> <064ad211-9f5f-7254-aa48-d7aea0ca2c7f@aalto.fi> <CAL02cgQrHK4-Hv1MQCDt_GcDQ-Rz2mQMCzdprink5jTfetdSAw@mail.gmail.com>
From: Konrad Kohbrok <konrad.kohbrok@datashrine.de>
Message-ID: <6d0b0e16-88a9-96c6-cb45-96262c61f337@datashrine.de>
Date: Thu, 30 Jul 2020 09:49:09 +0200
MIME-Version: 1.0
In-Reply-To: <CAL02cgQrHK4-Hv1MQCDt_GcDQ-Rz2mQMCzdprink5jTfetdSAw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: de-DE
Content-Transfer-Encoding: 8bit
X-MBO-SPAM-Probability: 0
X-Rspamd-Score: -6.43 / 15.00 / 15.00
X-Rspamd-Queue-Id: 24B2217AB
X-Rspamd-UID: 55ec65
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/JijKpfnT33iJ-tcp_SEcrJJcEmw>
Subject: Re: [MLS] Key Schedule: Replace DPRF with multi-input PRF (NPRF)
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 30 Jul 2020 07:49:22 -0000

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 <chris.brzuska@aalto.fi
> <mailto:chris.brzuska@aalto.fi>> 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 <chris.brzuska@aalto.fi
>>>     <mailto:chris.brzuska@aalto.fi>> 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 <chris.brzuska@aalto.fi
>>>>         <mailto:chris.brzuska@aalto.fi>> 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 <mls-bounces@ietf.org>
>>>>>             <mailto:mls-bounces@ietf.org> on behalf of Chris Brzuska
>>>>>             <chris.brzuska@aalto.fi> <mailto:chris.brzuska@aalto.fi>
>>>>>             *Date: *Tuesday, June 9, 2020 at 10:32 AM
>>>>>             *To: *"mls@ietf.org" <mailto:mls@ietf.org> <mls@ietf.org>
>>>>>             <mailto:mls@ietf.org>
>>>>>             *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
>>>>>             MLS@ietf.org <mailto:MLS@ietf.org>
>>>>>             https://www.ietf.org/mailman/listinfo/mls
>>>>             _______________________________________________
>>>>             MLS mailing list
>>>>             MLS@ietf.org <mailto:MLS@ietf.org>
>>>>             https://www.ietf.org/mailman/listinfo/mls
>>>>
> 
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>