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

Richard Barnes <rlb@ipv.sx> Mon, 03 August 2020 22:04 UTC

Return-Path: <rlb@ipv.sx>
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 E3F933A1105 for <mls@ietfa.amsl.com>; Mon, 3 Aug 2020 15:04:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.004
X-Spam-Level:
X-Spam-Status: No, score=0.004 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ipv-sx.20150623.gappssmtp.com
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 KZSRYP7mnk3m for <mls@ietfa.amsl.com>; Mon, 3 Aug 2020 15:04:01 -0700 (PDT)
Received: from mail-qt1-x836.google.com (mail-qt1-x836.google.com [IPv6:2607:f8b0:4864:20::836]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BBBE73A0C6F for <mls@ietf.org>; Mon, 3 Aug 2020 15:03:41 -0700 (PDT)
Received: by mail-qt1-x836.google.com with SMTP id v22so23555651qtq.8 for <mls@ietf.org>; Mon, 03 Aug 2020 15:03:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=syPncUsGbTkHc1jt0hnBdol3k6VCvGQ1voSOLaHkhNU=; b=lool8/ujgC85C97Vhi0vfJwVIZuy/k/FJaMkJ/srf6JUiv5HdRBRciwpOO23TkvZiE d1hK4GbgoRsVmQxtnrepdd6Sv+03VRc8hXzMGTPZGxNBhcOorfSTUkNcc/npHsWiIYiy DoxvYQiGQftAaGxxbIWHM7f3y5kCCEpsThQnE96cIWVl+z+5UhJCF6eRn0KmHABlg+Vl V3Zr+bYLFuWuIC1clGrTvmxf8rUFiN7+oz5OGKjXi4hDpfMynfBBmuDdlAJUGBclulh0 7KwJDcR5v8i546HdujKj6ExEyidkrZDAa5Nu537yoC+bCBtSlc9nhTzCRz4j0TOnPP1C HE3g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=syPncUsGbTkHc1jt0hnBdol3k6VCvGQ1voSOLaHkhNU=; b=Rsaf+6xU9wInZz9gB3l7/MN8RrUgW101Be0nebtBReGOQya982YQF5XChw0EaBaLMb ESniyn8H1/9nTqAPHpjEcxYzWkEO88W6vrZ0J413mRZP5x052BQi54oseMTkCXZ2rNpF jI8WmgtzV2rCdc27/qc8xSCu7hbABJVvneHGOXdynUaVHO35ETsO0rLAN2WO9fliUKX9 ktTgJCyCTwMt4Yh50sFJbyX8iBREteWDtXU5pRqGnHERr6jfHAG8iLm89zKKRy5rltUk G+RDNRgdYbOCqah0A94WSFSGsjLtA/sRyUGQUdf9S7mOOUjWlxZ7HdKOYX5SVAed/tcZ w33A==
X-Gm-Message-State: AOAM530rdOcvrpzjf0Ahe3ud+NWB8Xlxd1Fx6lK8smKdaFi8UJzPBlof +HntDBRfFuLkkyp60dpeUU7ZwJ7mq378eStzHN8ydg==
X-Google-Smtp-Source: ABdhPJw71YO/zOOpOoRXuINX2dbaIes5XJmkS2coLExUu7MAG9M29eElZucqSWnxsebc6VJtl2dn52LcmJSvCw8V5ac=
X-Received: by 2002:aed:34e2:: with SMTP id x89mr18465475qtd.313.1596492220172; Mon, 03 Aug 2020 15:03:40 -0700 (PDT)
MIME-Version: 1.0
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> <6d0b0e16-88a9-96c6-cb45-96262c61f337@datashrine.de>
In-Reply-To: <6d0b0e16-88a9-96c6-cb45-96262c61f337@datashrine.de>
From: Richard Barnes <rlb@ipv.sx>
Date: Mon, 3 Aug 2020 18:03:27 -0400
Message-ID: <CAL02cgRs9WJXkhVaswo0ANg5hUYwLR21Rpqgm_nZa_+ixECHDQ@mail.gmail.com>
To: Konrad Kohbrok <konrad.kohbrok@datashrine.de>
Cc: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000abadb505ac004fda"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/jOczMo1yACYWyCgoVhBLg2_csUE>
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: Mon, 03 Aug 2020 22:04:05 -0000

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 <konrad.kohbrok@datashrine.de>
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 <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
> >
>
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>