Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-07 Thread Peter Todd
Thanks for the great response! I had about a dozen or so people contact
me with solutions for one or more questions, and even a anonymous
donation of 75mBTC to cover the rewards.

I'll start with my summaries of those solutions:

On Tue, Feb 04, 2014 at 08:03:13AM -0500, Peter Todd wrote:
 On Tue, Feb 04, 2014 at 01:01:12PM +0100, Mike Hearn wrote:
  Hello,
  
  I'm pleased to announce the release of bitcoinj 0.11, a library for writing 
  Bitcoin applications that run on the JVM. BitcoinJ is widely used across 
  the Bitcoin community; some users include Bitcoin Wallet for Android, 
  MultiBit, Hive, blockchain.info, the biteasy.com block explorer (written in 
  Lisp!), Circle, Neo/Bee (Cypriot payment network), bitpos.me, Bitcoin 
  Touch, BlueMatt's relay network and DNS crawler, academic advanced 
  contracts research and more.
  
  The release-0.11 git tag is signed by Andreas Schildbach's GPG key. The 
  commit hash is 410d4547a7dd. This paragraph is signed by the same Bitcoin 
  key as with previous releases (check their release announcements to 
  establish continuity). Additionally, this email is signed using DKIM and 
  for the first time, a key that was ID verified by the Swiss government.
  
  Key: 16vSNFP5Acsa6RBbjEA7QYCCRDRGXRFH4m
  Signature for last paragraph: 
  H3DvWBqFHPxKW/cdYUdZ6OHjbq6ZtC5PHK4ebpeiE+FqTHyRLJ58BItbC0R2vo77h+DthpQigdEZ0V8ivSM7VIg=
 
 The above makes for a great homework problem for budding cryptographers:
 Why did the three forms of signature, DKIM, long-lived bitcoin address,
 and Official Swiss Government Identity fail to let you actually verify
 you have the right code? (but make for great security theater)

So as most people correctly guessed, the problem here is that Mike
truncated the git commit hash; normally it's 160 bits long, but he only
gave 48 of those bits. To understand why this is a problem, recall that
what a cryptographic hash does is it takes a arbitrary block of data,
the message, and returns a fixed length bit string, the message digest
or simply digest. With git the message essentially your source code and
commit history, and the digest is the git commit hash. Critically for a
cryptographic hash to be secure the mapping between messages and digests
must be random - it must not be infeasible to find two messages with the
same digest. (this is called a preimage attack)

The problem is that 48 bits just isn't that many bits. An attacker can
take the bitcoinj sourcecode and modify it to do something malicious
like generate private keys insecurely. Then they can keep modifying it
until the last 48-bits of the commit hash match Mike's message. (this
called a partial preimage attack) Each modification has a 1 in 2^48
chance of succeeding. You can calculate the attackers chances exactly
with the Binominal distribution, but a good enough approximation is
they'd have to make about 2^48 attempts.

That's not a very big number! Here's a nice visual comparison of how
long 48 bits is, compared to the partial preimage the Bitcoin network
cracks every 10 minutes:

0001512b077de3cc7ec88d1d65dc474a52a9ac9ac14ac34d7ac8
410d4547a7dd

Literally tens of thousands of times harder. This problem is similar to
password cracking, and they're getting speeds like ten million attempts
per second per CPU core. Just do the math: 2^48/10million/second/core =
46 Core Weeks. Now I can rent 32-core servers at Amazon EC2 for as
little as $0.27 per hour (spot requests) which gives me a cost for the
attack of about $100; my time to actually do it will cost more than
that.


But that calculation is missing the point; the extra bytes are really
cheap, so you can just use a simple rule of thumb: If a partial-preimage
attack is what you are trying to prevent, then in cryptography an
accepted number of bits to use is 128. Maybe just 80 bits would be
enough, or even just 64 bits, but pretty much everyone agrees 128 is
safe and conservative. But read on, because even 128 bits isn't safe
enough against another type of attack...


