Subject: [Cfrg] Adoption of threshold drafts by RG

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 21 Sep 2020 12:24:22 -0400

Could the chairs please start the discussion of adoption of my threshold
crypto drafts as was promised six months ago and on numerous occasions
since?

https://tools.ietf.org/id/draft-hallambaker-threshold-sigs-04.html#draft-hallambaker-threshold
https://tools.ietf.org/id/draft-hallambaker-threshold-sigs-04.html

The current state of affairs is this

1) 100% of all the most consequential data breaches today are of data at
rest.

2) PKI is a very successful technology whose use has been limited to
service authentication because of the client key management issue.

3) Over the past two years, at my own personal expense, I have developed an
open source Threshold Key Infrastructure which addresses both of the above
problems.

The Mesh is now passing its functionality tests and I am moving from a
state where I have been actively discouraging engagement while I get it
right to seeking publicity. I have a large rolodex with the names of many
well known tech journalists. When I was a Principal Scientist, I made very
sure that whenever my CEO called me up to ask about a new technology being
reported in the mainstream media, I knew exactly what it was, what it was
trying to be and how it might impact our business.

The promise of PKI has always been that pretty much every information
security problem can be solved if Alice and Bob have private keys on their
devices and their devices have the public key of the other. PKI has failed
on the client side because it turns out that isn't actually practical. Real
users have more than one device and on occasion they lose them. Nor are
smart cards any solution.

Threshold overcomes the problem of client PKI by eliminating the need to
generate or use an entire private key on a single device.

It is possible, very likely even that my Threshold Key Infrastructure is
not the best answer to the problem. In fact I am almost certain of that.
But right now, I am the only person on the planet working on a TKI. And
unless people start looking at my work pretty soon, we may well end up
being stuck with the Mesh the same way that the last 43 years of work on
PKI has been more or less limited to the ideas from Lauren
Kohnfelder's bachelor's thesis.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 21 Sep 2020 19:00:50 -0400

On Mon, Sep 21, 2020 at 12:25 PM Phillip Hallam-Baker
<[email-masked]> wrote:
>
> Could the chairs please start the discussion of adoption of my threshold crypto drafts as was promised six months ago and on numerous occasions since?
>

My understanding is NIST is carrying out a standardization activity
https://csrc.nist.gov/projects/threshold-cryptography . While that's
by no means a barrier to our adoption, I think alignment with the
results of that activity are valuable.

I would note the schemes described are insecure in the presence of
concurrency, as well. https://eprint.iacr.org/2018/417.pdf explains
some of the issues well, and it's really quite subtle and difficult.
The design of FROST https://eprint.iacr.org/2020/852.pdf solves these
issues, and I don't see any discussion in the draft of them.

Sincerely,
Watson Ladd

--
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 21 Sep 2020 23:45:53 -0400

> results of that activity are valuable.

I am aware of that work and provided feedback on their draft report.

> issues, and I don't see any discussion in the draft of them.

Where do you see concurrency in the nested signature approach? The issue is
elided by enforcing a sequential order on the operations.

I have reviewed FROST. However the authors keep telling me they are not yet
ready to have it considered so I am not.

>From a practical point of view, the most common use I have found for
threshold signatures has t=2 with an application level share holder calling
an HSM (which may be local or remote) to perform a part of the signature
and then completing the process.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 21 Sep 2020 23:54:51 -0400

Forgot to add. Yes we need to synchronize. But my understanding is that at
some point NIST will be endorsing the CFRG curves as alternatives to their
curves.

As a practical matter, SSH and TLS use the NIST curves and are likely to be
remaining with them for some time. So it is important and useful to specify
threshold modes for those curves. Thought where that gets published...

On Mon, Sep 21, 2020 at 11:45 PM Phillip Hallam-Baker <[email-masked]>
wrote:

>> > Could the chairs please start the discussion of adoption of my
>> threshold crypto drafts as was promised six months ago and on numerous
>> occasions since?
>> >
>> >
> Where do you see concurrency in the nested signature approach? The issue
> is elided by enforcing a sequential order on the operations.
>
> I have reviewed FROST. However the authors keep telling me they are not
> yet ready to have it considered so I am not.
>

---

From: Chelsea Komlo <[email-masked]>
Date: Tue, 22 Sep 2020 04:39:37 +0000

Hi Phillip,

We spoke before the last draft of FROST was published in July [1]. Since then, our work has undergone peer review and has been accepted.

While we will be making minor changes to [1] based on comments from reviewers and implementors that are interested in using FROST, the core contributions of the scheme are stable.

Chelsea

[1] https://eprint.iacr.org/2020/852

