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
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
|
Return-Path: <eth3rs@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id A2912259
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 25 Feb 2017 16:10:44 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ua0-f171.google.com (mail-ua0-f171.google.com
[209.85.217.171])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A9A82172
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 25 Feb 2017 16:10:43 +0000 (UTC)
Received: by mail-ua0-f171.google.com with SMTP id h65so27898532uah.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 25 Feb 2017 08:10:43 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=4WvF2SjmI5jJhveZvfhyNStj6yxMHYX8QOfq2DqM2x8=;
b=a8KBjPQN0lt+yZm6pTV+i1o2v9igUjViWeAcVT/2FJbO/WJPuFtWW2zMrIWcbvSvZP
UgbxTiQJdvRKmwNZjmIGoCeCzgUXsANBKdv9haXaqYN7zcarZwYx/JuoNNNl5YS9uF4n
jNTOJncvtXzG9PG2vQfxnLnWKQrEVA9Bmyn0SO6mNgYX7Q7GGCQxFkJLPCSwx95mkGss
8x+WNRVgX6gN8/dsduLLSkq8+wBn9bupEBL7aPpnZF8qFi4EggLpXWIBhDR6OT4Wdfe5
+ypX5R/ffcTqToWsP766iI9XxQ5FRLF1I4G9THZGKdiThRHzgWYj7etHEx8ow1+4hz05
qS6Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=4WvF2SjmI5jJhveZvfhyNStj6yxMHYX8QOfq2DqM2x8=;
b=P8SePNfHypb/NUtk8j9nFPcH06g0tql8IVkk6yCXIGnq/GD4/rRkawsFI4meZ/3dqa
tAvo36NG4TMxbL65HKjS5GyaLJ/zbW3Emt+YfyPGSKTvtFE7bcSNgSEovxtrKEQBixbR
Zb0bn1H3GzKBgbnjpD9p1E+c2+yK3lsfyJxKOyuNrFEoDUcWL0fLyH0S3CWPN+pS4q3u
ngcYpy9tw/o2q/kZfMRsT9czo6QKa+r4DPyAyTg59Xjl8Bsp66AKIL6gkmB+OBJxP0e/
oKBEgqfm4P7Y/arOQbzUd3WfZ89DlFIHoen1dylMwVVwFA7Mw2igktUHHbvyEex0SZ96
GxOg==
X-Gm-Message-State: AMke39lTwsIwfzz4YYZ62NOp2safIkPjBmqv7jsZu2CPTuQ7WQAsZ19SJ5qQb7757hKlu8L8ZWVc7tMaqv5zKw==
X-Received: by 10.176.85.213 with SMTP id w21mr3899858uaa.75.1488039042876;
Sat, 25 Feb 2017 08:10:42 -0800 (PST)
MIME-Version: 1.0
Received: by 10.176.6.106 with HTTP; Sat, 25 Feb 2017 08:10:02 -0800 (PST)
In-Reply-To: <CAN6UTayzQRowtWhLKr8LyFuXjw3m+GjQGtHfkDj-Xu41Hym32w@mail.gmail.com>
References: <mailman.22137.1487974823.31141.bitcoin-dev@lists.linuxfoundation.org>
<8F096BE1-D305-43D4-AF10-2CC48837B14F@gmail.com>
<20170225010122.GA10233@savin.petertodd.org>
<208F93FE-B7C8-46BE-8E00-52DBD0F43415@gmail.com>
<CAN6UTayzQRowtWhLKr8LyFuXjw3m+GjQGtHfkDj-Xu41Hym32w@mail.gmail.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Sat, 25 Feb 2017 11:10:02 -0500
Message-ID: <CAEM=y+WkgSkc07ZsU6APAkcu37zVZ7dwSc=jAg1nho31S5ZyxQ@mail.gmail.com>
To: Leandro Coutinho <lescoutinhovr@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=f403045ddf82900b2a05495d16b0
X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Sat, 25 Feb 2017 16:34:48 +0000
Cc: Steve Davis <steven.charles.davis@gmail.com>
Subject: Re: [bitcoin-dev] SHA1 collisions make Git vulnerable to attakcs by
third-parties, not just repo maintainers
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: Sat, 25 Feb 2017 16:10:44 -0000
--f403045ddf82900b2a05495d16b0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
>SHA1 is insecure because the SHA1 algorithm is insecure, not because
160bits isn't enough.
I would argue that 160-bits isn't enough for collision resistance. Assuming
RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random oracle), collisions
can be generated in 2^80 queries (actually detecting these collisions
requires some time-memory additional trade-offs). The Bitcoin network at
the current hash rate performs roughly SHA-256 ~2^78 queries a day or 2^80
queries every four days. Without any break in RIPEMD-160(SHA-256(msg)) the
US could build an ASIC datacenter and produce RIPEMD-160 collisions for a
fraction of its yearly cryptologic budget.
The impact of collisions in RIPEMD-160(SHA-256(msg)) according to "On
Bitcoin Security in the Presence of Broken Crypto Primitives"(
https://eprint.iacr.org/2016/167.pdf):
>Collisions are similar, though in this case both public keys are under the
adversary=E2=80=99s control, and again the adversary does not have access t=
o the
private keys. In both scenarios, there is a question of nonrepudiation
external to the protocol itself: by presenting a second pre-image of a key
used to sign a transaction, a user/adversary can claim that his coins were
stolen.
How would such an event effect the price of Bitcoin when headlines are
"Bitcoin's Cryptography Broken"? How much money could someone make by
playing the market in this way?
For both reasons of credibility and good engineering (safety
margins) Bitcoin should strive to always use cryptography which is beyond
reproach.
On Sat, Feb 25, 2017 at 9:50 AM, Leandro Coutinho via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Google recommeds "migrate to safer cryptographic hashes such as SHA-256
> and SHA-3"
> It does not mention RIPEMD-160
>
> https://security.googleblog.com/2017/02/announcing-first-
> sha1-collision.html?m=3D1
>
>
> Em 25/02/2017 10:47, "Steve Davis via bitcoin-dev" <bitcoin-dev@lists.
> linuxfoundation.org> escreveu:
>
>
> > On Feb 24, 2017, at 7:01 PM, Peter Todd <pete@petertodd.org> wrote:
> >
> > On Fri, Feb 24, 2017 at 05:49:36PM -0600, Steve Davis via bitcoin-dev
> wrote:
> >> If the 20 byte SHA1 is now considered insecure (with good reason), wha=
t
> about RIPEMD-160 which is the foundation of Bitcoin addresses?
> >
> > SHA1 is insecure because the SHA1 algorithm is insecure, not because
> 160bits isn't enough.
> >
> > AFAIK there aren't any known weaknesses in RIPEMD160,
>
> =E2=80=A6so far. I wonder how long that vacation will last?
>
> > but it also hasn't been
> > as closely studied as more common hash algorithms.
>
> ...but we can be sure that it will be, since the dollar value held in
> existing utxos continues to increase...
>
> > That said, Bitcoin uses
> > RIPEMD160(SHA256(msg)), which may make creating collisions harder if an
> attack
> > is found than if it used RIPEMD160 alone.
>
> Does that offer any greater protection? That=E2=80=99s not so clear to me=
as the
> outputs (at least for p2pkh) only verify the public key against the final
> 20 byte hash. Specifically, in the first (notional) case the challenge
> would be to find a private key that has a public key that hashes to the
> final hash. In the second (realistic) case, you merely need to add the
> sha256 hash into the problem, which doesn=E2=80=99t seem to me to increas=
e the
> difficulty by any significant amount?
>
>
> /s
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
--f403045ddf82900b2a05495d16b0
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">><span style=3D"font-size:12.8px">SHA1 is insecure beca=
use the SHA1 algorithm is insecure, not because 160bits isn't enough.<b=
r></span><br>I would argue that 160-bits isn't enough for collision res=
istance. Assuming RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random o=
racle), collisions can be generated in 2^80 queries (actually detecting the=
se collisions requires some time-memory additional trade-offs). The Bitcoin=
network at the current hash rate performs roughly SHA-256 ~2^78 queries a =
day or 2^80 queries every four days. Without any break in RIPEMD-160(SHA-25=
6(msg))=C2=A0the US could build an ASIC datacenter and produce RIPEMD-160 c=
ollisions for a fraction of its yearly cryptologic budget.<br><br>The impac=
t of collisions in RIPEMD-160(SHA-256(msg))=C2=A0according to "On Bitc=
oin Security in the Presence of Broken Crypto Primitives"(<a href=3D"h=
ttps://eprint.iacr.org/2016/167.pdf">https://eprint.iacr.org/2016/167.pdf</=
a>):<br><br>>Collisions are similar, though in this case
both public keys are under the adversary=E2=80=99s control, and
again the adversary does not have access to the private
keys. In both scenarios, there is a question of nonrepudiation
external to the protocol itself: by presenting
a second pre-image of a key used to sign a transaction, a
user/adversary can claim that his coins were stolen.
<br><br>How would such an event effect the price of Bitcoin when headlines =
are "Bitcoin's Cryptography Broken"? How much money could som=
eone make by playing the market in this way?=C2=A0<br><br>For both reasons =
of credibility and good engineering (safety margins)=C2=A0Bitcoin should st=
rive to always use cryptography which is beyond reproach.<br><br></div><div=
class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Sat, Feb 25, 2017 =
at 9:50 AM, Leandro Coutinho via bitcoin-dev <span dir=3D"ltr"><<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin=
-dev@lists.linuxfoundation.org</a>></span> wrote:<br><blockquote class=
=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex"><div dir=3D"auto"><div>Google recommeds "migrate to safe=
r cryptographic hashes such as SHA-256 and SHA-3"<div dir=3D"auto">It =
does not mention=C2=A0<span style=3D"font-family:sans-serif">RIPEMD-160</sp=
an></div><div dir=3D"auto"><span style=3D"font-family:sans-serif"><br></spa=
n></div><div dir=3D"auto"><font face=3D"sans-serif"><a href=3D"https://secu=
rity.googleblog.com/2017/02/announcing-first-sha1-collision.html?m=3D1" tar=
get=3D"_blank">https://security.googleblog.<wbr>com/2017/02/announcing-firs=
t-<wbr>sha1-collision.html?m=3D1</a></font></div><div><div class=3D"h5"><br=
><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">Em 25/02/2017 10=
:47, "Steve Davis via bitcoin-dev" <<a href=3D"mailto:bitcoin-=
dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.<wbr>lin=
uxfoundation.org</a>> escreveu:<br type=3D"attribution"><blockquote clas=
s=3D"m_4229699082726905060quote" style=3D"margin:0 0 0 .8ex;border-left:1px=
#ccc solid;padding-left:1ex"><div class=3D"m_4229699082726905060quoted-tex=
t"><br>
> On Feb 24, 2017, at 7:01 PM, Peter Todd <<a href=3D"mailto:pete@pet=
ertodd.org" target=3D"_blank">pete@petertodd.org</a>> wrote:<br>
><br>
> On Fri, Feb 24, 2017 at 05:49:36PM -0600, Steve Davis via bitcoin-dev =
wrote:<br>
>> If the 20 byte SHA1 is now considered insecure (with good reason),=
what about RIPEMD-160 which is the foundation of Bitcoin addresses?<br>
><br>
> SHA1 is insecure because the SHA1 algorithm is insecure, not because 1=
60bits isn't enough.<br>
><br>
> AFAIK there aren't any known weaknesses in RIPEMD160,<br>
<br>
</div>=E2=80=A6so far. I wonder how long that vacation will last?<br>
<div class=3D"m_4229699082726905060quoted-text"><br>
> but it also hasn't been<br>
> as closely studied as more common hash algorithms.<br>
<br>
</div>...but we can be sure that it will be, since the dollar value held in=
existing utxos continues to increase...<br>
<div class=3D"m_4229699082726905060quoted-text"><br>
> That said, Bitcoin uses<br>
> RIPEMD160(SHA256(msg)), which may make creating collisions harder if a=
n attack<br>
> is found than if it used RIPEMD160 alone.<br>
<br>
</div>Does that offer any greater protection? That=E2=80=99s not so clear t=
o me as the outputs (at least for p2pkh) only verify the public key against=
the final 20 byte hash. Specifically, in the first (notional) case the cha=
llenge would be to find a private key that has a public key that hashes to =
the final hash. In the second (realistic) case, you merely need to add the =
sha256 hash into the problem, which doesn=E2=80=99t seem to me to increase =
the difficulty by any significant amount?<br>
<br>
<br>
/s<br>
<div class=3D"m_4229699082726905060elided-text">___________________________=
___<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundat<wbr>ion.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-d<wbr>ev</a><br>
</div></blockquote></div><br></div></div></div></div></div>
<br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div><br></div>
--f403045ddf82900b2a05495d16b0--
|
