Subject: [Cfrg] Proposal: Threshold cryptography for CFRG curves + UDF

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 6 Jan 2020 00:42:24 -0500

All,

I have just submitted two new drafts:

https://www.ietf.org/id/draft-hallambaker-threshold-00.html
https://www.ietf.org/id/draft-hallambaker-threshold-sigs-00.html

I wish to (in due course) propose these as CFRG work items together with
the existing draft:

https://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html

(should have a proper HTML version of above soon, stress test on the tools.)

These are of course work that is motivated by my work on the Mathematical
Mesh. And since the obvious question for the IESG to ask is whether CFRG
has looked at the crypto, it probably makes sense to begin by discussing
the crypto here.

But more importantly, the Mesh is merely a vehicle to try to persuade the
field to start using some post 1990s crypto. So it isn't a problem for me
if the outcome is we end up putting threshold decryption into legacy CRM
schemes rather than deploying my new one.

The first draft describes the addition of three new capabilities to the
X25519 / X448 / Ed25519 / Ed448 repertoire:

1) Threshold Decryption (n, n)
2) Threshold Key Generation
3) Side channel disclosure resistance

The implementation of threshold signature is described in a separate draft.
Two schemes are described for Ed25519/Ed448

1) Unanimous threshold i.e. (n, n)
2) Quorate threshold, i.e. (n, t)

The third document describes the presentation of certain types of
cryptographic material that it is necessary for people to interact with
under certain circumstances. This began as a very tightly constrained piece
of work to 'do digest fingerprints right'. It has since grown in response
to requests and now has some capabilities that I think really need some
CFRG input:

1) Deterministic functions for generating ECDH and RSA keys from a
specified key via a KDF
2) Shamir secret sharing for escrow of encrypted keying material
3) Shamir secret sharing for escrow of seed used to generate key pairs

As previously discussed on the list, the threshold signatures are not
aggregate signatures. They are however compatible with the existing RFC7748
and RFC8032 curves and algorithms and that is my overarching goal. I am
aware of the BLS work but I don't see it as overlapping. There are numerous
references and citations missing including to previous IETF/IRTF proposals.
I am more than willing to share authorship. The key thing is to move the
work ahead.

Many thanks to all those who have helped on or off the list. Will be
following up to ask folk who helped me offlist if they want their names
mentioned in the acknowledgements. Also need to chase down the references
to source.

Security considerations are intentionally left blank as I think it better
to start this only after the scope is understood or things get missed.

Questions:

1) Should CFRG look at any/all of this work?

2) Is (n,k) quorum Threshold decryption worth adding?

3) UDF provides two escrow models at present, do we need to add in direct
escrow of the private keys?

4) If threshold signature is worth doing, should there be one threshold
spec for the  RFC7748 and RFC8032 curves or keep these as two?

5) I was planning to kill OID UDFs, they were originally added as a way to
allow QR code transmission of private keys and then Michael Richardson gave
me a better idea.

I understand that UDF might be a little on the 'lite' side and not so
suited to CFRG. But I would like people to take a look at the deterministic
key gen because it solves a very important problem a lot of sysadmins face
today: how to keep SSH keys in sync across machines. Some of the
instructions given on the net on how to do this are pitiful.

This technique is not as simple or easy to use as the Mesh of course, but
it does support 'offline' and 'paper' pretty well.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 6 Jan 2020 17:37:40 -0500

I managed to get the UDF draft through the HTML version of the Internet
Draft tools:

https://www.ietf.org/id/draft-hallambaker-mesh-udf-08.html

I am not proposing CFRG do the whole daft. Rather I would propose removing
all the URI and SIN naming components, the motivation sections, etc etc.

On Mon, Jan 6, 2020 at 12:42 AM Phillip Hallam-Baker <[email-masked]>
wrote:

> The implementation of threshold signature is described in a separate
> draft. Two schemes are described for Ed25519/Ed448
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 13 Jan 2020 15:47:11 -0500

I just saw a practical use case that justifies application of threshold
cryptography in (n,t) fashion at the ECDH level rather than using release
of a static symmetric key to unlock a private key for use.

Consider the case in which a service might be compromised and the private
key extracted. We split the private key across multiple servers (e.g. 3)
put them in different data centers and we perform each private key
operation on all three. The (2,3) quorum allows for fault tolerance when
one of the servers fails or is unable to communicate.

So at this point it seems best to move the Shamir Secret Sharing scheme
into the threshold spec. But I will wait on comment on that before going
ahead.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 14 Jan 2020 11:56:57 -0500

I have a different goal. Pedersen's distributed key generation term was
unhelpful. I think we should insist that Key generation is the process by
which one machine establishes one key pair in collaboration with other
machines. The paper is describing key generation for a key to be used as a
threshold key. That is a lot harder.

The use case for combining the key shares comes from the fact that

1) Many IoT devices are unable to generate secure key pairs.
2) Devices have been observed to have been compromised at every stage in
the supply chain: design, fabrication and distribution.

