From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ) 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 ; 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> <20140204131723.GA10309@savin> <20140204160414.GA23803@savin> Date: Wed, 5 Feb 2014 09:09:31 -0600 Message-ID: From: Brooks Boyd 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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
On Tue, Feb 4, 2014 = at 10:04 AM, Peter Todd <pete@pete= rtodd.org> wrote:
>
> On Tue, Feb 04, 2014 at 04:17:47PM= +0100, Natanael wrote:
> > Because it's trivial to create collisions! You can choose exa= ctly what
> > output you want. That's why XOR is a very bad di= gest 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 time= stamp the
> top digest in the Bitcoin blockchain right, and be sure t= hat digest
> 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
> the tree is using XOR rather than a proper hash function?
>

Given a tree like:

=A0 =A0 =A0 G
=A0 =A0 = =A0/ \ =A0
=A0 =A0 E =A0 F
=A0 =A0/ \
=A0 C = =A0 D
=A0/ \
A =A0 B

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.

Now an attacker could just make up an arbitrary set of = values that XOR together into G, like:

=A0 G
=
=A0/ \
Z =A0 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 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.

An attacker could look more convincing by using the dat= a passed with A as a starting point:

=A0 =A0 = =A0 =A0 G
=A0 =A0 =A0 =A0/ \ =A0
=A0 =A0 =A0 E =A0 F
=A0 =A0 =A0/ \
=A0 =A0 / =A0 \
=A0 =A0/ =A0 =A0 \
=A0 C =A0 =A0 = =A0 D
=A0/ \ =A0 =A0 / \
A =A0 B =A0 Z =A0 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 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.

Brooks
--001a11c2b5ded46d3c04f1aa24af--