path: root/06/499cca15b700f28c88a670d178dedbedd632c3

Return-Path: <lloyd.fourn@gmail.com>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 0C720C0177
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 25 Mar 2020 15:08:18 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by hemlock.osuosl.org (Postfix) with ESMTP id E86F1885E3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 25 Mar 2020 15:08:17 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from hemlock.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 3xwSz19pn7ZK
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 25 Mar 2020 15:08:16 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-io1-f52.google.com (mail-io1-f52.google.com
 [209.85.166.52])
 by hemlock.osuosl.org (Postfix) with ESMTPS id DF2C388407
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 25 Mar 2020 15:08:15 +0000 (UTC)
Received: by mail-io1-f52.google.com with SMTP id q128so2528071iof.9
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 25 Mar 2020 08:08:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=kqK2xpiWpasNolmhsC2qfpFOTfMu7D7fohUgpEzgctI=;
 b=JgVHsAKkP+VUtqHP1oKnwVKbwITZ3K0rXUpMt1NCmfmAsdtnzsKGNfqfy4t+AE7LJm
 ITq3BqzaYt+T6Ku3XVUKOlvMvFExbvMD9IKWPciBjDoQZr3qi+lro1SNR48z49NLCq7k
 M8ACWpCPpfNsVsOBZv+66a75I7JjGsrELj2DXSNxvuPIKbrIiQViX+2xAMwPtek2XHm5
 OuX06w8+Hh4/gDBEWEVuGCDBQ96rbH+TogXN+H9Y1I6SP25R0jJycY9jj7o1RT0+d/Mq
 h/ZSlD+jSVVzqfh/NRUs3HPBHTOfkX1W934Kgt3v/GXPE6mx5kg369azQ4LvMwH6jgsx
 BZsg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=kqK2xpiWpasNolmhsC2qfpFOTfMu7D7fohUgpEzgctI=;
 b=TUYT1kX27g4SwlCDx2UdXp/272a4/AjrJHgU0qIyPp5Qd6xftFnWWdS7kMROioz04Z
 2FYqNh12pauxU5CZJs6yPUIDFxNPf5mjnTDDsyf4oKtRpEMyHdX3Wua7q2rNGwDNDf1W
 oWWqqUCOGBUpAHMEHifYKUGV1BkojRp3TnlAr/8w0x4LFspve0kRYe/ODeVHdlQlsa10
 +r7hXTBziGRVf74wJ1R0kWdfUfmleA9Sc/0SyYCQJ3l29+MS8+9Ar0YE4gXPf1Gr/4Jh
 jOlgn206OqQM4gKiP0yASbOrutacliKXt5mR7Yr6MmiYQd1y4jy1NLXt6WwSSeBZ3Ih+
 O86w==
X-Gm-Message-State: ANhLgQ126EmjHTlicl40pkAsd8CURZoPB6j7tqhrhVf3tSR9I20CEDjk
 ZdKHntpJHsRH9JhFYFC3YumA8bIjrQbwOw9iVdtE1590/FQ=
X-Google-Smtp-Source: ADFU+vu6fiWbHP+CYUFRYgOhhSdcCLLdDzQplBbp7dnWrHWmPtp0HDt74N0J35HFlshdoiGaemCx1OHLHU4YkhW6RfU=
X-Received: by 2002:a05:6638:733:: with SMTP id
 j19mr3417531jad.131.1585148895083; 
 Wed, 25 Mar 2020 08:08:15 -0700 (PDT)
MIME-Version: 1.0
References: <CAH5Bsr3EtFpecXPG07so1KA0sre9Cy-XPv=BADBgUe4M7kuxFg@mail.gmail.com>
 <143g8W700TxSwkQM6rPf7NfRYcaVJoBqYLfR99gwtb-kBfL76EK556d4U8aNyEVRz5bp1eFzApLwPMSnhwAnK5m_htjqVREn5yZxXRCORiU=@wuille.net>
