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

Chris Brzuska <chris.brzuska@aalto.fi> Tue, 07 July 2020 09:29 UTC

Return-Path: <chris.brzuska@aalto.fi>
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 A7DFE3A0895 for <mls@ietfa.amsl.com>; Tue, 7 Jul 2020 02:29:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.096
X-Spam-Level:
X-Spam-Status: No, score=-2.096 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-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=aalto.fi
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 eU5CCT0OyOkx for <mls@ietfa.amsl.com>; Tue, 7 Jul 2020 02:29:47 -0700 (PDT)
Received: from smtp-out-02.aalto.fi (smtp-out-02.aalto.fi [130.233.228.121]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E29C93A0898 for <mls@ietf.org>; Tue, 7 Jul 2020 02:29:45 -0700 (PDT)
Received: from smtp-out-02.aalto.fi (localhost.localdomain [127.0.0.1]) by localhost (Email Security Appliance) with SMTP id 3E423271578_F044085B for <mls@ietf.org>; Tue, 7 Jul 2020 09:29:41 +0000 (GMT)
Received: from exng2.org.aalto.fi (exng2.org.aalto.fi [130.233.223.21]) (using TLSv1.2 with cipher AES256-GCM-SHA384 (256/256 bits)) (Client CN "exng2.org.aalto.fi", Issuer "org.aalto.fi RootCA" (not verified)) by smtp-out-02.aalto.fi (Sophos Email Appliance) with ESMTPS id B1CAC271574_F044084F for <mls@ietf.org>; Tue, 7 Jul 2020 09:29:40 +0000 (GMT)
Received: from exng6.org.aalto.fi (130.233.223.25) by exng2.org.aalto.fi (130.233.223.21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1979.3; Tue, 7 Jul 2020 12:29:40 +0300
Received: from [192.168.1.116] (130.233.0.5) by exng6.org.aalto.fi (130.233.223.25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1979.3; Tue, 7 Jul 2020 12:29:40 +0300
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>
From: Chris Brzuska <chris.brzuska@aalto.fi>
Message-ID: <4ceb1790-ef66-0113-0f59-023ab1e713e7@aalto.fi>
Date: Tue, 7 Jul 2020 12:29:36 +0300
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0
MIME-Version: 1.0
In-Reply-To: <7028_1594089739_5F03E109_7028_154_1_B0D017EB-1A15-4C96-84C8-1E202A5A51EF@nps.edu>
Content-Type: multipart/alternative; boundary="------------63DD37DE72328A6E35F687FD"
Content-Language: en-GB
X-Originating-IP: [130.233.0.5]
X-ClientProxiedBy: exng2.org.aalto.fi (130.233.223.21) To exng6.org.aalto.fi (130.233.223.25)
X-SASI-RCODE: 200
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aalto.fi; h=subject:to:references:from:message-id:date:mime-version:in-reply-to:content-type; s=its18; bh=Sz7EwD0W8ySwrJuqIYI0GgxC/kxo7MmA2IB2VuAII1k=; b=OOlNWh8ASh1fpD+twNtqamKayqkSWGxjEC0ShQtPBgtZvp3uN6kZMrc3sXOzF2q0Fh7GFcQOEM4scPM7cIvIhsTBJ7mxvAMzLNPEEhkAp3OFx4GQO7Dxrx2E5Ma3lRasNeKvhm3F1y/sOSFvU9so3Nxy6X3bWE+uVWbK8I/LWoLN8k8ayTMed2fL4fETSwMkZ6JmOV8leSBKobv4Fwlo7uT2/Rw4ZZIi396/3w9h7i6FF1sCPY16ycPh4NkTNg/SeLwJLV+LTFcjp+FltMtvIMvNk9nNtEo3fMCFzPaNScnhsxNy9Ss9CnrAasZNhAnBVXswpOM0eP/H39waOxwO4w==
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/tzvjhbtsDaJ2I-_KxeEAKKw8hm4>
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: Tue, 07 Jul 2020 09:29:50 -0000

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