<div dir="ltr"><font face="courier new, monospace">On Tue, Feb 4, 2014 at 10:04 AM, Peter Todd <<a href="mailto:pete@petertodd.org">pete@petertodd.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 exactly what<br>> > output you want. That's why XOR is a very bad digest 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 timestamp the<br>> top digest in the Bitcoin blockchain right, and be sure that 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> G</div><div> / \ </div><div> E F</div><div> / \</div><div> C D</div><div> / \</div><div>A B</div><div><br></div><div>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.</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> G</div><div> / \</div><div>Z 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 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.</div>
<div><br></div><div>An attacker could look more convincing by using the data passed with A as a starting point:</div><div><br></div><div><div> G</div><div> / \ </div><div> E F</div><div> / \</div>
<div> / \</div><div> / \</div><div> C D</div><div> / \ / \</div><div>A B Z 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 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.</div>
<div><br></div><div>Brooks</div></font></div>