Re: [MLS] UPKE for X25519/X448

Karthikeyan Bhargavan <karthik.bhargavan@gmail.com> Tue, 22 October 2019 18:42 UTC

Return-Path: <karthik.bhargavan@gmail.com>
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 BBDE2120918 for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 11:42:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
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 ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id PJddlnvLyLoJ for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 11:42:48 -0700 (PDT)
Received: from mail-wm1-x32a.google.com (mail-wm1-x32a.google.com [IPv6:2a00:1450:4864:20::32a]) (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 A4FC1120913 for <mls@ietf.org>; Tue, 22 Oct 2019 11:42:47 -0700 (PDT)
Received: by mail-wm1-x32a.google.com with SMTP id 3so17166756wmi.3 for <mls@ietf.org>; Tue, 22 Oct 2019 11:42:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=qqYqLW10Y5wyM+sr+qq5f2evRW6Gx7jFf5/ncFmoOPM=; b=q0pfGQE4gWyXC2yYz9Ro7x1yRdhU6xCSAkIXvuqS+mqJBWMCtvygl7ITtIBwy4Uij6 Yq8qn4z/ev28cxGb6kmjBB4rnEQusqwrgwOtvpiDREs8V0QHrH6lv0BS1deoK0sI1CVe ihjOYEcd3XPWCrEX8XQwRM6KGG2GK/IHQPYWVDZNq+YAEluhnf44cmLb5WCWZ6cyrodE dKtjaOALaTIfKO9tTH4RbkubSbQasY7bVFtUN+lXviC4PmVcbjKJN7L0uK0JLVtCp/Mz qe7pNAAq7UYZFRemEFtNkyuBLuzdIfcdiDT7HLhsKSDyN50Q8DT6tJur6a/zUUGnoGgn jYTA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=qqYqLW10Y5wyM+sr+qq5f2evRW6Gx7jFf5/ncFmoOPM=; b=SwW9nMxF4MoAUw+pcYcrhMyEF1L4nIAITYtHdbdZlCLNB7389gmSYHJ2sVpCmhKcDd 2e/UEUQ9MJ4LI/+0x0iz/32ot4xuew8uHR3IonVuOtlNM23Njd+0mDnwzh7ubSiZSavr GCKJqQlEqQi9Q4PmDnlNlXbCf6D7KCFTnKs87YMdn/eNqudH8tDWIXiA3gg+djxxNc/V PGnlh7jDRIVD+tpb10oPqaSwMro5UTC4cF13GG9XcQOaUNVTdkrYO2jDNfrtsteSpob+ WeDdXh4wDYr2jEXXZrKvppExT1q4ClgqoB5iW4PzrnpfkIHvJXJcL50z1bABz243ypGt U0Sw==
X-Gm-Message-State: APjAAAUxpXibUuRaXBKFY8pjjA7R7Fhjghi/csJQwtKw7OrLtnKpclyU 8S0Rxrh6QaadNqgzOANQZXzPicXgsR4=
X-Google-Smtp-Source: APXvYqzH+ZsCnANmmLFDmbmiqSiYRkGPkZlaEQHVj/Gs9xARXA505zsMsMS61pk5xunja92HwKhzWg==
X-Received: by 2002:a1c:f714:: with SMTP id v20mr4404129wmh.55.1571769765776; Tue, 22 Oct 2019 11:42:45 -0700 (PDT)
Received: from [192.168.0.62] (89-156-101-160.rev.numericable.fr. [89.156.101.160]) by smtp.gmail.com with ESMTPSA id d8sm5973809wrr.71.2019.10.22.11.42.44 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 22 Oct 2019 11:42:45 -0700 (PDT)
From: Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>
Message-Id: <16FB72F8-FBAF-4600-8CCE-0C17C3BA8B2A@gmail.com>
Content-Type: multipart/alternative; boundary="Apple-Mail=_87213DAA-37E5-4352-85E5-B2516CAEED99"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\))
Date: Tue, 22 Oct 2019 20:42:42 +0200
In-Reply-To: <CAMvzKsg0895RkaffJA7ZMQxKUr3uF3w-FZ3=T40YUDZd8TkisQ@mail.gmail.com>
Cc: Joel Alwen <jalwen@wickr.com>, Messaging Layer Security WG <mls@ietf.org>
To: Yevgeniy Dodis <dodis@cs.nyu.edu>
References: <71e63449-abba-854d-2962-eac3a64a80d0@wickr.com> <398CD178-3DB6-4D70-B230-3362BE63A3BE@gmail.com> <44b5f5f7-79e1-c9e3-cde0-d75074168469@wickr.com> <5DAAF42C-C4CE-4631-A6E3-A5A5C1D0143A@gmail.com> <CAMvzKsg0895RkaffJA7ZMQxKUr3uF3w-FZ3=T40YUDZd8TkisQ@mail.gmail.com>
X-Mailer: Apple Mail (2.3445.104.11)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/CWzRz2HfONaHZVUbxTKeei7fvE8>
Subject: Re: [MLS] UPKE for X25519/X448
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, 22 Oct 2019 18:42:51 -0000

Hi Yevgeniy,

Thanks for the clarification,

We have been formally analyzing TreeKEM against malicious insiders and it actually has some nice invariants.

In particular: the secret (and private key) for each node is only determined by the members of the
subtree rooted at that node. So if one of these subgroup members is malicious, it can of course
set the subgroup key to whatever it likes. But outsiders do not have the ability to influence a subgroup’s keys.
(There is an exception to this rule for late joiners, making the invariant a bit more complicated than the one I have informally stated here.)

I believe this agains-outsiders guarantee is a good invariant to have, and some of my questions about UPKE were in order to see how we could keep a version of this invariant.

Best,
Karthik



> On 22 Oct 2019, at 19:45, Yevgeniy Dodis <dodis@cs.nyu.edu> wrote:
> 
> Good point, Karthik, we should definitely add this check (and possibly something else).
> 
> As a small theoretical note, in our current model the users are considered honest rather than malicious.
> However, to model and prevent double-join attacks, the attacker is allowed to request honest people not
> to erase their local randomness (e.g., things like d' used above). So this is why in our current description
> we do not have to explicitly worry about d' being malicious.
> 
> We are pretty sure that with a check like the one you suggest we can also withstand adversarial randomness
> for UPKE. But we did not explore this yet - it is on the next to-do list. In general, we don't consider too many insider
> attacks (beside double join) for now, since TreeKEM and variants are not secure against them anyway. Great 
> direction for the future.
> 
> Yevgeniy
> 
> On Tue, Oct 22, 2019 at 12:30 PM Karthikeyan Bhargavan <karthik.bhargavan@gmail.com <mailto:karthik.bhargavan@gmail.com>> wrote:
> Yes, the sender would have to find a “d’” such that HKDF(sksize, d', "", "derive UPKE delta”) falls in a small set of values.
> This is a small risk, but it can be further reduced if we used epk in the derivation.
> E.g. why not define:
> 
> d := HKDF(sksize, d’, epk, “derive UPKE delta”)
> 
> This way, the attacker has to choose d’ based on the node’s old public key, which makes it harder for it to do malicious things.
> 
> -Karthik
> 
> 
> > On 22 Oct 2019, at 17:05, Joel Alwen <jalwen@wickr.com <mailto:jalwen@wickr.com>> wrote:
> > 
> > Good question!
> > 
> > I'll see if I can think of anything intelligent to say about it. :-)
> > 
> > But one thing that comes to mind is that the sender gets to choose "only" d', not d. Instead d := HKDF(d') so to get d=0
> > you'd have to first invert HKDF.
> > 
> > - Joel
> > 
> > On 22/10/2019 17:02, Karthikeyan Bhargavan wrote:
> >> Sorry if this is already in the paper, but a question.
> >> 
> >>> - UPKE-Decrypt(sk, (c1, c2)):
> >>> epk, context := HPKE.SetupBaseR(c1, sk, "")
> >>> d' || m := context.Open("", c2)
> >>> d := HKDF(sksize, d', "", "derive UPKE delta")
> >>> sk' := Mult(sk, d)
> >>> return (m, sk’)
> >> 
> >> I believe it is important for the recipient to do some validation before returning from UPKE-Decrypt.
> >> 
> >> For example, what if the (malicious) sender set d to “0” (whatever that means in the DH group).
> >> This would mean that the resulting key sk’ becomes “0” too, hence a non-member has been able to force the recipient group’s private key to a particular value, which is not ideal.
> >> What conditions should we add to avoid this kind of key-forcing attack from happening?
> >> 
> >> -Karthik
> >> 
> >> 
> >> 
> >>> 
> >>> 
> >>> References
> >>> ----------
> >>> [1] http:\\ia.cr <http://ia.cr/>\2019\1189.
> >>> 
> >>> _______________________________________________
> >>> MLS mailing list
> >>> MLS@ietf.org <mailto:MLS@ietf.org>
> >>> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> >> 
> > 
> > _______________________________________________
> > MLS mailing list
> > MLS@ietf.org <mailto:MLS@ietf.org>
> > https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> 
> _______________________________________________
> MLS mailing list
> MLS@ietf.org <mailto:MLS@ietf.org>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>