Re: [MLS] UPKE for X25519/X448

Yevgeniy Dodis <dodis@cs.nyu.edu> Wed, 23 October 2019 15:59 UTC

Return-Path: <zaumka@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 0C96112004D for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 08:59:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.423
X-Spam-Level:
X-Spam-Status: No, score=-1.423 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.226, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no 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 NGoSqR5WqZuy for <mls@ietfa.amsl.com>; Wed, 23 Oct 2019 08:59:19 -0700 (PDT)
Received: from mail-io1-f45.google.com (mail-io1-f45.google.com [209.85.166.45]) (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 60D9C120043 for <mls@ietf.org>; Wed, 23 Oct 2019 08:59:19 -0700 (PDT)
Received: by mail-io1-f45.google.com with SMTP id w12so25539927iol.11 for <mls@ietf.org>; Wed, 23 Oct 2019 08:59:19 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=q4ZId6xynGTHW4w/iVfHrRATTz0F21MZxNdR6zeSR08=; b=kgcxGwzBM3C/TVrLuR9vPrtQHBlgaWoCqt0CsK+g3kP4H71Knodkqew8ETg/Pkb3bf rLkNEEeL07Gwqn5uCnNMV0ipC9MAHh030iy9AK0t8oGIDzraHYzesv5HoUR3h1QFaFQl waoWQGSod4hrd7zwwinOe87Z7jUQ6GxQFJACA5QWkIGmdQsiRlAzHRizZwOQ1XjQvCNL VhtNkHa2DBHsliKRd2pzuSsMBrdSaUCJ7vyRntOLogDwC6Z4UsolXyjzxQYMu/HcqP/T AUJynYtxmQwkPtXTLi88RDBSl/vRLA+TcMuDdSO8vBQV7GIElbF0TyCOWM7NLHIY3XRT BddA==
X-Gm-Message-State: APjAAAXu55HFBEbr9h2oHOjc6z9pubBg8wMD1kTYwl541O+f5r+CnhIt x//HCYnbNVNTxyIszsfV6Vb7XX0facWsg1DkoY4=
X-Google-Smtp-Source: APXvYqx+8c6ZlxM1ljTqD3LuR+7DXnsfKINziyx5P2Q8SaBFD4A04DLxRa869UFd1aoQandXWCg3JR4JINUTQXGpBfk=
X-Received: by 2002:a05:6638:a0e:: with SMTP id 14mr9963237jan.4.1571846358260; Wed, 23 Oct 2019 08:59:18 -0700 (PDT)
MIME-Version: 1.0
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> <16FB72F8-FBAF-4600-8CCE-0C17C3BA8B2A@gmail.com>
In-Reply-To: <16FB72F8-FBAF-4600-8CCE-0C17C3BA8B2A@gmail.com>
From: Yevgeniy Dodis <dodis@cs.nyu.edu>
Date: Wed, 23 Oct 2019 11:59:08 -0400
Message-ID: <CAMvzKsjoC401fiaQEowGf0sFcfkjbF=rPk+PH5Guv7fF+pie5A@mail.gmail.com>
To: Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>
Cc: Joel Alwen <jalwen@wickr.com>, Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000d35f63059595ffd6"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/DHlGxF3quHadpxB9EXquouPAY3Q>
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: Wed, 23 Oct 2019 15:59:22 -0000

Hi Karthik.

Yes, our scheme already withstands malicious randomness when analyzed as
UPKE in isolation. We actually gave
both definitions in the paper, and satisfy the strongest. But we have not
propagated the stronger UPKE notion
into a formal continuous group key agreement game. Will not be hard, but we
wanted to get the paper out.

We have not captured yes a clean way to get fine-grained resilience to
insider attacks at the level you are suggesting,
since in the general notion there are no trees, or specific TreeKEM
structure (however, our safety predicate for TreeKEM
is scheme specific, --- because it has to be, --- which cold be viewed as
yet another advantage of RTreeKEM). But
resilience to bad update randomness is correlated to the property you are
saying: even though people outside a given sub-ttree
could somehow influence public-secret keys (by being on co-path and using
UPKE in place of PKE), they cannot violate
security of these nodes by being malicious. Hopefully we will add this to
the paper soon, but for now we wanted to make sure
we can support the X-curves, which we hopefully can.

Yevgeniy




On Tue, Oct 22, 2019 at 2:42 PM Karthikeyan Bhargavan <
karthik.bhargavan@gmail.com> wrote:

> 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> 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> 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\2019\1189.
>> >>>
>> >>> _______________________________________________
>> >>> MLS mailing list
>> >>> MLS@ietf.org
>> >>> https://www.ietf.org/mailman/listinfo/mls
>> >>
>> >
>> > _______________________________________________
>> > MLS mailing list
>> > MLS@ietf.org
>> > https://www.ietf.org/mailman/listinfo/mls
>>
>> _______________________________________________
>> MLS mailing list
>> MLS@ietf.org
>> https://www.ietf.org/mailman/listinfo/mls
>>
>
>