Subject: [Cfrg] Threshold signatures

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 2 Jan 2020 14:28:29 -0500

OK so with quite a bit of help, have got a prototype of threshold
signatures going. There is a bit more to the draft than just the algorithm
though as the way the scheme is presented and packaged has consequences.

>From the presentation side, I want to be able to argue that the threshold
sig scheme has (almost) precisely the same security properties as the
RFC8032 scheme. Which means that the core of the presentation must align as
closely as possible with the RFC8032 scheme.

There are some subtle design choices that don't impact security but may
well have impact on specific use cases. The use cases I am currently
considering are

1) HSM module: One or both parts of the signature key shares are located in
a HSM providing resistance against extraction of the public key. This is an
important use case as we want the operation of the HSM to be stateless. The
signing algorithm requires multiple rounds, in the first round, the signer
commits to a value R_i = r_i.B. In the second round, the value r_i is used.
So it is kinda important to construct r_i in such fashion that the HSM can
restore it from one round to the next even though it may have performed
other operations in the meantime.

Another issue that comes up with HSMs is auditability. The construction of
r_i must be auditalble which means it must be deterministic.

2) Code signing: The code signing role is split across two or more signers
and MAY permit a signature to be created by a quorum smaller than the total
number of authorized signers (n, t). Signing quorums may prove particularly
attractive for open source projects.

I have introduced a new role, of coordinator for the party that manages the
process.

Are there additional use cases that should be considered. That is use cases
that raise additional requirements. The need to sign blockchains is often
raised but that doesn't seem to raise additional requirements over code
signing.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 2 Jan 2020 14:57:42 -0500

I'd be interested in comparing / contrasting your scheme to prior art with
running code, notably:

- KZen's Multiparty EdDSA, a straightforward application of distributed
threshold Schnorr to Ed25519:
https://github.com/KZen-networks/multi-party-eddsa
- CoSi, a Merkle-tree based approach for collective Ed25519 signing
targeting something more along the lines of a consensus protocol:
https://tools.ietf.org/id/draft-ford-cfrg-cosi-00.html

On Thu, Jan 2, 2020 at 2:28 PM Phillip Hallam-Baker <[email-masked]>
wrote:

> 1) HSM module: One or both parts of the signature key shares are located
> in a HSM providing resistance against extraction of the public key. This is
> an important use case as we want the operation of the HSM to be stateless.
> The signing algorithm requires multiple rounds, in the first round, the
> signer commits to a value R_i = r_i..B. In the second round, the value r_i
> is used. So it is kinda important to construct r_i in such fashion that the
> HSM can restore it from one round to the next even though it may have
> performed other operations in the meantime.
>
> I have introduced a new role, of coordinator for the party that manages
> the process.
>
> Are there additional use cases that should be considered. That is use
> cases that raise additional requirements. The need to sign blockchains is
> often raised but that doesn't seem to raise additional requirements over
> code signing.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 2 Jan 2020 16:38:00 -0500

Well I will be looking for co-authors :-)

The big difference is that I want the threshold sigs to be plug compatible
with regular RFC8032. One of my big motivations for this work is to have a
clear 'want list' to give to the likes of Intel, AMD, Cypress etc for
onboard crypto co-processors to support Curve {X/ED}{25519/448} so that
they can support application level crypto operations providing a host bound
mix in to the application keys without exposing the on-chip keys to
external parties.

The point here is that with the interest from NIST and my needs for the
Mesh, I would like to move forward on choice of one scheme we can start
using.

The killer app for threshold sigs could be code signing. Shamir (n,k)
schemes would be particularly good for open source projects.

One thing I would like to understand what the security rationale for tying
the signature hash value k to the value R is. Because that is what creates
the need for a two round protocol.

On Thu, Jan 2, 2020 at 2:57 PM Tony Arcieri <[email-masked]> wrote:

>> Another issue that comes up with HSMs is auditability. The construction
>> of r_i must be auditalble which means it must be deterministic.
>>
>> 2) Code signing: The code signing role is split across two or more
>> signers and MAY permit a signature to be created by a quorum smaller than
>> the total number of authorized signers (n, t). Signing quorums may prove
>> particularly attractive for open source projects.
>>

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 2 Jan 2020 16:42:07 -0500

On Thu, Jan 2, 2020 at 4:38 PM Phillip Hallam-Baker <[email-masked]>
wrote:

> with regular RFC8032.

That is the case for https://github.com/KZen-networks/multi-party-eddsa

-- 
Tony Arcieri

