From: Eric Lombrozo <elombrozo@gmail•com>
To: Peter Todd <pete@petertodd•org>
Cc: Bitcoin Development <bitcoin-development@lists•sourceforge.net>
Subject: Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
Date: Wed, 5 Mar 2014 13:31:01 -0800 [thread overview]
Message-ID: <0720C223-E9DD-4E76-AD6F-0308CA5B5289@gmail.com> (raw)
In-Reply-To: <CANEZrP25N7W_MeZin_pyVQP5pC8bt5yqJzTXt_tN1P6kWb5i2w@mail.gmail.com>
[-- 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 --]
next prev parent reply other threads:[~2014-03-05 21:31 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-03-05 12:49 Mike Hearn
2014-03-05 12:56 ` Pieter Wuille
2014-03-05 13:18 ` Jean-Paul Kogelman
2014-03-05 14:04 ` Pieter Wuille
2014-03-05 16:21 ` Kevin
2014-03-05 19:39 ` Peter Todd
2014-03-05 19:51 ` Gregory Maxwell
2014-03-05 20:32 ` Peter Todd
2014-03-05 20:54 ` Gregory Maxwell
2014-03-12 9:44 ` Peter Todd
2014-03-05 22:17 ` James Hartig
2014-03-05 22:26 ` Eric Lombrozo
2014-03-06 7:02 ` Odinn Cyberguerrilla
2014-03-08 19:34 ` Luke-Jr
2014-03-09 1:57 ` Gregory Maxwell
2014-03-05 21:31 ` Eric Lombrozo [this message]
2014-03-05 21:44 ` Gregory Maxwell
2014-03-05 22:14 ` Eric Lombrozo
2014-03-05 22:25 ` Gregory Maxwell
2014-03-06 8:38 ` Mike Hearn
2014-03-06 10:00 ` Natanael
2014-03-25 13:39 ` Troy Benjegerdes
2014-03-25 13:50 ` Gavin Andresen
2014-03-08 19:29 ` Gustav Simonsson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=0720C223-E9DD-4E76-AD6F-0308CA5B5289@gmail.com \
--to=elombrozo@gmail$(echo .)com \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
--cc=pete@petertodd$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox