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
|
Return-Path: <jlrubin@mit.edu>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 00D53D7E;
Fri, 4 Oct 2019 18:41:08 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4A35D735;
Fri, 4 Oct 2019 18:41:07 +0000 (UTC)
Received: from mail-io1-f49.google.com (mail-io1-f49.google.com
[209.85.166.49]) (authenticated bits=0)
(User authenticated as jlrubin@ATHENA.MIT.EDU)
by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id x94If5Vk032243
(version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT);
Fri, 4 Oct 2019 14:41:05 -0400
Received: by mail-io1-f49.google.com with SMTP id z19so15791469ior.0;
Fri, 04 Oct 2019 11:41:05 -0700 (PDT)
X-Gm-Message-State: APjAAAUgueGOyBnK1g1expWdlupR1LQjeR3emk2XzTD3rADIDl8oUXmS
mMOLktY8c9p/PDWy8RbSzsYYrcIU5Lwq+81zjBU=
X-Google-Smtp-Source: APXvYqyHb3F6Y7Wiau1aPPSs3v3RtpD8gKyBhfkUSAV8cIm1qGI9cSCSN9du0ybmU2NyOpW8QZoHeNWKrLp8u4JsLzg=
X-Received: by 2002:a92:9:: with SMTP id 9mr17774535ila.49.1570214465026; Fri,
04 Oct 2019 11:41:05 -0700 (PDT)
MIME-Version: 1.0
References: <87wodp7w9f.fsf@gmail.com>
<20191001155929.e2yznsetqesx2jxo@erisian.com.au>
<CR-etCjXB-JWkvecjDog4Pkq1SuLUgndtSrZo-V4f4EGcNXzNCeAHRvCZGrxDWw7aHVdDY0pAF92jNLb_Hct0bMb3ew6JEpB9AfIm1tSGaQ=@protonmail.com>
<CAEM=y+XbP3Dn7X8rHu7h0vbX6DkKA0vFK5nQqzcJ_V+D4EVMmw@mail.gmail.com>
<C1OLL5FLxdOgfQ_A15mf88wIyztDapkyXJ2HZ0HxwmQADhRXGRe3le7Veso4tMIlbis6I0qiCd22xug5_GCKtgrjGnBtojWxOCMgn1UldkE=@protonmail.com>
<CAEM=y+WCGSF_=WXpgXJUZCZcGUQhxzXF6Wv1_iX+VwEyYSWypg@mail.gmail.com>
<CAD5xwhi7=5eiv1jjf72-rUezZMfj3caR+PGfZEa8i8rjNjodFg@mail.gmail.com>
<20191004111536.w7snbgpoe27xutfu@petertodd.org>
In-Reply-To: <20191004111536.w7snbgpoe27xutfu@petertodd.org>
From: Jeremy <jlrubin@mit.edu>
Date: Fri, 4 Oct 2019 11:40:53 -0700
X-Gmail-Original-Message-ID: <CAD5xwhhLd9Ufv50kOi+yaJ5dTX9LhB1dPsK_0bqjz038tChcjw@mail.gmail.com>
Message-ID: <CAD5xwhhLd9Ufv50kOi+yaJ5dTX9LhB1dPsK_0bqjz038tChcjw@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary="00000000000068c19c05941a0b9a"
X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,HTML_MESSAGE,
RCVD_IN_DNSWL_MED 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>,
"lightning-dev@lists.linuxfoundation.org"
<lightning-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the
discussion about noinput / anyprevout
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: Fri, 04 Oct 2019 18:41:08 -0000
--00000000000068c19c05941a0b9a
Content-Type: text/plain; charset="UTF-8"
Interesting point.
The script is under your control, so you should be able to ensure that you
are always using a correctly constructed midstate, e.g., something like:
scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2>
OP_SHA256STREAM
<hash> OP_EQUALVERIFY
would hash all the elements on the stack and compare to a known hash.
How is that sort of thing weak to midstateattacks?
--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>
On Fri, Oct 4, 2019 at 4:16 AM Peter Todd <pete@petertodd.org> wrote:
> On Thu, Oct 03, 2019 at 10:02:14PM -0700, Jeremy via bitcoin-dev wrote:
> > Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> > OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
> > function to allow concatenation of an unlimited amount of data, provided
> > the only use is to hash it.
> >
> > You can then use it perhaps as follows:
> >
> > // start a new hash with item
> > OP_SHA256STREAM (-1) -> [state]
> > // Add item to the hash in state
> > OP_SHA256STREAM n [item] [state] -> [state]
> > // Finalize
> > OP_SHA256STREAM (-2) [state] -> [Hash]
> >
> > <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> <3> OP_SHA256STREAM
> <-2>
> > OP_SHA256STREAM
>
> One issue with this is the simplest implementation where the state is just
> raw
> bytes would expose raw SHA256 midstates, allowing people to use them
> directly;
> preventing that would require adding types to the stack. Specifically I
> could
> write a script that rather than initializing the state correctly from the
> official IV, instead takes an untrusted state as input.
>
> SHA256 isn't designed to be used in situations where adversaries control
> the
> initialization vector. I personally don't know one way or the other if
> anyone
> has analyzed this in detail, but I'd be surprised if that's secure. I
> considered adding midstate support to OpenTimestamps but decided against
> it for
> exactly that reason.
>
> I don't have the link handy but there's even an example of an experienced
> cryptographer on this very list (bitcoin-dev) proposing a design that falls
> victim to this attack. It's a subtle issue and we probably don't want to
> encourage it.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
--00000000000068c19c05941a0b9a
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:#000000">Interesting point. <br></=
div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-=
serif;font-size:small;color:#000000"><br></div><div class=3D"gmail_default"=
style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:#000=
000">The script is under your control, so you should be able to ensure that=
you are always using a correctly constructed midstate, e.g., something lik=
e:<br></div><div class=3D"gmail_default" style=3D"font-family:arial,helveti=
ca,sans-serif;font-size:small;color:#000000"><br></div><div class=3D"gmail_=
default" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;co=
lor:#000000">scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM=
<-2> OP_SHA256STREAM<br clear=3D"all"></div><div><div dir=3D"ltr" cl=
ass=3D"gmail_signature" data-smartmail=3D"gmail_signature"><div dir=3D"ltr"=
><div style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color=
:rgb(0,0,0)" class=3D"gmail_default"><hash> OP_EQUALVERIFY</div><div =
style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:rgb(0=
,0,0)" class=3D"gmail_default"><br></div><div style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:rgb(0,0,0)" class=3D"gmail_default=
">would hash all the elements on the stack and compare to a known hash.<br>=
</div></div><div dir=3D"ltr"><div style=3D"font-family:arial,helvetica,sans=
-serif;font-size:small;color:rgb(0,0,0)" class=3D"gmail_default"></div><div=
style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:rgb(=
0,0,0)" class=3D"gmail_default">How is that sort of thing weak to midstatea=
ttacks?</div><div style=3D"font-family:arial,helvetica,sans-serif;font-size=
:small;color:rgb(0,0,0)" class=3D"gmail_default"></div><br></div><div dir=
=3D"ltr"><br></div><div dir=3D"ltr">--<br><a href=3D"https://twitter.com/Je=
remyRubin" target=3D"_blank">@JeremyRubin</a><a href=3D"https://twitter.com=
/JeremyRubin" target=3D"_blank"></a></div></div></div><br></div><br><div cl=
ass=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Fri, Oct 4, 20=
19 at 4:16 AM Peter Todd <<a href=3D"mailto:pete@petertodd.org">pete@pet=
ertodd.org</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex">On Thu, Oct 03, 2019 at 10:02:14PM -0700, Jeremy via bitcoin-dev=
wrote:<br>
> Awhile back, Ethan and I discussed having, rather than OP_CAT, an<br>
> OP_SHA256STREAM that uses the streaming properties of a SHA256 hash<br=
>
> function to allow concatenation of an unlimited amount of data, provid=
ed<br>
> the only use is to hash it.<br>
> <br>
> You can then use it perhaps as follows:<br>
> <br>
> // start a new hash with item<br>
> OP_SHA256STREAM=C2=A0 (-1) -> [state]<br>
> // Add item to the hash in state<br>
> OP_SHA256STREAM n [item] [state] -> [state]<br>
> // Finalize<br>
> OP_SHA256STREAM (-2) [state] -> [Hash]<br>
> <br>
> <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3=
> <3> OP_SHA256STREAM <-2><br>
> OP_SHA256STREAM<br>
<br>
One issue with this is the simplest implementation where the state is just =
raw<br>
bytes would expose raw SHA256 midstates, allowing people to use them direct=
ly;<br>
preventing that would require adding types to the stack. Specifically I cou=
ld<br>
write a script that rather than initializing the state correctly from the<b=
r>
official IV, instead takes an untrusted state as input.<br>
<br>
SHA256 isn't designed to be used in situations where adversaries contro=
l the<br>
initialization vector. I personally don't know one way or the other if =
anyone<br>
has analyzed this in detail, but I'd be surprised if that's secure.=
I<br>
considered adding midstate support to OpenTimestamps but decided against it=
for<br>
exactly that reason.<br>
<br>
I don't have the link handy but there's even an example of an exper=
ienced<br>
cryptographer on this very list (bitcoin-dev) proposing a design that falls=
<br>
victim to this attack. It's a subtle issue and we probably don't wa=
nt to<br>
encourage it.<br>
<br>
-- <br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> 'peter'[:-1]@<a href=3D"http://petertodd.org"=
rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
_______________________________________________<br>
Lightning-dev mailing list<br>
<a href=3D"mailto:Lightning-dev@lists.linuxfoundation.org" target=3D"_blank=
">Lightning-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev=
" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/ma=
ilman/listinfo/lightning-dev</a><br>
</blockquote></div>
--00000000000068c19c05941a0b9a--
|
