Subject: [Mathmesh] A different approach to key escrow

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 2 Sep 2019 17:20:30 -0400

[ccd to CFRG for comment]

At the moment, the approach used to escrow Mesh keys is

* Generate a master secret of at least 128 bits
* Use the master secret to derive an AES 256 encryption key and
initialization vector under which the private key information is encrypted.
* Use a content digest of the master secret as the identifier under which
the escrow record is stored on some sort of service (TBS).
* Use Shamir secret sharing to split the master secret  n out of m ways

This works with any public key algorithm but it requires a service. It has
since occurred to me that I may have gone down a blind alley because I
designed this part of the system back when RSA was still the default
algorithm (we were discussing the CFRG curves at the time). I am now
thinking about using this approach:

* Generate a master secret of at least 128 bits
* Use a KDF to generate the master key pairs for Encryption and Signature
from the master secret
* Use Shamir secret sharing to split the master secret  n out of m ways

Thoughts?

One side benefit of this approach is that it becomes quite easy to give
test vectors, just give the master secret used to generate the key pairs.

I know 128 bits is short, my preference is for 256 bits. But given the
number of times this ends up going through SHA-2-512, I am not really
worried.

---

From: Michael Richardson <[email-masked]>
Date: Tue, 03 Sep 2019 01:07:59 -0400

Phillip Hallam-Baker <[email-masked]> wrote:
    > This works with any public key algorithm but it requires a service.

...

    > Thoughts?

I don't understand how the need for the service is different.

    > test vectors, just give the master secret used to generate the key

please expand.

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 3 Sep 2019 10:51:11 -0400

OK so here is the difference.

In each case

Alice's master secret is
     97 BE C3 8C  EC 32 E3 A8  14 BE 38 AC  49 B3 58 D0

This has the UDF representation:
   ECL3-5Q4M-5QZO-HKAU-XY4K-YSNT-LDIA

We can split that using shamir secret sharing:

   f(1) = SAYE-UHOY-TVZO-LPGT-ZAGE-7JUW-6MTJ-I
   f(2) = SAYX-4HWP-3753-L4P3-N4S6-C2G4-QVPA-A
   f(3) = SAZD-HQNJ-KSDK-HAY7-BIFO-34Y2-NH7O-C
   f(4) = SAZW-WBTE-7MJ2-44B6-TC5X-KRKQ-UEEW-U
   f(5) = SA2C-H3IC-2ORN-NOK2-DM3X-OX37-FJ6W-Q

The difference is how we generate the private key pairs.

What is done now is that the Master Profile key pairs for encryption and
signature are generated in the normal way. The private keys are wrtiten out
to an escrow record that is encrypted under ECL3-5Q4M...

So recovery requires at least three of the key shares plus the encrypted
escrow record.

The other way to go about it is to use a KDF to generate the private keys
for the master profile:

Signing Key = HKDF ( [97 BE C3 8C EC 32 E3 A8 14 BE 38 AC 49 B3 58 D0],
"mmm/mesh-signature/Ed448". 448)
Escrow Key = HKDF ( [97 BE C3 8C EC 32 E3 A8 14 BE 38 AC 49 B3 58 D0],
"mmm/mesh-escrow/X448", 448)

So now recovery of the escrow record ONLY requires the master secret
ECL3-5Q4M-5QZO-HKAU-XY4K-YSNT-LDIA.
There is no encrypted escrow record.

Pros: More convenient.
Cons: The private keys have less ergodicity and are related by means of the
HMAC function.

If we are confident of our algorithms being secure, 2^128 is an infeasible
work factor. And if you look into how the scheme is implemented, we are not
talking about SHA-2-512 (x), we are talking about SHA-2-512 ( SHA-2-512 (
SHA-2-512 ( SHA-2-512 (x)  )  )  ).

If we are not confident of our algorithms being secure, we can use any size
work factor we like up to the size of our private key size. The recovery
shares just get a bit larger.

