Re: [MLS] Adapting Hierarchical Key Derivation for Ephemeral Signatures in MLS
Nick Sullivan <nick@cloudflare.com> Mon, 05 November 2018 10:48 UTC
Return-Path: <nick@cloudflare.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 9379D130F20 for <mls@ietfa.amsl.com>; Mon, 5 Nov 2018 02:48:47 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.47
X-Spam-Level:
X-Spam-Status: No, score=-2.47 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.47, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.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 YGrjRwrqw24D for <mls@ietfa.amsl.com>; Mon, 5 Nov 2018 02:48:42 -0800 (PST)
Received: from mail-oi1-x231.google.com (mail-oi1-x231.google.com [IPv6:2607:f8b0:4864:20::231]) (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 1D76F130DE2 for <mls@ietf.org>; Mon, 5 Nov 2018 02:48:42 -0800 (PST)
Received: by mail-oi1-x231.google.com with SMTP id v83-v6so7019169oia.5 for <mls@ietf.org>; Mon, 05 Nov 2018 02:48:42 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=42adlfFi+09h/4Gao4jzCNej5sYlammWNKOsUR3ra2o=; b=jzIRQbgyUz1zP6PYHtj1OQU2aj2ZpC7RHl4xocYG0KgSi2GwkPW5Jdm0kS+ZCJye/M pMGF2SrE/u9ckzsNYKHY+oy4srZZkHrZJxwZX5lmM6R3znMX7dxl3ZJGn7p6Js43uryZ qxXvolyaKiFeSD57X4hhOzs8JdZu6Q/q2nNSU=
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=42adlfFi+09h/4Gao4jzCNej5sYlammWNKOsUR3ra2o=; b=mmRnVe0dapPCiZvXL/dDo4jDt4wx2CZXsqMlTE1rRm7C9OPshRAJWjEfEZwCaGSJIf S4ffW/rSrerninWykwZhdEzNz/wboinnzja+CzpX9hrk7dW1Fm6EOj80ayjXNkPPNZf7 4BsnGbp9FzLRwJjs2j9nU47d0/Kj0jJP5gZhNVtePTb1CyUItuYifOmOpCCQK479KDbz OlbBEBB672oAscKLPjGnSgYieat6QiUJOaVt8re8vX9RZQsoIiRdFShm0V+HeiDm1Gn9 sOoJ0lnXsTBHWIc0DggUXp91pd8BYES1Mvgd1YgUuWI1lO3LWI9Qz8IFJHDGetrOFLMn JBUA==
X-Gm-Message-State: AGRZ1gJW2P8eWqNESUz6/3PpPR+dx4NacqDKvRfX6HRysW+f7Kbv6oXi fBsPo3OrS146XJ4UKn1lkxKGBcDgahXISBXi6CPjx/4xeM1yKw==
X-Google-Smtp-Source: AJdET5fbC/SR+g3oDKmAstlo8npqn3lYJN/ODZvGOBFEUf4tqv8iaLxKBLDabpe3QmJ8msuKA1xmxx1sSDZRmGgu9g0=
X-Received: by 2002:aca:f00b:: with SMTP id o11-v6mr12855496oih.35.1541414921265; Mon, 05 Nov 2018 02:48:41 -0800 (PST)
MIME-Version: 1.0
References: <CAJR2JpgwrgykbRGCCaEutou7x6-j4SGKFXurKah8rya=jMJ2cw@mail.gmail.com> <CA+9kkMDPp15pCmSwy5TeubZWNii0+uweH1XQATktP6=w_LhZXQ@mail.gmail.com> <CAJR2Jphb7aSVmY7F=wi3a5f5nB_sSNmtCqKBpN9JPE+5RqRnMw@mail.gmail.com> <0D3E4C60-1768-4661-85D5-AFA7B188DB0C@cloudflare.com> <CAJR2JpjDt5zGMNhcwLRL4LBhJXgfzTJiz=xzRopvcb=2QRbJxQ@mail.gmail.com> <CABP-pSSn_+_7QUCOnWDiCNHy8o7DBn8GGNz0OrXh1TUq-j8dPg@mail.gmail.com>
In-Reply-To: <CABP-pSSn_+_7QUCOnWDiCNHy8o7DBn8GGNz0OrXh1TUq-j8dPg@mail.gmail.com>
From: Nick Sullivan <nick@cloudflare.com>
Date: Mon, 05 Nov 2018 17:48:29 +0700
Message-ID: <CAFDDyk_JTp-yVvhiFS0zS5RPVA4Z1x0_KMO=RkDQrwNXGzqpww@mail.gmail.com>
To: Brendan McMillion <brendan=40cloudflare.com@dmarc.ietf.org>
Cc: mls@ietf.org
Content-Type: multipart/alternative; boundary="000000000000d5fdd10579e8a048"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/Mknmx868vBo-u4cwsAyYUL_pwEI>
Subject: Re: [MLS] Adapting Hierarchical Key Derivation for Ephemeral Signatures in MLS
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, 05 Nov 2018 10:48:52 -0000
Brendan, Does verifying these derived keys that are deeper down the tree require knowledge of the public keys up the tree? Are these keys included in the messages (implying a log(depth) increase in message size) or can they be compressed somehow or are they distributed in some other manner? Nick On Tue, Oct 16, 2018 at 7:03 AM Brendan McMillion <brendan= 40cloudflare.com@dmarc.ietf.org> wrote: > > We'd need to know the number of epochs we're allowing for this MLS > session in advance. > > I’d link the paper if I could find it, but there’s a tree construction > that allows an unbounded number of intervals and fast setup. The root key > would sign only two children: a left child which is the root of a tree of > height 1 whose leaf(s) are used for signing data, and a right child. Once > the left child is used up, the right child signs two children in the same > way the root key did, but now the left child is the root of a tree of > height 2. Every time you have to use the right-most node, the left child > gets twice as large. Here’s a diagram, if the description isn’t clear: > https://i.imgur.com/DosZ3Sf.png > > So the signer’s private key and signatures are proportional to log(T), the > current epoch count. > > We're simply trying to limit the impact of device compromise. We're able > to do this more easily for encryption keys, but signatures are more tricky. > > I agree it's valuable that if participant A is offline for a long time and > B’s key is compromised at epoch n, then when A comes back online she can > still trust everything signed by B in previous epochs. I think you can also > get something similar to post-compromise security with the above > construction: Once B is no longer compromised, he would continue walking > the tree and generating new keypairs where the attacker doesn’t know the > private keys. So to sign a message, the attacker would need to certify > their own keypairs. This can be prevented by all the group participants > refusing to accept more than one distinct public key per node in the tree. > > On Fri, Oct 12, 2018 at 10:45 PM Nadim Kobeissi <nadim@symbolic.software> > wrote: > >> Dear Brendan, >> Your proposed scheme could work, too. The disadvantages it presents, it >> seems to me, aren't severe: >> >> - Your proposed scheme seems to have a larger performance overhead: >> each leaf keypair/epoch tuple would have to be generated and signed in >> advance. >> - We'd need to know the number of epochs we're allowing for this MLS >> session in advance. >> - We may not be able to parametrize the choice of upcoming signature >> keys based on a dynamically generated epoch identifier with the same degree >> of freedom that HKD would give us. >> >> > Also, since I didn’t go to the interim, what problem do >> forward-signature signature schemes solve for MLS? >> >> We're simply trying to limit the impact of device compromise. We're able >> to do this more easily for encryption keys, but signatures are more tricky. >> >> Nadim Kobeissi >> Symbolic Software • https://symbolic.software >> <https://symbolic..software> >> Sent from office >> >> >> On Sat, Oct 13, 2018 at 2:43 AM Brendan McMillion <brendan@cloudflare.com> >> wrote: >> >>> Hey Nadim >>> >>> I believe the typical way to build a forward-secure signature scheme is >>> with a certification tree. You’d: >>> >>> 1. Generate a root keypair. >>> 2. Generate N leaf keypairs. >>> 3. Sign each leaf keypair and the epoch it is meant to be used in, with >>> the root keypair. >>> 4. Delete the root private key. >>> >>> Your root public key is what’s distributed to everybody. A signature at >>> a given epoch is the tuple: (leaf public key, sig over leaf key from root >>> key, sig over data from leaf key). >>> >>> Could you talk about why a scheme like the above is not suitable here? >>> Also, since I didn’t go to the interim, what problem do forward-signature >>> signature schemes solve for MLS? >>> >>> On Oct 12, 2018, at 1:22 PM, Nadim Kobeissi <nadim@symbolic.software> >>> wrote: >>> >>> Dear Ted, >>> Thanks for your quick read-through! >>> >>> You seem to be referring to [1], not to [2] as you wrote. In [1], the >>> concept of "hardened" keys is defined and is also ported by [2] into >>> Ed25519. >>> >>> > What I think that means is that if an attacker ever gets access to >>> both an extended public key and any extended private key, we have lost >>> forward secrecy for all the MLS communications covered by any keys derived >>> from any of the epoch pairs. Is that correct? >>> >>> This is correct in the sense that it allows you to rewind the key >>> derivation chain. However, this does not apply to hardened keys. This is >>> precisely why I'm trying to understand how epoch identifiers are agreed >>> upon, in order to see whether we can use them to restrict the HKD logic to >>> use only "hardened" keys in MLS. Since hardened keys in [2] cannot >>> themselves have children, it becomes important to understand whether we can >>> select enough of them for an HKD design in MLS to have a meaningful impact, >>> and how this selection/potential caching of hardened keys would work. >>> >>> > [...] means that Alice must refrain from ever using the parent >>> extended public key has a signing key, but must instantiate signing keys >>> from the n + 0 epoch. >>> >>> This could also be a solution, I suppose, but it sounds like it would >>> result in weaker "signing forward secrecy" (or whatever we're calling this >>> property) than focusing on hardened keys, although I'm frankly not sure off >>> the top of my head. >>> >>> Nadim Kobeissi >>> Symbolic Software • https://symbolic.software >>> Sent from office >>> >>> >>> On Fri, Oct 12, 2018 at 10:03 PM Ted Hardie <ted.ietf@gmail.com> wrote: >>> >>>> Hi Nadim, >>>> >>>> I suspect I'm missing something simple here in your proposal. >>>> According to your reference 2, one of the issues with the derivation of >>>> this type of hierarchical key is: >>>> >>>> that knowledge of a parent extended public key plus any non-hardened >>>>> private key descending from it is equivalent to knowing the parent extended >>>>> private key (and thus every private and public key descending from it). >>>>> This means that extended public keys must be treated more carefully than >>>>> regular public keys. It is also the reason for the existence of hardened >>>>> keys, and why they are used for the account level in the tree. This way, a >>>>> leak of account-specific (or below) private key never risks compromising >>>>> the master or other accounts. >>>>> >>>> >>>> What I think that means is that if an attacker ever gets access to both >>>> an extended public key and any extended private key, we have lost forward >>>> secrecy for all the MLS communications covered by any keys derived from any >>>> of the epoch pairs. Is that correct? >>>> >>>> This appears to make handling required of the parent extended public >>>> key roughly equivalent to the handling of a private key, so that your step: >>>> >>>> Alice sends a public signing key to Bob during epoch n. >>>> >>>> means that Alice must refrain from ever using the parent extended >>>> public key has a signing key, but must instantiate signing keys from the n >>>> + 0 epoch. >>>> >>>> Is that a correct understanding? >>>> >>>> Thanks, >>>> >>>> Ted >>>> >>>> >>>> On Fri, Oct 12, 2018 at 12:47 PM Nadim Kobeissi < >>>> nadim@symbolic.software> wrote: >>>> >>>>> Hello everyone, >>>>> >>>>> I've been working on adapting Hierarchical Key Derivation (HKD) in >>>>> order to obtain some kind of ephemeral signatures that may be useful in >>>>> MLS. I've arrived at a point where I'm optimistic that this is a direction >>>>> worth pursuing and might indeed be a solution to this problem. >>>>> >>>>> HKD was at some point a candidate for how signature keys are managed >>>>> per epoch in the Tor Hidden Service design [0]. HKD logic has also been >>>>> implemented in Bitcoin wallets for a while now [1]. HKD constructions can >>>>> be also derived from existing popular fast signature algorithms such as >>>>> Ed25519 with minimal changes [2], making them an easy fit for MLS. Very >>>>> simply, the functionality that HKD signature schemes bring to MLS is the >>>>> following: >>>>> >>>>> - Alice sends a public signing key to Bob during epoch n. >>>>> - At the onset of epoch n+1, Bob is able to immediately calculate >>>>> Alice's public signing key for epoch n+1 based purely on his knowledge of >>>>> Alice's public signing key for epoch 0. Alice doesn't need to send new >>>>> signing key information to Bob. >>>>> - At this point, Bob can delete Alice's public signing key for >>>>> epoch n. >>>>> - More importantly, Alice herself can delete Alice's private >>>>> signing key for epoch n, keeping only her private signing key for epoch n+1. >>>>> >>>>> The way that this could work in MLS would be heavily based on >>>>> HDKeys-Ed25519 [2]. I'll resist paraphrasing the paper, and instead will >>>>> point out the relevant sections (which are short, well-written and worth >>>>> reading:) >>>>> >>>>> - Section 2 describes the original concept as used for Bitcoin >>>>> wallet derivation. >>>>> - Section 4 describes the modifications to Ed25519 to enable HKD >>>>> constructions. >>>>> - Section 5 describes how private and public child keys are >>>>> generated (Fig. 1 is also helpful.) >>>>> >>>>> My questions: >>>>> >>>>> - How are we deriving epoch identifiers? Are they simply counters, >>>>> or each epoch identified by a nonce that's communicated confidentially? If >>>>> you read [2], you'll see why this can be important. >>>>> - Performance impact seems to be negligible for Montgomery-based >>>>> signing primitives, but I'm interested in more insight on this. >>>>> - Is anyone else interested in having a standard >>>>> HDKeys-Ed25519 implementation? I've been working on one in JavaScript and >>>>> plan to eventually also write one in Go. Perhaps Richard would like to help >>>>> with a C++ version? >>>>> - I'm also interested in hearing your thoughts on this generally. >>>>> >>>>> During the interim meeting (as well as before it), it was frequently >>>>> discussed how ephemeral signatures may be useful for MLS. This also appears >>>>> to be slated as a discussion topic for IETF 103, so it would be great if we >>>>> could continue the discussion there as well. >>>>> >>>>> References: >>>>> [0] >>>>> https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1979 >>>>> [1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki >>>>> [2] https://cardanolaunch.com/assets/Ed25519_BIP.pdf >>>>> >>>>> Nadim Kobeissi >>>>> Symbolic Software • https://symbolic.software >>>>> Sent from office >>>>> _______________________________________________ >>>>> 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 >
- [MLS] Adapting Hierarchical Key Derivation for Ep… Nadim Kobeissi
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Ted Hardie
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Nadim Kobeissi
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Brendan McMillion
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Nadim Kobeissi
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Brendan McMillion
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Raphael Robert
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Nick Sullivan
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Brendan McMillion
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Brendan McMillion
- Re: [MLS] Adapting Hierarchical Key Derivation fo… Jonathan Hoyland