[Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 1477 bytes --]

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.

[-- Attachment #2: Type: text/html, Size: 1686 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Pieter Wuille]

On Wed, Mar 5, 2014 at 1:49 PM, Mike Hearn <mike@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.

-- 
Pieter

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Jean-Paul Kogelman]

> On Mar 5, 2014, at 8:56 PM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> 
>> On Wed, Mar 5, 2014 at 1:49 PM, Mike Hearn <mike@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=122218951&iu=/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

[Pieter Wuille]

On Wed, Mar 5, 2014 at 2:18 PM, Jean-Paul Kogelman
<jeanpaulkogelman@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

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Kevin]

[-- Attachment #1: Type: text/plain, Size: 2296 bytes --]

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=122218951&iu=/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


[-- Attachment #2: Type: text/html, Size: 3727 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2437 bytes --]

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
000000000000000f9102d27cfd61ea9e8bb324593593ca3ce6ba53153ff251b3

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Gregory Maxwell]

On Wed, Mar 5, 2014 at 11:39 AM, Peter Todd <pete@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.

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2485 bytes --]

On Wed, Mar 05, 2014 at 11:51:25AM -0800, Gregory Maxwell wrote:
> On Wed, Mar 5, 2014 at 11:39 AM, Peter Todd <pete@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
000000000000000f9102d27cfd61ea9e8bb324593593ca3ce6ba53153ff251b3

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Gregory Maxwell]

On Wed, Mar 5, 2014 at 12:32 PM, Peter Todd <pete@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).

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2031 bytes --]

On Wed, Mar 05, 2014 at 12:54:04PM -0800, Gregory Maxwell wrote:
> On Wed, Mar 5, 2014 at 12:32 PM, Peter Todd <pete@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
0000000000000000afcad9265e8b44bf1171a08165c09b329fab2893bf13ec69

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[James Hartig]

[-- Attachment #1: Type: text/plain, Size: 1660 bytes --]

On Wed, Mar 5, 2014 at 2:39 PM, Peter Todd <pete@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

[-- Attachment #2: Type: text/html, Size: 2230 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Eric Lombrozo]

[-- Attachment #1.1: Type: text/plain, Size: 2928 bytes --]

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 <fastest963@gmail.com> wrote:

> On Wed, Mar 5, 2014 at 2:39 PM, Peter Todd <pete@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=122218951&iu=/4140/ostg.clktrk_______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


[-- Attachment #1.2: Type: text/html, Size: 4000 bytes --]

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Odinn Cyberguerrilla]

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
> 000000000000000f9102d27cfd61ea9e8bb324593593ca3ce6ba53153ff251b3
> ------------------------------------------------------------------------------
> 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=122218951&iu=/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

[Luke-Jr]

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

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Gregory Maxwell]

On Sat, Mar 8, 2014 at 11:34 AM, Luke-Jr <luke@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).

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Eric Lombrozo]

[-- Attachment #1.1: Type: text/plain, Size: 4188 bytes --]

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 <mike@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=122218951&iu=/4140/ostg.clktrk_______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


[-- Attachment #1.2: Type: text/html, Size: 5252 bytes --]

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Gregory Maxwell]

On Wed, Mar 5, 2014 at 1:31 PM, Eric Lombrozo <elombrozo@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)

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Eric Lombrozo]

[-- Attachment #1: Type: text/plain, Size: 2635 bytes --]

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 <gmaxwell@gmail.com> wrote:

> On Wed, Mar 5, 2014 at 1:31 PM, Eric Lombrozo <elombrozo@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)


[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Gregory Maxwell]

On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo <elombrozo@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.

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 3658 bytes --]

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 <gmaxwell@gmail.com> wrote:

> On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo <elombrozo@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=122218951&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: 4534 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Natanael]