These attacks are real and thus it is entirely appropriate to require a
system that enables an administration device to generate a key for an IoT
device cooperatively.

The objective here is to obtain a situation in which the generated key will
be as secure as the combination of the two key contributions that are used
to create it and to prove to the admin device that the IoT device is using
a key that is not known to the device manufacturer.

The timing attack described in the paper is not relevant because there is
no such disclosure round.

In the circumstances described, that of an IoT device joining a collection,
there is no possibility of a perfect defense against an adversary that has
compromised the state of the IoT device joining that is able to observe the
interactions between the IoT device and the administration device as it
joins. A malicious manufacturer can always simulate the device. But only if
they have that visibility into the communication channel. And note that
since we haven't excluded side channel release schemes, we aren't
attempting to close every possible manufacturer compromise in any case.

If the device has sound random state, transmitting the admin system key
contribution is easy, we can get sufficient protection for the private key
using TLS with forward secrecy alone.

If not, we are going to have to rely on channel security rather than the TLS

What it sounds like is that I should probably write up the device to
collection protocol separate from the Mesh as well. But I think that should
probably remain a separate doc from the on showing the basic scheme.

On Mon, Jan 13, 2020 at 11:19 PM Denis Kolegov <[email-masked]>
wrote:

> Hello Phillip.
>
> I have the following questions:
> 1) Why do not use a distributed key generation approach like that
> https://link.springer.com/content/pdf/10.1007%2F3-540-48910-X_21.pdf?
> In that case, the "auditability" can be verified by zero-knowledge proof
> protocols and other MPC primitives.
>
> 2) The informal protocol of the Section 3.3.1 states "The administration
> device private key is transmitted to the Device by means of a secure channel".
> Do not you think that can be insecure for some threat models? For example,
> a rogue device can steal the private key. I mean within this approach it is
> necessary to guarantee that the device has not been compromised and can not
> be attacked using KCI.
>
> Thank you.
>
> вт, 14 янв. 2020 г. в 03:47, Phillip Hallam-Baker <[email-masked]>:
>
>> On Mon, Jan 6, 2020 at 12:42 AM Phillip Hallam-Baker <
>> [email-masked]> wrote:
>>
>>> All,
>>>
>>> These are of course work that is motivated by my work on the
>>> Mathematical Mesh. And since the obvious question for the IESG to ask is
>>> whether CFRG has looked at the crypto, it probably makes sense to begin by
>>> discussing the crypto here.
>>>
>>> But more importantly, the Mesh is merely a vehicle to try to persuade
>>> the field to start using some post 1990s crypto. So it isn't a problem for
>>> me if the outcome is we end up putting threshold decryption into legacy CRM
>>> Many thanks to all those who have helped on or off the list.. Will be
>>> Security considerations are intentionally left blank as I think it
>>> better to start this only after the scope is understood or things get
>>> missed.
>>>
>>>
>>> Questions:
>>>
>>> 3) UDF provides two escrow models at present, do we need to add in
>>> direct escrow of the private keys?
>>>
>>> 5) I was planning to kill OID UDFs, they were originally added as a way
>>> to allow QR code transmission of private keys and then Michael Richardson
>>> gave me a better idea.
>>>
>>> This technique is not as simple or easy to use as the Mesh of course,
>>> but it does support 'offline' and 'paper' pretty well.
>>>
>>> _______________________________________________
>> Cfrg mailing list
>> [email-masked]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
> --
> Sincerely,
> Denis Kolegov
> @dnkolegov
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 14 Jan 2020 12:52:05 -0500

Would it help frame the discussion better if I pointed out that this is how
I ensure that my device keys are not subject to a government
imposed backdoor?

On Tue, Jan 14, 2020 at 11:56 AM Phillip Hallam-Baker <[email-masked]>
wrote:

> The objective here is to obtain a situation in which the generated key
> will be as secure as the combination of the two key contributions that are
> used to create it and to prove to the admin device that the IoT device is
> using a key that is not known to the device manufacturer.
>
> In the circumstances described, that of an IoT device joining a
> collection, there is no possibility of a perfect defense against an
> adversary that has compromised the state of the IoT device joining that is
> able to observe the interactions between the IoT device and the
> administration device as it joins. A malicious manufacturer can always
> simulate the device. But only if they have that visibility into the
> communication channel. And note that since we haven't excluded side channel
> release schemes, we aren't attempting to close every possible manufacturer
> compromise in any case.
>
>> вт, 14 янв. 2020 г. в 03:47, Phillip Hallam-Baker <[email-masked]
>> >:
>>
>>> Consider the case in which a service might be compromised and the
>>> private key extracted. We split the private key across multiple servers
>>> (e.g. 3) put them in different data centers and we perform each private key
>>>> I wish to (in due course) propose these as CFRG work items together
>>>> with the existing draft:
>>>>