Re: [MLS] Re-randomized TreeKEM

Brendan McMillion <> Thu, 24 October 2019 17:59 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6B308120115 for <>; Thu, 24 Oct 2019 10:59:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Z522TMHKihCo for <>; Thu, 24 Oct 2019 10:59:27 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::836]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id EFDEB120802 for <>; Thu, 24 Oct 2019 10:59:26 -0700 (PDT)
Received: by with SMTP id t20so39154378qtr.10 for <>; Thu, 24 Oct 2019 10:59:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=bE4MwQ7oe99jozbDkM4pHYfTNdgpnh/8lFowyTFeq68=; b=QxeqtJoC6xqnXzDCTpcOkyIiH1HURQsRmd9J0GVz62qTTPhbka//eF3d8n5PdXKUt2 NsjgDQSf76zjmRIhBBx9LOSSH/f1gaAbAxTRzcPbQ/ECGcql3OiEIVs46W8MzsrOg3FF l43URw9c0Tt3bGiVoKNeXjh9CeK4pAsd5MgRM=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=bE4MwQ7oe99jozbDkM4pHYfTNdgpnh/8lFowyTFeq68=; b=UZF47YUPwlvmxFJ4/hZ36lLAc/wBt8tAXJMfiaO8L682QcRVfmuNRlNwQlF5HtwwYE xBtOArARPjhm1V9wXkgV4Pl49PcXpeJ+TvXRJDO+DVvjIP4lmXGFCblWoYsCToe/E+MT BioxsYyRhLpZRfQVsduE+tWuVjxrVka31cB1X2ySWJBmaJ//bzxf0gBXaALANWHNSoLg Hvh5ib8aUu1WwjsQnm9D494wA45NrXvbD8+ZbMsuOtnISCnVsju1KrrP7strkPuHkQ8I OHvHVuB70Ko2CsgFhb4434TPV358T2ALsfIeA98uLiw3q2gPkJHUZnTiC+IRg5M0EbKV wLHQ==
X-Gm-Message-State: APjAAAWy71JVPtPnZrVPDjXu3HgWI04/lLgPxqhGdQNDOSOgei1s6s/o HsOLrNQByJYz9CLxBW+griXQzk4mKLnTiyToOzriZjeU+mW4LA==
X-Google-Smtp-Source: APXvYqxOzQU1gWUDmBnDgcnMAo22YeoVgoC3XRlSH/f9ug8mNn4eoWfeKrY7bp+FPfcbHbW+KLZKC7gkdZC8qdyur+Y=
X-Received: by 2002:ac8:6793:: with SMTP id b19mr3027965qtp.99.1571939965522; Thu, 24 Oct 2019 10:59:25 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <> <> <> <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
From: Brendan McMillion <>
Date: Thu, 24 Oct 2019 10:59:08 -0700
Message-ID: <>
To: Konrad Kohbrok <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="000000000000412f520595abcb01"
Archived-At: <>
Subject: Re: [MLS] Re-randomized TreeKEM
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 24 Oct 2019 17:59:30 -0000

> I might be confused what we're talking about here. In RTreeKEM processing a
> random update from a random user allows the processing party to achieve FS.
> Meaning that if previous messages and key material are deleted properly,
> even a
> full compromise of the processing party doesn't give the adversary access
> to
> those deleted messages. In regular TreeKEM on the other hand, processing
> the
> update only gives the sending party FS guarantees.

 Sorry, I think i confused PCS and FS. But still, if Alice and Bob are
talking and Alice is compromised, then having Bob send an Update doesn't
accomplish anything. In RTreeKEM, Alice needs to send and Update and Bob
needs to process it, and then we know that any messages sent after Bob
processes the Update are forward-secure again. I think we probably agree,
we're just talking past each other.

You have a good point in that the deletion of the init_secret gives you some
> form of FS, but it's somewhat fragile in that if the adversary has gotten
> hold
> of an init_secret in the past by some other means (e.g. compromise of
> another
> party), that fragile FS is gone.

Yes, this is the vulnerability that motivated the development of RTreeKEM,
but you're assuming multiple compromises while I wasn't. I want to state my
position again very clearly:

Assume that a single user was compromised and their state was given to an
adversary. Assume that the compromise has been *immediately healed* by an
Update/Remove message affecting the compromised user, meaning that the
adversary is no longer able to read messages. How long is it until we know
that messages sent after the compromise was healed are again
forward-secure, meaning that no future compromises will expose them?

   - *TreeKEM:* You need to wait until everyone sends an Update.
   - *RTreeKEM:* You need to wait until everyone processes the
   Update/Remove. How do you know everyone has processed the Update/Remove,
   and aren't offline with old key material waiting to be compromised? By
   waiting until everyone sends an Update.

Therefore RTreeKEM offers no material improvement over TreeKEM. RTreeKEM's
improvement over TreeKEM is unmeasurable, unenforceable.