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

"Hale, Britta (CIV)" <britta.hale@nps.edu> Tue, 07 July 2020 02:42 UTC

Return-Path: <britta.hale@nps.edu>
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 A69863A094B for <mls@ietfa.amsl.com>; Mon, 6 Jul 2020 19:42:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-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 m-SbzssFNqua for <mls@ietfa.amsl.com>; Mon, 6 Jul 2020 19:42:01 -0700 (PDT)
Received: from mule.nps.edu (mule.nps.edu [205.155.65.106]) by ietfa.amsl.com (Postfix) with ESMTP id 2C3083A0948 for <mls@ietf.org>; Mon, 6 Jul 2020 19:42:01 -0700 (PDT)
X-ASG-Debug-ID: 1594089718-0e394569e974680001-bGA3T6
Received: from mail.nps.edu (skywalker.ern.nps.edu [172.20.4.117]) by mule.nps.edu with ESMTP id xmfFcZeh2D3ZU3W3; Mon, 06 Jul 2020 19:41:58 -0700 (PDT)
X-Barracuda-Envelope-From: britta.hale@nps.edu
Received: from skywalker.ern.nps.edu (172.20.4.117) by skywalker.ern.nps.edu (172.20.4.117) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.1.1531.3; Mon, 6 Jul 2020 19:41:58 -0700
Received: from NAM11-BN8-obe.outbound.protection.outlook.com (104.47.58.173) by skywalker.ern.nps.edu (172.20.4.117) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.1.1531.3 via Frontend Transport; Mon, 6 Jul 2020 19:41:58 -0700
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=dXUBTXvmvrIhCNcV45lPTM68MfrQ4eJsncTQoJ2eyAHooCo5X/dxTVkXEJInnJv+woiG1TjEe3uxKxZdlhN4MiDodforydo24Tx+u1Z1t0yNT20Teponq1U0vj3I05Amg8Bxt6K+bqeYy43Wo51Bxb45A0lD6EOVsElgU8FlAMBklKvdLeTzOG0Knm51ctJRdolNlKE98oPC9ZT3iP4/fF+7YNAtJnbhUJaSjbtHHT6HFTjTvQqCw10ID5f9DUg84zbLTxwmS8ORXGRztuxKNJW3BNNHbr09L/MpffsLm/MjdjMoqb6Qc+OkwEODzEFKbuQJsRKmqe2s9RO2Hhxyuw==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=xCaXWS706zdNp9Tv5nFclkf+RS2VOM87RH2ktKcIOjw=; b=XwxsxyZocWVxspkYhPQrFLqiF9i4qVT0lfYtgZBBTT10SZoOKgv5QOb8V5IyjjfDf0iZaY5JJOWtQcvTpGYc1nAT9vo4x9wwRPd9/sz+jNwf3i19gZc91FLtfExWqf9J7SuxXlET2j/+fkdeePQxbh2qnauCHsXEKnBIZxAzmD1GtlOvvbVIRNMPpS1ROMyqZouQ2G66LyD8yzFBfP+utJ7+o0ypN3yHIKJk7mHZwtjM5mZR7BEXNA/tI+ojNkCwZ3ZxWL/yUKcsh4eHZF5qE3T6pHZW0pHc6Q4VBwS5imKd/ZLMwjsNjlSpw/f2dM37niN1cY8lyrBjpeBf4iNoIQ==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=nps.edu; dmarc=pass action=none header.from=nps.edu; dkim=pass header.d=nps.edu; arc=none
Received: from MWHPR13MB1072.namprd13.prod.outlook.com (2603:10b6:300:13::19) by MWHPR1301MB2029.namprd13.prod.outlook.com (2603:10b6:301:36::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3174.8; Tue, 7 Jul 2020 02:41:55 +0000
Received: from MWHPR13MB1072.namprd13.prod.outlook.com ([fe80::9080:78ca:a64b:304b]) by MWHPR13MB1072.namprd13.prod.outlook.com ([fe80::9080:78ca:a64b:304b%4]) with mapi id 15.20.3174.020; Tue, 7 Jul 2020 02:41:54 +0000
X-Barracuda-Effective-Source-IP: UNKNOWN[2603:10b6:301:36::12]
X-Barracuda-Apparent-Source-IP: 2603:10b6:301:36::12
From: "Hale, Britta (CIV)" <britta.hale@nps.edu>
To: Chris Brzuska <chris.brzuska@aalto.fi>, "mls@ietf.org" <mls@ietf.org>
Thread-Topic: [MLS] Key Schedule: Replace DPRF with multi-input PRF (NPRF)
X-ASG-Orig-Subj: Re: [MLS] Key Schedule: Replace DPRF with multi-input PRF (NPRF)
Thread-Index: AQHWPoPnV6XFdyfMMkWRCdiY8/bkhKjt41EA
Date: Tue, 7 Jul 2020 02:41:54 +0000
Message-ID: <B0D017EB-1A15-4C96-84C8-1E202A5A51EF@nps.edu>
References: <682de0fe-41c2-9b96-067b-6cb4b08e1e7c@aalto.fi>
In-Reply-To: <682de0fe-41c2-9b96-067b-6cb4b08e1e7c@aalto.fi>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/10.10.17.200615
authentication-results: aalto.fi; dkim=none (message not signed) header.d=none;aalto.fi; dmarc=none action=none header.from=nps.edu;
x-originating-ip: [2601:647:cb00:2941:c9af:a9c8:ee9b:400e]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: f15ce72d-c033-4ac1-ee06-08d8221f4fb9
x-ms-traffictypediagnostic: MWHPR1301MB2029:
x-microsoft-antispam-prvs: <MWHPR1301MB2029A4B8B5088D7F3A99C87EFB660@MWHPR1301MB2029.namprd13.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:9508;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: m1rrxdzDxYEVwGRwdM/hbRlREJbL/vTuTag66r9rhr+AujmhPClhGWvIdhHts9IF/x5PJU37D7k44ToCNMdMwhodJmyP5UFMQzLuq173Jfl8ZI4w4sfGT+ueqexdcOH5RPsTvi1kUMnvAbTFQ8IUH52tjq6x8qB3qjQlLF21cjnw1ZCd3z2J5oqPTAlHbhYDD6GxlDyPwlwDv/0k+90azA7I41f+1pz+V5/VIfjOu31EAlA4tYSKIvtIt3MykSvNdKabuyjn5PxmjC38jT6yVF/GfcmrshAbbSNJxqGFYIgLN3pKKegc1glz72RDZyKVkbpr2lDfKpZFGf7fBMM41iglsqLcMVdkR8VawKcONiW/vBbhYhkSSLr11nP2eL6d5EODHZwhm1DBgOnLS5ViYA==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:MWHPR13MB1072.namprd13.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(376002)(39860400002)(346002)(396003)(366004)(136003)(8676002)(8936002)(33656002)(966005)(478600001)(5660300002)(2906002)(91956017)(86362001)(75432002)(66446008)(64756008)(66556008)(66476007)(83380400001)(36756003)(6512007)(66946007)(76116006)(186003)(21615005)(83080400001)(110136005)(53546011)(71200400001)(2616005)(166002)(6486002)(316002)(786003)(6506007); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: Ah1sEcHGZmuGCb7Q97A6kAZcm1KBYJdkhVakAIcVkIe4KsNra6WMfTN5R90VEPXqfTFKOvmFUql7AsCOFoXF9nBsTnwxg0ryLcvfSDUCAjHsImtABDLPBCe+Td3B1GeU1HPq08uu5/bfGChq53su+vgkf8SmnQopnfctHT2XPV+DpCNE8ZTgGtdzv+PlbPBaC6Ng9tCngx8rHro1ZPOLLMKRPS26rXqFQh9dJsPiwvAxSAdnu1VkwT9cGvrKGAuPifHJiBGVcePkrLy48syKUERdCYm3dNXJ+gmC0GUjNE209aoFKhr2C58MDFduPQM9tpld94nL0fHqrDuViR4sCWu3y7EaJpeOdKPmslp6Vutr3vPI0hcjEoSmgDras2fyK9wT2pfgEsMHsfi8s3w6ODpx2t7smp0HyLYJh41m1dNzjaKyZ+JRFJMbJSclCMEf+CIJHVUErKKqCQPg5orkU/HVFRqA6ENJR5sPTdU7en6rjFJKRWq8/7fdjIT2xRALfeSCTlJd42fke6KOcywAdOy/26WE17MNnBuUmILJHSuRykqnX5JLErSQo1Mo42Lr
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_B0D017EB1A154C9684C81E202A5A51EFnpsedu_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: MWHPR13MB1072.namprd13.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: f15ce72d-c033-4ac1-ee06-08d8221f4fb9
X-MS-Exchange-CrossTenant-originalarrivaltime: 07 Jul 2020 02:41:54.8291 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 6d936231-a517-40ea-9199-f7578963378e
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: WI013Q/xFxW/QG2Q+Rq4hIc/leg01264Oxz8vyTpAXKJpNnon/LVaHhEOODc7sYXV9f7pnEz3sPuAuHN+c6QUQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR1301MB2029
X-OriginatorOrg: nps.edu
X-Barracuda-Connect: skywalker.ern.nps.edu[172.20.4.117]
X-Barracuda-Start-Time: 1594089718
X-Barracuda-URL: https://205.155.65.106:443/cgi-mod/mark.cgi
X-Virus-Scanned: by bsmtpd at nps.edu
X-Barracuda-Scan-Msg-Size: 12329
X-Barracuda-BRTS-Status: 1
X-Barracuda-Spam-Score: 0.00
X-Barracuda-Spam-Status: No, SCORE=0.00 using global scores of TAG_LEVEL=1000.0 QUARANTINE_LEVEL=1000.0 KILL_LEVEL=9.0 tests=HTML_MESSAGE
X-Barracuda-Spam-Report: Code version 3.2, rules version 3.2.3.83027 Rule breakdown below pts rule name description ---- ---------------------- -------------------------------------------------- 0.00 HTML_MESSAGE BODY: HTML included in message
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/ljfbu6J2WxLeHKIqMDHCW7XCA5Q>
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 02:42:04 -0000

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

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