From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1WLJPG-0004TC-Il for bitcoin-development@lists.sourceforge.net; Wed, 05 Mar 2014 21:31:14 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.192.178 as permitted sender) client-ip=209.85.192.178; envelope-from=elombrozo@gmail.com; helo=mail-pd0-f178.google.com; Received: from mail-pd0-f178.google.com ([209.85.192.178]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1WLJPF-00069z-1U for bitcoin-development@lists.sourceforge.net; Wed, 05 Mar 2014 21:31:14 +0000 Received: by mail-pd0-f178.google.com with SMTP id x10so1579594pdj.9 for ; Wed, 05 Mar 2014 13:31:07 -0800 (PST) X-Received: by 10.68.239.10 with SMTP id vo10mr10061340pbc.48.1394055067108; Wed, 05 Mar 2014 13:31:07 -0800 (PST) Received: from [192.168.1.107] (cpe-76-88-33-166.san.res.rr.com. [76.88.33.166]) by mx.google.com with ESMTPSA id cz3sm12081671pbc.9.2014.03.05.13.31.03 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 05 Mar 2014 13:31:04 -0800 (PST) Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\)) Content-Type: multipart/signed; boundary="Apple-Mail=_0153D336-805C-4DCA-ABCB-A2B314209E1C"; protocol="application/pgp-signature"; micalg=pgp-sha1 From: Eric Lombrozo In-Reply-To: Date: Wed, 5 Mar 2014 13:31:01 -0800 Message-Id: <0720C223-E9DD-4E76-AD6F-0308CA5B5289@gmail.com> References: To: Peter Todd X-Mailer: Apple Mail (2.1510) X-Spam-Score: -0.6 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (elombrozo[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no trust [209.85.192.178 listed in list.dnswl.org] 1.0 HTML_MESSAGE BODY: HTML included in message -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1WLJPF-00069z-1U Cc: Bitcoin Development Subject: Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 05 Mar 2014 21:31:14 -0000 --Apple-Mail=_0153D336-805C-4DCA-ABCB-A2B314209E1C Content-Type: multipart/alternative; boundary="Apple-Mail=_38FDF086-1B73-48BA-9A6B-458C4B89A9A1" --Apple-Mail=_38FDF086-1B73-48BA-9A6B-458C4B89A9A1 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii 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 wrote: > A new practical technique has been published that can recover = secp256k1 private keys after observing OpenSSL calculate as little as = 200 signatures: >=20 > http://eprint.iacr.org/2014/161.pdf >=20 > 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. >=20 > 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.=20 >=20 > 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.=20 > 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=3D122218951&iu=3D/4140/ostg.= clktrk_______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development --Apple-Mail=_38FDF086-1B73-48BA-9A6B-458C4B89A9A1 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=us-ascii 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,
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:


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://p= ubads.g.doubleclick.net/gampad/clk?id=3D122218951&iu=3D/4140/ostg.clkt= rk_______________________________________________
Bitcoin-developme= nt mailing = list
Bitcoin-development@lists.sourceforge.net
https://lists.sourcef= orge.net/lists/listinfo/bitcoin-development

= --Apple-Mail=_38FDF086-1B73-48BA-9A6B-458C4B89A9A1-- --Apple-Mail=_0153D336-805C-4DCA-ABCB-A2B314209E1C Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=signature.asc Content-Type: application/pgp-signature; name=signature.asc Content-Description: Message signed with OpenPGP using GPGMail -----BEGIN PGP SIGNATURE----- iQIcBAEBAgAGBQJTF5eVAAoJEAA1EyJsW9n+XzcQAOj5Ew3iq4B/4r5qI+CK9WKt vaMoCarAYGfplXprrt/pWcNkT8VKZ78Cz3CbdE5nQMN5H6lVMpod0bmX3qo0bI9m flN25yCE9ZCNqAOJqW5Dyi71eAuTabiH2RFLrJtvKhjBLupTjNkaRJ9u3Lr8Qowb pVCp3g1YNEiq4IQPfw17dD+i+iaE/tt9TgkGaUhnV3NiOc2DuNmg0FFkgFtD6c8+ eoccNmacv9Uuz7dh7Y52AuKxpYdG0vtgttmrGrL2iK5PnYllC1anYQ0E93LD1p/T AaCQju7ODmTK9e9oH78TGNneoCV4/GZsEYB3tZJ0rih6AVc6c170H6JJJcpDB2WV /t7J1MzU93tuydDA417ZLH0DDQChMzrVhC2Q0eN8XXHxnCdMTl9VhBxlgYrHDDHv zksce6FOo0XlmOyDydPGfHhCKDkrLgBVl1oQIV0ze3x1GudiCS3SIbuj8b4rnXsQ o13N/hgaj/9fsAdywMFRZ00EA7dSP+4s3iw/97AnyFD748H2hqFod0UkMvtXRFy2 U69IBSAZ/27ZZwqskvHvOubMtOxiJu/r6o/ZDF2cp2mqh8aoX9iICbVfYRIN22IB wTQbiVjZwqfH40tCrCLHlcbspdpHAOa+hjdgGqhWRHhdyjyBAfcBw0pqPev2eve2 0uZ5ydm6ehlkzOuE8IQi =Ue6V -----END PGP SIGNATURE----- --Apple-Mail=_0153D336-805C-4DCA-ABCB-A2B314209E1C--