In-Reply-To: <143g8W700TxSwkQM6rPf7NfRYcaVJoBqYLfR99gwtb-kBfL76EK556d4U8aNyEVRz5bp1eFzApLwPMSnhwAnK5m_htjqVREn5yZxXRCORiU=@wuille.net>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Thu, 26 Mar 2020 02:07:48 +1100
Message-ID: <CAH5Bsr2jgBHHTNEECC5OPZW6RjsEvto3mg0doTyWkrHCU-rdVw@mail.gmail.com>
To: Pieter Wuille <bitcoin-dev@wuille.net>
Content-Type: multipart/alternative; boundary="000000000000cec3a205a1af3c30"
X-Mailman-Approved-At: Wed, 25 Mar 2020 15:14:42 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Mitigating Differential Power Analysis in BIP-340
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Wed, 25 Mar 2020 15:08:18 -0000

--000000000000cec3a205a1af3c30
Content-Type: text/plain; charset="UTF-8"

Hi Pieter,

Thanks for the detailed response.


> /secret key/secret keyI'll try to summarize the discussion we had that led
> to this choice, but most of it is on
> https://github.com/sipa/bips/issues/195 if you want the details.


Ahh I can't believe I missed that github issue while searching. I guess I
started reading a paper on DPA and got carried away. I can see you got to
where I was and then went much further including some empirical analysis.
Nice. I agree with the conclusion that xor is more robust than just hashing
randomness in the same block as the secret key.


> Let me first try to address what I think you're overlooking: in a
> BIP32/Taproot like scenario, the private key that goes into the signing
> algorithm functions as *both* secret and known to the attacker. That is to
> say, there is a master secret s, and signing key x that goes into the hash
> is x=s+a (mod n) for some value a that the attacker knows, and can modify
> (he cannot control it directly, but he may be able to grind it to have a
> structure he likes). I believe that means that feeding x to a hash directly
> itself is already a problem, regardless of what else goes into the hash -
> interactions between bits inside the hash operation that all come from x
> itself can leak bit-level information of x.  XORing (or any other simple
> mix operation that does not expose bit-level information) into the private
> key before giving it to a hash function seems like it would address this.
>

This is an subtle point that I didn't cross my mind. My gut feeling is
there isn't even a computational argument to made that what I was
suggesting is secure against DPA in that setting. DPA seems to be a PITA. A
footnote in the BIP with a citation for DPA (the ed25519 one from the issue
is good) and a hint about why you should avoid hashing Bitcoin secret keys
altogether would be good. This brings us to the next point.

It also assumes that somehow the computation of x itself is immune from
> leaks (something you pointed out in a previous e-mail, I noticed).
>

From my reading of the HMAC papers it seems you might be able to vary the
BIP32 child index derivation to do this attack. Just thinking about it now,
these attacks seem far fetched just because in order for it to be useful
you need to have physical access to the device and to be able to accurately
measure power consumption in high resolution (which I guess you can't do
from a typical USB bus from corrupted software). Then you also need to get
the user to do lots of signing or derivation with their device. I guess a
malicious cable with some way of exfiltrating power consumption could do it.


> I'm happy for any input you may have here. In particular, the recent
> discussions around the interactions between anti-covert channel protection,
> randomness, and the ability to spot check hardware devices may mean we
> should revise the advice to consider not adding randomness unless such a
> anti-covert channel scheme is used.
>

My only comment here is that there will end up being more than one way to
do it and I think what you and your collaborators have put forward is at a
local optimum of design (now that I understand it). Thanks and well done!
It won't be the right optimum for everyone. To me, it seems like a good
place to start. If you develop a decent nonce exfiltration protected
signing protocol later then I don't see why HW wallets wouldn't compete for
favour amongst the community by implementing and updating their devices to
conform to it.

LL

