Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8D2CE120867 for ; Fri, 3 Jan 2020 11:03:26 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.897 X-Spam-Level: X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=nthpermutation-com.20150623.gappssmtp.com Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Lt1EgnsYvMWq for ; Fri, 3 Jan 2020 11:03:22 -0800 (PST) Received: from mail-qt1-x836.google.com (mail-qt1-x836.google.com [IPv6:2607:f8b0:4864:20::836]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A745012009E for ; Fri, 3 Jan 2020 11:03:22 -0800 (PST) Received: by mail-qt1-x836.google.com with SMTP id n15so37568023qtp.5 for ; Fri, 03 Jan 2020 11:03:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nthpermutation-com.20150623.gappssmtp.com; s=20150623; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-language; bh=uNbJyfZJLKSy068FP29Do+L5t+e0If1D7B/1Et9uoeA=; b=EU4TZoRcvB1YIgEC3o6HEJJcGNUzof7Wca15wEQEglv/xAR7YuNBwtLVc8E4CAU0FZ UIUgQz7ka+zPhZaI417TwqkibRpUO+vGcuMlrUsj4jD8AjY8vZOxezLTbOvCiWeWdb1+ U5A1dbDi0bfI7QDioVEWkM+blyviBrgMzwR1pnveVdhhTl1FL4Xl3jeJItickR8CzoIb /+v3QdzNpbuUMgBIMVi2i+aLHTYWohdH0LlqHtj7VOpYAVUaGE0FKBeqrs1Oir6UC8j+ XCg+0k4W+a3+nIcyDzppIZlZkpDLTKWHBtj+UZz8V9oZvLM8C2CtV0ivlaiY8SHs1eWL iQgw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=uNbJyfZJLKSy068FP29Do+L5t+e0If1D7B/1Et9uoeA=; b=Y2JMZPiPYB+lfZ71yjtr7edpulcsC4CknjpzLuppAU6YgjRUIVO941o6Xo8C1pa6hO TIUr558KTZLe2UNCvkyQaksHg1RSnMFms5ga1WM2hehW37+cn9FIrnjhUe4ycQxt/MDx GMCIbWVlhZ1n+2GiBJ1knOME3vinWrx9glhvNYIOefwiKI5JWYGkwioKq5rJGoXRF7j4 cOzxNqugroybVv+85J22YR5+IngksN0pHjpyLCYOpx26pp0P+FYqu7u5zOXR007JXrAQ G5I0qKEs0UbtZDLoaz648g+iRBEq7mZyLFVhhW9tXbbsu/QE2uejc/gdHghrwc8BM1Z6 iltg== X-Gm-Message-State: APjAAAV0HuMQxMvmFPyIpZFmyGPrVWMh7AvIwPYyRAlRZsQidy6CC6F4 zVFK4+DOylJztXhjsHKN+fTGZml2Woc= X-Google-Smtp-Source: APXvYqzaqYpLrfazj6oRR1PNn4Ec5Cl/ukfb0VleAggbmY7TK7KkWoY4ua8S7MEx7oetUmcGFMN5SQ== X-Received: by 2002:ac8:383d:: with SMTP id q58mr64117008qtb.45.1578078201240; Fri, 03 Jan 2020 11:03:21 -0800 (PST) Received: from ?IPv6:2601:152:4400:437c:a949:4b97:3f5f:3aa? ([2601:152:4400:437c:a949:4b97:3f5f:3aa]) by smtp.gmail.com with ESMTPSA id m8sm13108664qtk.60.2020.01.03.11.03.20 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 03 Jan 2020 11:03:20 -0800 (PST) To: cfrg@irtf.org References: <902BF3DD-4515-4A23-B7B7-0C9D8726E56F@gnunet.org> <0D2BAF97-6A23-4F74-9E20-F56E34ECDF10@gmail.com> From: Michael StJohns Message-ID: <5aaadff7-3752-e49c-a386-194da312e3cd@nthpermutation.com> Date: Fri, 3 Jan 2020 14:03:19 -0500 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.1 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/alternative; boundary="------------C7126C6B3E4A062FDD84B7F4" Content-Language: en-US Archived-At: Subject: Re: [Cfrg] Threshold signatures X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 03 Jan 2020 19:03:27 -0000 This is a multi-part message in MIME format. --------------C7126C6B3E4A062FDD84B7F4 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit On 1/3/2020 12:22 PM, Phillip Hallam-Baker wrote: > On Fri, Jan 3, 2020 at 12:08 PM Dan Wing > 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 --------------C7126C6B3E4A062FDD84B7F4 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit
On 1/3/2020 12:22 PM, Phillip Hallam-Baker wrote:
On Fri, Jan 3, 2020 at 12:08 PM Dan Wing <danwing@gmail.com> 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


--------------C7126C6B3E4A062FDD84B7F4--