Re: [Cfrg] Threshold signatures

[Phillip Hallam-Baker <[e-mail]>]

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

> 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
>
> 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.