________________________________
From: Cfrg <[email-masked]> on behalf of Phillip Hallam-Baker <[email-masked]>
Sent: Monday, September 21, 2020 3:45:53 PM
To: Watson Ladd
Cc: IRTF CFRG
Subject: Re: [Cfrg] Adoption of threshold drafts by RG

On Mon, Sep 21, 2020 at 7:01 PM Watson Ladd <[email-masked]<mailto:[email-masked]>> wrote:
On Mon, Sep 21, 2020 at 12:25 PM Phillip Hallam-Baker

Where do you see concurrency in the nested signature approach? The issue is elided by enforcing a sequential order on the operations.

I have reviewed FROST. However the authors keep telling me they are not yet ready to have it considered so I am not.

>From a practical point of view, the most common use I have found for threshold signatures has t=2 with an application level share holder calling an HSM (which may be local or remote) to perform a part of the signature and then completing the process.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 29 Sep 2020 13:16:35 -0400

Replying to Watson and Chelsea.

Having read through the papers, I think we are seeing a case of academic
hyperbole rather than an actual fundamental discovery in cryptography.
Rather the paper Watson cites constructs an age old result in concurrency
in terms of cryptography and discovers the same result. No surprise.

For my practical purposes, I am interested in a threshold signature scheme
that works with widely used algorithms and can be safely implemented within
common protocol interactions. This is a rather easier task than the one set
in most academic papers.

There are in fact two completely separate problems here: Creation of
threshold key shares and use of threshold key shares. The spurious claim
that a secure scheme can't be created comes from a crafty conflation of
these two very distinct issues.

Lets just ignore key share generation for the time being and look at use of
a threshold signature. There are four possible outcomes:

1) The process results in disclosure of the private key itself (or
information that enables another party to sign)
2) The process avoids 1 but creates a signature that does not verify
3) The process avoids 1, creates a signature that does verify but is non
deterministic and thus not fully compliant with the original Ed448 spec
4) The process avoids 1, creates a signature that does verify and is
deterministic and thus fully compliant with the original Ed448 spec

For my purposes, the third outcome is sufficient. And I can produce a
fairly straightforward proof that my construction is sound if Ed448 is.
'Attacks' in which a share holder does not provide the correct information
are only of concern if either this results in the private key or ability to
forge a signature leaks.

When it comes to use of the signature, FROST does add a capability that is
not in my current draft which I am very willing to add. But I am going to
need some text from the authors.

Creation of key shares is a rather different issue. The fundamental flaw in
the arguments in various papers asserting 'impossibility' of this or that
is that they don't consider the process of how the key is credentialed at
all. Which is a sure way to end up with nonsense.

There are two potential flows here.

In the first flow a group of contributors generate some data from which a
virtual key pair is established and that key pair is used in what is
essentially a certificate request protocol with some proof of
possession element and then the credential key is used to sign.

In the second flow, there is no certificate request protocol step and no
proof of possession and the result is insecure. That is neither surprising
nor problematic.

The problem is that if you use a proof of possession of the aggregate key
in the first flow it is essentially the same as the second.

If you wish to issue a credential for a threshold key of any type that is
held across multiple authorities, you have to establish a proof of
possession for each of the authorities concerned. This is not just a
problem with signature, there is a similar result for encryption.

So I see this problem as a problem of correctness of the cryptographic
protocol and not the cryptographic algorithm. And I am solving that problem
in my work by constructing keys in very specific ways that are simple,
robust and avoid the division of authority issue.

---

From: Ian Goldberg <[email-masked]>
Date: Tue, 29 Sep 2020 16:38:43 -0400

On Tue, Sep 29, 2020 at 08:21:28PM +0000, Chelsea Komlo wrote:
> After performing O(k*b*2^{1/lg(k)})

Typo fix: that should be O(k*b*2^{b/(1+lg(k))}) [and k here is actually
one more than the number of parallel signing operations the victim is
willing to support].  So 1 signing op at a time means k=2, and the above
is O(2b*2^{b/2}); i.e., basically the cost of extracting a DL in a b-bit
group, as expected.  But 7 parallel signing ops means k=8, and the above
is O(8b*2^{b/4}), etc.

---

From: Chelsea Komlo <[email-masked]>
Date: Tue, 29 Sep 2020 20:21:28 +0000

Hi Phillip,

Here is a summary of how the Drivers attack [1] can be performed, and the implications for schemes that are insecure.

Let the threshold be t=2, and assume one signer is malicious. Let the number of victim's commitments that the attacker can learn *before* selecting their own commitment be k >= 2 (such as by opening many simultaneous signing connections).

