* [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support @ 2014-02-04 12:01 Mike Hearn 2014-02-04 13:03 ` Peter Todd 0 siblings, 1 reply; 12+ messages in thread From: Mike Hearn @ 2014-02-04 12:01 UTC (permalink / raw) To: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 7263 bytes --] 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 control optimisations were made to allow much larger wallets to sync on Android. The transaction broadcast algorithm was changed to be more robust. Double spend handling in the wallet was improved. Generated signatures now use canonical S values. This will aid a future hard-forking rule change which bans malleable signatures. Some fixes were made for enable usage with the Orchid Tor library. Further support for Tor is planned for future releases. Notable bug fixes Some hard-forking full verification bugs were fixed. Thanks to Miron, PeerGroup now performs exponential backoff for peer connections, for instance if we cannot connect to them or if they disconnect us. This resolves an annoying bug in which if the library was configured with a single peer that was down, it would spin in a tight loop consuming battery. API changes Some functionality of the Wallet class was moved into separate classes under the wallet package. The micropayments API and protocol changed. New clients/servers are not compatible with apps running against previous releases. The Wallet sendCoins/completeTx methods no longer return booleans or null to indicate failure, they now throw InsufficientMoneyException or a subclass if the transaction cannot be completed. The exception object typically contains information on how much money is missing. Some mis-named methods in the HD key derivation API were renamed. The WalletEventListener interface has an extra method for watching scripts now. Peer discovery classes moved under the net.discovery package Any APIs that relied on Netty are now different. New documentation An article on the networking API Info on testing your apps, and how to use regtest mode to make a private Bitcoin network that allows you to mine blocks instantly. A reference table showing which API's implement which Bitcoin Improvement Proposals (BIPs). Please note that as I am no longer employed by Google, after 0.11 signing the Google contributor license agreement will no longer be necessary. I look forward to welcoming contributions from Andreas Schildbach now this requirement has gone away. Also, in future I plan to re-namespace the library from com.google.bitcoin to org.bitcoinj - auto-migration scripts will be provided when this is done. [-- Attachment #1.2: Type: text/html, Size: 12645 bytes --] [-- Attachment #2: smime.p7s --] [-- Type: application/pkcs7-signature, Size: 7453 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 12:01 [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support Mike Hearn @ 2014-02-04 13:03 ` Peter Todd 2014-02-04 13:13 ` Mike Hearn 2014-02-07 9:21 ` Peter Todd 0 siblings, 2 replies; 12+ messages in thread From: Peter Todd @ 2014-02-04 13:03 UTC (permalink / raw) To: Mike Hearn; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 1864 bytes --] 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 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 685 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 13:03 ` Peter Todd @ 2014-02-04 13:13 ` Mike Hearn 2014-02-04 13:17 ` Peter Todd 2014-02-07 9:21 ` Peter Todd 1 sibling, 1 reply; 12+ messages in thread From: Mike Hearn @ 2014-02-04 13:13 UTC (permalink / raw) To: Peter Todd; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2072 bytes --] Hah, good point. If nobody completes the homework, I'll post a fixed version tomorrow :) On Tue, Feb 4, 2014 at 2:03 PM, Peter Todd <pete@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 > 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 > [-- Attachment #2: Type: text/html, Size: 2826 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 13:13 ` Mike Hearn @ 2014-02-04 13:17 ` Peter Todd 2014-02-04 14:43 ` Jeff Garzik 2014-02-04 15:17 ` Natanael 0 siblings, 2 replies; 12+ messages in thread From: Peter Todd @ 2014-02-04 13:17 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2625 bytes --] 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 <pete@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 > > 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 > > -- 'peter'[:-1]@petertodd.org 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 685 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 13:17 ` Peter Todd @ 2014-02-04 14:43 ` Jeff Garzik 2014-02-04 14:46 ` Peter Todd 2014-02-04 15:17 ` Natanael 1 sibling, 1 reply; 12+ messages in thread From: Jeff Garzik @ 2014-02-04 14:43 UTC (permalink / raw) To: Peter Todd; +Cc: Bitcoin Dev On Tue, Feb 4, 2014 at 8:17 AM, Peter Todd <pete@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/ ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 14:43 ` Jeff Garzik @ 2014-02-04 14:46 ` Peter Todd 0 siblings, 0 replies; 12+ messages in thread From: Peter Todd @ 2014-02-04 14:46 UTC (permalink / raw) To: Jeff Garzik; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 456 bytes --] On Tue, Feb 04, 2014 at 09:43:31AM -0500, Jeff Garzik wrote: > On Tue, Feb 4, 2014 at 8:17 AM, Peter Todd <pete@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 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 685 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 13:17 ` Peter Todd 2014-02-04 14:43 ` Jeff Garzik @ 2014-02-04 15:17 ` Natanael 2014-02-04 16:04 ` Peter Todd 1 sibling, 1 reply; 12+ messages in thread From: Natanael @ 2014-02-04 15:17 UTC (permalink / raw) To: Peter Todd; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 3435 bytes --] 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" <pete@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 <pete@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 > > > 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 > > > > > -- > 'peter'[:-1]@petertodd.org > 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 > > > ------------------------------------------------------------------------------ > 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=121051231&iu=/4140/ostg.clktrk > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > [-- Attachment #2: Type: text/html, Size: 4952 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 15:17 ` Natanael @ 2014-02-04 16:04 ` Peter Todd 2014-02-05 7:57 ` Jeremy Spilman 2014-02-05 15:09 ` Brooks Boyd 0 siblings, 2 replies; 12+ messages in thread From: Peter Todd @ 2014-02-04 16:04 UTC (permalink / raw) To: Natanael; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 747 bytes --] 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 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 685 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 16:04 ` Peter Todd @ 2014-02-05 7:57 ` Jeremy Spilman 2014-02-05 15:09 ` Brooks Boyd 1 sibling, 0 replies; 12+ messages in thread From: Jeremy Spilman @ 2014-02-05 7:57 UTC (permalink / raw) To: Natanael, Peter Todd; +Cc: bitcoin-development 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 <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? ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 16:04 ` Peter Todd 2014-02-05 7:57 ` Jeremy Spilman @ 2014-02-05 15:09 ` Brooks Boyd 1 sibling, 0 replies; 12+ messages in thread From: Brooks Boyd @ 2014-02-05 15:09 UTC (permalink / raw) To: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 2150 bytes --] 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 [-- Attachment #2: Type: text/html, Size: 2773 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-04 13:03 ` Peter Todd 2014-02-04 13:13 ` Mike Hearn @ 2014-02-07 9:21 ` Peter Todd 2014-02-07 10:48 ` Mike Hearn 1 sibling, 1 reply; 12+ messages in thread From: Peter Todd @ 2014-02-07 9:21 UTC (permalink / raw) To: Mike Hearn, Brooks Boyd, Michael Gooden, Vitalik Buterin Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 11084 bytes --] 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: 0000000000000001512b077de3cc7ec88d1d65dc474a52a9ac9ac14ac34d7ac8 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 that PRNG, and/or ECC signatures were created with a known k value. (leaking the private key) But how to pull that off? The bitcoinj sourcecode is public, so they can't just backdoor bitcoinj directly - everyone would find out. What they need is a way to trick SatoshiDice into installing a bugged version, without leaving any evidence. With Mike Hearn's help they can calculate a pair of hashes, each with a n-bit prefix, but with only sqrt(2^n) work. This is called a second-preimage attack, and takes advantage of the birthday paradox, which as you may recall, is that in a room of just 23 people, there is a 50% chance that two them share the same birthday. Now the US government continually generates pairs of slightly different git commits, one being the honest code, the other with the backdoor. Generating these pairs is simple enough, just change something insignificant like the exact timestamp of last few commits. Every hash generated is saved in a big hashtable, as well as compared with all pre-existing hashes. In this case they'll just need to do about 2^24 tries to succeed, only 24 million attempts, which is frankly pretty trivial. Now that they have two collissions they have Mike release bitcoinj as before to the public, and at the same time they intercept the internet connections of the people suspected to be the SatoshiDice developers. For the latter a MITM attack is performed, secretly replacing the good copy of bitcoinj they download with the backdoored copy. The developers don't notice anything unusual, because both copies appear to have the same commit hash! The beauty of this technique is provided the disclosed hash isn't too long, it's still plausible that a powerful government agency brute forced the thing even if the backdoored code is leaked. With 48 bits that's obviously trivial, but even a 64-bit collision could be made at the cost of only a few million dollars. Thus, Mike Hearn has plausible deniability and can claim innocence. Moral of the story is if a second-pre-image attack is a threat, you need to use a lot of bits. Even a full SHA-1 commit hash is only 160 bits, which gives sqrt(2^160) or 2^80 security, so anything less than the full git commit hash is risky. Industry standard is to use at least 160 bits, and preferably you should always just use the full 256 bits that SHA-256 or similar provides unless you have a really good reason not too. On Tue, Feb 04, 2014 at 08:17:23AM -0500, Peter Todd wrote: > 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? Brooks Boyd already posted a great writeup, so I'm going to reference his instead: http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03882.html In closing I think it's important that we all remember we're writing software that handles money and the incentives to sneak backdoors into said software are enormous, and every worse, universal. Everyone can profit pretty directly from stealing cash, so the "Bad guys" we're up against range from your "Russian hackers" to the US government and everyone in between. Fortunately the nature of attacks is that for an attack to succeed, everything has to go right, but for it to fail, you only need a single person to notice something is wrong. This is why the Bitcoin Core development effort consists of multiple people, mutually verifying each other's work, and signing code with OpenPGP keys that in turn are verifiable via numerous different paths. Of course, many users will naturally not bother with that effort and outsoruce their trust to a single person or certificate authority, but the more advanced users with more stringent security needs, such as developers at exchanges and big merchants, can validate the code through the indepdent multiple independent paths OpenPGP signatures provide. Bitcoinj would do well to give their users that kind of security. So in the spirit of community auditing, I'll give one last 25mBTC reward out; I'll sneak in another obvious security flaw into something I write in the future, and I want to see if you guys catch it. As for the winners, I went by timestamp on the first email or other contact I got, and rewarded better descriptions where it wasn't clear. First of all I'm awarding the first bonus question to Vitalik, who in person at the Toronto Bitcoin Meetup noticed the issue immediately. He's no crypto-newbie, but at that point I had to give it to someone! Jeff Garzik will receive nothing for his answer, as it would be morally wrong to encourage further dad jokes. Brooks Boyd wins for #3, and thanks for the solid write up! Finally, #1 had a lot of submissions, but the earliest really clear answere was privately emailed to me. Dunno if they want to be named publicly, but here's the SHA256 hash of their email address for bragging rights: 49bf07a9ce1421effe887509a361b62283ed269d328bd3be12334f8cce7a0acd Finally, it'd be really awesome to have some concrete examples of git commits with these preimage and second-preimage attacks applied. So, I'm pledging 250mBTC to anyone who creates a tool that can run on Ubuntu Linux that takes two git commits, and brute-forces some not trivially noticed nonce within those commits - I suggest the timestamp - to make some subset of their hash collide. A fast C or C++ inner loop would be ideal - being able to create reasonably long collisions, best yet against arbitrary bit masks, would be an excellent way to show people why they need to be careful. Contact me if you want to take this on. -- 'peter'[:-1]@petertodd.org 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 685 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support 2014-02-07 9:21 ` Peter Todd @ 2014-02-07 10:48 ` Mike Hearn 0 siblings, 0 replies; 12+ messages in thread From: Mike Hearn @ 2014-02-07 10:48 UTC (permalink / raw) To: Peter Todd; +Cc: Vitalik Buterin, Michael Gooden, bitcoin-development [-- Attachment #1: Type: text/plain, Size: 1154 bytes --] 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. [-- Attachment #2: smime.p7s --] [-- Type: application/pkcs7-signature, Size: 7453 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2014-02-07 11:05 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2014-02-04 12:01 [Bitcoin-development] bitcoinj 0.11 released, with p2sh, bip39 and payment protocol support Mike Hearn 2014-02-04 13:03 ` Peter Todd 2014-02-04 13:13 ` Mike Hearn 2014-02-04 13:17 ` Peter Todd 2014-02-04 14:43 ` Jeff Garzik 2014-02-04 14:46 ` Peter Todd 2014-02-04 15:17 ` Natanael 2014-02-04 16:04 ` Peter Todd 2014-02-05 7:57 ` Jeremy Spilman 2014-02-05 15:09 ` Brooks Boyd 2014-02-07 9:21 ` Peter Todd 2014-02-07 10:48 ` Mike Hearn
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox