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

[Jonathan Hoyland <[e-mail]>]

Hi Nadim,

I was thinking about what was said yesterday about a PFS-style guarantee
for authentication and to me that sounds very much like a compound
authentication property (see def. 2 on page 4 of [1]).
Compound authentication describes the relationship between multiple
authentications within a single compound / layered protocol.
We can view MLS with hierarchical keys as a series of authentications.

If we consider a situation in which each epoch has a separate
authentication step (e.g. proves possession of some new key), then we can
use the lens of compound authentication.
Specifically, compound authentication says that as long as a single
authentication step in a compound protocol was successful and has an
uncompromised key, then all other apparently successful authentication
attempts (past and future) were/will be authentic, even if all the keys
associated with the other layers are compromised.
This is obviously a very strong guarantee, and there are weaker forms that
may be more applicable, such as only requiring past layers to be authentic,
but as a general idea of the type of guarantee we might want from HDKs I
think it has some merit.

Compound authentication neatly describes the authentication goals in the
case of partial compromise, i.e. compound authentication can leverage a
single uncompromised credential to authenticate authentication attempts
using compromised credentials.
For example, if an actor, A, is running a compound protocol with B, and A
has two credentials, c_1 and c_2, with associated secrets, s_1 and s_2,
 and c_2 is compromised (i.e. the attacker knows the associated secret,
s_2), and B completes an authentication step that uses c_2, B should be
able to prove that it was running the protocol with A, even though the
attacker also knows s_2.

The definition in [1] assumes that the keys are independent, which wouldn't
be the case if the master key is compromised, but if we assume that the
master key is uncompromised then the derived keys are in some way
independent.

Does that make any sense?

Regards,

Jonathan Hoyland

[1] Bhargavan, K., Delignat-Lavaud, A., & Pironti, A. (2015,
February). Verified
Contributive Channel Bindings for Compound Authentication
<https://pdfs.semanticscholar.org/e73e/60aef8ebd24491036c7d10c50494eb9d421a.pdf>.
In NDSS.


On Tue, 6 Nov 2018 at 02:35 Brendan McMillion <brendan=
[e-mail]> wrote:

> Sorry, I re-read your message Nick, and realized I could be clearer.
>
> > Does verifying these derived keys that are deeper down the tree require
> knowledge of the public keys up the tree?
>
> The base scheme always sends the full path starting at the root public key
> and ending at the signing key for the current epoch — this makes it
> stateless.
>
> Moving to the next epoch requires one of the parents of the current
> signing key to certify a new key. If all the verifiers are stateful, they
> already know all the parent nodes because the parents were signing keys for
> previous epochs. So we don’t need to re-send the parents, we just need to
> send the newly certified child.
>
>
> On Nov 5, 2018, at 10:26 AM, Brendan McMillion <[e-mail]>
> wrote:
>
> There is the base scheme which has the following properties:
>
>    - Constant-size public key, private key and signature of size approx
>    2*log(T).
>    - Stateless verification.
>    - Not post-compromise secure; can handle minor state regression.
>
>
> You can make these modifications to it:
>
>    - Require verifiers to verify signatures strictly one-after-the-other
>    and update their understanding of the public key.
>    - Require signers to certify the signing key for epoch N with the
>    signing key from epoch N-1, regardless of the tree structure.
>
> to get a construction with these properties:
>
>    - Public key and private key of size approx 2*log(T), constant-size
>    signature.
>    - Stateful verification.
>    - Post-compromise secure; state regression will lock the user out.
>
>
> On Nov 5, 2018, at 2:48 AM, Nick Sullivan <
> nick=[e-mail]> wrote:
>
> 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] <[e-mail]..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 <[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
>>
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>