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
|
Return-Path: <crypto@timruffing.de>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id A2578C07FF
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 21 Mar 2020 13:34:24 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by fraxinus.osuosl.org (Postfix) with ESMTP id 990D8873FE
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 21 Mar 2020 13:34:24 +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 Xc8xAry3yJ1N
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 21 Mar 2020 13:34:22 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mout-p-201.mailbox.org (mout-p-201.mailbox.org [80.241.56.171])
by fraxinus.osuosl.org (Postfix) with ESMTPS id 81DCF873F3
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 21 Mar 2020 13:34:22 +0000 (UTC)
Received: from smtp1.mailbox.org (smtp1.mailbox.org [80.241.60.240])
(using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits))
(No client certificate requested)
by mout-p-201.mailbox.org (Postfix) with ESMTPS id 48l1p34p7QzQl8k;
Sat, 21 Mar 2020 14:34:19 +0100 (CET)
X-Virus-Scanned: amavisd-new at heinlein-support.de
Received: from smtp1.mailbox.org ([80.241.60.240])
by hefe.heinlein-support.de (hefe.heinlein-support.de [91.198.250.172])
(amavisd-new, port 10030)
with ESMTP id xAiOYPXmxy8j; Sat, 21 Mar 2020 14:34:15 +0100 (CET)
Message-ID: <de7bd393327015a5b97ffff0d15a7c90d2d2196a.camel@timruffing.de>
From: Tim Ruffing <crypto@timruffing.de>
To: Pieter Wuille <bitcoin-dev@wuille.net>, Bitcoin Protocol Discussion
<bitcoin-dev@lists.linuxfoundation.org>
Date: Sat, 21 Mar 2020 14:34:14 +0100
In-Reply-To: <VZTbLR9RlkkyNg6mOOIxedh7H0g8NGlaCmgBfCVXZ4RNfW3axefgoTqZGXjAQZFEuekujVGjRMv8SifDIodZ6tRGaaXQ_R63rFa03SGS6rg=@wuille.net>
References: <VZTbLR9RlkkyNg6mOOIxedh7H0g8NGlaCmgBfCVXZ4RNfW3axefgoTqZGXjAQZFEuekujVGjRMv8SifDIodZ6tRGaaXQ_R63rFa03SGS6rg=@wuille.net>
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
X-Mailman-Approved-At: Sat, 21 Mar 2020 16:46:24 +0000
Subject: Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques
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: Sat, 21 Mar 2020 13:34:24 -0000
Hi Pieter,
That's a really nice overview.
Let's take a step back first. If we believe that malicious hardware
wallets are big enough of a concern, then signing is only part of the
problem. The other issue is key generation. The PRG from which the seed
is derived can be malicious, e.g., just H(k_OO,counter) for a key k_OO
chosen by the hardware manufacturer. I haven't seen an argument why
attacks during the signing model should more realistic than attacks
during key generation, so I'd be very hesitant to deploy anti-covert
channel singing protocols without deploying protocols for key
generation that are secure in the same attacker model.
While there's a bunch of protocols for signing, there's not much
research for key generation. One simple idea is a simple commit-and-
reveal protocol to generate a master (elliptic curve) public key pair
with entropy contributions from both HW and SW (similar to the
protocols here for generating R). Then use BIP32 public derivation for
all other keys in order to make sure that SW can verify the derivation
of the public kyes. The corresponding master secret key would replace
the seed, i.e., there's no "symmetric" seed. That idea comes with other
drawbacks however, most importantly this is not compatible with
hardened derivation, which creates a new security risk. If we want
(something like) hardened derivation, zero-knowledge proofs of correct
derivation could maybe used but they again come with other issues
(efficiency, complexity).
By the way, here's a paper that considers a similar setting where the
hardware wallet is also malicious during key generation:
https://fc19.ifca.ai/preproceedings/93-preproceedings.pdf
This model goes a step further and assumes threshold signatures but
interestingly here the human user (instead of the SW) is the trusted
party interacting with the HW. In this model the human user has a low-
entropy password.
Now back to the signing process: I think yet another security property
to look at is security against a malicious SW with parallel signing
sessions. I think it's reasonable to restrict a single HW device to a
single session but what if the same seed is stored in two or more HW
wallets? That's plausible at least. Taking this additional security
property into account, it appears that Scheme 4 is vulnerable to
Wagner's attack because SW can influence R by choosing t after seeing
R0. (This can be fixed, e.g., by using Scheme 5 instead.)
On Tue, 2020-03-03 at 21:35 +0000, Pieter Wuille via bitcoin-dev wrote:
> 2.d) Statefulness
>
> We're left with Schemes 4 and 5 that protect against all listed
> issues. Both
> need two interaction rounds, with state that needs to be kept by HW
> between
> the rounds (the k0 value). While not a problem in theory, this may be
> hard to
> implement safely in simple APIs.
A generic way to make one party (HW in this case) stateless is to let
it encrypt and authenticate its state, e.g., using AEAD. In our
particular case I think that the state does not need to be
confidential, and a simple MAC suffices. For simplicity let's assume we
have another hash function H' (modeled as a random oracle) used as MAC.
We can (ab)use d as a MAC key.
If we don't want to spend an entire signature verification on the side
of HW to protect against fault attacks, we can additionally let SW
compute and send the challenge hash e=H(R,Q,m) and let HW only verify
the computation of e. This helps against fault-attacks in the
computation of R and e because now SW needs to commit to e, which is a
commitment to the exact computation fault that HW will suffer from. But
I'm not sure yet if this is weaker or stronger or incomparable to
verifying the signature. I guess it's weaker [1]. If we don't drop
signature verification, this technique does not hurt at least.
[Scheme 7: synthetic nonce, two interactions, stateless using MAC,
verifying e]
First interaction:
* SW generates a random t, computes h=H(t), and requests the R0 point
that HW would use by sending (Q,m,h) to HW.
* HW uses a global counter c (or fresh randomness c), and computes
k0=H(d,m,c,h), R0=k0G, mac=H'(d,m,c,h) and sends R0,c,mac to SW.
Second interaction:
* SW computes R=R0+tG, e=H(R,Q,m) and requests a signature by sending
(Q,m,t,e,c,mac) to HW
* HW verifies mac=H'(d,m,c,H(t)), recomputes k0=H(d,m,c,H(t)), k=k0+t,
computes R=kG, verifies e=H(R,Q,m), and if all is good computes
s=k+H(R,Q,m)d and sends s to SW.
* SW verifies that sG=R+eQ and publishes (R,s) if all is good.
One last observation: Since the inputs to H and H' are the same, we
could even use H'(x)=H(H(x)). Not sure if that's useful.
Best,
Tim
[1] In the (admittedly weird) case that faults in two runs of the
executions are independent and can be made highly likely (say
probability almost 1), verifying e could indeed be stronger than
verifying the signature: When verifying the signature, the fault attack
is successful if the *same* fault happens during signing and
verification (birthday collision!). When verifying e instead, the
attack is successful if the attacker predicts the fault correctly. But
I guess if faults can be made very likely, there's no hope anyway.
|
