path: root/55/7e1f02bedd8a291c22c563a84a1a696447fc64

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.&nbsp;<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:&nbsp;<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 &lt;<a href=3D"mailto:mike@plan99.net">mike@plan99.net</a>&gt; =
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.&nbsp;</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: &nbsp;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 &amp; Make the =
Move to Perforce.<br>With Perforce, you get hassle-free workflows. Merge =
that actually works. <br>Faster operations. Version large binaries. =
&nbsp;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&amp;iu=3D=
/4140/ostg.clktrk_______________________________________________">http://p=
ubads.g.doubleclick.net/gampad/clk?id=3D122218951&amp;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--