From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 3A175C013E for ; Mon, 2 Mar 2020 20:02:20 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 2E68281FCC for ; Mon, 2 Mar 2020 20:02:20 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EHctkDaAQSnW for ; Mon, 2 Mar 2020 20:02:18 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-ot1-f49.google.com (mail-ot1-f49.google.com [209.85.210.49]) by whitealder.osuosl.org (Postfix) with ESMTPS id B412C81F48 for ; Mon, 2 Mar 2020 20:02:18 +0000 (UTC) Received: by mail-ot1-f49.google.com with SMTP id i14so563760otp.5 for ; Mon, 02 Mar 2020 12:02:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=NENuT9z8OBl2O5tpWMyvH228iZ+zXKW8T2xt8//YUbw=; b=kM7LjZzqIbCj6GkUPXFnN+Kv59PRO8seemPUX9NB7avsSZ4QnD2seIC6ibF8Ov732w VmW2CQkfPXC4w7L8xM8zcxcdIejFZlHHY0ERWCKfKCM/K7W72QqD8cCSYBxExApuCzOH l2POk7sZsEMq4SKQfOolUt9NJJbJVD7b4K5EMRDNMIwGXl9zEQcSamDDXe687K7ipqXy Kch+X1foSYdKAdLXeUfoUW0jEKQHsZU15jRHi+7C8StG8JICiCIuu7DGcRw0LSaAcmC1 N+x6ux21Sdeoi2kvCTm/oKMJAosomBWLgyUVM10+REj8c5eXGDlCZrn9CHVxKuerHyN6 FB9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=NENuT9z8OBl2O5tpWMyvH228iZ+zXKW8T2xt8//YUbw=; b=eVIDwGgJMPpGgsXa+Z08Mhl5n8D1ywOcQIgyn2iWD83+mcySxIWadYgr2dkQE6N4CM jyQ5QuoMJnJYxl0l2UN5QJ4tb4ErkSYfeWfk1gJrRaQQvTrAr6PNn/qx6LeYffBCJcxF xvF/6fIo3OnyxEwHGTPqBGrcuQ6Z9cfcsbnuVbxS1WG//+kSKUq5ykDJnZMFQcSjrGKo WnH0awJmmr1MVHg616Yt6nBRJsZ4zAvqT/Gc8qnuF+CjM95s8UD6YqrzYSi2w9K4Y0OY 8pZigbaKIN5ohFoIBRG6md4iqEHBnsLzrZiXRzTKFYMpwa8HczKu5NuzWsGcKK3jHRwp iHEg== X-Gm-Message-State: ANhLgQ3xUJ6Ul1hufjx3DydVzHnNHlbXaCNJTZX0AiHRe1frJdt0JdYl i1zPVE4rRb2b5emzRW6jjdt9Jhq3q8LNLSmoy9c= X-Google-Smtp-Source: ADFU+vuvKmwu/9c4AyOfDfWMhA8Np6ejnstP7vfzASN/uOytwXDYPUaOGM+aKOBeuW3u6VNXhsn3ro8Hb/2g5Uun8JY= X-Received: by 2002:a05:6830:155a:: with SMTP id l26mr645165otp.339.1583179337632; Mon, 02 Mar 2020 12:02:17 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Dustin Dettmer Date: Mon, 2 Mar 2020 12:01:51 -0800 Message-ID: To: Stepan Snigirev , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000090e61059fe4aaf2" X-Mailman-Approved-At: Tue, 03 Mar 2020 14:38:56 +0000 Subject: Re: [bitcoin-dev] Nonce blinding protocol for hardware wallets and airgapped signers X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 02 Mar 2020 20:02:20 -0000 --000000000000090e61059fe4aaf2 Content-Type: text/plain; charset="UTF-8" Stepan have you spent any time considering a scheme that could involve HD keys, preregistering n (ie. 1000) preimages, or something similar to reduce the number of rounds at time of signing? Would a zero knowledge solution allow for a reduction in rounds? On Wed, Feb 26, 2020 at 7:13 PM Stepan Snigirev via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > This topic appeared in the list a few times so I would like to discuss it > in more detail and maybe push forward to standardization. > > We have to accept that any hardware wallet or an air-gapped computer we > use to sign transactions can be compromised. It may happen via a supply > chain attack or malicious firmware update. > > If the signer is isolated (faraday cage, airgap and so on), it still can > leak private keys to the outside world by choosing nonces for signatures in > a funny way such that the attacker can calculate our private keys. Back in > the days, I wrote a small post [1] and a proof-of-concept demo [2] of this > attack. > > Deterministic nonce generation can be verified only if we have private > keys somewhere else. It doubles the attack surface - now we need to > maintain two independent signers from different vendors that use the same > private key and the same deterministic algorithm for a nonce generation. In > addition to that, as Pieter mentioned in the Schnorr-BIP, deterministic > nonces are vulnerable to glitch attacks [3]. > > A simple way to fix it is by forcing the signer to use additional entropy > from the host. This protocol takes away the privilege of picking nonce from > the signer and doesn't require any secret material outside the signer. > > I suggest the following implementation of the protocol for signing a > message `m`: > > 1. Host picks a random number `n` and sends its hash together with the > message `m` to the signer. > 2. Signer computes a nonce `k` it wants to use for signing. It can be > either a deterministic scheme or using RNG. Signer commits to the chosen > nonce by sending the corresponding point `R=kG` to the host. > 3. Host sends the preimage `n` to the signer > 4. Signer tweaks the nonce by this number `k'=k+n`, signs the message and > sends back the signature (R',s) > 5. Host verifies that the public point in the signature is tweaked by n: > `R'==R+nG` > > ASCII-art: > > Host Untrusted signer > 1. Pick random n --- sha256(n),m --> calculate nonce k > 2. <------ R=kG ------ commit to k > 3. Send preimage -------- n -------> sign with nonce k'=k+n > 4. Verify R'==R+nG <------- sig ------ > > I believe this protocol solves the problem. A drawback of this scheme is > that the number of communication rounds doubles, so it might be pretty > inconvenient for air-gapped remotely located signers. > > I also suggest the following extensions that might be helpful for certain > use-cases > > # Extensions > > ## Multiple hosts > > There are some use-cases where multiple hosts are involved in the setup > and all hosts don't trust each other and the signer. So all of them want to > give extra entropy to the signer and verify that it was included. At the > moment I have exactly this scenario - our main MCU doesn't trust the > proprietary closed-source secure element, and the computer doesn't trust > the whole hardware wallet. We need a way to convince both of them that > their entropy was used in the nonce. > > It can be solved by concatenating hashes and preimages: > > Host1 ------- h(n1) --> Host 2 -- h(n1) h(n2) --> Signer > <--- R+n2 G ----- <------- R ------- > ------- n1 -----> ------ n1 n2 ----> sign with k''=k+n1+n2 > Ver: R''==R'+n1 G Ver: R''==R+n2 G + n1 G > > In this case, the first host doesn't even notice that the second host was > also using this protocol and mixing in the entropy. And the signer only > needs to add one extra number to the nonce. > > ## Stateless random signer > > If the signer wants to generate a nonce non-deterministically but doesn't > have an ability to store a generated nonce it may send back to the host > some meta-information that would help it to re-generate the same nonce > later. It can be for example additional random data used in a deterministic > scheme, either encrypted and authenticated or just as a plain text (I am > more a fan of encrypted though). > > Generally, the host shouldn't care what this data is about - he just > stores the data between rounds and sends it back to the signer with the > next round. > > # Implementation for PSBT > > We can either use proprietary fields [4] or define key-value pairs and add > them to the BIP-174. Depends if anyone else is interested in using this > protocol or not. > > I would suggest the following key-value per-input pairs assuming multiple > hosts want to mix in external entropy: > > 1. Key: {PSBT_IN_EXT_NONCE_HASH}|{pubkey}, Value: > {sha256(n1)}|{sha256(n2)}|... > 2. Key: {PSBT_IN_NONCE_COMMITMENT}|{pubkey}, Value: {33-byte R point} > 3. Key: {PSBT_IN_NONCE_SIGNER_METADATA}|{pubkey}, Value: {anything} > 4. Key: {PSBT_IN_EXT_NONCE_PREIMAGE}|{pubkey}, Value: {n1}|{n2}|... > > Then the signature from the signer is placed into existing > PSBT_IN_PARTIAL_SIG. Combiner and Finaliser should verify that nonce in the > signature includes external entropy and may remove their own entropy from > the set. They should also verify that the values of the fields did not > change between rounds. > > So, list, what do you think? Am I missing something? Would it be > interesting to have this protocol standardized and deployed? > > # References > > [1] > https://medium.com/cryptoadvance/hardware-wallets-can-be-hacked-but-this-is-fine-a6156bbd199 > [2] > https://github.com/stepansnigirev/chosen_nonce_demo/blob/master/HD_key.ipynb > [3] > https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#alternative-signing > [4] > https://github.com/bitcoin/bips/blob/master/bip-0174.mediawiki#proprietary-use-type > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --000000000000090e61059fe4aaf2 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Stepan have you spent any time considering a scheme that c= ould involve HD keys, preregistering n (ie. 1000) preimages, or something s= imilar to reduce the number of rounds at time of signing?

Would a zero knowledge solution allow for a reduction in rounds?

On = Wed, Feb 26, 2020 at 7:13 PM Stepan Snigirev via bitcoin-dev <bitcoin-de= v@lists.linuxfoundation.org> wrote:
This topic appeared in the list= a few times so I would like to discuss it in more detail and maybe push fo= rward to standardization.

We have to accept that any hardware wallet= or an air-gapped computer we use to sign transactions can be compromised. = It may happen via a supply chain attack or malicious firmware update.
If the signer is isolated (faraday cage, airgap and so on), it still can = leak private keys to the outside world by choosing nonces for signatures in= a funny way such that the attacker can calculate our private keys. Back in= the days, I wrote a small post [1] and a proof-of-concept demo [2] of this= attack.

Deterministic nonce generation can be verified only if we h= ave private keys somewhere else. It doubles the attack surface - now we nee= d to maintain two independent signers from different vendors that use the s= ame private key and the same deterministic algorithm for a nonce generation= . In addition to that, as Pieter mentioned in the Schnorr-BIP, deterministi= c nonces are vulnerable to glitch attacks [3].

A simple way to fix i= t is by forcing the signer to use additional entropy from the host. This pr= otocol takes away the privilege of picking nonce from the signer and doesn&= #39;t require any secret material outside the signer.

I suggest the = following implementation of the protocol for signing a message `m`:

= 1. Host picks a random number `n` and sends its hash together with the mess= age `m` to the signer.
2. Signer computes a nonce `k` it wants to use fo= r signing. It can be either a deterministic scheme or using RNG. Signer com= mits to the chosen nonce by sending the corresponding point `R=3DkG` to the= host.
3. Host sends the preimage `n` to the signer
4. Signer tweaks = the nonce by this number `k'=3Dk+n`, signs the message and sends back t= he signature (R',s)
5. Host verifies that the public point in the si= gnature is tweaked by n: `R'=3D=3DR+nG`

ASCII-art:

=C2=A0= =C2=A0Host =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Untrusted signer
1. Pick= random n =C2=A0 --- sha256(n),m --> =C2=A0calculate nonce k
2. =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 <------ R=3DkG ----= -- =C2=A0commit to k
3. Send preimage =C2=A0 -------- n -------> =C2= =A0sign with nonce k'=3Dk+n
4. Verify R'=3D=3DR+nG <------- s= ig ------

I believe this protocol solves the problem. A drawback of = this scheme is that the number of communication rounds doubles, so it might= be pretty inconvenient for air-gapped remotely located signers.

I a= lso suggest the following extensions that might be helpful for certain use-= cases

# Extensions

## Multiple hosts

There are some us= e-cases where multiple hosts are involved in the setup and all hosts don= 9;t trust each other and the signer. So all of them want to give extra entr= opy to the signer and verify that it was included. At the moment I have exa= ctly this scenario - our main MCU doesn't trust the proprietary closed-= source secure element, and the computer doesn't trust the whole hardwar= e wallet. We need a way to convince both of them that their entropy was use= d in the nonce.

It can be solved by concatenating hashes and preimag= es:

Host1 ------- h(n1) --> Host 2 -- h(n1) h(n2) --> Signer=C2=A0 =C2=A0 =C2=A0 <--- R+n2 G ----- =C2=A0 =C2=A0 =C2=A0 =C2=A0<= ------- R -------
=C2=A0 =C2=A0 =C2=A0 ------- n1 -----> =C2=A0 =C2= =A0 =C2=A0 =C2=A0------ n1 n2 ----> sign with k''=3Dk+n1+n2
V= er: R''=3D=3DR'+n1 G =C2=A0 =C2=A0 =C2=A0 Ver: R''=3D= =3DR+n2 G + n1 G

In this case, the first host doesn't even notic= e that the second host was also using this protocol and mixing in the entro= py. And the signer only needs to add one extra number to the nonce.

= ## Stateless random signer

If the signer wants to generate a nonce n= on-deterministically but doesn't have an ability to store a generated n= once it may send back to the host some meta-information that would help it = to re-generate the same nonce later. It can be for example additional rando= m data used in a deterministic scheme, either encrypted and authenticated o= r just as a plain text (I am more a fan of encrypted though).

Gener= ally, the host shouldn't care what this data is about - he just stores = the data between rounds and sends it back to the signer with the next round= .

# Implementation for PSBT

We can either use proprietary fie= lds [4] or define key-value pairs and add them to the BIP-174. Depends if a= nyone else is interested in using this protocol or not.

I would sugg= est the following key-value per-input pairs assuming multiple hosts want to= mix in external entropy:

1. Key: {PSBT_IN_EXT_NONCE_HASH}|{pubkey},= Value: {sha256(n1)}|{sha256(n2)}|...
2. Key: {PSBT_IN_NONCE_COMMITMENT}= |{pubkey}, Value: {33-byte R point}
3. Key: {PSBT_IN_NONCE_SIGNER_METADA= TA}|{pubkey}, Value: {anything}
4. Key: {PSBT_IN_EXT_NONCE_PREIMAGE}|{pu= bkey}, Value: {n1}|{n2}|...

Then the signature from the signer is pl= aced into existing PSBT_IN_PARTIAL_SIG. Combiner and Finaliser should verif= y that nonce in the signature includes external entropy and may remove thei= r own entropy from the set. They should also verify that the values of the = fields did not change between rounds.

So, list, what do you think? A= m I missing something? Would it be interesting to have this protocol standa= rdized and deployed?

# References

[1] https://medium.com/cryptoadvance/hardware-wallets-= can-be-hacked-but-this-is-fine-a6156bbd199
[2] https://github.com/stepansnigirev/chosen_nonce_demo/blob/master= /HD_key.ipynb
[3] https://gith= ub.com/bitcoin/bips/blob/master/bip-0340.mediawiki#alternative-signing<= br>[4] https://github.com/bitcoin/bi= ps/blob/master/bip-0174.mediawiki#proprietary-use-type
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000090e61059fe4aaf2--