A second issue that a few people noticed was that Mike just said
Andreas Schildbach's GPG key, rather than specifying the fingerprint
of the key. By now I'd expect Mike to be confident as to what PGP key
is actually the correct one for the human Andreas Schildbach, so there's
absolutely no reason not state what that key is, either in the release
notes, or by signing the key with Mike's (non-existant?) PGP key.
Preferably both.

 Bonus question: Who has the smallest work-factor for such an attack?

No-one got this one correct or even tried!

What if Mike Hearn himself were the attacker? For instance, US officials
wanted to shutdown the gambling site SatoshiDice, which reportedly uses
the bitcoinj library. One way to do this would be to seize the funds
held by SatoshiDice, putting them out of business. If they could trick
SatoshiDice into using a version of bitcoinj with a broken PRNG, they
could simply wait until funds had moved into addresses generated by 

Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-07 Thread Mike Hearn
Here’s a new release announcement with full ID’s this time:

The v0.11 tag is signed by Andreas Schildbach’s GPG key (fingerprint E944 AE66 
7CF9 60B1 004B C32F CA66 2BE1 8B87 7A60). The commit hash is 
410d4547a7dd20745f637313ed54d04d08d28687.

Key: 16vSNFP5Acsa6RBbjEA7QYCCRDRGXRFH4m
Signature: 
IFXzt4ZdWFEpLrAXRDnQS6ZKJYGmyHDHtyAgeg/2/EaTvg41jSsUQW8rq19evT2UNp+eP0+OWgWM7iDKrTv11DY=

It’s worth noting that this problem crops up in other contexts too. For 
instance, it’s very common for people to identify PGP keys by a short 
identifier.

As it happens I do have a PGP key, fingerprint C85A AB0F 7A1C CCA3 2BFC EECC 
F2E4 861C 9988 816F, and I just signed Andreas’ key with it. However, as I’m 
not myself well connected in the web of trust, that doesn’t add a whole lot. 
But now that my key is effectively signed out of band by SwissSign so if people 
wanted to manually trace a trust path across systems, they could. I am 
skeptical anyone will :-)

Note that thanks to Gary Rowe, there is a Maven dependency checker plugin that 
verifies the (full) hashes of library dependencies. It could be better 
integrated but it provides another backstop.

smime.p7s
Description: S/MIME cryptographic signature
--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-05 Thread Brooks Boyd
On Tue, Feb 4, 2014 at 10:04 AM, Peter Todd p...@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
--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


[Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-04 Thread Mike Hearn
Hello,

I'm pleased to announce the release of bitcoinj 0.11, a library for writing 
Bitcoin applications that run on the JVM. BitcoinJ is widely used across the 
Bitcoin community; some users include Bitcoin Wallet for Android, MultiBit, 
Hive, blockchain.info, the biteasy.com block explorer (written in Lisp!), 
Circle, Neo/Bee (Cypriot payment network), bitpos.me, Bitcoin Touch, BlueMatt's 
relay network and DNS crawler, academic advanced contracts research and more.

The release-0.11 git tag is signed by Andreas Schildbach's GPG key. The commit 
hash is 410d4547a7dd. This paragraph is signed by the same Bitcoin key as with 
previous releases (check their release announcements to establish continuity). 
Additionally, this email is signed using DKIM and for the first time, a key 
that was ID verified by the Swiss government.

Key: 16vSNFP5Acsa6RBbjEA7QYCCRDRGXRFH4m
Signature for last paragraph: 
H3DvWBqFHPxKW/cdYUdZ6OHjbq6ZtC5PHK4ebpeiE+FqTHyRLJ58BItbC0R2vo77h+DthpQigdEZ0V8ivSM7VIg=

Notable changes and new features

Thanks to Ken Sedgwick, an implementation of BIP39 (Mnemonic code for 
generating deterministic keys) has been added. This is compatible with the 
latest Trezor implementation.
Thanks to Mike Belshe, the wallet can now send to P2SH addresses.
Thanks to Matt Corallo, the network layer was rewritten from scratch. It no 
longer depends on Netty, and it now supports both blocking and non-blocking 
sockets. In practice that means Java's built in support for transparent SSL and 
SOCKS becomes available again, which in turn means connecting via Tor is now 
possible. The new framework is lightweight, easy to understand and has been 
running a DNS seed crawler for some months now.
Thanks to Kevin Greene, we've added some support for the BIP70 payment 
protocol. Wallet authors can now consume payment requests, check their 
signatures and submit payments with the new easy to use PaymentSession class. 
The wallet-tool command line UI has support and an article explains how to use 
it.
Thanks to Miron Cuperman, the wallet can now watch arbitrary addresses and 
scripts. The wallet could previously watch an address as long as the public key 
was known. Now it's possible to watch for addresses even when the public key is 
not known.
Also thanks to Miron, Bloom filtering was also improved. The system now tracks 
false positive rates and cleans the filter when FP rates get too high. 
Unfortunately, some privacy bugs in Bloom filtering remain, which could 
(amongst other things) allow a malicious remote peer to test whether you own a 
particular key.
Thanks to Alex Taylor (bitpos.me), a new PostgreSQL based pruning block store 
was added. This block store is fast, and indexes the UTXO set, allowing for 
fast lookup of the balance of any given address.
A Java 8 based wallet template app is now included. The template is designed 
for people writing contract based applications. It provides a simple app that 
can be copy/pasted, which connects to the P2P network, manages a wallet, and 
provides a GUI that shows progress, balance, address+qrcode for receiving money 
and has a button that is used to empty the wallet out. It's designed to have an 
attractive and modern look, with tasteful animations and artwork.
Micropayment channels got many big improvements to the API and implementation. 
The release in 0.10 can be seen as a beta, in this release the micropayments 
code has been taken for a test drive for a couple of real apps and many rough 
edges polished as a result.
The default USER_THREAD executor can now be replaced, allowing a 1-line switch 
of all callbacks onto a thread of your choice instead of needing to override 
each callback, each time. This should simplify and clean up the GUI code of 
wallet apps significantly.
The WalletTool command line app has a more convenient user interface now.
A new DNS seed has been added. The seed is run by Christian Decker, from ETH 
Zurich.
bitcoinj 0.11 will shortly be available via Maven Central. Please use the 
dependency verifier plugin and/or check the PGP signatures on the uploads, if 
you use this!
Smaller improvements

We finished adding nullity annotations to the API. You should now be able to 
assume that any method not annotated with @Nullable won't ever return null 
values.
The WalletAppKit got a bunch of new features and convenience APIs.
The wallet will now create inputs with dummy signatures if the private key for 
an output is missing, rather than throwing an exception. You can then edit the 
input later to substitute in a real signature. This is useful when the signing 
is being done elsewhere, outside of the library.
In full verification mode, execution of scripts (i.e. checking signatures) can 
now be switched off. This is useful if you trust the source of the chain and 
just want to calculate the UTXO set.
The wallet risk analysis code is now pluggable, better documented and checks 
for finality in a more sensible way.
Various memory usage and flow 

Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-04 Thread Peter Todd
On Tue, Feb 04, 2014 at 01:01:12PM +0100, Mike Hearn wrote:
 Hello,
 
 I'm pleased to announce the release of bitcoinj 0.11, a library for writing 
 Bitcoin applications that run on the JVM. BitcoinJ is widely used across the 
 Bitcoin community; some users include Bitcoin Wallet for Android, MultiBit, 
 Hive, blockchain.info, the biteasy.com block explorer (written in Lisp!), 
 Circle, Neo/Bee (Cypriot payment network), bitpos.me, Bitcoin Touch, 
 BlueMatt's relay network and DNS crawler, academic advanced contracts 
 research and more.
 
 The release-0.11 git tag is signed by Andreas Schildbach's GPG key. The 
 commit hash is 410d4547a7dd. This paragraph is signed by the same Bitcoin key 
 as with previous releases (check their release announcements to establish 
 continuity). Additionally, this email is signed using DKIM and for the first 
 time, a key that was ID verified by the Swiss government.
 
 Key: 16vSNFP5Acsa6RBbjEA7QYCCRDRGXRFH4m
 Signature for last paragraph: 
 H3DvWBqFHPxKW/cdYUdZ6OHjbq6ZtC5PHK4ebpeiE+FqTHyRLJ58BItbC0R2vo77h+DthpQigdEZ0V8ivSM7VIg=

The above makes for a great homework problem for budding cryptographers:
Why did the three forms of signature, DKIM, long-lived bitcoin address,
and Official Swiss Government Identity fail to let you actually verify
you have the right code? (but make for great security theater)

Bonus question: Who has the smallest work-factor for such an attack?

Two rewards of 25mBTC for correct responses to each question from a
crypto newbie.

 Thanks to Mike Belshe, the wallet can now send to P2SH addresses.

Thanks

 Generated signatures now use canonical S values. This will aid a future 
 hard-forking rule change which bans malleable signatures.

Soft-forking rule change.

-- 
'peter'[:-1]@petertodd.org
75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0


signature.asc
Description: Digital signature
--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-04 Thread Peter Todd
On Tue, Feb 04, 2014 at 02:13:12PM +0100, Mike Hearn wrote:
 Hah, good point. If nobody completes the homework, I'll post a fixed
 version tomorrow :)