[-- Attachment #1: Type: text/plain, Size: 4654 bytes --]

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" <mike@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 <gmaxwell@gmail.com>wrote:
>
>> On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo <elombrozo@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=122218951&iu=/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=122218951&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: 6070 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Troy Benjegerdes]

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" <mike@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 <gmaxwell@gmail.com>wrote:
> >
> >> On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo <elombrozo@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=122218951&iu=/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=122218951&iu=/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=122218951&iu=/4140/ostg.clktrk

> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


-- 
----------------------------------------------------------------------------
Troy Benjegerdes                 'da hozer'                  hozer@hozed.org
7 elements      earth::water::air::fire::mind::spirit::soul        grid.coop

      Never pick a fight with someone who buys ink by the barrel,
         nor try buy a hacker who makes money by the megahash

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 722 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 1136 bytes --]

Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys

[Gustav Simonsson]

[-- Attachment #1: Type: text/plain, Size: 7887 bytes --]

While there is no mention of virtualization in the side-channel article,
the FLUSH+RELOAD paper [1] mentions virtualization and claims the clflush
instruction works not only towards processes on the same OS, but also
against processes in a separate guest OS if executed on the host OS (type 2
hypervisor) [2]. It also works if executed from within another guest OS
(though that reduces the efficiency of the attack) [3].

Both the authors [4] and Vulnerability Note VU#976534 [5] claim disabling
hypervisor memory page de-duplication prevents the attack. This could
perhaps be a first step for bitcoin companies running their software on
shared hosts; demand their allocated instances to be on hosts with this
disabled. Question is how common it is for virtualization providers to
offer that as an option.

TRESOR is is only applicable if running in a non-virtualized OS [6].

While TRESOR only implements AES, it seems it could work for ECDSA as well,
as they use the four x86 debug registers to fit a 256 bit privkey [7] for
the entire machine uptime, and then use other registers when doing the
actual AES ops. They use the Intel AES-NI instruction set though, and since
there is no corresponding instruction set for EC extra work would be
required to manually implement EC math in assembler.

They actually do what Mike Hearn mentioned and disable preemption in Linux
(their code runs in kernel space; they patched the kernel) to ensure
atomicity. Not only do they manage to protect against memory attacks (and
RAM/cache timing attacks) from other processes running on the same host,
but even from root on the same host (from userland, the debug registers are
only accessible through ptrace, which they patched, and they also disabled
LKM & KMEM).

One could imagine different levels of TRESOR-like ECDSA with different
tradeoffs of complexity vs security. For example, if one is fine with
keeping the privkey(s) in RAM but want to avoid cache timing attacks, the
signing could be implemented as a userspace program holding key(s) in RAM
together with a kernel module providing a syscall for signing. Signing is
then run with preemption using only x86 registers for intermediate data and
then using e.g. movntps [8] to write to RAM without data being cached. The
benefit of this compared with the full TRESOR approach is that it would not
require a patched kernel, only a kernel module. It would also be simpler to
implement compared to keeping the privkey in the debug registers for the
entire machine uptime, especially if multiple privkeys are used. It would
not protect against root though, since an adversary getting root could load
their own kernel module and read the registers.

To handle multiple keys (maybe as one-time-use) and get full TRESOR
benefits, one could perhaps (with the original TRESOR approach, i.e. with
patched kernel) store a BIP 0032 starting string / seed + counter in the
debug registers and have the atomic kernel code generate new keys and do
the signing.

Cheers,
Gustav Simonsson

1. http://eprint.iacr.org/2013/448.pdf
2. Page 1 of [1]
3. page 5 of [1]
4. page 8 (end of conclusions section) of [1]
5. http://www.kb.cert.org/vuls/id/976534
6. page 8, "3.2 Hardware compatibility",
https://www.usenix.org/legacy/event/sec11/tech/full_papers/Muller.pdf
7. page 3, "2.2 Key Management" of [6]
8. page 1041 of
http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-manual-325462.pdf



On Thu, Mar 6, 2014 at 9:38 AM, Mike Hearn <mike@plan99.net> wrote:

> 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 <gmaxwell@gmail.com>wrote:
>
>> On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo <elombrozo@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=122218951&iu=/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=122218951&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: 9855 bytes --]