---

From: Jeff Burdges <[email-masked]>
Date: Fri, 3 Jan 2020 01:16:23 +0100

At first blush, I’d think code signing could be accomplished with a set of Ed25519 signatures, no?  How can 64 bytes per signer be any concern when signing code large code blobs?  Also, I’d expect code signing should require accountability, so no threshold signatures anyways, right?

I'll assume however that you actually want an cryptographic multisig that returns only one Schnorr/Ed25519 signature though:

As a rule, you should assume the adversary controls all but one of the signing keys and initiates numerous parallel signing interactions with the remaining honest key.  There are cyber-coins use cases where one party possesses all the shares, which weakens this adversary, but code signing means different parties presumably.

> 1) HSM module: One or both parts of the signature key shares are located in a HSM providing resistance against extraction of the public key. This is an important use case as we want the operation of the HSM to be stateless. The signing algorithm requires multiple rounds, in the first round, the signer commits to a value R_i = r_i..B. In the second round, the value r_i is used. So it is kinda important to construct r_i in such fashion that the HSM can restore it from one round to the next even though it may have performed other operations in the meantime.

You need three round trips here because all published two round trip Schnorr multi-signatures are vulnerable to k-sum forgery attacks: https://eprint.iacr.org/2018/417.pdf  Admittedly these attacks have a high complexity, like 2^45 with open 128 parallel signing queries, so hard but still doable.

Afaik, there are no published stateless protocols either, not sure anything simple exists.  If you abandon stateless then one should enforce correct usage using session types like I did in https://github.com/w3f/schnorrkel/blob/master/src/musig.rs although you could approximate session types in C with opaque pointers and runtime checks though.

We’re working on some new approaches to two round trip versions, but no security proofs yet, and nothing stateless.  I’m afraid the mBCJ signature scheme from that paper kinda sucks in practice.

> Another issue that comes up with HSMs is auditability. The construction of r_i must be auditalble which means it must be deterministic.

I've heard about upcoming work that achieves this for a two round trip stateless protocol, but requires zero-knowlede proofs, presumably of elliptic curve arithmetic, and may or may not really address the threshold situation, and may even exploit the secp256k1 mirror curve.  In other word, you might require another secure curve whose group order is 2^255-19, or maybe some clever CRT games.  Those zero-knowlede proofs run only between the signers, but probably way beyond your smart card.

If you’d accept a trusted setup then a zkSNARK on BLS12-381 could verify numerous RedJubJub signatures (EdDSA).

> I will be looking for co-authors :-)

I’ve an unrelated topic that might interest you if you’re interested in code signing.

> One thing I would like to understand what the security rationale for tying the signature hash value k to the value R is. Because that is what creates the need for a two round protocol.

Almost sounds like you’re asking about the Fiat-Shamir transform that makes an interactive Schnorr identification protocol into a non-interactive Schnorr signature.

You need pairings ala BLS signatures for a one round trip multi-signature scheme.  I donno if anyone proved that but you’ll get nothing from fancy zero-knowlede proof tricks among the signers obviously.  I’d expect BLS smart cards for cyber-coin validators within the next couple years, if not already.

Jeff

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 2 Jan 2020 19:26:34 -0500

On Thu, Jan 2, 2020 at 4:42 PM Tony Arcieri <[email-masked]> wrote:

>> The big difference is that I want the threshold sigs to be plug
>> compatible with regular RFC8032.
>>
>

I am not an academic, I have absolutely no interest in originality. What I
am interested in is whether a component works or not and how it fits into
the rest of the system.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 2 Jan 2020 19:28:52 -0500

>
> At first blush, I’d think code signing could be accomplished with a set of
> Ed25519 signatures, no?

TUF[1] implements threshold signatures for codesigning this way. It's
simple and supports offline/airgapped signers, as opposed to a Schnorr-like
multisignature scheme which requires all of the signers be online. In
practice when multisignatures are leveraged in systems like this they're
almost always a 2-of-3 threshold signature, so using a multisignature saves
only 64-bytes.

[1]: https://theupdateframework.github.io/

-- 
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 2 Jan 2020 19:36:09 -0500

On Thu, Jan 2, 2020 at 7:18 PM Jeff Burdges <[email-masked]> wrote:

> Ed25519 signatures, no?  How can 64 bytes per signer be any concern when
> signing code large code blobs?  Also, I’d expect code signing should
> require accountability, so no threshold signatures anyways, right?
>

