Re: [Cfrg] Threshold signatures

[Michael StJohns <[e-mail]>]

On 1/3/2020 12:22 PM, Phillip Hallam-Baker wrote:
> On Fri, Jan 3, 2020 at 12:08 PM Dan Wing <[e-mail] 
> <mailto:[e-mail]>> 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.
>

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