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
|
Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 423F4A45
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jan 2016 23:52:30 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f46.google.com (mail-wm0-f46.google.com [74.125.82.46])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9A4FC191
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Jan 2016 23:52:29 +0000 (UTC)
Received: by mail-wm0-f46.google.com with SMTP id l65so116388064wmf.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 07 Jan 2016 15:52:29 -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
:cc:content-type;
bh=XizQpQS3r9BkYr0MvnBHL0i9Ls44QRVNGMucNltt/NA=;
b=I3CFl1ayXOdt6WPXCq6IoCO+eIqNzjDKDzmiXf1iWpHkHt4wIRpxpouxn5/EgeYUmm
r/NWU8K4r5vx0HinrdX5vi1w9xKi/la/eV6efbFloQu+sEqnSCnTo6fvq4uWDa5q+g3V
dPYhCvRUk5o8LiFdA4b584EN6C/sfY0kcNLlItEgktCXSGeW14kzpAr+/mH1YGE/ZshB
Aq3SQkXSrUtov302OQ2k5IofefCLuXWTH2h8WEGLk9IytnEStJg7C/Kg+n8dXnQb4DNx
iY/3KQHyex9DqBFmDcoaSwTe7kgOeLKjZOpT7Bnc3lver7QuaYHnLxfXq59Vded9hq3v
k2QQ==
MIME-Version: 1.0
X-Received: by 10.28.174.77 with SMTP id x74mr18344982wme.99.1452210748211;
Thu, 07 Jan 2016 15:52:28 -0800 (PST)
Received: by 10.194.190.100 with HTTP; Thu, 7 Jan 2016 15:52:27 -0800 (PST)
Received: by 10.194.190.100 with HTTP; Thu, 7 Jan 2016 15:52:27 -0800 (PST)
In-Reply-To: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
Date: Fri, 8 Jan 2016 00:52:27 +0100
Message-ID: <CAPg+sBhH0MODjjp8Avx+Fy_UGqzMjUq_jn3vT3oH=u3711tsSA@mail.gmail.com>
From: Pieter Wuille <pieter.wuille@gmail.com>
To: Gavin Andresen <gavinandresen@gmail.com>
Content-Type: multipart/alternative; boundary=001a11444344c94aab0528c729ed
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,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
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 23:52:30 -0000
--001a11444344c94aab0528c729ed
Content-Type: text/plain; charset=UTF-8
> "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.
Yes, this is what I worry about. We're constructing a 2-of-2 multisig
escrow in a contract. I reveal my public key A, you do a 80-bit search for
B and C such that H(A and B) = H(B and C). You tell me your keys B, and I
happily send to H(A and B), which you steal with H(B and C).
Sending along a proof does not help, you can't prove that you do not know
of a collision. Pre-committing does help, but is a very non-obvious
security requirement, something I strongly believe is far riskier in
practice.
Bitcoin does have parts that rely on economic arguments for security or
privacy, but can we please stick to using cryptography that is up to par
for parts where we can? It's a small constant factor of data, and it
categorically removes the worry about security levels.
--
Pieter
--001a11444344c94aab0528c729ed
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<p dir=3D"ltr">> "The problem case is where someone in a contract s=
etup shows you a script, which you accept as being a payment to yourself. A=
n 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=
.<br>
><br>
> So you really want collision security, and I don't think 80 bits i=
s something we should encourage for that. Normal pubkey hashes don't ha=
ve that problem, as they can't be constructed to pay to you."<br>
><br>
> ... but I'm unconvinced:<br>
><br>
> "But it is trivial for contract wallets to protect against collis=
ion attacks-- if you give me a script that is "gavin_pubkey CHECKSIG a=
rbitrary_data OP_DROP" with "I promise I'm not trying to rip =
you off, just ignore that arbitrary data" a wallet can just refuse. Ev=
en more likely, a contract wallet won't even recognize that as a pay-to=
-gavin transaction.<br>
><br>
> I suppose it could be looking for some form of "gavin_pubkey some=
body_else_pubkey CHECKMULTISIG ... with the attacker using somebody_else_pu=
bkey to force the collision, but, again, trivial contract protocol tweaks (=
"send along a proof you have the private key corresponding to the publ=
ic key" or "everybody pre-commits pubkeys they'll use at prot=
ocol start") would protect against that.</p>
<p dir=3D"ltr">Yes, this is what I worry about. We're constructing a 2-=
of-2 multisig escrow in a contract. I reveal my public key A, you do a 80-b=
it search for B and C such that H(A and B) =3D H(B and C). You tell me your=
keys B, and I happily send to H(A and B), which you steal with H(B and C).=
</p>
<p dir=3D"ltr">Sending along a proof does not help, you can't prove tha=
t you do not know of a collision. Pre-committing does help, but is a very n=
on-obvious security requirement, something I strongly believe is far riskie=
r in practice.</p>
<p dir=3D"ltr">Bitcoin does have parts that rely on economic arguments for =
security or privacy, but can we please stick to using cryptography that is =
up to par for parts where we can? It's a small constant factor of data,=
and it categorically removes the worry about security levels.</p>
<p dir=3D"ltr">-- <br>
Pieter<br>
</p>
--001a11444344c94aab0528c729ed--
|