I discuss multi-sigs in the paper but the short answer is that pretty much
every code signing system out there has a de facto assumption of one
signature. I want to be able to add robustness without impacting workflow.

But more specifically, what I want to do is to divide the ability to use a
code signing key between a cloud service and one (or more) engineers
holding code signing keys. Code signing keys have leaked from both places
but separation of duties means we are not vulnerable to a single point of
failure.

> You need three round trips here because all published two round trip
> Schnorr multi-signatures are vulnerable to k-sum forgery attacks:
> https://eprint.iacr.org/2018/417.pdf  Admittedly these attacks have a
> high complexity, like 2^45 with open 128 parallel signing queries, so hard
> but still doable.
>

Yes, just seeing how those come into the picture now.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 2 Jan 2020 19:46:43 -0500

On Thu, Jan 2, 2020 at 7:36 PM Phillip Hallam-Baker <[email-masked]>
wrote:

> signature.

In addition to TUF, simple threshold signatures are also supported by
OpenPGP via TSIG.

> holding code signing keys.
>

A simple threshold signature set is definitely going to be the most
practical way to support this use case. Even Ed25519 support is exceedingly
rare in cloud KMS systems. I think that even if a spec for an interactive
Schnorr-based scheme existed, it's extremely unlikely that such systems
would adopt support for it, as these systems are deliberately slow-moving
by design, don't add new features without extremely strong and pervasive
customer support, and when they do add features, take quite awhile to do so.

-- 
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 3 Jan 2020 08:53:08 -0500

So I am currently deep into the literature and trying to understand quite
where people are coming from.

There seems to be a lot of conflation of 'we can't prove this is secure'
with 'this is insecure'.

Sure, if you allow people to 'bring your own key', you are going to have to
validate those keys in some fashion before you begin. But that isn't a
signature round, it is part of the certification and/or key distribution
protocol and so it does not count against my digital signature scheme
rounds.

The path to success in academia is to invent problems that don't need
solving that have cute proofs. Yes, been there, done that. Tony Hoare was
my College Tutor. It is important to make sure that the security and
protocol properties we are validating for are in fact part of our real
requirements. I spent months reading about attempts to create 'proper'
proxy re-encryption schemes until I realized that I could avoid all the
complexity by giving people the decryption keypair rather than using one
they already had.

The field spent 20 years thinking RSA was superior to DH because DH doesn't
do 'true' public key encryption. But embedded in a protocol, DH provides
exactly the same capability as RSA - establishing a shared session key. And
it is far more flexible and does so with far less complexity. DH is
actually the better scheme but it took us too long to realize that.

So the security concerns I recognize are:

1) Engaging in the protocol causes disclosure of a participants private
signature key.

2) Engaging in the protocol to sign document M, provides an attacker with
information that allows them to sign document M' without the participation
of the full signature quorum.

Security concerns that aren't (much of) a concern to me are:

1) Introducing spurious information into the protocol causes the creation
of a signature that fails validation.

It is probably sensible for the coordinator to verify that the signature
validates. If it is possible to construct a rogue key that results in a
valid signature, then our base signature scheme is broken. But this
particular attack is irrelevant for most of the scenarios I am considering
because the key shares are split from a master key and distributed to the
key share holders in two of the three schemes. And I can use either
threshold key generation or a proof of possession mechanism in the third.

The only information the signers provide in the protocol I am currently
considering is R_i in the first round and S_i = r_i + s_i.k in the second.
Presenting a false R_i in the first round will cause the signature protocol
to fail.

As for how long it takes for the industry to get a clue, that should not be
of any concern in IRTF. I am quite happy sitting in a House or Senate
hearing telling the members of Congress that we do have the technology to
win the cryptowars but it isn't being used. I don't (often) get to talk to
current NSA directors but I do get to talk to past directors and it seems
that one of those may have started the chain reaction that caused NIST to
start looking at threshold (pity they didn't invite me to the party last
year but that is the cost of Chatham House rules).

The reason NSA was vulnerable to the Snowden breach was that the Microsoft
CRM system they were using was not designed to protect against an insider
threat. I doubt that I am the only person who has pointed out that
employing threshold decryption would allow the existing system to afford
the necessary separation of duties.

The industry does move very slowly, but one of the main reasons for that is
that there are very few people in the industry pushing to do stuff that is
breaking the established pattern because most folk are resigned to failure.
If people are resigned to failure let them say so and get out of the way of
those of us who are not. We have work to do.

---

From: Bill Cox <[email-masked]>
Date: Fri, 3 Jan 2020 06:43:41 -0800

On Thu, Jan 2, 2020 at 4:18 PM Jeff Burdges <[email-masked]> wrote:

>
> You need pairings ala BLS signatures for a one round trip multi-signature
> scheme.  I donno if anyone proved that but you’ll get nothing from fancy
> zero-knowlede proof tricks among the signers obviously.  I’d expect BLS
> smart cards for cyber-coin validators within the next couple years, if not
> already.
>
> Jeff
>

You can also use this pairing scheme for rate-limited threshold
password-authenticated key generation.  This could be useful for his
Mathematical Mesh, but as he says, crypto on devices changes only very
slowly.  A brilliant intern we had last year re-invented this pairing
scheme, and I spent a week trying to work out how to do it without bilinear
pairing.  It can also be done on RSA-like groups of unknown order (the OPRF
server is allowed to know the order, but probably should forget it), but
the security of the scheme is less obvious.  Both of these schemes also
enable the quorum members to do extra work to strengthen password guesses,
similar to Makwa.

What is unclear to me is whether these schemes are generally useful because:

1) It is important for the server to know whether the password guess was
correct, which is a key signal in rate-limiting.
2) Secret shares can only migrate to new HSMs/cloud providers when the user
re-enters their password.

More traditional threshold password-protected secret sharing schemes
address these issues, at the cost of higher complexity and more
communication rounds.  Which way should the world go?

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 3 Jan 2020 10:04:02 -0500

On Fri, Jan 3, 2020 at 9:43 AM Bill Cox <[email-masked]> wrote:

> slowly.

We take a long time to get comfortable with it. NSA nagged us about Suite-B
for how many decades before we started using ECC?

At this point, I think we need to focus on making X25519/448 and
Ed25519/448 the basis for the next gen of security products. It took about
five years from AES being announced as a winner for it to become the new
normal.

A brilliant intern we had last year re-invented this pairing scheme, and I
> spent a week trying to work out how to do it without bilinear pairing.  It
> can also be done on RSA-like groups of unknown order (the OPRF server is
> allowed to know the order, but probably should forget it), but the security
> of the scheme is less obvious.  Both of these schemes also enable the
> quorum members to do extra work to strengthen password guesses, similar to
> Makwa.
>

A correct formal proof is useful but it isn't a substitute for a compelling
explanation of why the scheme is secure. I can provide that for threshold
decryption. And I think I can get there for the threshold signature schemes
I am looking at.

What is unclear to me is whether these schemes are generally useful because:
> 2) Secret shares can only migrate to new HSMs/cloud providers when the
> user re-enters their password.
>

Lets make it easy to use public key authentication across devices and
forget about passwords altogether.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 3 Jan 2020 15:24:50 +0000

From: Cfrg <[email-masked]> On Behalf Of Phillip Hallam-Baker
Sent: Friday, January 03, 2020 10:04 AM
To: Bill Cox <[email-masked]>
Cc: IRTF CFRG <[email-masked]>
Subject: Re: [Cfrg] Threshold signatures

On Fri, Jan 3, 2020 at 9:43 AM Bill Cox <[email-masked]<mailto:[email-masked]>> wrote:
On Thu, Jan 2, 2020 at 4:18 PM Jeff Burdges <[email-masked]<mailto:[email-masked]>> wrote:

Jeff

You can also use this pairing scheme for rate-limited threshold password-authenticated key generation.  This could be useful for his Mathematical Mesh, but as he says, crypto on devices changes only very slowly.

We take a long time to get comfortable with it. NSA nagged us about Suite-B for how many decades before we started using ECC?

At this point, I think we need to focus on making X25519/448 and Ed25519/448 the basis for the next gen of security products. It took about five years from AES being announced as a winner for it to become the new normal.

Hmmmm, it is likely at some point someone will have a cryptographically relevant Quantum Computer, such a Quantum Computer can break elliptic curves (and, in fact, Elliptic Curves appear to be the easiest cryptographical object to break, as it requires the fewest qubits and circuit depth).  No one is certain when (or if) such a Quantum Computer will exist; maybe in 10 years, or 20.  However, if we are planning for the future, it would appear to be reasonable to take that into account, and include a postquantum scheme (possibly in conjunction with a classical ECC or RSA scheme)

---

From: Bill Cox <[email-masked]>
Date: Fri, 3 Jan 2020 08:14:23 -0800

> forget about passwords altogether.

Yes, kill passwords, but please don't disable  my device unlock secret.

