Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
	helo=mx.sourceforge.net)
	by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <elombrozo@gmail.com>) id 1WLK5A-0006BG-Cm
	for bitcoin-development@lists.sourceforge.net;
	Wed, 05 Mar 2014 22:14:32 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.220.46 as permitted sender)
	client-ip=209.85.220.46; envelope-from=elombrozo@gmail.com;
	helo=mail-pa0-f46.google.com; 
Received: from mail-pa0-f46.google.com ([209.85.220.46])
	by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1WLK59-00015j-HE
	for bitcoin-development@lists.sourceforge.net;
	Wed, 05 Mar 2014 22:14:32 +0000
Received: by mail-pa0-f46.google.com with SMTP id kp14so1686916pab.5
	for <bitcoin-development@lists.sourceforge.net>;
	Wed, 05 Mar 2014 14:14:25 -0800 (PST)
X-Received: by 10.66.155.102 with SMTP id vv6mr9896975pab.89.1394057665696;
	Wed, 05 Mar 2014 14:14:25 -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
	pe3sm12288471pbc.23.2014.03.05.14.14.22 for <multiple recipients>
	(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
	Wed, 05 Mar 2014 14:14:23 -0800 (PST)
Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\))
Content-Type: multipart/signed;
	boundary="Apple-Mail=_CEBCA4D2-C917-447F-BCA1-68B961D976B7";
	protocol="application/pgp-signature"; micalg=pgp-sha1
From: Eric Lombrozo <elombrozo@gmail.com>
In-Reply-To: <CAAS2fgTGDzPFDP=ii08VXcXYpWr2akYWxqJCNHW-ABuN=ESc8A@mail.gmail.com>
Date: Wed, 5 Mar 2014 14:14:20 -0800
Message-Id: <7E50E1D6-3A9F-419B-B01E-50C6DE044E0F@gmail.com>
References: <CANEZrP25N7W_MeZin_pyVQP5pC8bt5yqJzTXt_tN1P6kWb5i2w@mail.gmail.com>
	<0720C223-E9DD-4E76-AD6F-0308CA5B5289@gmail.com>
	<CAAS2fgTGDzPFDP=ii08VXcXYpWr2akYWxqJCNHW-ABuN=ESc8A@mail.gmail.com>
To: Gregory Maxwell <gmaxwell@gmail.com>
X-Mailer: Apple Mail (2.1510)
X-Spam-Score: -1.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.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: 1WLK59-00015j-HE
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 22:14:32 -0000


--Apple-Mail=_CEBCA4D2-C917-447F-BCA1-68B961D976B7
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

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.
>=20
> Do take care that branchless doesn't mean side-channel free: On
> non-trivial hardware you must have uniform memory accesses too.
>=20
> (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)


--Apple-Mail=_CEBCA4D2-C917-447F-BCA1-68B961D976B7
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-----

iQIcBAEBAgAGBQJTF6G8AAoJEAA1EyJsW9n+HI8QAMRRMwlyZfOc5IPkT5HCSe20
yjQl+HjtLhjMz74ABdc3ONuGLEiNFwBic4jfa4rEBF9DPr0F9QMH0CkycqTVpktI
goxQxcfNkJNE6hGdOMzFHzWjbzOjhl71eoImpUvjYbSjuVcoWUFlpbH2Uyd653Pz
xxcr0P8Nc3Oym/CpArXS4LTpJalUmc59WAt72JpWtRNjUPSfkJPgl35+rpYhaSpq
ldPTvkbLucVbHpTnKRiOVe+ySIfqF+xpQQDB8oVyIWgBxNPfwPLYuRPaJYIcEx9i
ctHjnp8P+F+cQ4ApVLt50OmwIPHY3j04o2yEMC5SNpfHjMPh1IncJy0LMKhm+WFw
x6ogRfzpL6JzP98QvYVIZraTvQ9umF1vyyMRstkI4OBaDvgj48dGbSMCMsni8H0B
Hi3RfnIuIHHbBd6oUZuiYd7P2H6uHBMkQoy4Hkzcpz6yzbQdiOSDA4MAWhm+DXx/
uHJEovDvXlilzQq+ZUWZCBky75x2IEH0ieD+pgGU/OJwQ1SsMEfBQgFFuZotz2Zv
RIh1UpqRvoGYJNOTukyuR/6C8sDULnSkSipkuGfOWzg69El71wGhCwTu0Z5icyEF
iBd8Pyp+TXldGKce8xG0X74ohlBcylB8aF+JQSKgoNlnDBLR5GjcxMb+3RJsYZEe
ZoonTdzgoo8ekf2s3Q5T
=hsvw
-----END PGP SIGNATURE-----

--Apple-Mail=_CEBCA4D2-C917-447F-BCA1-68B961D976B7--