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
|
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 BB0A7D36
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jan 2016 20:40:05 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f41.google.com (mail-wm0-f41.google.com [74.125.82.41])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CDE7D141
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jan 2016 20:40:04 +0000 (UTC)
Received: by mail-wm0-f41.google.com with SMTP id f206so112711518wmf.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 07 Jan 2016 12:40:04 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:content-type; bh=LMkG4tifrqujJZJ56iatRICQGCYlJ4k7tmHLqlOMiHI=;
b=T9A6EXeyMtP8/0DYo87aoJxUik1Ru4MqfZtqN2ewtSEOBPxccoWSXqbeW0/huWnRcL
oSbPG+LbnEWXwPraZE0fpMPtKKoUrUXAp6gaXoYX8i53qc/j3Eu/vrxhuDAqM8986i+t
YoTYfufwI6auxjtuomrGIGXENCS/szwofEj1WaT82LgzF883v1wgETurtfV26EVZGb8j
b+Icpd0JeAbiaFZIH9Qkoa6F6Qc+JiUYpvrX+dSbed7Gm3No5tU1bHRtdxJjtlQqiMQa
cwUeoYCeyEy15Zv78c7dV1P2dycPt5pzOnjh++Qed2smLqBTM8Rt30lHft5UbyQXPA+Z
wN8Q==
MIME-Version: 1.0
X-Received: by 10.194.113.38 with SMTP id iv6mr16574596wjb.19.1452199203648;
Thu, 07 Jan 2016 12:40:03 -0800 (PST)
Received: by 10.27.217.12 with HTTP; Thu, 7 Jan 2016 12:40:03 -0800 (PST)
In-Reply-To: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
Date: Thu, 7 Jan 2016 15:40:03 -0500
Message-ID: <CAEM=y+VNGDjS3gQRXh4qCDXccMLMTG8F30OFi-XrM=gJbJQs7A@mail.gmail.com>
From: Ethan Heilman <eth3rs@gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset=UTF-8
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Thu, 07 Jan 2016 21:22:06 +0000
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or
not?
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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: Thu, 07 Jan 2016 20:40:05 -0000
Based on current GH/s count of 775,464,121 Bitcoin tests 2^80 every 19 days.
log2(775464121*(1000*1000*1000*60*60*24*19)) = ~80.07
I don't fully understand the security model of segwit, so my analysis
will assume that any collision is bad.
>But it also requires O(2^80) storage, which is utterly infeasible
You don't store all 2^80 previous hashes, instead you just hash a seed
value 2^80 times, then look for a cycle.
seed = {0,1}^160
x = hash(seed)
for i in 2^80:
....x = hash(x)
x_final = x
y = hash(x_final)
for j in 2^80:
....if y == x_final:
........print "cycle len: "+j
........break
....y = hash(y)
If at any point x collides with a prior value of x it will form a
cycle. Thus y will also cycle and collide with x_final. j gives you
the cycle length, which allows you find the collision:
hash^(2^80-j)(seed) == hash^(j)(hash^(2^80-j)(seed)).
Worst case:
First loop costs 2**80, second loop costs 2**80=j, finding the
colliding value is 2**80. Total cost 2**80+2**80+2**80 = 2**81.5 and
requires storing less than a kilobyte.
This is a toy example, does not exploit parallelism, time memory trade
offs, can be easily made better, etc...
On Thu, Jan 7, 2016 at 2:02 PM, Gavin Andresen via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> I'm hoisting this from some private feedback I sent on the segregated
> witness BIP:
>
> I said:
>
> "I'd also use RIPEMD160(SHA256()) as the hash function and save the 12
> bytes-- a successful preimage attack against that ain't gonna happen before
> we're all dead. I'm probably being dense, but I just don't see how a
> collision attack is relevant here."
>
> Pieter responded:
>
> "The problem case is where someone in a contract setup shows you a script,
> which you accept as being a payment to yourself. An attacker could use a
> collision attack to construct scripts with identical hashes, only one of
> which does have the property you want, and steal coins.
>
> So you really want collision security, and I don't think 80 bits is
> something we should encourage for that. Normal pubkey hashes don't have that
> problem, as they can't be constructed to pay to you."
>
> ... but I'm unconvinced:
>
> "But it is trivial for contract wallets to protect against collision
> attacks-- if you give me a script that is "gavin_pubkey CHECKSIG
> arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, just
> ignore that arbitrary data" a wallet can just refuse. Even more likely, a
> contract wallet won't even recognize that as a pay-to-gavin transaction.
>
> I suppose it could be looking for some form of "gavin_pubkey
> somebody_else_pubkey CHECKMULTISIG ... with the attacker using
> somebody_else_pubkey to force the collision, but, again, trivial contract
> protocol tweaks ("send along a proof you have the private key corresponding
> to the public key" or "everybody pre-commits pubkeys they'll use at protocol
> start") would protect against that.
>
> Adding an extra 12 bytes to every segwit to prevent an attack that takes
> 2^80 computation and 2^80 storage, is unlikely to be a problem in practice,
> and is trivial to protect against is the wrong tradeoff to make."
>
> 20 bytes instead of 32 bytes is a savings of almost 40%, which is
> significant.
>
> The general question I'd like to raise on this list is:
>
> Should we be worried, today, about collision attacks against RIPEMD160 (our
> 160-bit hash)?
>
> Mounting a successful brute-force collision attack would require at least
> O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bitcoin
> POW has computed more SHA256 hashes than that). But it also requires O(2^80)
> storage, which is utterly infeasible (there is something on the order of
> 2^35 bytes of storage in the entire world). Even assuming doubling every
> single year (faster than Moore's Law), we're four decades away from an
> attacker with THE ENTIRE WORLD's storage capacity being able to mount a
> collision attack.
>
>
> References:
>
> https://en.wikipedia.org/wiki/Collision_attack
>
> https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/
>
>
> --
> --
> Gavin Andresen
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
|