What I like about this is that I can easily specify an example key set just
by giving the master secret.

On Tue, Sep 3, 2019 at 1:08 AM Michael Richardson <[email-masked]>
wrote:

> ....
> Mathmesh mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mathmesh
>

---

From: Nico Williams <[email-masked]>
Date: Tue, 3 Sep 2019 13:07:30 -0500

> * Use Shamir secret sharing to split the master secret  n out of m ways

I don't see why in the first case you'd need a separate service to store
the private keys encrypted in the master secret.  All the entities that
hold secret shares can also hold copies of the encrypted record along
with the secret shares.

In any case, both of these approaches have similar security properties.
Most importantly, compromise of a master secret compromises all the
private keys it protects.

However, you might find it difficult to generate key pairs from a master
secret, especially if you ever need to generate keys on a hardware
token.  If you won't have that requirement, and if you're willing to
have that as an anti-requirement, then the second scheme is simpler,
indeed, and the entities that store key shares will need to store
smaller records.

> number of times this ends up going through SHA-2-512, I am not really

In a PQ world you want 256 bits of entropy, otherwise 128 bits is
sufficient.

Nico
--

---

From: Michael Richardson <[email-masked]>
Date: Wed, 04 Sep 2019 02:47:07 -0400

> OK so here is the difference.

okay, thank you.
I didn't realize the "done now" version encrypted the private keys like that.
I assumed in my brain that it would always be the KDF version :-)

>ECL3-5Q4M-5QZO-HKAU-XY4K-YSNT-LDIA. There is no encrypted escrow record.

I'm confused here.  Isn't the private key is deterministically created from the
master key, why do we need an escrow key?   Won't the key need to be numbered
so that one knows which of potentially many pieces are generated? Or is
there a master key for each key that Alice needs to generate?

    > Pros: More convenient.  Cons: The private keys have less ergodicity and
    > are related by means of the HMAC function.

I think that it's okay for the reasons you gave.

Nico Williams <[email-masked]> wrote:
    > I don't see why in the first case you'd need a separate service to
    > store the private keys encrypted in the master secret.  All the
    > entities that hold secret shares can also hold copies of the encrypted
    > record along with the secret shares.

This allows the secrets to split and sent to appropriate entities once at the
beginning of the process, and they never need to be updated again.  Alice
can generate as many keys (and as frequently) as she wishes, interacting only
with the escrow service.  Assuming that I understand correctly.

    > However, you might find it difficult to generate key pairs from a
    > master secret, especially if you ever need to generate keys on a
    > hardware token.  If you won't have that requirement, and if you're
    > willing to have that as an anti-requirement, then the second scheme is
    > simpler, indeed, and the entities that store key shares will need to
    > store smaller records.

You are saying: If you use a hardware token, then you need the escrow service.
Isn't it the case that some hardware tokens have no mechanism to get the
private key out?  I guess they are SOL regardless of scheme.

Couldn't we generate per-key escrow keys from the master key using
the same KDF mechanism?  Doesn't that get us the best of both worlds,
with the confusion as to how the different 

