Re: [MLS] Adapting Hierarchical Key Derivation for Ephemeral Signatures in MLS

[Brendan McMillion <[e-mail]>]

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 <[e-mail]> 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 <https://symbolic.software/>
> Sent from office
> 
> 
> On Fri, Oct 12, 2018 at 10:03 PM Ted Hardie <[e-mail] <mailto:[e-mail]>> 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 <[e-mail]> 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 <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 <https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki>
> [2] https://cardanolaunch.com/assets/Ed25519_BIP.pdf <https://cardanolaunch.com/assets/Ed25519_BIP.pdf>
> 
> Nadim Kobeissi
> Symbolic Software • https://symbolic.software <https://symbolic.software/>
> Sent from office
> _______________________________________________
> MLS mailing list
> [e-mail] <mailto:[e-mail]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls