1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
Return-Path: <freedom@reardencode.com>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id E359AC0177
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 27 Feb 2020 03:33:16 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by fraxinus.osuosl.org (Postfix) with ESMTP id DA56B86C2B
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 27 Feb 2020 03:33:16 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from fraxinus.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id JdhLSLGgsEOP
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 27 Feb 2020 03:33:16 +0000 (UTC)
X-Greylist: delayed 00:07:05 by SQLgrey-1.7.6
Received: from mail.reardencode.com (mail.reardencode.com [206.125.169.165])
by fraxinus.osuosl.org (Postfix) with ESMTPS id 063E186C19
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 27 Feb 2020 03:33:16 +0000 (UTC)
Date: Wed, 26 Feb 2020 19:26:07 -0800
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=reardencode.com;
s=mail; t=1582773969;
bh=lQwdS68xs7SOr7+wZUKd5jEOkdwnc/tnqDxFTYZ3sZg=;
h=Date:From:To:Subject;
b=hX+dKAoyzb5UPPEBaiMPeolmya+iRjG7tZ01A5zghkHLUS88Q1bzKKPhw5fEd+zcs
76/tQMrN8x/0JD3T+xyVMCmRHn7sPoT733R2UfpTAJsZkfis6bAkNmJrFHWNxUy4KI
DR2TiLOelkkYkT2RhclM189PYgGWBCzDLkcubM00=
From: freedom@reardencode.com
To: bitcoin-dev@lists.linuxfoundation.org,
Stepan Snigirev <snigirev.stepan@gmail.com>
Message-ID: <2dcae576-983a-40d9-a0aa-de0f0381cb4e.maildroid@localhost>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
X-Mailman-Approved-At: Thu, 27 Feb 2020 03:40:57 +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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Thu, 27 Feb 2020 03:33:17 -0000
I've been working on developing exactly this for a hardware wallet in working on as well. So far I only had a rough sketch of how the comments would flow. I'd be thrilled to see this standardized.
Thanks much,
--Brandon, sent by an android
-----Original Message-----
From: Stepan Snigirev via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
To: bitcoin-dev@lists.linuxfoundation.org
Sent: Wed, 26 Feb 2020 19:13
Subject: [bitcoin-dev] Nonce blinding protocol for hardware wallets and airgapped signers
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
|
