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

Richard Barnes <rlb@ipv.sx> Sat, 25 July 2020 22:01 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 69AEE3A0B3D for <mls@ietfa.amsl.com>; Sat, 25 Jul 2020 15:01:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 11Jcgh-tOWCI for <mls@ietfa.amsl.com>; Sat, 25 Jul 2020 15:01:19 -0700 (PDT)
Received: from mail-qt1-x833.google.com (mail-qt1-x833.google.com [IPv6:2607:f8b0:4864:20::833]) (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 1EF953A0B3C for <mls@ietf.org>; Sat, 25 Jul 2020 15:01:18 -0700 (PDT)
Received: by mail-qt1-x833.google.com with SMTP id s23so9549414qtq.12 for <mls@ietf.org>; Sat, 25 Jul 2020 15:01:18 -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=/zaIqwPTZDNiPLSrIbbdguY5n5oNDFzAlIe4C8IvZYg=; b=uFy302HteHcSzpgR6vx1AqOjh3UYkwhG/sLBMzR+mfnUESwedF7zD5J2/DipT/bokm ApDnblxE4oJj5nlfrlll14DceE7RR4nT5fLd42eZverTSBhNGjAaEnZZE6/blrXiOrVS G8F0EKXI/zzMARSPgOdO9GbuKLyTmYVsdWCJoSwAeJrBhBp325fWSqkmP+puHHSZ7b89 sQ9P9MkPguu2Zu+P3bJ7otHghUSzMGswy+XbYUEZE+oQyBLQV/6hfkRDgBUJbD8ptdlb qNZMjECYg8r6Q93Xy6/OBJgUWapjYCxhMSO8BwiZaX5V8BmuiDJxQTeV1N/oxSQ/I2g1 kjfg==
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=/zaIqwPTZDNiPLSrIbbdguY5n5oNDFzAlIe4C8IvZYg=; b=ne+86YhqBxmDkcUsFhv5rYpuMRudGf69QTkqjQ757syaLlwRu13x/LYn0VoEKqgK+c WslXz3xHKxnP13hiAWH6+04DMSaymVKie/pNdk6GdeKnclcam3FWcCYGN/wJ5WHzJ3h6 2J+hvcgwHB3oh/239AgbkXirREjY1Z2Gn2ZunF40GzIwRklvCKmJk8h2Mwy07YYX+V/Y YFVLgdi4qz/YACnI7jlwptzOObq2Teey0EehPai6aMisJmtUl57yToxAVZmGkavlIgcB R+KwucP/nj68AipLlfHxriQ/9u1eVEibiBFShWzUy+WEm/MzxPsXWzIV1rTZcniZ/Yrp pIwQ==
X-Gm-Message-State: AOAM531L1qIxoZqvtxmSm7YU4AYmppz5W2MDR5SmBe4wuV2KXnd5UBUf gEbGtH1f1Vf78nkDqmqAUDeBbt4wpr69VGwOzKXOKgi89tY=
X-Google-Smtp-Source: ABdhPJw7dRRszfYjQF1tFbUVZhYC/oFOjnk1RWyZcdMfYhb+xe9v0M+TIiMFr2EOxrGT0vx+9PYRK0SOIRKWhXtAbQM=
X-Received: by 2002:ac8:5207:: with SMTP id r7mr15561455qtn.191.1595714477562; Sat, 25 Jul 2020 15:01:17 -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> <7c3c0f7f-58d2-acfb-d5d6-e8e5e80299da@aalto.fi>
In-Reply-To: <7c3c0f7f-58d2-acfb-d5d6-e8e5e80299da@aalto.fi>
From: Richard Barnes <rlb@ipv.sx>
Date: Sat, 25 Jul 2020 18:01:06 -0400
Message-ID: <CAL02cgRVdoKoY8WkneWpA5=ELBsJMfNZF+96VcZ+YBkV6eKH=A@mail.gmail.com>
To: Chris Brzuska <chris.brzuska@aalto.fi>
Cc: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="0000000000009931b905ab4b3a05"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/UdAt_nS2bwl9ulY0w40PMhU2ey0>
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: Sat, 25 Jul 2020 22:01:23 -0000

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 <chris.brzuska@aalto.fi> wrote:

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