Both Apple and Google use secure hardware to protect your phone unlock
secret, and these HSMs (Titan chips in Google's case) will restore your
data to your new device if you first login, and then prove you know the
unlock secret.  Neither Google nor Apple can trivially decrypt your data
due to hardware rate-limiting.  I would guestimate that about 100M people
per year are currently making use of these features.  Can we ignore 100M
data recoveries per year?  Most users around the world still only have only
one device running Android or IOs.  Running a Mesh protocol on a USB key
for $15 would be great, but we're finding that users don't want hardware
keys.  It might be simple to replace all the crypto protocols currently
baked into all the world's devices, than to change user behavior.

When I want to recover my data on a new device after hot-tubbing for an
hour with my only Android device (happened to me 2 years ago), what is the
right protocol?  There are two main threshold schemes, OPRF-based, and
traditional pasword-protected secret sharing.  Honestly, I'd be interested
in any good insight into which way to go.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 3 Jan 2020 11:15:38 -0500

On Fri, Jan 3, 2020 at 10:24 AM Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

>
>
> *From:* Cfrg <[email-masked]> *On Behalf Of * Phillip Hallam-Baker
>

> We take a long time to get comfortable with it. NSA nagged us about
> Suite-B for how many decades before we started using ECC?
>
>
>
> Hmmmm, it is likely at some point someone will have a cryptographically
> relevant Quantum Computer, such a Quantum Computer can break elliptic
> curves (and, in fact, Elliptic Curves appear to be the easiest
> cryptographical object to break, as it requires the fewest qubits and
> circuit depth).  No one is certain when (or if) such a Quantum Computer
> will exist; maybe in 10 years, or 20.  However, if we are planning for the
> future, it would appear to be reasonable to take that into account, and
> include a postquantum scheme (possibly in conjunction with a classical ECC
> or RSA scheme)
>

Building a post-quantum PKI is a worthwhile project that the IRTF should
pursue and I would be very interested in participating in such a scheme.

But why should anyone believe we are capable of building a PKI with the
next generation of crypto technology that we haven't invented yet if we
still haven't deployed a PKI capable of meeting the needs of user
authentication across multiple devices, IoT onboarding or Data at Rest
security?

I am just as skilled in the art of procrastination as anyone else. The
reason I am focused on existing PKI technology is because that is what I
believe the world needs right now.

If we are serious about quantum, we should consider the worst case
scenario. That is someone has a working quantum machine capable of breaking
all existing public key systems in 2030 and we do not have a post quantum
algorithm we are confident in.

That is the only scenario I have currently considered for the Mesh and my
proposed approach is to use PKI while we still have it to establish shared
secrets and Lamport signatures that we can then use to establish a Kerberos
type key distribution scheme.

I do not think it is very likely the quantum folk will have such a machine
in 2030. But I am very confident that if they can build a machine capable
of breaking X25519 then it is game over for RSA4096. Don't be fooled by
Moore's law, the barrier to building bigger quantum machines is not minimum
feature size. Building a 1000 QBit machine today would be well within the
capabilities of the fabs. There would just be no way to use it before
losing coherence. The time to get worried is not when someone shows a 50 or
100 QBit machine, the time to get worried is when they can make it work
without the fridge. If they get trapped ions to work at scale, worry.
Biggly.

Right now, nobody is paying me to do any of this stuff. If people are
seriously worried about post quantum PKI, cut me a check and I will be more
than happy spending the next three, six months or however long it takes to
get something. But as things stand, the probability that we will see more
billion dollar data at rest breaches is 100% and the probability of a
quantum computer breaking x25519 by 2030 is less than 5%.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 3 Jan 2020 11:28:40 -0500

OK, right, you can keep your device unlock codes and your device based
biometrics. Let us leverage both.

The reason for focusing on this threshold stuff now is that we can
supplement the data locking capability you are describing with a key
binding capability.

Well over 90% of TLS key breaches are the result of private keys being
recorded to backups. Most of the rest are due to a machine on the network
being compromised and a private key file being found on an accessible
share. CA breaches are close to non existent and which is why we can have
the post mortems and blamestorming sessions.

Binding TLS keys to a key that is embedded in and cannot be extracted from
the Host service without national lab scale tech (and physical access)
would greatly reduce exposure.

Splitting the code signing key for authenticode between a cloud service and
the software provider would only require the CAs to offer the relevant
cloud service. Sure, some enterprises that have legacy KMS software that
would lock them in to the obsolete approach. But that is less than 1% of
the software providers.

Threshold sig was not a priority for me at the start as I thought multisig
would be sufficient. That may well be true. But I think it is going to be
much easier to sell a complete suite of threshold capabilities than
something that looks like a work in progress. Put threshold decryption and
Key generation on the table and people will say 'let me know when you are
finished'. Add threshold sig and there is a complete set.

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 3 Jan 2020 11:42:21 -0500

> five years from AES being announced as a winner for it to become the new

Given your stated goals of a multisignature which can work for both
developers and things like HSMs and cloud KMS services, and code signing
systems only supporting a single signature as opposed to threshold
signature sets, I think it's worth questioning whether Ed25519 signatures
are the right tool for the job.

I think draft-boneh-bls-signature might be a better fit as it supports
offline aggregation. This means HSMs/KMS systems do not need to participate
in an interactive protocol to produce a signature. It also facilitates
offline/"airgapped" codesigning (using e.g. hardware tokens).

An interactive signing protocol where all of the participants must be able
to reach a central online "broker" in order to produce a multisignature
(and also all be online at the same time) is an onerous requirement, as
opposed to one where each system can produce a signature and they can be
retroactively aggregated.

-- 
Tony Arcieri

---

From: Dan Wing <[email-masked]>
Date: Fri, 3 Jan 2020 09:08:22 -0800

Also, if just need signatures, why not do 3 normal signatures where each signature says "to be valid, there need to be 2 other valid signatures".  Or are you trying to enforce correctness via crypto (so that if only one signature, it can't be valid)?  If so, that is admirable, but unless something critical is encrypted, not achievable.

-d

> On Jan 3, 2020, at 8:42 AM, Tony Arcieri <[email-masked]> wrote:
> 
> On Fri, Jan 3, 2020 at 10:04 AM Phillip Hallam-Baker <[email-masked] <mailto:[email-masked]>> wrote:
> At this point, I think we need to focus on making X25519/448 and Ed25519/448 the basis for the next gen of security products.. It took about five years from AES being announced as a winner for it to become the new normal. 
> 
> Given your stated goals of a multisignature which can work for both developers and things like HSMs and cloud KMS services, and code signing systems only supporting a single signature as opposed to threshold signature sets, I think it's worth questioning whether Ed25519 signatures are the right tool for the job.
> 
> I think draft-boneh-bls-signature might be a better fit as it supports offline aggregation. This means HSMs/KMS systems do not need to participate in an interactive protocol to produce a signature. It also facilitates offline/"airgapped" codesigning (using e.g. hardware tokens).
> 
> An interactive signing protocol where all of the participants must be able to reach a central online "broker" in order to produce a multisignature (and also all be online at the same time) is an onerous requirement, as opposed to one where each system can produce a signature and they can be retroactively aggregated.
> 
> -- 
> Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 3 Jan 2020 12:08:39 -0500

On Fri, Jan 3, 2020 at 11:42 AM Tony Arcieri <[email-masked]> wrote:

> On Fri, Jan 3, 2020 at 10:04 AM Phillip Hallam-Baker <
> [email-masked]> wrote:
>

They may well be more convenient if the number of signers is greater than
two. For the case where n=2 and the coordinator is one of the parties,
Ed25519 is fine.

BLS requires protocol designers like myself to get comfortable with an
entirely new mathematical construct. That is a much bigger ask than you
seem to think.

Rather than seeing threshold variants of Ed25519 as competing with BLS, you
should consider the possibility that acceptance and use of Threshold
Ed25519 is likely to be a necessary pre-condition to considering BLS type
signatures at all.

> retroactively aggregated.

If a device isn't online, it is not communicating. If it is not
communicating it is hardly going to need a threshold signature scheme
capable of supporting a huge value of n.

People are always positing central control as a potential source of
unreliability which is rather odd as in my experience, peer-peer systems
are vastly more fragile in practice.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 3 Jan 2020 12:22:42 -0500

On Fri, Jan 3, 2020 at 12:08 PM Dan Wing <[email-masked]> wrote:

> Also, if just need signatures, why not do 3 normal signatures where each
> signature says "to be valid, there need to be 2 other valid signatures".
> Or are you trying to enforce correctness via crypto (so that if only one
> signature, it can't be valid)?  If so, that is admirable, but unless
> something critical is encrypted, not achievable.
>
> -d
>

That is a perfectly valid approach in my view. The cost of three signatures
over two is that the verifier has to check three signatures and three
signature key validation chains. It also means that the verifier knows the
structure of who signed.

So let us consider the case where BigCorp decides Alice, Bob or Mallet can
sign code releases. Today, they all get the same private key, no separation
of duties, no accountability if the key is lost.

Introducing a simple two way split between a cloud service and tokens
separately issued to Alice, Bob, Mallet means that we now have the
potential for accountability if Mallet sells his key on hacker-bay, we can
prevent it being used to sign more stuff after we find out.

Introducing shamir secret sharing (n,t) scheme would allow us to require
two of the engineers to sign.

Back in the days when I was doing XML Web Services, we discovered that a
compressed encoding was an absolute and inescapable requirement for
deployment. The problem was that message size was really easy for a
journalist with an shoe size level IQ to measure and print a snotty
irrelevant report. So we wrote a stupid compression scheme and journalists
stopped commenting on the message sizes (10K vs 5K) and nobody ever used
it. But we couldn't have got people using SAML etc. without that.

So it might well be that multi-signatures turn out to be perfectly adequate
for everyone's needs. But we probably still need Edwards curve threshold
sigs to get people to agree that is the case.

---

From: Michael StJohns <[email-masked]>
Date: Fri, 3 Jan 2020 14:03:19 -0500

On 1/3/2020 12:22 PM, Phillip Hallam-Baker wrote:
> On Fri, Jan 3, 2020 at 12:08 PM Dan Wing <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Also, if just need signatures, why not do 3 normal signatures
>     where each signature says "to be valid, there need to be 2 other
>     valid signatures".  Or are you trying to enforce correctness via
>     crypto (so that if only one signature, it can't be valid)? If so,
>     that is admirable, but unless something critical is encrypted, not
>     achievable.
>
>     -d
>
>
> That is a perfectly valid approach in my view. The cost of three 
> signatures over two is that the verifier has to check three signatures 
> and three signature key validation chains. It also means that the 
> verifier knows the structure of who signed.
>
> So let us consider the case where BigCorp decides Alice, Bob or Mallet 
> can sign code releases. Today, they all get the same private key, no 
> separation of duties, no accountability if the key is lost.
>
> potential for accountability if Mallet sells his key on hacker-bay, we 
> can prevent it being used to sign more stuff after we find out.
>
> Introducing shamir secret sharing (n,t) scheme would allow us to 
> require two of the engineers to sign.
>

A generic N of M threshold scheme involving HSMs is   (And I think this 
what Dan was suggesting sort of):

1) Generate M key pairs (one per signer), done individually say on smart 
cards

2) Generate live key pair K using the public keys from M and specify N 
as the threshold as parameters

3) HSM enforces:

     If I see N signatures over HASH(data) that verify with a distinct 
public key from M, I will emit a signature over HASH(data) using K 
private key.

4) Master of ceremonies (MOC) generates "data" and calculates HASH(data) 
and provides this publicly.

