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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
|
Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 25A16CFF
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 Jul 2018 14:36:30 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f51.google.com (mail-it0-f51.google.com
[209.85.214.51])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5BEBEFC
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 Jul 2018 14:36:29 +0000 (UTC)
Received: by mail-it0-f51.google.com with SMTP id 188-v6so23130152ita.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 08 Jul 2018 07:36:29 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=blockstream.io; s=google;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=8bYjBPlFhYSokhUNeWnBLn7uHM1NN2NLLQc56TCn2as=;
b=Dug/k8fD5B68Fhz9/IrtwDDmdQoAjvT3r+U5xsPv9UU5c/WyEvr5wbeIHqmrefR2Ps
Na4ccg9hENEI66+aP5dttEojsKgsh9pvNFy4ycuH/XrROngCv1EmRxBckKQFXILgS5Jz
jWsOv5asQwW6zeg6ZONw3YDHGpaztonoL5T4Y=
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:cc;
bh=8bYjBPlFhYSokhUNeWnBLn7uHM1NN2NLLQc56TCn2as=;
b=UimvbNkwOTuFdkFIloDIlMdofPzEG7ELnvNS4AgpfFA5BinrnmWXBS1B2O8JPLFk+v
KO18HR/KXhO5yFkebZnbCfbClKb/FOnBzTofvf/2QSB9xa4e5FvDNvBJbJzuhK+X0U7v
uf7uGL/F0wDOjAeCmjdYuz7IeCGBwo6U9i5GkXB1mVCBI+ENho8OTzxrSCSOJDKRwhoi
SIyEKHmUkREUKvOvEW9/BQ7RmZsWWbuyq7Vu6J0lPzei69At3icwK9xacK2MzMvwFnuy
Z6utxAmf4lflrs7Y2t8rBX8YA4VAGi5iUMIh4IxVNx79ysSQWLOhNcOqNmh/gwi6W2UN
RKIQ==
X-Gm-Message-State: APt69E2bOVdz1gUxltAnF8xQB3dLuIbTB0Gph5q4IIao1Np9p2k9DFr6
617ZOSaq2durow/I1RLJ1FvhqBZGfUwuQIYf2xx52LHW
X-Google-Smtp-Source: AAOMgpdA+kUv4GUyvsRtyxt81l9eFVfy8x2Fbr8iEvAWycIhM/N0cxxd7L98xeTsSNzbZ0rQS+fzTyU7hbTep1/PoOw=
X-Received: by 2002:a24:7b97:: with SMTP id
q145-v6mr13389868itc.79.1531060588649;
Sun, 08 Jul 2018 07:36:28 -0700 (PDT)
MIME-Version: 1.0
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
<CAMZUoKks9of0oWdn8J=601cY2PMf+EV4e=PeWpDAXPcGPNFkRw@mail.gmail.com>
<CAAS2fgTM+8mORcgjGdQxGxMkXjW7NOqByZwD1_VEad80ofVObA@mail.gmail.com>
In-Reply-To: <CAAS2fgTM+8mORcgjGdQxGxMkXjW7NOqByZwD1_VEad80ofVObA@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Sun, 8 Jul 2018 10:36:16 -0400
Message-ID: <CAMZUoKnCkUybwMh_X3GksDW-zJ0NtfUsqfxC2sRgxpNiHFpBTQ@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>
Content-Type: multipart/alternative; boundary="00000000000084362d05707dd298"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Sun, 08 Jul 2018 14:36:30 -0000
--00000000000084362d05707dd298
Content-Type: text/plain; charset="UTF-8"
On Fri, Jul 6, 2018 at 6:00 PM, Gregory Maxwell <greg@xiph.org> wrote:
> On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > If the inputs to hash were reordered as hash(bytes(dG) || bytes(x(R)) ||
> m)
> > then there is an opportunity for SHA256 expander to be partially
> prefilled
> > for a fixed public key. This could provide a little benefit, especially
> > when multiple signatures for a single public key need to be generated
> and/or
> > verified. If all things are otherwise equal, perhaps this alternate
> order
> > is better.
>
> There is a minor design preference to have message before nonce when
> H() is a MD-style hash function. Say the attacker knows some weakness
> in H and can find pairs of messages m and m' so that the compression
> function results in the same midstate. He could then ask you to sign
> m but get a signature that also works for m'. If the signer
> controlled R value comes first, then this doesn't work. The pubkey
> being where it is in the current design just follows from the idea
> that it is just logically prepended on the message. I don't think the
> pubkey is sufficiently attacker controlled that the above argument
> would apply, so H(P || R.x || m) would be okay.
>
> BUT, the sha256 compression function reads 64 bytes at a time. PRM
> would not let you precompute a whole compression function run, but
> instead would just let you hardwire part of the expander in a pubkey
> dependant way-- an optimization I'm pretty confident virtually no one
> would use. (Hardwiring to a constant, yes. Hardwiring to a reused
> dynamic value that comes in from the network, no)
>
Right. I readily admit my proposal has extremely marginal efficiency
benefits. However, I didn't realize there is also an extremely marginal
security benefit to placing the nonce in front of everything. Although
these things are so marginal that it is perhaps a waste of time to even be
considering them, I think I'd judge the extremely marginal security benefit
to exceed the value of the extremely marginal efficiency gain. It's
probably best to leave the nonce at the beginning after all.
> If instead the hash function were defined as using 31 zeros then
> P||R||m (or P || 31 zeros bytes || R || m, I'm not sure what would be
> better), an entire midstate could be cached for different pubkeys. m
> is often 32 bytes, sadly- - but the final compression run in that case
> would only be the constant update with the length.... and
> almost-all-zeros + constant length, is an easy optimization. (Bitcoin
> core even has it for computing sha256(sha256())).
>
I did consider this, however the 31 bytes of zeros, plus the SHA256 padding
means we would need to compress *three* blocks in general instead of the
current proposal of just two blocks. This burden seems to exceed the
benefit of maybe sometimes getting a slightly fast
two-blocks-with-lots-of-zeros when public keys are reused. I wouldn't
recommend it.
There is an alternative of just dropping the SHA-256 length padding. This
would still be secure in this context because the data is of fixed size.
However, I doubt it is worth breaking the API of every SHA-256 library in
existence to enable that.
> [I'm not really sure if I was clear, so I'll try TLDRing it: I think
> optimizing sha256 where part of the input is constant is realistic,
> optimizing midstate reuse is realistic, optimizing where part is
> reused is less realistic. If we insert padding, and put P first, we
> can make it possible to midstate cache P, and the 'extra' compression
> function run ends up with all constant input, so it could be made
> faster.]
>
--00000000000084362d05707dd298
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto"><div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div =
class=3D"gmail_quote">On Fri, Jul 6, 2018 at 6:00 PM, Gregory Maxwell <span=
dir=3D"ltr"><<a href=3D"mailto:greg@xiph.org" target=3D"_blank" rel=3D"=
noreferrer">greg@xiph.org</a>></span> wrote:<br><blockquote class=3D"gma=
il_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-lef=
t:1ex"><span>On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitco=
in-dev<br>
<<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk" rel=3D"noreferrer">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:=
<br>
> If the inputs to hash were reordered as hash(bytes(dG) || bytes(x(R)) =
|| m)<br>
> then there is an opportunity for SHA256 expander to be partially prefi=
lled<br>
> for a fixed public key.=C2=A0 This could provide a little benefit, esp=
ecially<br>
> when multiple signatures for a single public key need to be generated =
and/or<br>
> verified.=C2=A0 If all things are otherwise equal, perhaps this altern=
ate order<br>
> is better.<br>
<br>
</span>There is a minor design preference to have message before nonce when=
<br>
H() is a MD-style hash function.=C2=A0 Say the attacker knows some weakness=
<br>
in H and can find pairs of messages m and m' so that the compression<br=
>
function results in the same midstate.=C2=A0 He could then ask you to sign<=
br>
m but get a signature that also works for m'.=C2=A0 =C2=A0If the signer=
<br>
controlled R value comes first, then this doesn't work.=C2=A0 =C2=A0 Th=
e pubkey<br>
being where it is in the current design just follows from the idea<br>
that it is just logically prepended on the message.=C2=A0 I don't think=
the<br>
pubkey is sufficiently attacker controlled that the above argument<br>
would apply,=C2=A0 so H(P || R.x || m) would be okay.<br>
<br>
BUT, the sha256 compression function reads 64 bytes at a time. PRM<br>
would not let you precompute a whole compression function run, but<br>
instead would just let you hardwire part of the expander in a pubkey<br>
dependant way-- an optimization I'm pretty confident virtually no one<b=
r>
would use.=C2=A0 (Hardwiring to a constant, yes. Hardwiring to a reused<br>
dynamic value that comes in from the network, no)<br></blockquote><div><br>=
</div><div>Right.=C2=A0 I readily admit my proposal has extremely marginal =
efficiency benefits. However, I didn't realize there is also an extreme=
ly marginal security benefit to placing the nonce in front of everything.=
=C2=A0 Although these things are so marginal that it is perhaps a waste of =
time to even be considering them, I think I'd judge the extremely margi=
nal security benefit to exceed the value of the extremely marginal efficien=
cy gain.=C2=A0 It's probably best to leave the nonce at the beginning a=
fter all.<br></div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
If instead the hash function were defined as using 31 zeros then<br>
P||R||m (or P || 31 zeros bytes || R || m, I'm not sure what would be<b=
r>
better), an entire midstate could be cached for different pubkeys. m<br>
is often 32 bytes, sadly- - but the final compression run in that case<br>
would only be the constant update with the length.... and<br>
almost-all-zeros + constant length, is an easy optimization. (Bitcoin<br>
core even has it for computing sha256(sha256())).<br></blockquote><div><br>=
</div><div>I did consider this, however the 31 bytes of zeros, plus the SHA=
256 padding means we would need to compress *three* blocks in general inste=
ad of the current proposal of just two blocks.=C2=A0 This burden seems to e=
xceed the benefit of maybe sometimes getting a slightly fast two-blocks-wit=
h-lots-of-zeros when public keys are reused. I wouldn't recommend it.<b=
r><br>There is an alternative of just dropping the SHA-256 length padding.=
=C2=A0 This would still be secure in this context because the data is of fi=
xed size.=C2=A0 However, I doubt it is worth breaking the API of every SHA-=
256 library in existence to enable that.<br></div><div>=C2=A0</div><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc s=
olid;padding-left:1ex">
[I'm not really sure if I was clear, so I'll try TLDRing it:=C2=A0 =
I think<br>
optimizing sha256 where part of the input is constant is realistic,<br>
optimizing midstate reuse is realistic, optimizing where part is<br>
reused is less realistic.=C2=A0 If we insert padding, and put P first, we<b=
r>
can make it possible to midstate cache P,=C2=A0 and the 'extra' com=
pression<br>
function run ends up with all constant input, so it could be made<br>
faster.]<br>
</blockquote></div><br></div></div></div>
--00000000000084362d05707dd298--
|
