From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 (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 In-Reply-To: Date: Wed, 5 Mar 2014 14:14:20 -0800 Message-Id: <7E50E1D6-3A9F-419B-B01E-50C6DE044E0F@gmail.com> References: <0720C223-E9DD-4E76-AD6F-0308CA5B5289@gmail.com> To: Gregory Maxwell 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 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 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 wrote: > On Wed, Mar 5, 2014 at 1:31 PM, Eric Lombrozo = 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--