5) Each of N share holders verifies "data" is what is supposed to be 
signed, calculates HASH(data) and compares it to the public version 
already provided, and if valid signs the data/hash using their private 
key.  The signature is publish publicly.

6) The HSM operator in conjunction with the MOC takes the N signatures, 
and gets the HSM to emit SIGN(K, data) using SIGN(M1, data), SIGN(M2, 
data), etc as input.

7) The MOC publishes SIGN(K, data), and various people verify that the 
signature verifies the data

8) The signature is then used for whatever purpose.

!! The M signers need never be in the same room with the HSM.

This assumes that K has a policy wrapper that the HSM uses to enforce 
this use, that the HSM is sufficiently secure enough that you trust the 
policy wrapper, and that cryptographic separation (ala various math 
mechanisms) of shares of K private key is not a specific requirement.  
(e.g. the HSM has sufficient knowledge of K to form a signature, and the 
compromise of the HSM might expose K, but that risk is sufficiently 
small relative to the benefit as to be acceptable).

If you want something where the private key is never reconstituted (and 
hence never directly vulnerable), you're looking for the ECDSA 
equivalent of "Practical Threshold Signatures", Victor Shoup, IBM 
Research Paper RZ3121, April 1999.   This is a nice scheme in that it 
produces signature values that can be verified like any normal RSA 
signature, and that it never requires the private key to be 
reconstituted.   It's also invertable in that you can use this for 
public encryption with threshold decryption.  (See 
https://github.com/sweis/threshsig for an implementation).

For PHB's notes above:

AFAICT, all of the EC* schemes based on Shamir require the private key 
to be reconstituted somewhere secure (e.g. an HSM).  I haven't found a 
scheme like Shoup's that's usable in threshold systems exactly.

Generally, even with a true threshold system like Shamir or Shoup, you 
want control over the duplication of the shares, so that if you have a 
compromise of M-1 shares, you can kill the key by destroying the other 
uncompromised keys.  That suggests some sort of HSM of some sort even 
for the shares.

For the scheme above, its "just a small matter of programming" to 
enhance the policy wrapper to allow for the "secure" addition, 
revocation and replacement of signer public keys in the M set, or even a 
change in the value of N.

Mike

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 3 Jan 2020 16:19:26 -0500

On Fri, Jan 3, 2020 at 2:03 PM Michael StJohns <[email-masked]>
wrote:

> 2) Generate live key pair K using the public keys from M and specify N as
> the threshold as parameters
>
> Yes, I will add this to the draft. It is kind of a middle ground between
multi-sigs and true threshold sigs.

