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
|
Return-Path: <adam@cypherspace.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id DE17CD13
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jan 2016 19:19:44 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mout.perfora.net (mout.perfora.net [74.208.4.197])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3EBAF19D
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jan 2016 19:19:44 +0000 (UTC)
Received: from mail-ig0-f179.google.com ([209.85.213.179]) by
mrelay.perfora.net (mreueus001) with ESMTPSA (Nemesis) id
0LimxX-1ZetbW1F5Z-00cnSA for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 07 Jan 2016 20:19:43 +0100
Received: by mail-ig0-f179.google.com with SMTP id t15so35781125igr.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 07 Jan 2016 11:19:42 -0800 (PST)
MIME-Version: 1.0
X-Received: by 10.50.136.226 with SMTP id qd2mr17730162igb.37.1452194382473;
Thu, 07 Jan 2016 11:19:42 -0800 (PST)
Received: by 10.36.130.130 with HTTP; Thu, 7 Jan 2016 11:19:42 -0800 (PST)
In-Reply-To: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
Date: Thu, 7 Jan 2016 20:19:42 +0100
X-Gmail-Original-Message-ID: <CALqxMTHjvFT2aCBYDEiG-6F5qvsXK57_LR6ttpPb3xUG2i443w@mail.gmail.com>
Message-ID: <CALqxMTHjvFT2aCBYDEiG-6F5qvsXK57_LR6ttpPb3xUG2i443w@mail.gmail.com>
From: Adam Back <adam@cypherspace.org>
To: Gavin Andresen <gavinandresen@gmail.com>
Content-Type: text/plain; charset=UTF-8
X-Provags-ID: V03:K0:MsFceSiBAmjqu3nbCGloCTihybz32nhx0P3UzTR+ULEoIEz61zW
7LsIY5H0p0vr6xt5siZrJeCHHakpzM8GbVNHPFO9cyjhRv2xdTDwSw3PNdEDO/uFYG7Ud6S
/Hqom9TRMiJOji+OhLXWgT6dnM9VthvN6K8tecqO9/83nYTA5151zzEOTwnyD8GYh1sDZEd
U6SLYeza1jsa4O2rX/fXQ==
X-UI-Out-Filterresults: notjunk:1;V01:K0:eAacCbFpLtY=:a1ly0gw3oIYTKLDzSSvxu9
AEYGQGMll4NDKhREoPrYrPUwQUED9KxS+zuL+6V8wA3qrc+29I2+o2uDFNq9CAYgY0jBOZ55+
pXiCJWgaGC65qnqLAZQjdHBjlv7tHfPETmFq7q5QrblaqxTLreHeI3tO913kV4wIigSXjQwl2
kOTr2kFZO6mpC22dTHrA+6FGrwC2mZPSxAZdlnR+GhF7FblFhEl+nBDIi9lWL7t0t3lo/Rmfk
3FJ8255lFTBAyAHKcA1dGokJPyXB4qa381iEedsbs3gpcg1ekFOyL26lA/oKt1KS4rORM5vuY
pTdt+EgY8kxRPm6bNyImP7u+XKdn+MnQfX6o3/Rd365bS7D/BhNUbgVlrHQ8EoiOLlhNoMHLV
rEoRjC/0KPk5ZQ56cPgfyb75RzSotVsy7XX61x+iYc4YZ78jeFnnsNCeOja+NHC+aMMUO51bl
TGWwPzNULeA7BF0jZwPNUR6fcQ3NJI0K8LyxC1AF4e0tAoS+tp20utHLrOBw7pVWjiatZPvZi
YFPWcPsxy3IHcZVKTOyf7mESRuzL7N53R2ObEU6hOKzadOxnwL63595RUe2jj5ezkP+4KtQ6L
ecrYJURoDs1vqXG0NW6yTSNyJHy2HPnX1rmPVENuUTSqabjUotH9kBvniX9xDg4rc0DEJglt6
2cDTXjv5l1bwxdcPqQDkTSOFOP7uO5M3sWXwxJIpa6qhfJ+kjoUriNDznfhpsf+dKAQ0iVsES
EpSbJCXCYfkqh621
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,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 Dev <bitcoin-dev@lists.linuxfoundation.org>
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 19:19:45 -0000
You could say 256 bit ECDSA is overkill lets go to 160 equivalently.
Saves even more bytes.
The problem with arguing down is where to stop.
As Matt said these things dont degrade gracefully so a best practice
is to aim for a bit of extra margin.
256-bit is quite common at this point since AES, SHA256 etc even in
things with much less at stake than Bitcoin.
You could send the compressed (unhashed) pubkey then there's no hash
(and omit it from the sig). Greg had mentioned that in the past.
I think it might be possible to do both (reclaim the hash bits in the
serialisation of the pub key).
Adam
On 7 January 2016 at 20:02, 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
>
|
