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

[Nick Sullivan <[e-mail]>]

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=
[e-mail]> 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 <[e-mail]>
> 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 <[e-mail]>
>> 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 <[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
>>> Sent from office
>>>
>>>
>>> On Fri, Oct 12, 2018 at 10:03 PM Ted Hardie <[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
>>>>> [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
>>>>> [e-mail]
>>>>> https://www.ietf.org/mailman/listinfo/mls
>>>>>
>>>> _______________________________________________
>>> MLS mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/mls
>>>
>>>
>>> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>