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

Chris Brzuska <chris.brzuska@aalto.fi> Tue, 09 June 2020 17:31 UTC

Return-Path: <chris.brzuska@aalto.fi>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 4F0323A0B8A for <mls@ietfa.amsl.com>; Tue, 9 Jun 2020 10:31:52 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.096
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_H4=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 ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id Qj0LuFh24xKb for <mls@ietfa.amsl.com>; Tue, 9 Jun 2020 10:31:50 -0700 (PDT)
Received: from smtp-out-01.aalto.fi (smtp-out-01.aalto.fi []) (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 A38013A0B67 for <mls@ietf.org>; Tue, 9 Jun 2020 10:31:48 -0700 (PDT)
Received: from smtp-out-01.aalto.fi (localhost.localdomain []) by localhost (Email Security Appliance) with SMTP id F2FDC1155E6_EDFC77FB for <mls@ietf.org>; Tue, 9 Jun 2020 17:31:43 +0000 (GMT)
Received: from exng2.org.aalto.fi (exng2.org.aalto.fi []) (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-01.aalto.fi (Sophos Email Appliance) with ESMTPS id 955FE1154A1_EDFC77FF for <mls@ietf.org>; Tue, 9 Jun 2020 17:31:43 +0000 (GMT)
Received: from exng7.org.aalto.fi ( by exng2.org.aalto.fi ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1847.3; Tue, 9 Jun 2020 20:31:43 +0300
Received: from [] ( by exng7.org.aalto.fi ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1847.3; Tue, 9 Jun 2020 20:31:43 +0300
To: <mls@ietf.org>
From: Chris Brzuska <chris.brzuska@aalto.fi>
Message-ID: <682de0fe-41c2-9b96-067b-6cb4b08e1e7c@aalto.fi>
Date: Tue, 9 Jun 2020 20:31:42 +0300
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.9.0
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="------------6DE6494CDDCE855E0C3E470D"
Content-Language: en-GB
X-Originating-IP: []
X-ClientProxiedBy: exng5.org.aalto.fi ( To exng7.org.aalto.fi (
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aalto.fi; h=to:from:subject:message-id:date:mime-version:content-type; s=its18; bh=DMH1T9FSQtU2+Lpp+FORnty7+S+XWc+eMo20e6r1BXk=; b=Z+PNS7W/hOSnWERANUV+QQ5+65BWYUicyqAWf/qIFPwdzRJhxztYjD6g6HF3Ci5sHROsnNzXYFpPiADJY2Y58BCKwF3luhh6ALUduSgmbWxgL6MQm5pv7avo0OBo7ek3pMPqH9Sj3bGs2H59XSqIMPsdjfzgNEzrOX9mPgCG0mQrc7DYsCZFrYJl7tELsYjarDjKimHOREOSOKPNHcF43NEcejgw78LgY5KSpVPzdQQMP+F40uJcMeKHUypxr7iLUZ742ZN6mucp5fLmoIpxhjitZ3LVDPc7GzMPYzQG6NJTxBlVGeXH5qCaqDK3jKzH1XBmEcK+r1OD9YK6Od5vGA==
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/lU3Uu0uzw3Akphcct8NejfkLAyw>
Subject: [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, 09 Jun 2020 17:31:52 -0000

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!


(*) 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.

- The suggested construction has higher parallel efficiency. It 
increases the overall number of HMAC evaluations by 1.

- HMAC is a standard PRF.
- Relies on a unique value, the group_context was suggested.

(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.

- 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.