Heh, here's another 25mBTC while we're at it:

https://github.com/opentimestamps/opentimestamps-client/commit/288f3c17626974de7eaef4f1c9b5cd93eecf40f6

Why is that a bad idea?

Bonus question: What was I smoking? (hint: where do I live?)

 On Tue, Feb 4, 2014 at 2:03 PM, Peter Todd p...@petertodd.org wrote:
 
  On Tue, Feb 04, 2014 at 01:01:12PM +0100, Mike Hearn wrote:
   Hello,
  
   I'm pleased to announce the release of bitcoinj 0.11, a library for
  writing Bitcoin applications that run on the JVM. BitcoinJ is widely used
  across the Bitcoin community; some users include Bitcoin Wallet for
  Android, MultiBit, Hive, blockchain.info, the biteasy.com block explorer
  (written in Lisp!), Circle, Neo/Bee (Cypriot payment network), bitpos.me,
  Bitcoin Touch, BlueMatt's relay network and DNS crawler, academic advanced
  contracts research and more.
  
   The release-0.11 git tag is signed by Andreas Schildbach's GPG key. The
  commit hash is 410d4547a7dd. This paragraph is signed by the same Bitcoin
  key as with previous releases (check their release announcements to
  establish continuity). Additionally, this email is signed using DKIM and
  for the first time, a key that was ID verified by the Swiss government.
  
   Key: 16vSNFP5Acsa6RBbjEA7QYCCRDRGXRFH4m
   Signature for last paragraph:
  H3DvWBqFHPxKW/cdYUdZ6OHjbq6ZtC5PHK4ebpeiE+FqTHyRLJ58BItbC0R2vo77h+DthpQigdEZ0V8ivSM7VIg=
 
  The above makes for a great homework problem for budding cryptographers:
  Why did the three forms of signature, DKIM, long-lived bitcoin address,
  and Official Swiss Government Identity fail to let you actually verify
  you have the right code? (but make for great security theater)
 
  Bonus question: Who has the smallest work-factor for such an attack?
 
  Two rewards of 25mBTC for correct responses to each question from a
  crypto newbie.
 
   Thanks to Mike Belshe, the wallet can now send to P2SH addresses.
 
  Thanks
 
   Generated signatures now use canonical S values. This will aid a future
  hard-forking rule change which bans malleable signatures.
 
  Soft-forking rule change.
 
  --
  'peter'[:-1]@petertodd.org
  75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0
 

-- 
'peter'[:-1]@petertodd.org
75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0


signature.asc
Description: Digital signature
--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-04 Thread Jeff Garzik
On Tue, Feb 4, 2014 at 8:17 AM, Peter Todd p...@petertodd.org wrote:
 Bonus question: What was I smoking? (hint: where do I live?)

Cryptographers smoke... hash, right?

