[MLS] UPKE and Epoch Forward Secrecy

Karthikeyan Bhargavan <karthik.bhargavan@gmail.com> Thu, 31 October 2019 07:27 UTC

Return-Path: <karthik.bhargavan@gmail.com>
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 6746F120803 for <mls@ietfa.amsl.com>; Thu, 31 Oct 2019 00:27:48 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id YMN1gqdHbypq for <mls@ietfa.amsl.com>; Thu, 31 Oct 2019 00:27:46 -0700 (PDT)
Received: from mail-lj1-x233.google.com (mail-lj1-x233.google.com [IPv6:2a00:1450:4864:20::233]) (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 EA7951200C1 for <mls@ietf.org>; Thu, 31 Oct 2019 00:27:45 -0700 (PDT)
Received: by mail-lj1-x233.google.com with SMTP id 139so5518376ljf.1 for <mls@ietf.org>; Thu, 31 Oct 2019 00:27:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:mime-version:subject:message-id:date:to; bh=YV74r7YaV/FH4ffMVpjM7Hlx6a2uBN+f3ZH0hJemeQY=; b=uOGGEKOf2xzI632v0vyqZ+RBOpSF7OrxJqvkEhsmjYkftpdnhVjmy2T6elG9b+qFLA 3f8AKnITIVAfT3kvBimpWd3SIuVMSN3rhmGQZqRDUj6HF21qIhcgq+ZjWkhFTvSiqtmu s1jLBtJQuggflMU7BVcIGmL75PM5hZwvEhgcyQ5tHl+ZrA28tl1apuPxoqdgeAbzp/VT 3unPCc494uwVU1k2gevhG/sPIPDY108NwCdPiqucYB0qqNNV71nGsg+PKX+j80m/0tDw 9D6rMB2Eey0gm3WCbN9nZvFBwaQeLnPRAjq/QovXAnBEKZTU71W+gXH+Sxl3sJDDlNY1 PV8w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:mime-version:subject:message-id:date:to; bh=YV74r7YaV/FH4ffMVpjM7Hlx6a2uBN+f3ZH0hJemeQY=; b=mMEm0LD/mc4FG9gMnI44VTu+T8/8hGD+r9F6BlRSaE/abB9qp4NVuNen0qjUN6qvU2 2L94FtF7JpoMl5iGy1cWTWtUm/1+X8DP/7DGOch3kVur77LGnZ27J4E75cIr/YuDcMOW DcKmbRV/LxNBqFv1TCnaFS0fH9SpCV0BbGB9eKMKc33XnH/zSNv3XmuZ01mPLYQxf+g9 R790zRQde6wsK9JV4UnfjIShS3jdUq60MIfRH3tZpJ1FtAQ4S5pV68V4JST7ETBlbfYI Z6VRnIaQjfXlkwkF8GDNQfMRz7Yy2oKUI/dB5VIN0VgiLz/YiccawIJcVu8svjjG9ko7 8qAQ==
X-Gm-Message-State: APjAAAXKS/KdvMZOePMiPUQGCtb2viBXh6/bavGU18VoHK1CqJ+4g5Ai CE09zawA5YJQkYat5DFt3JSnEnDYQTu8LQ==
X-Google-Smtp-Source: APXvYqy2tjbtDetcRuVGxILZkoYBvaIVjbxTtHOjw/dFmF1QV/YUnkjscFSlN3L/wTsOdmEqSNcv3Q==
X-Received: by 2002:a2e:87c9:: with SMTP id v9mr2838219ljj.65.1572506863663; Thu, 31 Oct 2019 00:27:43 -0700 (PDT)
Received: from [] (host103-147-static.7-79-b.business.telecomitalia.it. []) by smtp.gmail.com with ESMTPSA id i190sm1397881lfi.45.2019. for <mls@ietf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 31 Oct 2019 00:27:43 -0700 (PDT)
From: Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>
Content-Type: multipart/alternative; boundary="Apple-Mail=_68F0EF5B-575D-423E-A103-A16B7AF4203C"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\))
Message-Id: <2E73A0A5-1D4A-4E76-A2FA-AFFE51598407@gmail.com>
Date: Thu, 31 Oct 2019 08:27:39 +0100
To: Messaging Layer Security WG <mls@ietf.org>
X-Mailer: Apple Mail (2.3445.104.11)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/DMFACd68aZ3iAi2gMmNnBT-qjK8>
Subject: [MLS] UPKE and Epoch Forward Secrecy
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: Thu, 31 Oct 2019 07:27:49 -0000

I must begin by saying that I have been enjoying reading Alwen et al’s work [1] and they make some excellent points.
I particularly like the idea of using a primitive like UPKE (or SkuPke as [2] calls it) to improve the forward secrecy guarantees of TreeKEM.
If this can be made to work with standards-compliant EC implementations, we should definitely consider adding this mechanism to MLS.

For my own better understanding, however, I am trying to figure out the exact forward secrecy improvement this will bring to the protocol.
It is clear from [1] that the *update secret* and each *subgroup secret* in TreeKEM provides weak Forward Secrecy (since each update
only modifies one leaf key, leaving the attacker N-1 members to compromise.)

However, the public key part of TreeKEM is only part of the Forward Secrecy story, we must also account for the “init_secret” which
changes with every update. As far as I can see, the discussion in [1] appears to ignore the “init_secret -> update_secret -> epoch_secret+init_secret”
ratchet which has always been part of MLS. So I don’t fully see how the attack of [1] works, and maybe someone can explain.

One may argue that the goal of TreeKEM is to provide FS and PCS for the epoch_secret, not the update_secret.
If every member of the group is honest, then A sends an update , then B accepts the update (ratcheting forward its init_secret), 
and then B is compromised, then how can the attacker learn the new epoch secret?

Perhaps we are worried about post-compromise forward secrecy (PCFS), but I don’t see any attack on that either.
It is likely I am missing something, so do chime in and explain.


[1] https://eprint.iacr.org/2019/1189.pdf <https://eprint.iacr.org/2019/1189.pdf>
[2] https://eprint.iacr.org/2018/954 <https://eprint.iacr.org/2018/954>