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
|
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 62B936C
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 25 Feb 2017 18:37:31 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f68.google.com (mail-vk0-f68.google.com
[209.85.213.68])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DF1A914E
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 25 Feb 2017 18:37:30 +0000 (UTC)
Received: by mail-vk0-f68.google.com with SMTP id r136so3538671vke.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 25 Feb 2017 10:37:30 -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;
bh=k0BpqV/9DBJSAzeDAUUXuJr/bzQ3jhX1I3QVhNsLrNA=;
b=ZYqVe95VMpZswyWCN80bQIL1N4K7SH1ZxJSn63KT7lGmUdKrCdIjY46GveqvhCwXfF
o2g8VmWFtipvDLBkkZpORyCT5kdLAtEAXPoOxzjjZ4vnV86jYSDu6inGNRkLnE31z8+i
6c+MsleOGabdAsgaYI5Kf0VbpwxK0dRVPLgiAAKg390Prpm1V66Cjda0FNHl38SDKmlK
I+t3FW9gNLxxoiTKxxk+DFZVcc5+PMVvbPpG3aIBrakR9KRzCQh5vP1PUpIsM2Ll9B5B
iBm/VKaCCjtnfCI+UqPp3TAoGXCCFxNb63vmIAwCvKkdlzLCQ7URe5Yy0E6sWVQQj1ni
M4qg==
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;
bh=k0BpqV/9DBJSAzeDAUUXuJr/bzQ3jhX1I3QVhNsLrNA=;
b=t+79kFLruWEfCUNCMmQ1ovzaLgQVo4e05ikPwxJiyc+X3VPP0u5IQA08BNi9HvEDnr
W0cLlE8h1lQ04u9bBZMF65HYpQOvVVYvPSv1mLLppzcMJu7Zdk66QAC41sXUyttkb5J0
DRRdwPTdFwN2L3sgwxx8olRZQpYIMpOcS185ouPwGOQx17kAS4USrkrL4Pwaw3sNfUfy
ZLhQv2tIEP0vQqEsKZ2U8KGB7AFK4Mruqfl3F8wvHC8jZA76G8cB0NYMdC1ncCCKxahx
x71III8javof/lGyj1suJY6PE/6N0pXzX346pPTl/PUay7ZUsF/pittRFPNBcs2MgPla
vmiQ==
X-Gm-Message-State: AMke39mWKzYMd1YAmlyw3HVsxNOMnBiRr+tR6D7qZ98/7UhzVK4uynUaBfVsuh+2ROUatPNGonpl2gOJsKvBJg==
X-Received: by 10.31.70.66 with SMTP id t63mr2844924vka.19.1488047850065; Sat,
25 Feb 2017 10:37:30 -0800 (PST)
MIME-Version: 1.0
Received: by 10.176.6.106 with HTTP; Sat, 25 Feb 2017 10:36:49 -0800 (PST)
In-Reply-To: <f309ea73-053d-c3e9-134e-4561e89715f1@librelamp.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>
<CAEM=y+WkgSkc07ZsU6APAkcu37zVZ7dwSc=jAg1nho31S5ZyxQ@mail.gmail.com>
<f309ea73-053d-c3e9-134e-4561e89715f1@librelamp.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Sat, 25 Feb 2017 13:36:49 -0500
Message-ID: <CAEM=y+U7khq4FVift9aKewmasbdnFvn99pEkkYORmTCD-5thyQ@mail.gmail.com>
To: Alice Wonder <alice@librelamp.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a11484ae083228c05495f234b
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
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 18:37:31 -0000
--001a11484ae083228c05495f234b
Content-Type: text/plain; charset=UTF-8
>You have to not only produce a ripemd160 collision, you have to produce a
collision that is also a valid sha-256 hash - and that's much much much
more difficult.
I agree that merely finding a collision in RIPEMD-160 will be hard to use
in Bitcoin.
However finding a collision in RIPEMD-160(SHA-256(msg)) via bruteforce
(2^80 queries) is not particular more difficult than finding a collision in
RIPEMD-160 via brute force. Furthermore if you find a collision in
RIPEMD-160(SHA-256(msg)) you also get a valid SHA-256 hash for which you
know the preimage.
On Sat, Feb 25, 2017 at 1:19 PM, Alice Wonder via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> On 02/25/2017 08:10 AM, Ethan Heilman via bitcoin-dev wrote:
>
>> 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.
>>
>
> You have to not only produce a ripemd160 collision, you have to produce a
> collision that is also a valid sha-256 hash - and that's much much much
> more difficult.
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--001a11484ae083228c05495f234b
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">><span style=3D"font-size:12.8px">You have to not only =
produce a ripemd160 collision, you have to produce a collision that is also=
a valid sha-256 hash - and that's much much much more difficult.</span=
><div class=3D"gmail-yj6qo gmail-ajU" style=3D"font-size:12.8px"></div><br>=
I agree that merely finding a collision in RIPEMD-160 will be hard to use i=
n Bitcoin.<br><br>However finding a collision in RIPEMD-160(SHA-256(msg)) v=
ia bruteforce (2^80 queries) is not particular more difficult than finding =
a collision in RIPEMD-160 via brute force. Furthermore if you find a collis=
ion in RIPEMD-160(SHA-256(msg)) you also get a valid SHA-256 hash for which=
you know the preimage.<br><br></div><div class=3D"gmail_extra"><br><div cl=
ass=3D"gmail_quote">On Sat, Feb 25, 2017 at 1:19 PM, Alice Wonder via bitco=
in-dev <span dir=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfound=
ation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>><=
/span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><span class=3D"">On 02/25/2=
017 08:10 AM, Ethan Heilman via bitcoin-dev wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><blockquote class=3D"gmail_quote" style=3D"m=
argin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
SHA1 is insecure because the SHA1 algorithm is insecure, not because<br>
</blockquote>
160bits isn't enough.<br>
<br>
I would argue that 160-bits isn't enough for collision resistance.<br>
Assuming RIPEMD-160(SHA-256(msg)) has no flaws (i.e. is a random<br>
oracle), collisions can be generated in 2^80 queries (actually detecting<br=
>
these collisions requires some time-memory additional trade-offs). The<br>
Bitcoin network at the current hash rate performs roughly SHA-256 ~2^78<br>
queries a day or 2^80 queries every four days.<br>
</blockquote>
<br></span>
You have to not only produce a ripemd160 collision, you have to produce a c=
ollision that is also a valid sha-256 hash - and that's much much much =
more difficult.<div class=3D"HOEnZb"><div class=3D"h5"><br>
<br>
______________________________<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></div></blockquote></div><br></div>
--001a11484ae083228c05495f234b--
|