-- 
]               Never tell me the odds!                 | ipv6 mesh networks [ 
]   Michael Richardson, Sandelman Software Works        | network architect  [ 
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 5 Sep 2019 22:26:22 -0400

> there a master key for each key that Alice needs to generate?

Ah, the escrow key is the 'master escrow key' that may be used to create an
escrow record for the user's application keys should they choose.

So let us imagine that I am using OpenPGP and disk level encryption. I will
have an encryption key for both applications. I might not want to escrow
the encryption keys for the applications at all but it I did, I could
create key shares for those applications as for my mesh signature key or I
could just escrow them to my mesh escrow key.

Sorry for the confusion. There are two different levels of encryption going
on.

> with the escrow service.  Assuming that I understand correctly.

Allowing escrow of the secrets alone allows them to be protected using
steganographic techniques.

For example, let us say we want to hide the secret
SAYE-UHOY-TVZO-LPGT-ZAGE-7JUW-6MTJ-I

So lets render it in Base-32768-English which uses a dictionary of 32678
words to represent the code points. It (might) now become

Marmalade Snorkel Tuna Smoked Perambulate Throat Wombat Perfume Dredging
Tufted

That is something I can read to someone over a (secure) telephone line or
write down in a book

> private key out?  I guess they are SOL regardless of scheme.

I agree. If someone is using a hardware token, the hardware token needs to
manage the escrow mechanism itself (e.g. like the way Luna cards do). But
it will in any case need a way to import a private master key generated
elsewhere.

> with the confusion as to how the different

Hmm... that might be the way to do it. The only problem is that then you
need access to the offline master to be able to generate application key
sets and the idea of the offline master is that you should only need to
ever use it when changing your administration device.

---

From: Michael Richardson <[email-masked]>
Date: Sun, 08 Sep 2019 12:45:36 +0100

I understand now. The master escrow key can be used to escrow both asymmetric
private keys, but also to escrow session-level keys used for specific
purposes (such as the disk encryption example)

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 9 Sep 2019 11:09:10 -0400

> purposes (such as the disk encryption example)

Yes, sorry for the confusion. I am trying to unpack this all and make two
video presentations describing first what the Mesh is trying to do and
second the components used to do it.

The three big problems I see in Internet security are
1) Managing and credentialing the users keys across their many devices.
2) Managing and accepting contact information including public keys of
other users and services
3) Securing data at rest.

The mechanism required to address any one of these by itself is only
slightly less than the mechanism required to solve all three

---

From: Nico Williams <[email-masked]>
Date: Mon, 9 Sep 2019 11:38:14 -0500

On Thu, Sep 05, 2019 at 10:26:22PM -0400, Phillip Hallam-Baker wrote:
> >     > I don't see why in the first case you'd need a separate
> >     > service to store the private keys encrypted in the master
> >     > secret.  All the entities that hold secret shares can also
> >     > hold copies of the encrypted record along with the secret
> >     > shares.
> >
> > This allows the secrets to split and sent to appropriate entities
> > once at the beginning of the process, and they never need to be
> > updated again.  Alice can generate as many keys (and as frequently)
> > as she wishes, interacting only with the escrow service.  Assuming
> > that I understand correctly.

If you use a master secret to to generate all the others, indeed.

The first scheme, however, requires storing updated encrypted secrets
payloads.  That's the "service" that we'd asked about, but I assumed the
services that store secret shares would also store those payloads.

> >     > However, you might find it difficult to generate key pairs
> >     > from a master secret, especially if you ever need to generate
> >     > keys on a hardware token.  If you won't have that requirement,
> >     > and if you're willing to have that as an anti-requirement,
> >     > then the second scheme is simpler, indeed, and the entities
> >     > that store key shares will need to store smaller records.
> >

Yes, though I expect wrapped key export to be generally available,

> it will in any case need a way to import a private master key generated

not supporting such tokens is a reasonable thing to do.

> > with the confusion as to how the different

That enlarges the amount of secret share storage needed, which gets us
back to Phillip's desire to avoid that.  A nice feature of this scheme
is that there's a fixed number of fixed-sized keyshares generated early
on and this need never change unless you want to re-key everything.

Speaking of which, how does master secret change work?

Nico
--

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 9 Sep 2019 23:02:41 -0400

> Speaking of which, how does master secret change work?

That might not be so critical with the changes I made to the way accounts
work.

The master secret for the Mesh is only used in the management of the user's
Mesh devices. It is no longer something that is exposed to other people.
Only the account keys are exposed to other users.

What we probably need to do is to go through the scenarios that would
require re-keying a personal Mesh.

The way that would have least impact on other systems would be to simply
create a parallel Mesh and then create an assertion 'the person who used to
have fingerprint X now has fingerprint Y'. And then various parties would
have to decide the extent to which they trust that assertion.