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
|
Return-Path: <bitcoin-dev@wuille.net>
Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138])
by lists.linuxfoundation.org (Postfix) with ESMTP id D642BC0177
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 24 Mar 2020 18:56:47 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by whitealder.osuosl.org (Postfix) with ESMTP id CB95D87C8A
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 24 Mar 2020 18:56:47 +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 iQA4QEjhTDny
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 24 Mar 2020 18:56:46 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-40134.protonmail.ch (mail-40134.protonmail.ch
[185.70.40.134])
by whitealder.osuosl.org (Postfix) with ESMTPS id 4B5F687C89
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 24 Mar 2020 18:56:46 +0000 (UTC)
Date: Tue, 24 Mar 2020 18:56:38 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wuille.net;
s=protonmail; t=1585076203;
bh=5yM1hPmXUmC3iNJfKo1qaO0/M8xoK4sCNdX0JUDEJpA=;
h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From;
b=Hpoyf7D/VTY7JQ5itMbxkzcZbm91OtHtw93G5RExkUYROTOxACrVK8y/T/vDp/gWD
k4DEFF4ogBgIAm0xYhM19l4ZMPC70q9XjHimZ/1wz0OBIJ0syN31EyK/S0PvqhmIrc
X6c52+ELJ2Crr2V/7wptkaE/xZNnCLkYeJsrX+w0=
To: Lloyd Fournier <lloyd.fourn@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: Pieter Wuille <bitcoin-dev@wuille.net>
Reply-To: Pieter Wuille <bitcoin-dev@wuille.net>
Message-ID: <143g8W700TxSwkQM6rPf7NfRYcaVJoBqYLfR99gwtb-kBfL76EK556d4U8aNyEVRz5bp1eFzApLwPMSnhwAnK5m_htjqVREn5yZxXRCORiU=@wuille.net>
In-Reply-To: <CAH5Bsr3EtFpecXPG07so1KA0sre9Cy-XPv=BADBgUe4M7kuxFg@mail.gmail.com>
References: <CAH5Bsr3EtFpecXPG07so1KA0sre9Cy-XPv=BADBgUe4M7kuxFg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Mailman-Approved-At: Tue, 24 Mar 2020 19:36:25 +0000
Subject: Re: [bitcoin-dev] Mitigating Differential Power Analysis in BIP-340
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: Tue, 24 Mar 2020 18:56:48 -0000
On Tuesday, March 24, 2020 6:00 AM, Lloyd Fournier via bitcoin-dev <bitcoin=
-dev@lists.linuxfoundation.org> wrote:
> Hi List,
>
> I felt this topic deserved it's own thread but it follows on from the mai=
ling list post [2] announcing a new PR [1] to change BIP-340 in several way=
s, including adding random auxiliary=C2=A0data into the nonce derivation=
=C2=A0function. Rather than hashing the randomness with the secret key and =
message etc, the randomness is hashed then XOR'd (^) with the secret key an=
d the result is hashed like so to determine the secret nonce k:
>
> (1) k =3D H_derive( sec_key ^ H_aux(rand) || pub_key_x || message)
>
> The claim made in the mailing list post is that this is more secure again=
st "differential power analysis" (DPA) attacks than just doing the simpler =
and more efficient:
>
> (2) k =3D H_derive(sec_key || rand || pub_key_x || message)
>
> The TL;DR here is that I don't think this is the case.
Hi Lloyd,
Thank you for looking into this. I very much agree we haven't given nearly =
enough justification for the use of a non-standard scheme here.
I'll try to summarize the discussion we had that led to this choice, but mo=
st of it is on https://github.com/sipa/bips/issues/195 if you want the deta=
ils.
Let me first try to address what I think you're overlooking: in a BIP32/Tap=
root like scenario, the private key that goes into the signing algorithm fu=
nctions as *both* secret and known to the attacker. That is to say, there i=
s a master secret s, and signing key x that goes into the hash is x=3Ds+a (=
mod n) for some value a that the attacker knows, and can modify (he cannot =
control it directly, but he may be able to grind it to have a structure he =
likes). I believe that means that feeding x to a hash directly itself is al=
ready a problem, regardless of what else goes into the hash - interactions =
between bits inside the hash operation that all come from x itself can leak=
bit-level information of x. XORing (or any other simple mix operation tha=
t does not expose bit-level information) into the private key before giving=
it to a hash function seems like it would address this.
That said, all these DPA issues are very hard to reason about, as it's hard=
to find a realistic attack model that both (a) leaks some information but =
(b) doesn't obviously leak the entire key immediately. In the reasoning abo=
ve I assumed an attacker who can observe word-level Hamming weight aggregat=
es of all variables in the algorithm (which seems to match what one of the =
papers observed), but not bit level information. It also assumes that someh=
ow the computation of x itself is immune from leaks (something you pointed =
out in a previous e-mail, I noticed).
So really, all of this is trying to choose one alternative among a set of (=
when ignoring DPA) nearly equally good constructions. Note that randomness =
is useful for protection against fault attacks, but for that purpose it doe=
sn't matter where in the hash it goes, or even that it's particularly stron=
g randomness (a counter would also work). There are a number of other conce=
rns we discussed in the linked thread:
* Efficiency (how many SHA256 transformations, including the ability for so=
me to be precomputed)
* The risk that the randomness added is correlated with the private key in =
a way that cancels things out when they're naively XORed together.
* The risk of having a midstate in the hash function leak (without leaking =
the actual private key, but enough to predict nonces).
* The issue with public keys that are input to the signing algorithm which =
come directly from an attacker (which is the reason why pubkey goes into th=
e nonce function too).
The solution we came up with (H(priv XOR H(aux) || pub || msg)) is the only=
that ticks most of the boxes - but a different prioritization may certainl=
y lead to a different conclusion.
I'm happy for any input you may have here. In particular, the recent discus=
sions around the interactions between anti-covert channel protection, rando=
mness, and the ability to spot check hardware devices may mean we should re=
vise the advice to consider not adding randomness unless such a anti-covert=
channel scheme is used.
Cheers,
--
Pieter
|