--000000000000cec3a205a1af3c30
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_quote"><div>Hi Pieter,</div><div><br><=
/div><div>Thanks for the detailed response.</div><div>=C2=A0</div><blockquo=
te class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px =
solid rgb(204,204,204);padding-left:1ex">/secret key/secret keyI&#39;ll try=
 to summarize the discussion we had that led to this choice, but most of it=
 is on <a href=3D"https://github.com/sipa/bips/issues/195" rel=3D"noreferre=
r" target=3D"_blank">https://github.com/sipa/bips/issues/195</a> if you wan=
t the details.</blockquote><div><br></div><div>Ahh I can&#39;t believe I mi=
ssed that github issue while searching. I guess I started reading a paper o=
n DPA and got carried away. I can see you got to where I was and then went =
much further including some empirical analysis. Nice. I agree with the conc=
lusion that xor is more robust than just hashing randomness in the same blo=
ck as the secret key.</div><div>=C2=A0</div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)=
;padding-left:1ex">
Let me first try to address what I think you&#39;re overlooking: in a BIP32=
/Taproot like scenario, the private key that goes into the signing algorith=
m functions as *both* secret and known to the attacker. That is to say, the=
re is a master secret s, and signing key x that goes into the hash is x=3Ds=
+a (mod n) for some value a that the attacker knows, and can modify (he can=
not control it directly, but he may be able to grind it to have a structure=
 he likes). I believe that means that feeding x to a hash directly itself i=
s already a problem, regardless of what else goes into the hash - interacti=
ons between bits inside the hash operation that all come from x itself can =
leak bit-level information of x.=C2=A0 XORing (or any other simple mix oper=
ation that does not expose bit-level information) into the private key befo=
re giving it to a hash function seems like it would address this.<br></bloc=
kquote><div><br></div><div>This is an subtle point that I didn&#39;t cross =
my mind. My gut feeling is there isn&#39;t even a computational argument to=
 made that what I was suggesting is secure against DPA in that setting. DPA=
 seems to be a PITA. A footnote in the BIP with a citation for DPA (the ed2=
5519 one from the issue is good) and a hint about why you should avoid hash=
ing Bitcoin secret keys altogether would be good. This brings us to the nex=
t point.</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"mar=
gin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1=
ex">It also assumes that somehow the computation of x itself is immune from=
 leaks (something you pointed out in a previous e-mail, I noticed).<br></bl=
ockquote><div><br></div><div>From my reading of the HMAC papers it seems yo=
u might be able to vary the BIP32 child index derivation to do this attack.=
 Just thinking about it now, these attacks seem far fetched just because in=
 order for it to be useful you need to have physical access to the device a=
nd to be able to accurately measure power consumption in high resolution (w=
hich I guess you can&#39;t do from a typical USB bus from corrupted softwar=
e). Then you also need to get the user to do lots of signing or derivation =
with their device. I guess a malicious cable with some way of exfiltrating =
power consumption could do it.</div><div>=C2=A0</div><blockquote class=3D"g=
mail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204=
,204,204);padding-left:1ex">
I&#39;m happy for any input you may have here. In particular, the recent di=
scussions around the interactions between anti-covert channel protection, r=
andomness, and the ability to spot check hardware devices may mean we shoul=
d revise the advice to consider not adding randomness unless such a anti-co=
vert channel scheme is used.<br></blockquote><div>=C2=A0</div><div>My only =
comment here is that there will end up being more than one way to do it and=
 I think what you and your collaborators have put forward is at a local opt=
imum of design (now that I understand it). Thanks and well done! It won&#39=
;t be the right optimum for everyone. To me, it seems like a good place to =
start. If you develop a decent nonce exfiltration protected signing protoco=
l later then I don&#39;t see why HW wallets wouldn&#39;t compete for favour=
 amongst the community by implementing and updating their devices to confor=
m to it.</div><div><br></div><div>LL</div><div>=C2=A0</div></div></div>

--000000000000cec3a205a1af3c30--