And going to a DH based system gives us great flexibility because we can
obtain (n,t) quorums where the secret scalar is the thing that drops out.

So we have a continuum:

1) Multi Sigs,  Document is signed by Alice Bob and Carol

2) HSM activated by multiple key holders, Document is signed by the HSM,
Alice, Bob and Carol hold activation keys

3) Multi-round threshold signatures

4) Single round threshold signatures.

AFAICT, all of the EC* schemes based on Shamir require the private key to
> be reconstituted somewhere secure (e.g. an HSM).  I haven't found a scheme
> like Shoup's that's usable in threshold systems exactly.
>
I have running code. It certainly exists. Whether it is secure...

It is really easy to divide up S.B = R + kA into Ri = ri.B and Si = ri + ksi
.

What makes it hard is that the difficulty of constructing a value  S.B =
R + kA comes from the fact that k is strongly coupled to R by means of a
digest.

If we are allowed to pick any value of R we like, forgery is trivial. We
can just pick any value of S and then calculate R = kA - S.B

Which means that we have to know R before we can calculate Si It is
possible, but we need at least two rounds for the signature.

If we are going to allow users to 'bring their own key' then the last
person to join the club can take a look at all the other signer's public
keys and pick one. This is not a signature round (because we are only going
to do it once for a given aggregate key). But it does need to be considered.

