Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id D642BC0177 for ; Tue, 24 Mar 2020 18:56:47 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id CB95D87C8A for ; Tue, 24 Mar 2020 18:56:47 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id iQA4QEjhTDny for ; Tue, 24 Mar 2020 18:56:46 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40134.protonmail.ch (mail-40134.protonmail.ch [185.70.40.134]) by whitealder.osuosl.org (Postfix) with ESMTPS id 4B5F687C89 for ; Tue, 24 Mar 2020 18:56:46 +0000 (UTC) Date: Tue, 24 Mar 2020 18:56:38 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wuille.net; s=protonmail; t=1585076203; bh=5yM1hPmXUmC3iNJfKo1qaO0/M8xoK4sCNdX0JUDEJpA=; h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From; b=Hpoyf7D/VTY7JQ5itMbxkzcZbm91OtHtw93G5RExkUYROTOxACrVK8y/T/vDp/gWD k4DEFF4ogBgIAm0xYhM19l4ZMPC70q9XjHimZ/1wz0OBIJ0syN31EyK/S0PvqhmIrc X6c52+ELJ2Crr2V/7wptkaE/xZNnCLkYeJsrX+w0= To: Lloyd Fournier , Bitcoin Protocol Discussion From: Pieter Wuille Reply-To: Pieter Wuille Message-ID: <143g8W700TxSwkQM6rPf7NfRYcaVJoBqYLfR99gwtb-kBfL76EK556d4U8aNyEVRz5bp1eFzApLwPMSnhwAnK5m_htjqVREn5yZxXRCORiU=@wuille.net> In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Mailman-Approved-At: Tue, 24 Mar 2020 19:36:25 +0000 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 24 Mar 2020 18:56:48 -0000 On Tuesday, March 24, 2020 6:00 AM, Lloyd Fournier via bitcoin-dev 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