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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <boydb@midnightdesign.ws>) id 1WB46f-0005yq-5Q
for bitcoin-development@lists.sourceforge.net;
Wed, 05 Feb 2014 15:09:41 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of
midnightdesign.ws designates 50.87.144.70 as permitted sender)
client-ip=50.87.144.70; envelope-from=boydb@midnightdesign.ws;
helo=gator3054.hostgator.com;
Received: from gator3054.hostgator.com ([50.87.144.70])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES256-SHA:256)
(Exim 4.76) id 1WB46e-0001gi-3G
for bitcoin-development@lists.sourceforge.net;
Wed, 05 Feb 2014 15:09:41 +0000
Received: from [74.125.82.175] (port=59304 helo=mail-we0-f175.google.com)
by gator3054.hostgator.com with esmtpsa (TLSv1:RC4-SHA:128)
(Exim 4.80) (envelope-from <boydb@midnightdesign.ws>)
id 1WB46X-0002CJ-Km for bitcoin-development@lists.sourceforge.net;
Wed, 05 Feb 2014 09:09:33 -0600
Received: by mail-we0-f175.google.com with SMTP id q59so386052wes.20
for <bitcoin-development@lists.sourceforge.net>;
Wed, 05 Feb 2014 07:09:31 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:date
:message-id:subject:from:to:content-type;
bh=jxV/33Vn+EMwmAZJurmqOU4JhQR8ISWZ5wF1Ux6WP+0=;
b=gTDf5z3LPQa5Sg+Q8fiylgYOHP4+pCU7L9JkfTvmxHqsiqfIdHfNIHrpwLGDqxyA/X
VU4SvYSbZ/MUeZ23e0yWp/5eIeEJubAZnVdgSiS77tMEDPI/7Juj5d27Pic7rGp14Low
GcBH9AuM/yXWmFLAy4LjTDVi2OoEeOdn7hj95ullMyiQa3A5LHPNlUes4S6llIeUWrdd
DYtIsuTcYMVGLBLZPB6ftjUZgxjm21GiFdtLxO+NH7gqQySxI+vNqq1MwbSCiU8DROzT
yWQ5MQ+nETHPGaBxkxxM61qitS2MI/Jho2slCQRDCXlyl4F6nCZhVWNWlCBtkFdF0/+s
ORcg==
X-Gm-Message-State: ALoCoQmTrjRGII72DRyRdWnwPelYOz802XcauQhG+ZDBtOmRUUqmW8y/NaA1PeTXjx0Ll0t0KeFE
MIME-Version: 1.0
X-Received: by 10.180.9.51 with SMTP id w19mr2865000wia.27.1391612971468; Wed,
05 Feb 2014 07:09:31 -0800 (PST)
Received: by 10.227.134.4 with HTTP; Wed, 5 Feb 2014 07:09:31 -0800 (PST)
In-Reply-To: <20140204160414.GA23803@savin>
References: <1D8E0828-D07F-46EF-9F9F-5CA83AA9DB59@plan99.net>
<20140204130312.GA23538@savin>
<CANEZrP2NyvRKwSEZORjAOq6G7UqLv=F3FjxmGNTPMT10yWGxzw@mail.gmail.com>
<20140204131723.GA10309@savin>
<CAAt2M1-LZ1APX9F93WE7Z877-WxqvJFbGaUmu5eriRGwvAOESw@mail.gmail.com>
<20140204160414.GA23803@savin>
Date: Wed, 5 Feb 2014 09:09:31 -0600
Message-ID: <CANg-TZBvZGwXaNoz5h7FD7Rh072+qc6T3FrUV-J81o4xZEuZ9A@mail.gmail.com>
From: Brooks Boyd <boydb@midnightdesign.ws>
To: bitcoin-development@lists.sourceforge.net
Content-Type: multipart/alternative; boundary=001a11c2b5ded46d3c04f1aa24af
X-AntiAbuse: This header was added to track abuse,
please include it with any abuse report
X-AntiAbuse: Primary Hostname - gator3054.hostgator.com
X-AntiAbuse: Original Domain - lists.sourceforge.net
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain - midnightdesign.ws
X-BWhitelist: no
X-Source-IP: 74.125.82.175
X-Source:
X-Source-Args:
X-Source-Dir:
X-Source-Sender: (mail-we0-f175.google.com) [74.125.82.175]:59304
X-Source-Auth: midnight
X-Email-Count: 1
X-Source-Cap: bWlkbmlnaHQ7bWlkbmlnaHQ7Z2F0b3IzMDU0Lmhvc3RnYXRvci5jb20=
X-Spam-Score: -0.5 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
-0.0 SPF_HELO_PASS SPF: HELO matches SPF record
-0.0 SPF_PASS SPF: sender matches SPF record
1.0 HTML_MESSAGE BODY: HTML included in message
X-Headers-End: 1WB46e-0001gi-3G
Subject: Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh,
bip39 and payment protocol support
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Wed, 05 Feb 2014 15:09:41 -0000
--001a11c2b5ded46d3c04f1aa24af
Content-Type: text/plain; charset=ISO-8859-1
On Tue, Feb 4, 2014 at 10:04 AM, Peter Todd <pete@petertodd.org> wrote:
>
> On Tue, Feb 04, 2014 at 04:17:47PM +0100, Natanael wrote:
> > Because it's trivial to create collisions! You can choose exactly what
> > output you want. That's why XOR is a very bad digest scheme.
>
> You're close, but not quite.
>
> So, imagine you have a merkle tree, and you're trying to timestamp some
> data at the bottom of the tree. Now you can successfully timestamp the
> top digest in the Bitcoin blockchain right, and be sure that digest
> existed before some time. But what about the digests at the bottom of
> the tree? What can an attacker do exactly to make a fake timestamp if
> the tree is using XOR rather than a proper hash function?
>
Given a tree like:
G
/ \
E F
/ \
C D
/ \
A B
Where G is the root hash and A is the legitimate data that was included in
the tree, the legitimate user provides B, D and F along with A to prove A
is part of the tree G.
Now an attacker could just make up an arbitrary set of values that XOR
together into G, like:
G
/ \
Z Y
And could therefore claim Z is part of tree G by providing Y. But if A is
also trying to prove its a part of G, we know the first level of the tree
must be E and F. It cannot also be Z and Y, so one of the two users is
lying and the deceit is obvious, though not obvious which user is lying.
An attacker could look more convincing by using the data passed with A as a
starting point:
G
/ \
E F
/ \
/ \
/ \
C D
/ \ / \
A B Z Y
Instead of working off of G, work of the lowest branch provided by A in its
verification (D, in this case), and create the fake data Z, and calculate Y
such that Z XOR Y == D (which is just Z XOR D). Now the attacker can claim
Z is part of G by supplying Y, C, and F. The tree looks valid (it can
coexist with the proof provided by A, at least until someone else claims to
be a descendant of the D node as well), and since G was verified by
timestamp, looks like Z existed before that timestamp, when really it could
be added at any time by calculating Z XOR D.
Brooks
--001a11c2b5ded46d3c04f1aa24af
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><font face=3D"courier new, monospace">On Tue, Feb 4, 2014 =
at 10:04 AM, Peter Todd <<a href=3D"mailto:pete@petertodd.org">pete@pete=
rtodd.org</a>> wrote:<br>><br>> On Tue, Feb 04, 2014 at 04:17:47PM=
+0100, Natanael wrote:<br>
> > Because it's trivial to create collisions! You can choose exa=
ctly what<br>> > output you want. That's why XOR is a very bad di=
gest scheme.<br>><br>> You're close, but not quite.<br>><br>
> So, imagine you have a merkle tree, and you're trying to timestamp=
some<br>> data at the bottom of the tree. Now you can successfully time=
stamp the<br>> top digest in the Bitcoin blockchain right, and be sure t=
hat digest<br>
> existed before some time. But what about the digests at the bottom of<=
br>> the tree? What can an attacker do exactly to make a fake timestamp =
if<br>> the tree is using XOR rather than a proper hash function?<br>
><br><br>Given a tree like:<br><br><div>=A0 =A0 =A0 G</div><div>=A0 =A0 =
=A0/ \ =A0</div><div>=A0 =A0 E =A0 F</div><div>=A0 =A0/ \</div><div>=A0 C =
=A0 D</div><div>=A0/ \</div><div>A =A0 B</div><div><br></div><div>Where G i=
s the root hash and A is the legitimate data that was included in the tree,=
the legitimate user provides B, D and F along with A to prove A is part of=
the tree G.</div>
<div><br></div><div>Now an attacker could just make up an arbitrary set of =
values that XOR together into G, like:</div><div><br></div><div>=A0 G</div>=
<div>=A0/ \</div><div>Z =A0 Y</div><div><br></div><div>And could therefore =
claim Z is part of tree G by providing Y. But if A is also trying to prove =
its a part of G, we know the first level of the tree must be E and F. It ca=
nnot also be Z and Y, so one of the two users is lying and the deceit is ob=
vious, though not obvious which user is lying.</div>
<div><br></div><div>An attacker could look more convincing by using the dat=
a passed with A as a starting point:</div><div><br></div><div><div>=A0 =A0 =
=A0 =A0 G</div><div>=A0 =A0 =A0 =A0/ \ =A0</div><div>=A0 =A0 =A0 E =A0 F</d=
iv><div>=A0 =A0 =A0/ \</div>
<div>=A0 =A0 / =A0 \</div><div>=A0 =A0/ =A0 =A0 \</div><div>=A0 C =A0 =A0 =
=A0 D</div><div>=A0/ \ =A0 =A0 / \</div><div>A =A0 B =A0 Z =A0 Y</div></div=
><div><br></div><div>Instead of working off of G, work of the lowest branch=
provided by A in its verification (D, in this case), and create the fake d=
ata Z, and calculate Y such that Z XOR Y =3D=3D D (which is just Z XOR D). =
Now the attacker can claim Z is part of G by supplying Y, C, and F. The tre=
e looks valid (it can coexist with the proof provided by A, at least until =
someone else claims to be a descendant of the D node as well), and since G =
was verified by timestamp, looks like Z existed before that timestamp, when=
really it could be added at any time by calculating Z XOR D.</div>
<div><br></div><div>Brooks</div></font></div>
--001a11c2b5ded46d3c04f1aa24af--
|
