Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.219.47 as permitted sender)
	client-ip=209.85.219.47; envelope-from=mh.in.england@gmail.com;
	helo=mail-oa0-f47.google.com; 
MIME-Version: 1.0
Sender: mh.in.england@gmail.com
In-Reply-To: <CAAS2fgScLKgq8_V0oVpvP1gYAKxiyVNGVWA86XfecSmPqsMKUg@mail.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>
	<CAAS2fgScLKgq8_V0oVpvP1gYAKxiyVNGVWA86XfecSmPqsMKUg@mail.gmail.com>
Date: Thu, 6 Mar 2014 09:38:40 +0100
Message-ID: <CANEZrP1+=JY0RGEMvm9iL09L-tZAWqsSOOwFaroYUKkWumx+xg@mail.gmail.com>
From: Mike Hearn <mike@plan99.net>
To: Gregory Maxwell <gmaxwell@gmail.com>
Content-Type: multipart/alternative; boundary=001a11c2e4587684dc04f3ec10b7
Cc: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] New side channel attack that can recover
 Bitcoin keys
Precedence: list

--001a11c2e4587684dc04f3ec10b7
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

I'm wondering about whether (don't laugh) moving signing into the kernel
and then using the MTRRs to disable caching entirely for a small scratch
region of memory would also work. You could then disable pre-emption and
prevent anything on the same core from interrupting or timing the signing
operation.

However I suspect just making a hardened secp256k1 signer implementation in
userspace would be of similar difficulty, in which case it  would naturally
be preferable.


On Wed, Mar 5, 2014 at 11:25 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote=
:

> 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
> 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.
>
> 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 an=
d
> will actually do so in some cases=E2=80=94, so you cannot be completely s=
ure
> unless you check and freeze the toolchain)
>
> > 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 poin=
t
> addition (in the case of ECDSA) are performed. I believe using a branchle=
ss
> 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.
>
> I wouldn't be surprised.
>
>
> -------------------------------------------------------------------------=
-----
> Subversion Kills Productivity. Get off Subversion & Make the Move to
> Perforce.
> With Perforce, you get hassle-free workflows. Merge that actually works.
> 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
>

--001a11c2e4587684dc04f3ec10b7
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I&#39;m wondering about whether (don&#39;t laugh) moving s=
igning into the kernel and then using the MTRRs to disable caching entirely=
 for a small scratch region of memory would also work. You could then disab=
le pre-emption and prevent anything on the same core from interrupting or t=
iming the signing operation.<div>
<br></div><div>However I suspect just making a hardened secp256k1 signer im=
plementation in userspace would be of similar difficulty, in which case it =
=C2=A0would naturally be preferable.</div></div><div class=3D"gmail_extra">=
<br>
<br><div class=3D"gmail_quote">On Wed, Mar 5, 2014 at 11:25 PM, Gregory Max=
well <span dir=3D"ltr">&lt;<a href=3D"mailto:gmaxwell@gmail.com" target=3D"=
_blank">gmaxwell@gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gm=
ail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-le=
ft:1ex">
<div class=3D"">On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo &lt;<a href=
=3D"mailto:elombrozo@gmail.com">elombrozo@gmail.com</a>&gt; wrote:<br>
&gt; Everything you say is true.<br>
&gt;<br>
&gt; However, branchless does reduce the attack surface considerably - if n=
othing else, it significantly ups the difficulty of an attack for a relativ=
ely low cost in program complexity, and that might still make it worth doin=
g.<br>

<br>
</div>Absolutely. I believe these things are worth doing.<br>
<br>
My comment on it being insufficient was only that &quot;my signer is<br>
branchless&quot; doesn&#39;t make other defense measures (avoiding reuse,<b=
r>
multsig with multiple devices, not sharing hardware, etc.)<br>
unimportant.<br>
<div class=3D""><br>
&gt; As for uniform memory access, if we avoided any kind of heap allocatio=
n, wouldn&#39;t we avoid such issues?<br>
<br>
</div>No. At a minimum to hide a memory timing side-channel you must perfor=
m<br>
no data dependent loads (e.g. no operation where an offset into memory<br>
is calculated). A strategy for this is to always load the same values,<br>
but then mask out the ones you didn&#39;t intend to read... even that I&#39=
;d<br>
worry about on sufficiently advanced hardware, since I would very much<br>
not be surprised if the processor was able to determine that the load<br>
had no effect and eliminate it! :) )<br>
<br>
Maybe in practice if your data dependencies end up only picking around<br>
in the same cache-line it doesn&#39;t actually matter... but it&#39;s hard =
to<br>
be sure, and unclear when a future optimization in the rest of the<br>
system might leave it exposed again.<br>
<br>
(In particular, you can&#39;t generally write timing sign-channel immune<br=
>
code in C (or other high level language) because the compiler is<br>
freely permitted to optimize things in a way that break the property.<br>
... It may be _unlikely_ for it to do this, but its permitted=E2=80=94 and<=
br>
will actually do so in some cases=E2=80=94, so you cannot be completely sur=
e<br>
unless you check and freeze the toolchain)<br>
<div class=3D""><br>
&gt; Anyhow, without having gone into the full details of this particular a=
ttack, it seems the main attack point is differences in how squaring and mu=
ltiplication (in the case of field exponentiation) or doubling and point ad=
dition (in the case of ECDSA) are performed. I believe using a branchless i=
mplementation where each phase of the operation executes the exact same cod=
e and accesses the exact same stack frames would not be vulnerable to FLUSH=
+RELOAD.<br>

<br>
</div>I wouldn&#39;t be surprised.<br>
<div class=3D"HOEnZb"><div class=3D"h5"><br>
---------------------------------------------------------------------------=
---<br>
Subversion Kills Productivity. Get off Subversion &amp; Make the Move to Pe=
rforce.<br>
With Perforce, you get hassle-free workflows. Merge that actually works.<br=
>
Faster operations. Version large binaries. =C2=A0Built-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" target=3D"_blank">http://pubads.g.doubleclick.net/gam=
pad/clk?id=3D122218951&amp;iu=3D/4140/ostg.clktrk</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</div></div></blockquote></div><br></div>

--001a11c2e4587684dc04f3ec10b7--