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
|
Return-Path: <peter_r@gmx.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id BA5FD69
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 10 May 2016 01:42:51 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mout.gmx.net (mout.gmx.net [212.227.17.22])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CB67A150
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 10 May 2016 01:42:50 +0000 (UTC)
Received: from [192.168.1.59] ([205.250.126.165]) by mail.gmx.com (mrgmx103)
with ESMTPSA (Nemesis) id 0LxxNo-1benFD3KiK-015LI0 for
<bitcoin-dev@lists.linuxfoundation.org>; Tue, 10 May 2016 03:42:48 +0200
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2104\))
From: Peter R <peter_r@gmx.com>
In-Reply-To: <5C2809F9-286D-49E4-89DB-7109B73F6076@gmx.com>
Date: Mon, 9 May 2016 18:42:45 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <6BF6388E-2D1F-4A3D-BA57-B1AA94E40F7A@gmx.com>
References: <5727D102.1020807@mattcorallo.com> <86058327.pdmfHP132A@kiwi>
<CAAS2fgRiSNNHA5psaUYOM6rHfjJ1aOgWhnsT8Z-pU4FBcR_65w@mail.gmail.com>
<2273040.Bd6rtJjYLF@garp>
<CAAS2fgR01=SfpAdHhFd_DFa9VNiL=e1g4FiguVRywVVSqFe9rA@mail.gmail.com>
<CAAS2fgRL1=YSrAZVES0WBySyL1brZcvQsvZdsqUEY2-8UOFFiA@mail.gmail.com>
<5C2809F9-286D-49E4-89DB-7109B73F6076@gmx.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
X-Mailer: Apple Mail (2.2104)
X-Provags-ID: V03:K0:mypDKhK8s896EYvRX/Y+9nJyizDYt76qnbc/Tl7CJwyQrNYWkbo
okUOQGLBXZZ4Gvm9blesJ0+YN0S2AEp+Qo19xRGBen20Cg/f3u+VUEre5ou2V/2tfZRREPj
BVhC5lk/Ne2y3rqsmcZV6FNVvRsDxfRp4LYA5yrPJ6IgG+1zYnENvDWdvNz9LIfmoEkei3f
bI/u7WHjxK3L8X8UkhQxg==
X-UI-Out-Filterresults: notjunk:1;V01:K0:FNRY8zvybeE=:e19CIesWquFl1VAbbk2Nvl
VN0cdowHWB6v8a+5qUqxnmLHQuQe2ZqtaeHJ7AX0VYAZk37SnTZrNgG4V+51g4YNJUu3Z11lG
G+XAn6txOQaIamp/KOejmsUqZKK0iTWn7mnM/+pm5Kg2Fz3aBpEZyVsvViXyTvWk7ExWUPigE
hZgn86VNxUz1i2LaCksh/SyEz04aCXza0ZX1C6vVJIB0SZ/JyOZKtG7m3AKndVY0OPcW8sFge
2cw4w2HWCURQ9wtwdy8gWFrVuI6ql1ur658oEPcA/fHGm3HmWeWxE2X8BegIS3u4OwxYjzZ7W
qKIXjPEVtjDv2+TrvC+qHLXchMUT+1NWa1sLa+qsrSox9qFpo4w4Pfic7fiMVLWpC2PK2sFsO
FUgom98KSsNkrvzMeZH0BeBxNP9jA2Hc+N/SrCdf6Vt19VmK2c2yCRmJrW5VMB3g8IkwO4d6h
EOXoMQtJfDq7OD+8ITJHvHwWWw2NC49f3ATC6eRyU5L/wsn2dQOlWSae1LosD4enBzJJSPpPR
mz7+JyGPlZj4ftqIrPNZSME1CxOVQu3EuprN+Rgu7wgJIIURZ5+rFma3VEhnOE/IP9aAtDXnJ
9Thh2lua68KP8WFBG+wgolUdfxVDN/Sbk57teJihyUJVLDABhhW1UudsXzfDDmKnMkeULM01g
pxQcmM5cHbXrwytdHfVfxEl4VLi7I4Y9eezUjofcSPK3nTZsVn6tTdOY8P4CwgtF1dUSyJZs0
tq/U+ypa5byLwFA+pBAUFm+caezAmnu3rhZcJgVMvAR1bwZG1JpOmqABHnEKoyvRNhAdEV+sW
K4n1GXQ
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,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: Tue, 10 May 2016 02:16:07 +0000
Subject: Re: [bitcoin-dev] Compact Block Relay BIP
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: Tue, 10 May 2016 01:42:51 -0000
[9 May 16 @ 6:40 PDT]
For those interested in the hash collision attack discussion, it turns =
out there is a faster way to scan your set to find the collision: =
you=E2=80=99d keep a sorted list of the hashes for each TX you generate =
and then use binary search to check that list for a collision for each =
new TX you randomly generate. Performing these operations can probably =
be reduced to N lg N complexity, which is doable for N ~2^32. In other =
words, I now agree that the attack is feasible. =20
Cheers,
Peter
hat tip to egs
> On May 9, 2016, at 4:37 PM, Peter R via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> Greg Maxwell wrote:
>=20
>> What are you talking about? You seem profoundly confused here...
>>=20
>> I obtain some txouts. I write a transaction spending them in =
malleable
>> form (e.g. sighash single and an op_return output).. then grind the
>> extra output to produce different hashes. After doing this 2^32 =
times
>> I am likely to find two which share the same initial 8 bytes of txid.
>=20
> [9 May 16 @ 4:30 PDT]
>=20
> I=E2=80=99m trying to understand the collision attack that you're =
explaining to Tom Zander. =20
>=20
> Mathematica is telling me that if I generated 2^32 random =
transactions, that the chances that the initial 64-bits on one of the =
pairs of transactions is about 40%. So I am following you up to this =
point. Indeed, there is a good chance that a pair of transactions from =
a set of 2^32 will have a collision in the first 64 bits. =20
>=20
> But how do you actually find that pair from within your large set? =
The only way I can think of is to check if the first 64-bits is equal =
for every possible pair until I find it. How many possible pairs are =
there? =20
>=20
> It is a standard result that there are=20
>=20
> m! / [n! (m-n)!]=20
>=20
> ways of picking n numbers from a set of m numbers, so there are
>=20
> (2^32)! / [2! (2^32 - 2)!] ~ 2^63
>=20
> possible pairs in a set of 2^32 transactions. So wouldn=E2=80=99t you =
have to perform approximately 2^63 comparisons in order to identify =
which pair of transactions are the two that collide?
>=20
> Perhaps I made an error or there is a faster way to scan your set to =
find the collision. Happy to be corrected=E2=80=A6
>=20
> Best regards,
> Peter
>=20
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
|
