1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
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--
|
