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
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <gmaxwell@gmail.com>) id 1WLKFS-0005n3-BR
for bitcoin-development@lists.sourceforge.net;
Wed, 05 Mar 2014 22:25:10 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.217.174 as permitted sender)
client-ip=209.85.217.174; envelope-from=gmaxwell@gmail.com;
helo=mail-lb0-f174.google.com;
Received: from mail-lb0-f174.google.com ([209.85.217.174])
by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1WLKFR-0001Pu-Hg
for bitcoin-development@lists.sourceforge.net;
Wed, 05 Mar 2014 22:25:10 +0000
Received: by mail-lb0-f174.google.com with SMTP id u14so1169176lbd.33
for <bitcoin-development@lists.sourceforge.net>;
Wed, 05 Mar 2014 14:25:03 -0800 (PST)
MIME-Version: 1.0
X-Received: by 10.112.45.108 with SMTP id l12mr4957526lbm.21.1394058302951;
Wed, 05 Mar 2014 14:25:02 -0800 (PST)
Received: by 10.112.189.164 with HTTP; Wed, 5 Mar 2014 14:25:02 -0800 (PST)
In-Reply-To: <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>
<7E50E1D6-3A9F-419B-B01E-50C6DE044E0F@gmail.com>
Date: Wed, 5 Mar 2014 14:25:02 -0800
Message-ID: <CAAS2fgScLKgq8_V0oVpvP1gYAKxiyVNGVWA86XfecSmPqsMKUg@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Eric Lombrozo <elombrozo@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
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
(gmaxwell[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: 1WLKFR-0001Pu-Hg
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:25:10 -0000
On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo <elombrozo@gmail.com> wrote:
> Everything you say is true.
>
> However, branchless does reduce the attack surface considerably - if noth=
ing 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.
Absolutely. I believe these things are worth doing.
My comment on it being insufficient was only that "my signer is
branchless" doesn't make other defense measures (avoiding reuse,
multsig with multiple devices, not sharing hardware, etc.)
unimportant.
> As for uniform memory access, if we avoided any kind of heap allocation, =
wouldn't we avoid such issues?
No. At a minimum to hide a memory timing side-channel you must perform
no data dependent loads (e.g. no operation where an offset into memory
is calculated). A strategy for this is to always load the same values,
but then mask out the ones you didn't intend to read... even that I'd
worry about on sufficiently advanced hardware, since I would very much
not be surprised if the processor was able to determine that the load
had no effect and eliminate it! :) )
Maybe in practice if your data dependencies end up only picking around
in the same cache-line it doesn't actually matter... but it's hard to
be sure, and unclear when a future optimization in the rest of the
system might leave it exposed again.
(In particular, you can't generally write timing sign-channel immune
code in C (or other high level language) because the compiler is
freely permitted to optimize things in a way that break the property.
... It may be _unlikely_ for it to do this, but its permitted=E2=80=94 and
will actually do so in some cases=E2=80=94, so you cannot be completely sur=
e
unless you check and freeze the toolchain)
> Anyhow, without having gone into the full details of this particular atta=
ck, it seems the main attack point is differences in how squaring and multi=
plication (in the case of field exponentiation) or doubling and point addit=
ion (in the case of ECDSA) are performed. I believe using a branchless impl=
ementation where each phase of the operation executes the exact same code a=
nd accesses the exact same stack frames would not be vulnerable to FLUSH+RE=
LOAD.
I wouldn't be surprised.
|