(couldn't resist)

-- 
Jeff Garzik
Bitcoin core developer and open source evangelist
BitPay, Inc.  https://bitpay.com/

--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-04 Thread Peter Todd
On Tue, Feb 04, 2014 at 09:43:31AM -0500, Jeff Garzik wrote:
 On Tue, Feb 4, 2014 at 8:17 AM, Peter Todd p...@petertodd.org wrote:
  Bonus question: What was I smoking? (hint: where do I live?)
 
 Cryptographers smoke... hash, right?
 
 (couldn't resist)

groan

I think we have a winner; as you can see Jeff must be a great father.

-- 
'peter'[:-1]@petertodd.org
75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0


signature.asc
Description: Digital signature
--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-04 Thread Natanael
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.

- Sent from my phone
Den 4 feb 2014 14:20 skrev Peter Todd p...@petertodd.org:

 On Tue, Feb 04, 2014 at 02:13:12PM +0100, Mike Hearn wrote:
  Hah, good point. If nobody completes the homework, I'll post a fixed
  version tomorrow :)

 Heh, here's another 25mBTC while we're at it:


 https://github.com/opentimestamps/opentimestamps-client/commit/288f3c17626974de7eaef4f1c9b5cd93eecf40f6

 Why is that a bad idea?

 Bonus question: What was I smoking? (hint: where do I live?)

  On Tue, Feb 4, 2014 at 2:03 PM, Peter Todd p...@petertodd.org wrote:
 
   On Tue, Feb 04, 2014 at 01:01:12PM +0100, Mike Hearn wrote:
Hello,
   
I'm pleased to announce the release of bitcoinj 0.11, a library for
   writing Bitcoin applications that run on the JVM. BitcoinJ is widely
 used
   across the Bitcoin community; some users include Bitcoin Wallet for
   Android, MultiBit, Hive, blockchain.info, the biteasy.com block
 explorer
   (written in Lisp!), Circle, Neo/Bee (Cypriot payment network),
 bitpos.me,
   Bitcoin Touch, BlueMatt's relay network and DNS crawler, academic
 advanced
   contracts research and more.
   
The release-0.11 git tag is signed by Andreas Schildbach's GPG key.
 The
   commit hash is 410d4547a7dd. This paragraph is signed by the same
 Bitcoin
   key as with previous releases (check their release announcements to
   establish continuity). Additionally, this email is signed using DKIM
 and
   for the first time, a key that was ID verified by the Swiss government.
   
Key: 16vSNFP5Acsa6RBbjEA7QYCCRDRGXRFH4m
Signature for last paragraph:
  
 H3DvWBqFHPxKW/cdYUdZ6OHjbq6ZtC5PHK4ebpeiE+FqTHyRLJ58BItbC0R2vo77h+DthpQigdEZ0V8ivSM7VIg=
  
   The above makes for a great homework problem for budding
 cryptographers:
   Why did the three forms of signature, DKIM, long-lived bitcoin address,
   and Official Swiss Government Identity fail to let you actually verify
   you have the right code? (but make for great security theater)
  
   Bonus question: Who has the smallest work-factor for such an attack?
  
   Two rewards of 25mBTC for correct responses to each question from a
   crypto newbie.
  
Thanks to Mike Belshe, the wallet can now send to P2SH addresses.
  
   Thanks
  
Generated signatures now use canonical S values. This will aid a
 future
   hard-forking rule change which bans malleable signatures.
  
   Soft-forking rule change.
  
   --
   'peter'[:-1]@petertodd.org
   75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0
  

 --
 'peter'[:-1]@petertodd.org
 75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0


 --
 Managing the Performance of Cloud-Based Applications
 Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
 Read the Whitepaper.

 http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development


--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-04 Thread Peter Todd
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?

-- 
'peter'[:-1]@petertodd.org
75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0


signature.asc
Description: Digital signature
--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support

2014-02-04 Thread Jeremy Spilman
Well the point of the Merkle tree is that if I all you have is the top,  
and all I give you is a leaf node and the siblings of all parents of that  
leaf, then by simply hashing you can check if the node was actually  
present in the tree.

The only reason this works is because it's hard for an attacker to come up  
with the list of values which would ultimately hash together to produce  
the expected top value. But if the hash function is actually just XOR, it  
becomes completely trivial for me to claim any value I want was in the  
tree.

1) Pick the fake value you want to claim was in the tree (leaf node)
2) Choose some random values to fake the depth in the tree
3) Calculate the last value as 'Prev (x) Top'
4) When your victim goes to verify set membership, they will get the top  
value they expected



On Tue, 04 Feb 2014 08:04:14 -0800, Peter Todd p...@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?


--
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121051231iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development