After performing O(k*b*2^{1/lg(k)}) local computations (where b is the bitlength of the order of the group), the adversary can compute a valid forged signature. They do so by first completing the k signing executions, sending the victim k messages to sign of the adversary's choosing, along with their own commitments. From the victim's responses, the adversary can derive a partial forged signature for the victim over a message that the victim has never seen. The adversary then simply provides their own partial signature to complete what is a valid forged joint signature.

For a scheme defined over a group order of bitlength 256, an adversary that is allowed to make up to 3 concurrent signing operations reduces the security of the scheme to ~95 bits of security. Allowing up to 7 concurrent signing operations reduces the security to 75 bits, etc.

With that said, even if you did integrate a FROST-like approach into your scheme, after a quick look, there are parts of your design that remain insecure. For example, the stateless computation of the final share [2] would remain insecure against the Drijvers attack as the final signer is not required to commit to their nonce before seeing all other signers' commitments.

We would however like schemes that are designed for specific use cases to build upon FROST as needed. Because of the interest here and as expressed previously on this list, I would like to ask the chairs to consider moving our draft for FROST [3] forward.

Chelsea

[1] https://eprint.iacr.org/2018/417.pdf
[2] https://tools.ietf.org/id/draft-hallambaker-threshold-sigs-04.html#section-3.3
[3] https://www.ietf.org/id/draft-komlo-frost-00.txt

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 30 Sep 2020 16:51:09 +0200

Phillip,

It’s quite simple and basically free to delinearize the witnesses/nonces in a Schnorr multi-signature. 

I implemented witnesses delinearization in schnorrkel’s musig way back in early January https://github.com/w3f/schnorrkel/commit/fa6c35f832 after discussing it with numerous people in Fall 2019.  We’re not actually using witnesses delinearization in production right now, but only because our wallet folks move slowly. 

It works for threshold signatures too of course, so it appears FROST adopted roughly the same trick of delinearizing the witnesses in their recent version.  If threshold confuse matters then you should consider the simpler case of musig plus witnesses delinearization first.

If you want a multi-signer Schnorr protocol then you'll need either some form of witnesses delinearization or else some fancy determinism solution like MuSig-DN.

Best,
Jeff

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Sep 2020 12:05:49 -0400

On Wed, Sep 30, 2020 at 10:52 AM Jeff Burdges <[email-masked]> wrote:

> I implemented witnesses delinearization in schnorrkel’s musig way back in
> early January https://github.com/w3f/schnorrkel/commit/fa6c35f832 after
> discussing it with numerous people in Fall 2019.  We’re not actually using
> witnesses delinearization in production right now, but only because our
> wallet folks move slowly.
>
> It works for threshold signatures too of course, so it appears FROST
> adopted roughly the same trick of delinearizing the witnesses in their
> recent version.  If threshold confuse matters then you should consider the
> simpler case of musig plus witnesses delinearization first.
>
> If you want a multi-signer Schnorr protocol then you'll need either some
> form of witnesses delinearization or else some fancy determinism solution
> like MuSig-DN.
>

I did initially consider multi-sig sufficient for pretty much every need.
There are however two requirements where I think threshold is pretty
compelling.

The first is the case where we want to divide private key operations
between an application layer key and a key embedded in an HSM built into a
CPU. Such an HSM cannot be fully trusted when it comes to considering
supply chain issues. I am aware of multiple instances of supply chain
hardware compromise (and no, I am not able to provide references).

The second comes up in fault tolerant systems. If I have a redundant 2-of-3
host configuration for my service, I want the crypto to match. The problem
with multi-sigs is that if one host is compromised, they end up signing an
incorrect sequence. And that is visible to outsiders. Use of threshold
signs allows us to align the crypto with the redundancy configuration.

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 30 Sep 2020 18:35:37 +0200

> On 30 Sep 2020, at 18:05, Phillip Hallam-Baker <[email-masked]> wrote:
> I did initially consider multi-sig sufficient for pretty much every need. There are however two requirements where I think threshold is pretty compelling.

I never said “don’t do threshold”.  I said roughly: You need to understand why the witness/nonce attacks work.  And the defenses.  

If threshold gets in the way, then try to understand it for musig first.  

Also, MuSig-DN is *not* MuSig.  A derandomized nonce (the DN) is incredibly insecure unless you pull tricks similar to what they do.  MuSig and MuSig-DN both have natural threshold variants.  And both are closer to their threshold variants than to one another.

Jeff

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Sep 2020 12:50:22 -0400

I think this is starting to get into discussion of the drafts rather than
the decision for the WG to move forward on the work. Which I would also
like to see happen. I am indifferent as to whose draft is used as the basis
for the signature part. My goal is to get a scheme I can use.

As far as the use cases go, I am starting to see the basis for the Drijvers
attack. Your use of the term 'concurrency' is a little confusing to me. I
am a protocol guy, not a cryptographer. What is the information that you
are assuming is shared between a set of 'concurrent' signatures?