In practice, this particular attack that has caused endless papers to be
written is pure piffle. Sure, mallet gets control of the master signature
key and that is a real concern in contexts like BitCoin where there is no
PKI. Lets think through how this attack works for a code signing scheme
like authenticode, right?

We form the aggregate public signature key A = A1 + A2 + … + An
But Mallet is signer n! He creates a public key {m.B, m} he sends in m.B -
(A1 + A2 + … + An-1)

Horrors! When the administrator calculates A = (A1 + A2 + … + An-1) m.B -
(A1 + A2 + … + An-1)
A = m.B

Yeah right, but the minute the administrator tries to apply for the code
signing certificate for A, the signature group is unable to sign the CSR.
So this key is never going to be the one that is used.

This is exactly like an attack on the Student Union elections that happened
when I was at Southampton. Someone stole the returning officer's stamp used
to validate the ballots between the elections. But it was the only stamp he
had so they had to make a new one which was entirely different.

Wading through the papers on why these schemes don't work is incredibly
tedious as the cryptographers don't seem to appreciate how crypto protocols
actually work in practice.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 3 Jan 2020 18:01:11 -0500

OK so current state of play:

Multi-signatures are simple to create. But think about what it really takes
to verify them. We are going to have to specify a signature validation
policy which is of course a subset of the security policy problem.

I and many others are more than willing to do security policy. But there
are folk who reach for a hammer and some oak stakes.

The difference between the use cases I am considering and those that result
from the Bitcoin use cases is that they are operating under a particular
set of constraints and I am not.

Specifically, their concern is that they would like Alice Bob and Carol
with public keys A, B, C to be able to create ad-hoc compound signatures
that can be validated in a single operation under a public key f(A, B, C)
where f is a function that can be calculated by any observer.

My concern is that Alice Bob and Carol each have the ability to control the
creation of a signature under an aggregate signature key Z but do not have
the ability to create a signature without the necessary quorum of signers.
I do not require that the key Z bear any correspondence to A, B or C at all.

Boneh and co are calling the  f(A, B, C) signature an aggregate signature
and consider it as being distinct from threshold signatures. I believe that
is the correct approach and that we should adopt that nomenclature.

https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf

I am not surprised aggregate signatures require pairing for security. Is it
really likely that f(A, B, C) = A + B + C is going to give us the type of
security guarantee we are looking for?