Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
This *could* be a useful feature, but only if it's generalizable to other processor architectures, and **in particular** has an implementation using dedicated silicon that has a **public** open-source hardware layout, so you can X-ray the chip, and confirm with a thermal imager that yes, the encryption code is actually running where you think it's running. I was *almost* convinced that the 'new key per address' was a good idea to mitigate ECDSA side channel attacks. Now, however, I find it quite plausible that intelligence agencies are promoting 'new key per transaction' as a way to make sure all your keys are leaked all over RAM and the nearby electromagnetic spectrum with side channels intentionally embedded in commodity hardware. If you want to convince me otherwise, then help me crowdfund an open-source hardware Bitcoin ASIC that does the crypto and stores your private keys. I expect the 'new key per transaction' crowd will be in for a rude awakening when they finally understand the silicon area cost to do this securely. Conclusion: Not only is 'de-prioritizing address re-use' BAD privacy, it provides a social engineering/key leakage attack vector where someone can track you down from the EMF generated by your bitcoin wallet when they send you money. If you think otherwise, let's build some ficking open-source hardware and find out how much silicon this will cost. Although it's probably more profitable to just build a bitcoin wallet detector and keep your mouth shut. On Thu, Mar 06, 2014 at 11:00:14AM +0100, Natanael wrote: You've heard of TRESOR? No, not Trezor. https://en.wikipedia.org/wiki/TRESOR Signing on the CPU, without touching RAM. - Sent from my phone Den 6 mar 2014 09:41 skrev Mike Hearn m...@plan99.net: I'm wondering about whether (don't laugh) moving signing into the kernel and then using the MTRRs to disable caching entirely for a small scratch region of memory would also work. You could then disable pre-emption and prevent anything on the same core from interrupting or timing the signing operation. However I suspect just making a hardened secp256k1 signer implementation in userspace would be of similar difficulty, in which case it would naturally be preferable. On Wed, Mar 5, 2014 at 11:25 PM, Gregory Maxwell gmaxw...@gmail.comwrote: On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo elombr...@gmail.com wrote: Everything you say is true. However, branchless does reduce the attack surface considerably - if nothing else, it significantly ups the difficulty of an attack for a relatively low cost in program complexity, and that might still make it worth doing. Absolutely. I believe these things are worth doing. My comment on it being insufficient was only that my signer is branchless doesn't make other defense measures (avoiding reuse, multsig with multiple devices, not sharing hardware, etc.) unimportant. As for uniform memory access, if we avoided any kind of heap allocation, wouldn't we avoid such issues? No. At a minimum to hide a memory timing side-channel you must perform no data dependent loads (e.g. no operation where an offset into memory is calculated). A strategy for this is to always load the same values, but then mask out the ones you didn't intend to read... even that I'd worry about on sufficiently advanced hardware, since I would very much not be surprised if the processor was able to determine that the load had no effect and eliminate it! :) ) Maybe in practice if your data dependencies end up only picking around in the same cache-line it doesn't actually matter... but it's hard to be sure, and unclear when a future optimization in the rest of the system might leave it exposed again. (In particular, you can't generally write timing sign-channel immune code in C (or other high level language) because the compiler is freely permitted to optimize things in a way that break the property. ... It may be _unlikely_ for it to do this, but its permitted— and will actually do so in some cases—, so you cannot be completely sure unless you check and freeze the toolchain) Anyhow, without having gone into the full details of this particular attack, it seems the main attack point is differences in how squaring and multiplication (in the case of field exponentiation) or doubling and point addition (in the case of ECDSA) are performed. I believe using a branchless implementation where each phase of the operation executes the exact same code and accesses the exact same stack frames would not be vulnerable to FLUSH+RELOAD. I wouldn't be surprised. -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
Y'all are getting deep into tinfoil-wearing-hat-conspiracy-theory territory. If you are worried about the NSA compromising your hardware or software, then use multisig transactions and sign on diverse hardware/software stacks. Generate the multiple private keys on different hardware/software stacks, too. Or, in other words, eliminate the single point of failure and you will mitigate whole families of possible attacks, from NSA compromised the hardware random number generator in my CPU to NSA is listening to EMF radiation coming from my dedicated server in my data center to the much more likely data center employee is tricked into letting somebody have access to my dedicated server. -- -- Gavin Andresen -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wed, Mar 05, 2014 at 12:54:04PM -0800, Gregory Maxwell wrote: On Wed, Mar 5, 2014 at 12:32 PM, Peter Todd p...@petertodd.org wrote: That's nice, but I wrote my advice to show people how even if they don't know any crypto beyond what the black boxes do - the absolute minimum you need to know to write any Bitcoin software - you can still defend yourself against that attack and many others. But it's still incomplete. Say you have an address— used only once!— with a txout with a lot of value. Someone starts paying you small amounts to that address over and over again. You haven't asked them to, they're just doing it. Do you ignore the funds?— maybe tell some customer that was ignorantly paying you over and over again to a single address sorry, those are my rules: I only acknowledge the first payment, those funds are lost!. No, of course not. You spend the darn coins and if you're on a shared host perhaps you disclose a private key. The probability of an attack actually going on is low enough compared to the cost of spending the coins in that case that even someone with good knoweldge of the risks will choose to do so. So absolutely, not reusing addresses massively increases your safety and limits losses when there is theft. But it isn't enough alone. (Nor is smarter signing, considering complex software like this has bugs and its hard to be confident that something is side channel free— esp when you allow attacker interference). I think you're misunderstanding me: I'm assuming one of the n parties signing transactions in my multi-factor authentication scheme is uncompromised - much easier to do when it's a low-bandwidth box sitting in a secure location. Not re-using keys is nice too of course, and while not perfect - your above scenario - certainely helps limit losses. -- 'peter'[:-1]@petertodd.org afcad9265e8b44bf1171a08165c09b329fab2893bf13ec69 signature.asc Description: Digital signature -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wednesday, March 05, 2014 4:21:52 PM Kevin wrote: How can we patch this issue? No need, it is not an issue for Bitcoin. Properly used, there is only ever one signature per public key. Luke -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Sat, Mar 8, 2014 at 11:34 AM, Luke-Jr l...@dashjr.org wrote: On Wednesday, March 05, 2014 4:21:52 PM Kevin wrote: How can we patch this issue? No need, it is not an issue for Bitcoin. Properly used, there is only ever one signature per public key. Security shouldn't depend on perfect use. There are many things that result in multiple key use: Bitcoin address authentication (something which the pool you created uses!), someone spamming you with multiple payments to a common address which you didn't solicit (what, are you just going to ignore the extra coins?), ... or just practical considerations— I note the mining pool you founded continually pays a single address for 'fall back' payments when it can't pay in the coinbase transact, I know you consider that a bug, but its the reality today. Most security issues aren't the result of one problem but several problems combined, so it's important to make each layer strong even if the strength shouldn't be important due to proper use in other layers. Fortunately, libsecp256k1 has a nearly constant time/constant memory access multiply for signing which should reduce exposure substantially (and is generally built in a way that reduces vulnerabilities). -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
I'm wondering about whether (don't laugh) moving signing into the kernel and then using the MTRRs to disable caching entirely for a small scratch region of memory would also work. You could then disable pre-emption and prevent anything on the same core from interrupting or timing the signing operation. However I suspect just making a hardened secp256k1 signer implementation in userspace would be of similar difficulty, in which case it would naturally be preferable. On Wed, Mar 5, 2014 at 11:25 PM, Gregory Maxwell gmaxw...@gmail.com wrote: On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo elombr...@gmail.com wrote: Everything you say is true. However, branchless does reduce the attack surface considerably - if nothing else, it significantly ups the difficulty of an attack for a relatively low cost in program complexity, and that might still make it worth doing. Absolutely. I believe these things are worth doing. My comment on it being insufficient was only that my signer is branchless doesn't make other defense measures (avoiding reuse, multsig with multiple devices, not sharing hardware, etc.) unimportant. As for uniform memory access, if we avoided any kind of heap allocation, wouldn't we avoid such issues? No. At a minimum to hide a memory timing side-channel you must perform no data dependent loads (e.g. no operation where an offset into memory is calculated). A strategy for this is to always load the same values, but then mask out the ones you didn't intend to read... even that I'd worry about on sufficiently advanced hardware, since I would very much not be surprised if the processor was able to determine that the load had no effect and eliminate it! :) ) Maybe in practice if your data dependencies end up only picking around in the same cache-line it doesn't actually matter... but it's hard to be sure, and unclear when a future optimization in the rest of the system might leave it exposed again. (In particular, you can't generally write timing sign-channel immune code in C (or other high level language) because the compiler is freely permitted to optimize things in a way that break the property. ... It may be _unlikely_ for it to do this, but its permitted— and will actually do so in some cases—, so you cannot be completely sure unless you check and freeze the toolchain) Anyhow, without having gone into the full details of this particular attack, it seems the main attack point is differences in how squaring and multiplication (in the case of field exponentiation) or doubling and point addition (in the case of ECDSA) are performed. I believe using a branchless implementation where each phase of the operation executes the exact same code and accesses the exact same stack frames would not be vulnerable to FLUSH+RELOAD. I wouldn't be surprised. -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
You've heard of TRESOR? No, not Trezor. https://en.wikipedia.org/wiki/TRESOR Signing on the CPU, without touching RAM. - Sent from my phone Den 6 mar 2014 09:41 skrev Mike Hearn m...@plan99.net: I'm wondering about whether (don't laugh) moving signing into the kernel and then using the MTRRs to disable caching entirely for a small scratch region of memory would also work. You could then disable pre-emption and prevent anything on the same core from interrupting or timing the signing operation. However I suspect just making a hardened secp256k1 signer implementation in userspace would be of similar difficulty, in which case it would naturally be preferable. On Wed, Mar 5, 2014 at 11:25 PM, Gregory Maxwell gmaxw...@gmail.comwrote: On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo elombr...@gmail.com wrote: Everything you say is true. However, branchless does reduce the attack surface considerably - if nothing else, it significantly ups the difficulty of an attack for a relatively low cost in program complexity, and that might still make it worth doing. Absolutely. I believe these things are worth doing. My comment on it being insufficient was only that my signer is branchless doesn't make other defense measures (avoiding reuse, multsig with multiple devices, not sharing hardware, etc.) unimportant. As for uniform memory access, if we avoided any kind of heap allocation, wouldn't we avoid such issues? No. At a minimum to hide a memory timing side-channel you must perform no data dependent loads (e.g. no operation where an offset into memory is calculated). A strategy for this is to always load the same values, but then mask out the ones you didn't intend to read... even that I'd worry about on sufficiently advanced hardware, since I would very much not be surprised if the processor was able to determine that the load had no effect and eliminate it! :) ) Maybe in practice if your data dependencies end up only picking around in the same cache-line it doesn't actually matter... but it's hard to be sure, and unclear when a future optimization in the rest of the system might leave it exposed again. (In particular, you can't generally write timing sign-channel immune code in C (or other high level language) because the compiler is freely permitted to optimize things in a way that break the property. ... It may be _unlikely_ for it to do this, but its permitted— and will actually do so in some cases—, so you cannot be completely sure unless you check and freeze the toolchain) Anyhow, without having gone into the full details of this particular attack, it seems the main attack point is differences in how squaring and multiplication (in the case of field exponentiation) or doubling and point addition (in the case of ECDSA) are performed. I believe using a branchless implementation where each phase of the operation executes the exact same code and accesses the exact same stack frames would not be vulnerable to FLUSH+RELOAD. I wouldn't be surprised. -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net
[Bitcoin-development] New side channel attack that can recover Bitcoin keys
A new practical technique has been published that can recover secp256k1 private keys after observing OpenSSL calculate as little as 200 signatures: http://eprint.iacr.org/2014/161.pdf This attack is based on the FLUSH+RELOAD technique published last year. It works by observing L3 CPU cache timings and forcing cache line flushes using the clflush opcode. As a result, it is applicable to any x86 environment where an attacker may be able to run on the same hardware i.e. virtualised hosting environments where keys are being reused. I am not currently aware of any efforts to make OpenSSL's secp256k1 implementation completely side channel free in all aspects. Also, unfortunately many people have reimplemented ECDSA themselves and even if OpenSSL gets fixed, the custom implementations probably won't. So, IMHO this is a sign for hot wallet users to start walking (but not running) towards the exits of these shared cloud services: it doesn't feel safe to sign transactions on these platforms, so hot wallets should be managed by dedicated hardware. Of course other parts of the service, like the website, are less sensitive and can still run in the cloud. I doubt the researchers will release their code to do the side channel attack and it's rather complex to reimplement, so this gives some time for mitigation. Unfortunately the huge sums being held in some bitbank style hot wallets mean that attackers are well motivated to pull off even quite complex attacks. -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Mar 5, 2014, at 8:56 PM, Pieter Wuille pieter.wui...@gmail.com wrote: On Wed, Mar 5, 2014 at 1:49 PM, Mike Hearn m...@plan99.net wrote: I am not currently aware of any efforts to make OpenSSL's secp256k1 implementation completely side channel free in all aspects. Also, unfortunately many people have reimplemented ECDSA themselves and even if OpenSSL gets fixed, the custom implementations probably won't. As far as I know, judging from the implementation, there is hardly any effort to try to prevent timing attacks. Is it safe to assume that this is also true for your secp256k1 implementation? jp -- Pieter -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wed, Mar 5, 2014 at 2:18 PM, Jean-Paul Kogelman jeanpaulkogel...@me.com wrote: As far as I know, judging from the implementation, there is hardly any effort to try to prevent timing attacks. Is it safe to assume that this is also true for your secp256k1 implementation? I've done some preliminary work on making it leak less, but it's by no means guaranteed to be constant time either (so better assume it is not). -- Pieter -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On 3/5/2014 7:49 AM, Mike Hearn wrote: A new practical technique has been published that can recover secp256k1 private keys after observing OpenSSL calculate as little as 200 signatures: http://eprint.iacr.org/2014/161.pdf This attack is based on the FLUSH+RELOAD technique published last year. It works by observing L3 CPU cache timings and forcing cache line flushes using the clflush opcode. As a result, it is applicable to any x86 environment where an attacker may be able to run on the same hardware i.e. virtualised hosting environments where keys are being reused. I am not currently aware of any efforts to make OpenSSL's secp256k1 implementation completely side channel free in all aspects. Also, unfortunately many people have reimplemented ECDSA themselves and even if OpenSSL gets fixed, the custom implementations probably won't. So, IMHO this is a sign for hot wallet users to start walking (but not running) towards the exits of these shared cloud services: it doesn't feel safe to sign transactions on these platforms, so hot wallets should be managed by dedicated hardware. Of course other parts of the service, like the website, are less sensitive and can still run in the cloud. I doubt the researchers will release their code to do the side channel attack and it's rather complex to reimplement, so this gives some time for mitigation. Unfortunately the huge sums being held in some bitbank style hot wallets mean that attackers are well motivated to pull off even quite complex attacks. -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development How can we patch this issue? -- Kevin -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wed, Mar 05, 2014 at 11:21:52AM -0500, Kevin wrote: On 3/5/2014 7:49 AM, Mike Hearn wrote: A new practical technique has been published that can recover secp256k1 private keys after observing OpenSSL calculate as little as 200 signatures: How can we patch this issue? If you're following good practices you're not particularly vulneable to it, if at all, even if you make use of shared hosting. First of all you shouldn't be re-using addresses, which means you won't be passing that ~200 sig threshold. More important though is you shouldn't be using single factor Bitcoin addresses. Use n-of-m multisig instead and architect your system such that that every transaction that happens in your service has to be authorized by both the online server(s) that host your website as well as a second hardened server with an extremely limited interface between it and the online server. The hardened second factor *should* use a separate codebase, ideally even a second language, to authenticate actions that withdraw funds or generate new addresses based on data given to it by the online server. In the best case your customers are PGP-signing requests so you can verify their intent independently and cryptographically on both servers. Mircea Popescu's MPEx exchange is an example of this model, although I don't think they're doing any multisig stuff. Failing that you can at least use the second server to do things like limit losses by flagging higher-than-expected withdrawl volumes and unusual events. Since this second-factor server only deals with business logic - not the website - you can certainly find a secure hosting arrangement for it with physical control. I recommend you stick the machine in your apartment and use tor + hidden services to connect to it from your VM instances. Note too that even if all you're doing is accepting Bitcoins from customers, perhaps in exchange for goods, all of the above *still* applies modulo the fact that the payment protocol is very incomplete. With P2SH (finally!) supported in all the major Bitcoin wallets there simply is no excuse not to have such an architecture other than lazyness and transaction fees; if you fall into the latter category you're business may very well be wiped out anyway by increased fees. -- 'peter'[:-1]@petertodd.org 000f9102d27cfd61ea9e8bb324593593ca3ce6ba53153ff251b3 signature.asc Description: Digital signature -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wed, Mar 05, 2014 at 11:51:25AM -0800, Gregory Maxwell wrote: On Wed, Mar 5, 2014 at 11:39 AM, Peter Todd p...@petertodd.org wrote: If you're following good practices you're not particularly vulneable to it, if at all, even if you make use of shared hosting. First of all you shouldn't be re-using addresses, which means you won't be passing that ~200 sig threshold. More important though is you shouldn't be using single factor Bitcoin addresses. Use n-of-m multisig instead and architect your system such Both of these things have long been promoted as virtuous in part because they increase robustness against this sort of thing. But while I don't disagree with these things the reality is that many people do not follow either of these piece of advice and following them requires behavioral changes that will not be adopted quickly... so I don't think that advice is especially useful. And even if it were—, good security involves defense in depth, so adding on top of them things like side-channel resistant signing is important. I haven't had a chance to sit down and think through it completely but I believe oleganza's recent blind signature scheme for ECDSA may be helpful (http://oleganza.com/blind-ecdsa-draft-v2.pdf): The idea is that instead of (or in addition to— belt and suspenders) making the signing constant time, you use the blinding scheme to first locally blind the private key and point being signed, then sign, then unblind. This way even if you are reusing a key every signing operation is handling different private data... and the only point where unblinded private data is handled is a simple scalar addition. That's nice, but I wrote my advice to show people how even if they don't know any crypto beyond what the black boxes do - the absolute minimum you need to know to write any Bitcoin software - you can still defend yourself against that attack and many others. Point is you can architect systems that remain secure even when parts of them fail, and you don't need any special cryptographic background to do so - any competent programmer can. Meanwhile, if you're not willing to take those simple steps, the Bitcoin community damn well should look down on your amateur efforts, e.g. Coinbase and EasyWallet. -- 'peter'[:-1]@petertodd.org 000f9102d27cfd61ea9e8bb324593593ca3ce6ba53153ff251b3 signature.asc Description: Digital signature -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wed, Mar 5, 2014 at 12:32 PM, Peter Todd p...@petertodd.org wrote: That's nice, but I wrote my advice to show people how even if they don't know any crypto beyond what the black boxes do - the absolute minimum you need to know to write any Bitcoin software - you can still defend yourself against that attack and many others. But it's still incomplete. Say you have an address— used only once!— with a txout with a lot of value. Someone starts paying you small amounts to that address over and over again. You haven't asked them to, they're just doing it. Do you ignore the funds?— maybe tell some customer that was ignorantly paying you over and over again to a single address sorry, those are my rules: I only acknowledge the first payment, those funds are lost!. No, of course not. You spend the darn coins and if you're on a shared host perhaps you disclose a private key. The probability of an attack actually going on is low enough compared to the cost of spending the coins in that case that even someone with good knoweldge of the risks will choose to do so. So absolutely, not reusing addresses massively increases your safety and limits losses when there is theft. But it isn't enough alone. (Nor is smarter signing, considering complex software like this has bugs and its hard to be confident that something is side channel free— esp when you allow attacker interference). -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
If we don't mind sacrificing some performance when signing, there's a fairly simple way to implement a constant-time constant-cache-access-pattern secp256k1. It is based on the idea of branchless implementations of the field and group operations. Multiprecision arithmetic can be implemented branch-free by assuming fixed sized limbs and always performing dummy carry operations even when they aren't needed. The most critical field operation that could potentially leak data is the modular inverse. Again, if we don't mind a slow implementation, a simple constant-time implementation involves exponentiation by the field modulus minus two - which is a known constant. As for group operations in secp256k1, the main sources of leaks are the branchings that exist in typical implementations as well as optimizations for special inputs, i.e. http://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates To avoid leaking any information, we can use the most general operation, Point Addition, in the following way: Always carry through the full point addition algorithm even if we get POINT_AT_INFINITY. Also, always carry through the POINT_DOUBLE operation even on unequal inputs. Store the three possible results (POINT_ADDITION, POINT_AT_INFINITY, and POINT_DOUBLE) and then do a branchless conditional swap with the output location as a final step. Branchless swaps can be performed using bitwise operations such as the examples here: https://github.com/CodeShark/cmp/blob/master/src/constant-time.h -- In the case of bitcoin, signature verification is where performance optimization is really helpful - and here there are no risks of sidechannel leaks, so we can go ahead and use the most optimal implementations. But for signing, the amount of throughput required is generally not that large and constant-time implementations will be more than adequate on typical hardware. -Eric Lombrozo On Mar 5, 2014, at 4:49 AM, Mike Hearn m...@plan99.net wrote: A new practical technique has been published that can recover secp256k1 private keys after observing OpenSSL calculate as little as 200 signatures: http://eprint.iacr.org/2014/161.pdf This attack is based on the FLUSH+RELOAD technique published last year. It works by observing L3 CPU cache timings and forcing cache line flushes using the clflush opcode. As a result, it is applicable to any x86 environment where an attacker may be able to run on the same hardware i.e. virtualised hosting environments where keys are being reused. I am not currently aware of any efforts to make OpenSSL's secp256k1 implementation completely side channel free in all aspects. Also, unfortunately many people have reimplemented ECDSA themselves and even if OpenSSL gets fixed, the custom implementations probably won't. So, IMHO this is a sign for hot wallet users to start walking (but not running) towards the exits of these shared cloud services: it doesn't feel safe to sign transactions on these platforms, so hot wallets should be managed by dedicated hardware. Of course other parts of the service, like the website, are less sensitive and can still run in the cloud. I doubt the researchers will release their code to do the side channel attack and it's rather complex to reimplement, so this gives some time for mitigation. Unfortunately the huge sums being held in some bitbank style hot wallets mean that attackers are well motivated to pull off even quite complex attacks. -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development signature.asc Description: Message signed with OpenPGP using GPGMail -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wed, Mar 5, 2014 at 1:31 PM, Eric Lombrozo elombr...@gmail.com wrote: If we don't mind sacrificing some performance when signing, there's a fairly simple way to implement a constant-time constant-cache-access-pattern secp256k1. It is based on the idea of branchless implementations of the field and group operations. Do take care that branchless doesn't mean side-channel free: On non-trivial hardware you must have uniform memory accesses too. (and that itself isn't enough for sidechannel freeness against an attacker that can do power analysis... then you star worrying about the internal structure your primitive adders and the hamming weight of your numbers, and needing to build hardware that uses differential logic, and yuck yuck yuck: This is why you still shouldn't reuse addresses, and why a blinding approach may still be sensible, even if you believe your implementation is hardened against side-channels) -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
Everything you say is true. However, branchless does reduce the attack surface considerably - if nothing else, it significantly ups the difficulty of an attack for a relatively low cost in program complexity, and that might still make it worth doing. As for uniform memory access, if we avoided any kind of heap allocation, wouldn't we avoid such issues? Anyhow, without having gone into the full details of this particular attack, it seems the main attack point is differences in how squaring and multiplication (in the case of field exponentiation) or doubling and point addition (in the case of ECDSA) are performed. I believe using a branchless implementation where each phase of the operation executes the exact same code and accesses the exact same stack frames would not be vulnerable to FLUSH+RELOAD. To be able to recover the sequence of point additions and doublings, the spy program should distinguish between consecutive doubling operations and must be able to order them with respect to point additions. Our spy program achieves this by setting the time slot to less than half the length of the group operations. With the selected curve, group add operations take 7,928 cycles on average, while group double operation take 7,601 cycles. Setting the time slot to 3,000 cycles ensures that there is an empty time slot within any group operation, allowing our spy to correctly distinguish consecutive doubles The approach I've suggested makes doubling operations indistinguishable from point additions from the perspective of cache access. On Mar 5, 2014, at 1:44 PM, Gregory Maxwell gmaxw...@gmail.com wrote: On Wed, Mar 5, 2014 at 1:31 PM, Eric Lombrozo elombr...@gmail.com wrote: If we don't mind sacrificing some performance when signing, there's a fairly simple way to implement a constant-time constant-cache-access-pattern secp256k1. It is based on the idea of branchless implementations of the field and group operations. Do take care that branchless doesn't mean side-channel free: On non-trivial hardware you must have uniform memory accesses too. (and that itself isn't enough for sidechannel freeness against an attacker that can do power analysis... then you star worrying about the internal structure your primitive adders and the hamming weight of your numbers, and needing to build hardware that uses differential logic, and yuck yuck yuck: This is why you still shouldn't reuse addresses, and why a blinding approach may still be sensible, even if you believe your implementation is hardened against side-channels) signature.asc Description: Message signed with OpenPGP using GPGMail -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wed, Mar 5, 2014 at 2:39 PM, Peter Todd p...@petertodd.org wrote: More important though is you shouldn't be using single factor Bitcoin addresses. Use n-of-m multisig instead and architect your system such that that every transaction that happens in your service has to be authorized by both the online server(s) that host your website as well as a second hardened server with an extremely limited interface between it and the online server. This adds a very minor amount of security, if any, if someone manages to hack into your hot wallet server they can just initiate a non-multisig transaction and still steal all your bitcoins in that wallet. You can't give the argument that the RPC API is password protected because the password is stored in plain-text in the config so all someone has to do is first grep for the file. There doesn't appear to be a way to force ALL outgoing transactions to be multisig and even if there was one, would you be able to force one of the addresses to be the hardened server? That still wouldn't prevent anyone from just stopping bitcoind, changing the config, then restarting it. Unless you're using your own custom wallet software there doesn't seem to be any sufficient way to prevent someone from stealing all your money once they have access to your server. Other software, like MySQL has access controls so I can prevent ALTERs, DROPs, DELETEs, etc for all live accounts limiting the scope of any attack if they manage to get into the server. Maybe this is beyond the scope of bitcoind, not sure. Thanks, -- James Hartig Software Engineer @ Grooveshark.com http://twitter.com/jameshartig -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo elombr...@gmail.com wrote: Everything you say is true. However, branchless does reduce the attack surface considerably - if nothing else, it significantly ups the difficulty of an attack for a relatively low cost in program complexity, and that might still make it worth doing. Absolutely. I believe these things are worth doing. My comment on it being insufficient was only that my signer is branchless doesn't make other defense measures (avoiding reuse, multsig with multiple devices, not sharing hardware, etc.) unimportant. As for uniform memory access, if we avoided any kind of heap allocation, wouldn't we avoid such issues? No. At a minimum to hide a memory timing side-channel you must perform no data dependent loads (e.g. no operation where an offset into memory is calculated). A strategy for this is to always load the same values, but then mask out the ones you didn't intend to read... even that I'd worry about on sufficiently advanced hardware, since I would very much not be surprised if the processor was able to determine that the load had no effect and eliminate it! :) ) Maybe in practice if your data dependencies end up only picking around in the same cache-line it doesn't actually matter... but it's hard to be sure, and unclear when a future optimization in the rest of the system might leave it exposed again. (In particular, you can't generally write timing sign-channel immune code in C (or other high level language) because the compiler is freely permitted to optimize things in a way that break the property. ... It may be _unlikely_ for it to do this, but its permitted— and will actually do so in some cases—, so you cannot be completely sure unless you check and freeze the toolchain) Anyhow, without having gone into the full details of this particular attack, it seems the main attack point is differences in how squaring and multiplication (in the case of field exponentiation) or doubling and point addition (in the case of ECDSA) are performed. I believe using a branchless implementation where each phase of the operation executes the exact same code and accesses the exact same stack frames would not be vulnerable to FLUSH+RELOAD. I wouldn't be surprised. -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
Oh, I absolutely agree that this type of attack is NOT the weakest link in security. There are MANY far easier targets in bitcoind and typical use scenarios of it. If we want to dramatically improve the security of a typical bitcoin wallet, the FLUSH+RELOAD attack is probably not where our efforts would be best rewarded trying to prevent. However, this thread IS about this particular attack vector - and my suggestion IS specific to this thread. -Eric Lombrozo On Mar 5, 2014, at 2:17 PM, James Hartig fastest...@gmail.com wrote: On Wed, Mar 5, 2014 at 2:39 PM, Peter Todd p...@petertodd.org wrote: More important though is you shouldn't be using single factor Bitcoin addresses. Use n-of-m multisig instead and architect your system such that that every transaction that happens in your service has to be authorized by both the online server(s) that host your website as well as a second hardened server with an extremely limited interface between it and the online server. This adds a very minor amount of security, if any, if someone manages to hack into your hot wallet server they can just initiate a non-multisig transaction and still steal all your bitcoins in that wallet. You can't give the argument that the RPC API is password protected because the password is stored in plain-text in the config so all someone has to do is first grep for the file. There doesn't appear to be a way to force ALL outgoing transactions to be multisig and even if there was one, would you be able to force one of the addresses to be the hardened server? That still wouldn't prevent anyone from just stopping bitcoind, changing the config, then restarting it. Unless you're using your own custom wallet software there doesn't seem to be any sufficient way to prevent someone from stealing all your money once they have access to your server. Other software, like MySQL has access controls so I can prevent ALTERs, DROPs, DELETEs, etc for all live accounts limiting the scope of any attack if they manage to get into the server. Maybe this is beyond the scope of bitcoind, not sure. Thanks, -- James Hartig Software Engineer @ Grooveshark.com http://twitter.com/jameshartig -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development signature.asc Description: Message signed with OpenPGP using GPGMail -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
One wonders also re. bitmessage, though that may not be relevant to this particular list. On Wed, Mar 05, 2014 at 11:21:52AM -0500, Kevin wrote: On 3/5/2014 7:49 AM, Mike Hearn wrote: A new practical technique has been published that can recover secp256k1 private keys after observing OpenSSL calculate as little as 200 signatures: How can we patch this issue? If you're following good practices you're not particularly vulneable to it, if at all, even if you make use of shared hosting. First of all you shouldn't be re-using addresses, which means you won't be passing that ~200 sig threshold. More important though is you shouldn't be using single factor Bitcoin addresses. Use n-of-m multisig instead and architect your system such that that every transaction that happens in your service has to be authorized by both the online server(s) that host your website as well as a second hardened server with an extremely limited interface between it and the online server. The hardened second factor *should* use a separate codebase, ideally even a second language, to authenticate actions that withdraw funds or generate new addresses based on data given to it by the online server. In the best case your customers are PGP-signing requests so you can verify their intent independently and cryptographically on both servers. Mircea Popescu's MPEx exchange is an example of this model, although I don't think they're doing any multisig stuff. Failing that you can at least use the second server to do things like limit losses by flagging higher-than-expected withdrawl volumes and unusual events. Since this second-factor server only deals with business logic - not the website - you can certainly find a secure hosting arrangement for it with physical control. I recommend you stick the machine in your apartment and use tor + hidden services to connect to it from your VM instances. Note too that even if all you're doing is accepting Bitcoins from customers, perhaps in exchange for goods, all of the above *still* applies modulo the fact that the payment protocol is very incomplete. With P2SH (finally!) supported in all the major Bitcoin wallets there simply is no excuse not to have such an architecture other than lazyness and transaction fees; if you fall into the latter category you're business may very well be wiped out anyway by increased fees. -- 'peter'[:-1]@petertodd.org 000f9102d27cfd61ea9e8bb324593593ca3ce6ba53153ff251b3 -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN optimization and the freedom to use Git, Perforce or both. Make the move to Perforce. http://pubads.g.doubleclick.net/gampad/clk?id=122218951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
