Date: Tue, 24 Mar 2020 18:56:38 +0000
To: Lloyd Fournier <lloyd.fourn@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: Pieter Wuille <bitcoin-dev@wuille.net>
Reply-To: Pieter Wuille <bitcoin-dev@wuille.net>
Message-ID: <143g8W700TxSwkQM6rPf7NfRYcaVJoBqYLfR99gwtb-kBfL76EK556d4U8aNyEVRz5bp1eFzApLwPMSnhwAnK5m_htjqVREn5yZxXRCORiU=@wuille.net>
In-Reply-To: <CAH5Bsr3EtFpecXPG07so1KA0sre9Cy-XPv=BADBgUe4M7kuxFg@mail.gmail.com>
References: <CAH5Bsr3EtFpecXPG07so1KA0sre9Cy-XPv=BADBgUe4M7kuxFg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Mitigating Differential Power Analysis in BIP-340
Precedence: list

On Tuesday, March 24, 2020 6:00 AM, Lloyd Fournier via bitcoin-dev <bitcoin=
-dev@lists.linuxfoundation.org> wrote:

> Hi List,
>
> I felt this topic deserved it's own thread but it follows on from the mai=
ling list post [2] announcing a new PR [1] to change BIP-340 in several way=
s, including adding random auxiliary=C2=A0data into the nonce derivation=
=C2=A0function. Rather than hashing the randomness with the secret key and =
message etc, the randomness is hashed then XOR'd (^) with the secret key an=
d the result is hashed like so to determine the secret nonce k:
>
> (1) k =3D H_derive( sec_key ^ H_aux(rand) || pub_key_x || message)
>
> The claim made in the mailing list post is that this is more secure again=
st "differential power analysis" (DPA) attacks than just doing the simpler =
and more efficient:
>
> (2) k =3D H_derive(sec_key || rand || pub_key_x || message)
>
> The TL;DR here is that I don't think this is the case.

Hi Lloyd,

Thank you for looking into this. I very much agree we haven't given nearly =
enough justification for the use of a non-standard scheme here.

I'll try to summarize the discussion we had that led to this choice, but mo=
st of it is on https://github.com/sipa/bips/issues/195 if you want the deta=
ils.

Let me first try to address what I think you're overlooking: in a BIP32/Tap=
root like scenario, the private key that goes into the signing algorithm fu=
nctions as *both* secret and known to the attacker. That is to say, there i=
s 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 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 al=
ready 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 tha=
t does not expose bit-level information) into the private key before giving=
 it to a hash function seems like it would address this.

That said, all these DPA issues are very hard to reason about, as it's hard=
 to find a realistic attack model that both (a) leaks some information but =
(b) doesn't obviously leak the entire key immediately. In the reasoning abo=
ve I assumed an attacker who can observe word-level Hamming weight aggregat=
es of all variables in the algorithm (which seems to match what one of the =
papers observed), but not bit level information. It also assumes that someh=
ow the computation of x itself is immune from leaks (something you pointed =
out in a previous e-mail, I noticed).

So really, all of this is trying to choose one alternative among a set of (=
when ignoring DPA) nearly equally good constructions. Note that randomness =
is useful for protection against fault attacks, but for that purpose it doe=
sn't matter where in the hash it goes, or even that it's particularly stron=
g randomness (a counter would also work). There are a number of other conce=
rns we discussed in the linked thread:
* Efficiency (how many SHA256 transformations, including the ability for so=
me to be precomputed)
* The risk that the randomness added is correlated with the private key in =
a way that cancels things out when they're naively XORed together.
* The risk of having a midstate in the hash function leak (without leaking =
the actual private key, but enough to predict nonces).
* The issue with public keys that are input to the signing algorithm which =
come directly from an attacker (which is the reason why pubkey goes into th=
e nonce function too).

The solution we came up with (H(priv XOR H(aux) || pub || msg)) is the only=
 that ticks most of the boxes - but a different prioritization may certainl=
y lead to a different conclusion.

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

Cheers,

--
Pieter