Re: [MLS] Re-randomized TreeKEM

Joel Alwen <jalwen@wickr.com> Mon, 21 October 2019 21:16 UTC

Return-Path: <jalwen@wickr.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 4FA2B12090B for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 14:16:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=wickr-com.20150623.gappssmtp.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 l_HW6T-PboUL for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 14:15:58 -0700 (PDT)
Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com [IPv6:2a00:1450:4864:20::42f]) (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 5118B1209AF for <mls@ietf.org>; Mon, 21 Oct 2019 14:15:58 -0700 (PDT)
Received: by mail-wr1-x42f.google.com with SMTP id s1so6822067wro.0 for <mls@ietf.org>; Mon, 21 Oct 2019 14:15:58 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=subject:to:cc:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=O7YW+RO3Z41Gi8k10p7Wcg8GRs73Fl90hxJeV7xHkzg=; b=XgnnyWOvlq45qXzDFDPPj/+ImLJwdoK93TejWGPnAf3n/jm46mTbh2+2jgxySDsjYg aP1C19gGfhOTiEcl9dv0BtxmJ5Hv77I5K4r1swi8zNLNokHsV4PdE0TjaiiTVFSlU6vO YWh/ycC2qzHkfj3NnUGg6EfZLnrZEY9IHNQA5QyyUufmZ8yLumm+IyWiYmwyonjAnar7 28PgpbjycTTV9kZFw6lKevyyzmvIt9i0ilrGnOMgY0nYIrnHbXasyCCyhXVjp4rbZOem fpgN+WYrB1Y99hRVfHPFrzl9jHprYaVuntRqJBVPrrsoCpRBVvXXvl2j5M3ven61q1qJ 5cVA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:openpgp:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=O7YW+RO3Z41Gi8k10p7Wcg8GRs73Fl90hxJeV7xHkzg=; b=nRfpV12jvCD1HpLSSRMIrbQdwupYooOxBgJBF8AiIotKzwf6/J2FUnqmW/aQeU8kdU TzAMw2UlAlZ3W81NQ6g82Bf9POFa9A3K7MTJxOmWZDgC1DplPUZcjtDR2TTgp0ULSSf6 7tyeVkpSah8N3pAD7ZuWflfA5FluTLujnyEkAcDV0zbGK4PWYZR+/iXkw2DzvfD3We0t 8oNJZDZQZcoW8UPu3niepzZz2gUO+o7eIEqOf1qsKRYczgLwQN0YfEqBOJL1OhI6s3k0 kpOqEQUrFHfl8Ux1Hx5m6QmraAPYSl0X7mVpbnqXnWdqafWF3C9K9Izz39oyIbbmMd8l 9uuA==
X-Gm-Message-State: APjAAAWPLMbLr+z1NZuDtfIE1kreU7q0e3ha2rQP3aF5rJjFg7EHZy0k eQo4Vnwbsg53AbqaO3jF1VgsERIMFQ8=
X-Google-Smtp-Source: APXvYqwYYCXn7W8OK4GJkWOk026bpGtBPq6iaLXnIhZQ7AEcjTA46GpVko7thqHcw7zdEiJIgBumAQ==
X-Received: by 2002:adf:ed02:: with SMTP id a2mr235895wro.11.1571692556384; Mon, 21 Oct 2019 14:15:56 -0700 (PDT)
Received: from [192.168.1.137] (84-114-27-5.cable.dynamic.surfer.at. [84.114.27.5]) by smtp.gmail.com with ESMTPSA id a13sm17458131wrf.73.2019.10.21.14.15.55 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 21 Oct 2019 14:15:55 -0700 (PDT)
To: Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>
Cc: mls@ietf.org
References: <5b1d9cb1-509a-da7d-1361-188dfe0f21d6@wickr.com> <4BEAE096-9597-4619-ADD4-CE13E899481B@inria.fr> <CAMvzKsgMvLP5mmk8fOoTopKhFM6+EQzognv4Eq_FfMHSs9qwiA@mail.gmail.com> <5673C061-B15D-4DD2-A90C-4F179E82C31A@inria.fr> <133ba15a-037f-6a3b-182c-836b14ba233b@wickr.com> <8E87A52E-62CB-4CC0-A715-F236B03AC9E1@gmail.com>
From: Joel Alwen <jalwen@wickr.com>
Openpgp: preference=signencrypt
Autocrypt: addr=jalwen@wickr.com; keydata= mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY 1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0 xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e 03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7 LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0L7kB DQRciGbxAQgA0Qx9LlxvJ0LGZlZRVyV8kPIxg8pNMmxJwJJ+JnTciW0LpfigfdAvGVf6PU0x 3V6SJKtz8D61c8KLyztxwPGRgJX2TRK3zvTlT5mqqnGYMAANttCF1+8DNpiYOMg3ibPRby46 4JPhMgWgvCJ1vHGu9cghjn1ttWIwBuKBXMc8HgACKYWsYZJiYtFEsnOdsD6aPWCg6NiImoc7 vRwNMKNNtDPxY95Yj4CRiLPVrZje3LyJlA9S+y2/p3w69R4AVLSRzAwDlupjXYs03QdNjGjP 2IR2u8RhstDgqW8+Bk3p7wjJ1kHTHgyox81/aHbnIRGKksPGPMPT3bvbpxevfqZ7ywARAQAB iQE8BBgBCAAmFiEEYFNg9IH2SV6e03O3FR5tDZv8eygFAlyIZvECGwwFCQHhM4AACgkQFR5t DZv8eygbLQf+OHSG6K9qiPdYxe61IR2kZdyogc2ArEGrl6AmcNzySXC8wlnreZo3FjfkD6xV CQWwWDxI7B0JPM86IcfCfn45ADeI8rwm6yYIs00B4ag9Mmo0GQ4kQd2aTy60/QaE2ZSrnEtt 0fuz1G8DGnhPnOnMyCnCnkSNuTNG20OlI0cn5EJSxBS4fXVeBMBaV91DEmvLU6DjL+fOBQPq CXIbFY7XffOmC4VxtAGhTadJ8WmUD8ZezXNs8c40Btpukr7j4piUshITfazPGEMXzTUTkimf fAhNX1QQBsfP9kjfjxBn6jDl+lDJY34mANWwEJ8BKjgr09P0sOz4zjjFL62GcFczQA==
Message-ID: <5715b312-bced-51e9-2b0b-abf681754958@wickr.com>
Date: Mon, 21 Oct 2019 23:15:55 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
In-Reply-To: <8E87A52E-62CB-4CC0-A715-F236B03AC9E1@gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/q-D6MsdbVjsII1KVz9DGr1r2HsM>
Subject: Re: [MLS] Re-randomized TreeKEM
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: Mon, 21 Oct 2019 21:16:00 -0000

> - Every time a member A sends an update, it generates fresh node secrets
> for nodes on the path from A to the root
> - From each node secret, A generates a large number K (= 100)
> private-public encryption keypairs and sends the public keys with the
> update.
> - On receiving the update, each member B stores all K public keys for
> each node in its co-path
> - Each of these public keys can be used only once for sending an update,
> after which the private key is deleted from all recipients.
> - The last public key at each node is not deleted; it can only be
> replaced when one of the members under that node sends a new update
> (with a fresh batch of public keys).
> 
> As far as I understand, the above scheme can be seen as an (inefficient)
> implementation of UPKE, right?

I think your right. I think its similar to UPKE with the caveat that
only K ciphertext can be sent per call to UPKE-KeyGen. (In other words,
as you point out below, after K nodes encrypted to a ciphertext it
effectively becomes blank.)

But I think it does achieves the same properties for TreeKEM as the UPKE
constructions based on re-randomization, at least for the corruption
model we've been looking at.

> Of course, it increases the size of each update by K, and only provides
> FS for K updates, after which some member has to send an update.
> Conversely, it does not require any new crypto algorithm. Is this a good
> baseline to compare UPKE schemes against?

Well, its close but but has the limit on how many ciphertexts can be
sent to any given key-pair which UPKE normally doesnt have. On the other
hand if sender knows the old SK and then they can compute the new SK in
UPKE which is not the case in your construction. So I'd say its (at
least formally speaking) incomparable to UPKE.

- Joël