From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1WBhdZ-0004uu-D3 for bitcoin-development@lists.sourceforge.net; Fri, 07 Feb 2014 09:22:17 +0000 Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.148.93 as permitted sender) client-ip=62.13.148.93; envelope-from=pete@petertodd.org; helo=outmail148093.authsmtp.net; Received: from outmail148093.authsmtp.net ([62.13.148.93]) by sog-mx-3.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1WBhdX-0004Rl-E8 for bitcoin-development@lists.sourceforge.net; Fri, 07 Feb 2014 09:22:17 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt14.authsmtp.com (8.14.2/8.14.2) with ESMTP id s179M7dF004149; Fri, 7 Feb 2014 09:22:07 GMT Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s179M1gt020746 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Fri, 7 Feb 2014 09:22:03 GMT Date: Fri, 7 Feb 2014 04:21:41 -0500 From: Peter Todd To: Mike Hearn , Brooks Boyd , Michael Gooden , Vitalik Buterin Message-ID: <20140207092141.GA3532@savin> References: <1D8E0828-D07F-46EF-9F9F-5CA83AA9DB59@plan99.net> <20140204130312.GA23538@savin> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="liOOAslEiF7prFVr" Content-Disposition: inline In-Reply-To: <20140204130312.GA23538@savin> User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: 4f01a277-8fd9-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR bwdMdgUUHlAWAgsB AmIbW11eUl97WWc7 bAxPbAVDY01GQQRq WVdMSlVNFUsrABsI ex9JFhlwdwJCfjB3 YE9jXD5fCkR7JER6 RVNcQzkPeGZhPWMC AkhYdR5UcAFPdx8U a1UrBXRDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA4BHyI3 QBEEH313WxRcDz8+ KxEvMVMQWA4OM1ky eUN7QlJcexUTElYP fQlEBiMRP1AQQict EUtCR0kCFzZaRW9H HwUwJQVUagAA X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -0.4 (/) 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_PASS SPF: sender matches SPF record 1.1 TRACKER_ID BODY: Incorporates a tracking ID number 0.0 T_FRT_LOLITA1 BODY: ReplaceTags: Lolita (1) 0.0 LOTS_OF_MONEY Huge... sums of money 0.0 T_MONEY_PERCENT X% of a lot of money for you X-Headers-End: 1WBhdX-0004Rl-E8 Cc: bitcoin-development@lists.sourceforge.net 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: Fri, 07 Feb 2014 09:22:17 -0000 --liOOAslEiF7prFVr Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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, > >=20 > > I'm pleased to announce the release of bitcoinj 0.11, a library for wri= ting Bitcoin applications that run on the JVM. BitcoinJ is widely used acro= ss the Bitcoin community; some users include Bitcoin Wallet for Android, Mu= ltiBit, Hive, blockchain.info, the biteasy.com block explorer (written in L= isp!), Circle, Neo/Bee (Cypriot payment network), bitpos.me, Bitcoin Touch,= BlueMatt's relay network and DNS crawler, academic advanced contracts rese= arch and more. > >=20 > > 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 establi= sh continuity). Additionally, this email is signed using DKIM and for the f= irst time, a key that was ID verified by the Swiss government. > >=20 > > Key: 16vSNFP5Acsa6RBbjEA7QYCCRDRGXRFH4m > > Signature for last paragraph: H3DvWBqFHPxKW/cdYUdZ6OHjbq6ZtC5PHK4ebpeiE= +FqTHyRLJ58BItbC0R2vo77h+DthpQigdEZ0V8ivSM7VIg=3D >=20 > 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 =3D 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 :) >=20 > Heh, here's another 25mBTC while we're at it: >=20 > https://github.com/opentimestamps/opentimestamps-client/commit/288f3c1762= 6974de7eaef4f1c9b5cd93eecf40f6 >=20 > 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/msg03= 882.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. --=20 'peter'[:-1]@petertodd.org 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 --liOOAslEiF7prFVr Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (GNU/Linux) iQGrBAEBCACVBQJS9KWkXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDA3NTgyOWY2MTY5Yzc5ZDdkNWFhYTIwYmZhOGRhNmU5ZWRi MjM5M2M0Zjg2NjJiYTAvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfstZQgApGEhbyttrEP2eF8Qi7qjg6Tk XTuhvSKlYvil4G94A+bXm7IFi9kFlnHL+gb4nJAwP2BkXBm+TXqDXPVKaoO4CUiK d/cUe0rsUVYhtLd4x/fKH8pUyV63bFDzNui9a8hCBAMYCxNw0puo8OSFDm+a9vJD bLASek3Un927E88gkiV/IwcxNyKTXLapa9vve/HO1AP+qE4rsy0HH99LX6WSvC2g TcDWwRT5sSzusEP66K3qiDPKYeZV4TowRjs1PIjwAkJyS/KR+PLcobc/+YkSU4fz cltI+BMC9KJl30Eo1wKtJ+bZDqjSKukdYDKKOQYFbNv4Tp7KjSKpC4Qzd92omQ== =aj8u -----END PGP SIGNATURE----- --liOOAslEiF7prFVr--