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; 
MIME-Version: 1.0
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
Subject: Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh,
 bip39 and payment protocol support
Precedence: list

--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 &lt;<a href=3D"mailto:pete@petertodd.org">pete@pete=
rtodd.org</a>&gt; wrote:<br>&gt;<br>&gt; On Tue, Feb 04, 2014 at 04:17:47PM=
 +0100, Natanael wrote:<br>
&gt; &gt; Because it&#39;s trivial to create collisions! You can choose exa=
ctly what<br>&gt; &gt; output you want. That&#39;s why XOR is a very bad di=
gest scheme.<br>&gt;<br>&gt; You&#39;re close, but not quite.<br>&gt;<br>
&gt; So, imagine you have a merkle tree, and you&#39;re trying to timestamp=
 some<br>&gt; data at the bottom of the tree. Now you can successfully time=
stamp the<br>&gt; top digest in the Bitcoin blockchain right, and be sure t=
hat digest<br>
&gt; existed before some time. But what about the digests at the bottom of<=
br>&gt; the tree? What can an attacker do exactly to make a fake timestamp =
if<br>&gt; the tree is using XOR rather than a proper hash function?<br>
&gt;<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--