However I am not convinced that an HSM can perform the attack from the
information made available to it. When implemented as a CPU co-processor,
the HSM will only ever see the R contribution value from the other party
and the message. The HSM never sees the final signature or the other
contributions, nor does it get to choose the message. This is not the case
for a threshold signature service however. That will see the final
signature.

For the CPU co-processor case, offering less than FIPS-140 level security
might well be acceptable. The key concern is preventing leakage of the
co-processor key. The possibility that a malicious co-processor could
perform an active attack on the application key is less of a concern. It is
hard to see how that sort of thing can be easily hidden in the microcode.

>From my point of view, the critical thing for a threshold signature service
is to enable a single request/response pattern to service a single API call
to 'sign'. But I can offload a pre-commitment phase as is being done in
FROST.

To be more specific about my particular use case. Alice (@alice) creates a
Mesh profile which she will initially use with the service example.com and
later with example.net (but only one at a time). Connecting a device to her
Mesh requires the creation of a Mesh Activation record and connection
record for the device. These must be signed under an administrator key
declared in the User profile. Alice may connect multiple administrator
devices to her Mesh. She is also likely to lose one of them at some point.
So the ability to split the threshold signature across the administrator
device and a threshold service is really desirable but neither essential
nor is it currently implemented.

The quorum criteria here is going to be that Alice must use an
administrator device and one of the services. The services must not be able
to collude and create a signature on their own. This is achieved by first
splitting the private key into two parts, giving one of them to the device
and performing a Shamir secret share n=3, t=2 on the other.

If use of threshold signatures is limited to the specific task of device
connection, the service can compute a pre-commitment every time it receives
a device connection request. But it would be nice if this could be made
more general.

On Tue, Sep 29, 2020 at 4:21 PM Chelsea Komlo <[email-masked]> wrote:

> Hi Phillip,
>
>
> Here is a summary of how the Drivers attack [1] can be performed, and the
> implications for schemes that are insecure.
>
>
> Let the threshold be t=2, and assume one signer is malicious. Let the
> number of victim's commitments that the attacker can learn *before*
> selecting their own commitment be k >= 2 (such as by opening many
> simultaneous signing connections).
>
>
> After performing O(k*b*2^{1/lg(k)}) local computations (where b is the
> bitlength of the order of the group), the adversary can compute a valid
> forged signature. They do so by first completing the k signing executions,
> sending the victim k messages to sign of the adversary's choosing, along
> with their own commitments. From the victim's responses, the adversary can
> derive a partial forged signature for the victim over a message that the
> victim has never seen. The adversary then simply provides their own partial
> signature to complete what is a valid forged joint signature.
>
>
> For a scheme defined over a group order of bitlength 256, an adversary
> that is allowed to make up to 3 concurrent signing operations reduces the
> security of the scheme to ~95 bits of security. Allowing up to 7 concurrent
> signing operations reduces the security to 75 bits, etc.
>
>
> With that said, even if you did integrate a FROST-like approach into your
> scheme, after a quick look, there are parts of your design that remain
> insecure. For example, the stateless computation of the final share [2]
> would remain insecure against the Drijvers attack as the final signer is
> not required to commit to their nonce before seeing all other signers'
> commitments.
>
>
> We would however like schemes that are designed for specific use cases to
> build upon FROST as needed. Because of the interest here and as expressed
> previously on this list, I would like to ask the chairs to consider moving
> our draft for FROST [3] forward.
>
>
> Chelsea
>
>
> [2]
> https://tools.ietf.org/id/draft-hallambaker-threshold-sigs-04.html#section-3.3

---

From: Ian Goldberg <[email-masked]>
Date: Wed, 30 Sep 2020 13:20:03 -0400

> are assuming is shared between a set of 'concurrent' signatures?

Just to clear up the terminology here: 'concurrency' is used in its
protocol sense: two executions of a protocol are concurrent if, roughly,
a party can see some initial messages from runs of multiple instances of
the protocol before deciding what messages to send to continue/complete
all of the instances.

For example, participant P1 initiates say 7 signing requests with
participant P2.  P2 sends their R contributions for each of those
requests, and only after seeing all 7 of P2's contributions does P1
choose its 7 R contributions to continue the 7 concurrent protocols.

> for a threshold signature service however. That will see the final

The attack does not require choosing the messages (just seeing the
messages).  It does require seeing the final signatures, but signatures
aren't typically considered private, so who knows where they'll end up.
-- 
Ian Goldberg
Canada Research Chair in Privacy Enhancing Technologies
Professor, Cheriton School of Computer Science
University of Waterloo