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 <elombrozo@gmail.com>) 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 <bitcoin-development@lists.sourceforge.net>; 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 <multiple recipients> (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 <elombrozo@gmail.com> In-Reply-To: <CANEZrP25N7W_MeZin_pyVQP5pC8bt5yqJzTXt_tN1P6kWb5i2w@mail.gmail.com> Date: Wed, 5 Mar 2014 13:31:01 -0800 Message-Id: <0720C223-E9DD-4E76-AD6F-0308CA5B5289@gmail.com> References: <CANEZrP25N7W_MeZin_pyVQP5pC8bt5yqJzTXt_tN1P6kWb5i2w@mail.gmail.com> To: Peter Todd <pete@petertodd.org> 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 <bitcoin-development@lists.sourceforge.net> 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: <bitcoin-development.lists.sourceforge.net> List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>, <mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe> List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development> List-Post: <mailto:bitcoin-development@lists.sourceforge.net> List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help> List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>, <mailto:bitcoin-development-request@lists.sourceforge.net?subject=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 <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: >=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 <html><head><meta http-equiv=3D"Content-Type" content=3D"text/html = charset=3Dus-ascii"></head><body style=3D"word-wrap: break-word; = -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">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.<div>It is based on the idea of branchless implementations of = the field and group operations.<div><br></div><div>Multiprecision = arithmetic can be implemented branch-free by assuming fixed sized limbs = and always performing dummy carry operations even when they aren't = needed.</div><div><br></div><div>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.</div><div><br></div><div>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,</div><div>i.e. <a = href=3D"http://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coo= rdinates">http://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_C= oordinates</a></div><div>To avoid leaking any information, we can use = the most general operation, Point Addition, in the following = way:</div><div><br></div><div>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.</div><div><br></div><div>Branchless swaps can = be performed using bitwise operations such as the examples here: <a = href=3D"https://github.com/CodeShark/cmp/blob/master/src/constant-time.h">= https://github.com/CodeShark/cmp/blob/master/src/constant-time.h</a></div>= <div><br></div><div>--------------</div><div><br></div><div>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.</div><div><br></div><div>-Eric = Lombrozo</div><div><br></div><div><div><div>On Mar 5, 2014, at 4:49 AM, = Mike Hearn <<a href=3D"mailto:mike@plan99.net">mike@plan99.net</a>> = wrote:</div><br class=3D"Apple-interchange-newline"><blockquote = type=3D"cite"><div dir=3D"ltr">A new practical technique has been = published that can recover secp256k1 private keys after observing = OpenSSL calculate as little as 200 signatures:<div><br></div><div><a = href=3D"http://eprint.iacr.org/2014/161.pdf">http://eprint.iacr.org/2014/1= 61.pdf</a><br> </div><div><br></div><div>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.</div> <div><br></div><div>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. </div> <div><br></div><div>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.</div> </div> = --------------------------------------------------------------------------= ----<br>Subversion Kills Productivity. Get off Subversion & Make the = Move to Perforce.<br>With Perforce, you get hassle-free workflows. Merge = that actually works. <br>Faster operations. Version large binaries. = Built-in WAN optimization and the<br>freedom to use Git, Perforce = or both. Make the move to Perforce.<br><a = href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D122218951&iu=3D= /4140/ostg.clktrk_______________________________________________">http://p= ubads.g.doubleclick.net/gampad/clk?id=3D122218951&iu=3D/4140/ostg.clkt= rk_______________________________________________</a><br>Bitcoin-developme= nt mailing = list<br>Bitcoin-development@lists.sourceforge.net<br>https://lists.sourcef= orge.net/lists/listinfo/bitcoin-development<br></blockquote></div><br></di= v></div></body></html>= --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--