MIME-Version: 1.0
References: <CACL8y1vNEOfATJvkYTOV3pZQA5uac3hbTe9Onfz-38zJUzL_Ug@mail.gmail.com>
In-Reply-To: <CACL8y1vNEOfATJvkYTOV3pZQA5uac3hbTe9Onfz-38zJUzL_Ug@mail.gmail.com>
From: Dustin Dettmer <dustinpaystaxes@gmail.com>
Date: Mon, 2 Mar 2020 12:01:51 -0800
Message-ID: <CABLeJxT4mCfrM7K+ygHk6CwSEnHUTdCPjR5VOrMVvA6EmDm6VA@mail.gmail.com>
To: Stepan Snigirev <snigirev.stepan@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000090e61059fe4aaf2"
Subject: Re: [bitcoin-dev] Nonce blinding protocol for hardware wallets and
 airgapped signers
Precedence: list

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

<div dir=3D"ltr">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?<div><br></div><di=
v>Would a zero knowledge solution allow for a reduction in rounds?</div></d=
iv><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On =
Wed, Feb 26, 2020 at 7:13 PM Stepan Snigirev via bitcoin-dev &lt;<a href=3D=
"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-de=
v@lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gm=
ail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,=
204,204);padding-left:1ex"><div dir=3D"ltr">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.<br><br>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.<br><b=
r>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.<br><br>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].<br><br>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.<br><br>I suggest the =
following implementation of the protocol for signing a message `m`:<br><br>=
1. Host picks a random number `n` and sends its hash together with the mess=
age `m` to the signer.<br>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.<br>3. Host sends the preimage `n` to the signer<br>4. Signer tweaks =
the nonce by this number `k&#39;=3Dk+n`, signs the message and sends back t=
he signature (R&#39;,s)<br>5. Host verifies that the public point in the si=
gnature is tweaked by n: `R&#39;=3D=3DR+nG`<br><br>ASCII-art:<br><br>=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<br>1. Pick=
 random n =C2=A0 --- sha256(n),m --&gt; =C2=A0calculate nonce k<br>2. =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 &lt;------ R=3DkG ----=
-- =C2=A0commit to k<br>3. Send preimage =C2=A0 -------- n -------&gt; =C2=
=A0sign with nonce k&#39;=3Dk+n<br>4. Verify R&#39;=3D=3DR+nG &lt;------- s=
ig ------<br><br>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.<br><br>I a=
lso suggest the following extensions that might be helpful for certain use-=
cases<br><br># Extensions<br><br>## Multiple hosts<br><br>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&#39;t trust the proprietary closed-=
source secure element, and the computer doesn&#39;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.<br><br>It can be solved by concatenating hashes and preimag=
es:<br><br>Host1 ------- h(n1) --&gt; Host 2 -- h(n1) h(n2) --&gt; Signer<b=
r>=C2=A0 =C2=A0 =C2=A0 &lt;--- R+n2 G ----- =C2=A0 =C2=A0 =C2=A0 =C2=A0&lt;=
------- R -------<br>=C2=A0 =C2=A0 =C2=A0 ------- n1 -----&gt; =C2=A0 =C2=
=A0 =C2=A0 =C2=A0------ n1 n2 ----&gt; sign with k&#39;&#39;=3Dk+n1+n2<br>V=
er: R&#39;&#39;=3D=3DR&#39;+n1 G =C2=A0 =C2=A0 =C2=A0 Ver: R&#39;&#39;=3D=
=3DR+n2 G + n1 G<br><br>In this case, the first host doesn&#39;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.<br><br>=
## Stateless random signer<br><br>If the signer wants to generate a nonce n=
on-deterministically but doesn&#39;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). <br><br>Gener=
ally, the host shouldn&#39;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=
.<br><br># Implementation for PSBT<br><br>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.<br><br>I would sugg=
est the following key-value per-input pairs assuming multiple hosts want to=
 mix in external entropy:<br><br>1. Key: {PSBT_IN_EXT_NONCE_HASH}|{pubkey},=
 Value: {sha256(n1)}|{sha256(n2)}|...<br>2. Key: {PSBT_IN_NONCE_COMMITMENT}=
|{pubkey}, Value: {33-byte R point}<br>3. Key: {PSBT_IN_NONCE_SIGNER_METADA=
TA}|{pubkey}, Value: {anything}<br>4. Key: {PSBT_IN_EXT_NONCE_PREIMAGE}|{pu=
bkey}, Value: {n1}|{n2}|...<br><br>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.<br><br>So, list, what do you think? A=
m I missing something? Would it be interesting to have this protocol standa=
rdized and deployed?<br><br># References<br><br>[1] <a href=3D"https://medi=
um.com/cryptoadvance/hardware-wallets-can-be-hacked-but-this-is-fine-a6156b=
bd199" target=3D"_blank">https://medium.com/cryptoadvance/hardware-wallets-=
can-be-hacked-but-this-is-fine-a6156bbd199</a><br>[2] <a href=3D"https://gi=
thub.com/stepansnigirev/chosen_nonce_demo/blob/master/HD_key.ipynb" target=
=3D"_blank">https://github.com/stepansnigirev/chosen_nonce_demo/blob/master=
/HD_key.ipynb</a><br>[3] <a href=3D"https://github.com/bitcoin/bips/blob/ma=
ster/bip-0340.mediawiki#alternative-signing" target=3D"_blank">https://gith=
ub.com/bitcoin/bips/blob/master/bip-0340.mediawiki#alternative-signing</a><=
br>[4] <a href=3D"https://github.com/bitcoin/bips/blob/master/bip-0174.medi=
awiki#proprietary-use-type" target=3D"_blank">https://github.com/bitcoin/bi=
ps/blob/master/bip-0174.mediawiki#proprietary-use-type</a><br></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000090e61059fe4aaf2--