Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 75E83C0177 for ; Thu, 27 Feb 2020 04:55:50 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 6C77F20467 for ; Thu, 27 Feb 2020 04:55:50 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id z08EvQ0+cOYI for ; Thu, 27 Feb 2020 04:55:48 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-il1-f177.google.com (mail-il1-f177.google.com [209.85.166.177]) by silver.osuosl.org (Postfix) with ESMTPS id 1C05020013 for ; Thu, 27 Feb 2020 04:55:48 +0000 (UTC) Received: by mail-il1-f177.google.com with SMTP id p8so1231816iln.12 for ; Wed, 26 Feb 2020 20:55:48 -0800 (PST) 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=Kad9gPxjAE2hY1qIUasyX++lvTOOosfAsTAPs03DVG4=; b=IALqAE5h4kvEI+ShmP+sgVETfrRdVjOuSslGPSm60H8njLjV2oUxvdLgJjLlXRPbT6 FWQPJMtI6yZKyj2Vwi2iYgS3l7Ytw2TiqMs75c5YSibygh9mC1/jKSzl6UJyYSKwhN2M lqxsZwL8B9CtLnUMaEX5fi3azhq++nmeL2nPjCnONUO0pAsdbDs2Mmw4rWRs/d9PLs28 gyLWVy8/Jq7R1DAo9//bpB8nCJEQ/qqtbzrSkMHGrzKyh1+BZ1OuluKg38VxbnYGR4bH AKWtoWcUNbHg7OYHUfZ1T2h+2rgf0822uMEcToI+P+G/OIKYbFAAqFgDL4/QwD4S9pCh ipKA== 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=Kad9gPxjAE2hY1qIUasyX++lvTOOosfAsTAPs03DVG4=; b=s7WoKgNQu1gmb5DuglSERqsd0gvxMeNVXYsyBDZaNQzvlmdI7Hy8YCiyHtDfNvLqDz /0EvpRs3YlU0M7TVReRwZ10hINr2rrde8wZKBuJIQ6sC9URT/UgF4TF4eKTyEU8WleKN mEZ0HGSAXnJ9O8GnorbEiui624AWepOKsFQ1QG5oTLUVSQdH+71coCDoHh6pghaMuvot RN4RwjMKrzZqBDQEB3V7yzSsDSm5RzsoqAzy0w1U9+8WuKQtdvw1z3uavJB0+S0eMHL+ hYyAHBZTs1yd+lkkxpsfHt2Ca7HsH0zk0eVwxNGy6aZvR+Db0xIZHRAzCeRaZFFLAc/0 zbVw== X-Gm-Message-State: APjAAAVXdG4M0c3/2UvnCSHWTjvQChSuoFW4MHkvTj40nN7yts39JVbd m+VXFUtlY3AtaBmh54FbAvgDUSmDdUaojNTqk0s= X-Google-Smtp-Source: APXvYqwZfWcsPIKDEN0POW9JWPyeCGMYO8XboBX+gBJu9WbZti4OJnwyVkOmRIsRMeTh8xAerl7cPccemJrFp7EjasI= X-Received: by 2002:a92:8f4b:: with SMTP id j72mr2814907ild.17.1582779347242; Wed, 26 Feb 2020 20:55:47 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Lloyd Fournier Date: Thu, 27 Feb 2020 15:55:21 +1100 Message-ID: To: Jonas Nick Content-Type: multipart/alternative; boundary="000000000000c014fe059f87881b" X-Mailman-Approved-At: Thu, 27 Feb 2020 05:59:25 +0000 Cc: Bitcoin Protocol Discussion , Pieter Wuille Subject: Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation 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: Thu, 27 Feb 2020 04:55:50 -0000 --000000000000c014fe059f87881b Content-Type: text/plain; charset="UTF-8" > Correct, except that the speedup from is_even(y) over is_quadratic_residue(y) affects signing and not keypair generation. Isn't this the same thing since in the spec it generates the public key in the signing algorithm? If you pre-generate public key and pass it in there would be no speedup to signing that I can see. > It's not clear why removing these features from the spec would be an improvement. It could just be me but "here's the most minimal signing algorithm, you can add things in these ways to make it more robust in some settings" is more intuitive than "here's the most robust signing algorithm, you can remove these things in these ways if they don't apply to your setting". I see your point that if it is likely to be misused then maybe the latter is preferable. LL On Thu, Feb 27, 2020 at 2:33 AM Jonas Nick wrote: > > Let me put change (1) into my own words. > > Correct, except that the speedup from is_even(y) over > is_quadratic_residue(y) > affects signing and not keypair generation. > > > With change (2), I feel like including this auxiliary random data is > overkill > > for the spec. [...] I feel similarly about hashing the public key to get > the > > nonce. > > It's not clear why removing these features from the spec would be an > improvement. > The BIP follows a more reasonable approach: it specifies a reasonably > secure > signing algorithm and provides the rationale behind the design choices. > This > allows anyone to optimize for their use case if they choose to do so. > Importantly, "reasonably secure" includes misuse resistance which would be > violated if the pubkey was not input to the nonce generation function. > > > Perhaps they even deserve their own BIP? > > Yes, a standard for nonce exfiltration protection and MuSig would be > important > for compatibility across wallets. > > > On 2/26/20 4:20 AM, Lloyd Fournier via bitcoin-dev wrote: > > Hi Pieter, > > > > Let me put change (1) into my own words. We are already computing affine > > coordinates since we store public keys as the affine x-coordinate. It is > > faster to compute is_even(y) than is_quadratic_residue(y) so we get a > speed > > up here during keypair generation. In the verification algorithm, we do > the > > following for the public key x_only => affine + negate if not is_even(y) > > => jacobian. The minor slowdown in verification comes from the extra > > evenness check and possible negation which we didn't have to be done in > the > > previous version. This seems like a reasonable change if it makes things > > easier for existing code bases and infrastructure. > > > > With change (2), I feel like including this auxiliary random data is > > overkill for the spec. For me, the main point of the spec is the > > verification algorithm which actually affects consensus. Providing a note > > that non-deterministic signatures are preferable in many cases and here's > > exactly how you should do that (hash then xor with private key) is > > valuable. In the end, people will want several variations of the signing > > algorithm anyway (e.g. pass in public key with secret key) so I think > > specifying the most minimal way to produce a signature securely is the > most > > useful thing for this document. > > > > I feel similarly about hashing the public key to get the nonce. A note in > > the alternative signing section that "if you pass the public key into > > `sign` along with the secret key then you should do hash(bytes(d) || > > bytes(P) || m)" would suffice for me. > > > > Despite only being included in the alternative signing section, I it > would > > be nice to have a few of test vectors for these alternative methods > anyway. > > Perhaps they even deserve their own BIP? > > > > Cheers, > > > > LL > > > > > > On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev < > > bitcoin-dev@lists.linuxfoundation.org> wrote: > > > >> Hello list, > >> > >> Despite saying earlier that I expected no further semantical changes > >> to BIP 340-342, I've just opened > >> https://github.com/bitcoin/bips/pull/893 to make a number of small > >> changes that I believe are still worth making. > >> > >> 1. Even public keys > >> > >> Only one change affects the validation rules: the Y coordinate of > >> 32-byte public keys is changed from implicitly square to implicitly > >> even. This makes signing slightly faster (in the microsecond range), > >> though also verification negligibly slower (in the nanosecond range). > >> It also simplifies integration with existing key generation > >> infrastructure. For example BIP32 produces public keys with known > >> even/oddness, but squaredness would need to be computed separately. > >> Similar arguments hold for PSBT and probably many other things. > >> > >> Note that the Y coordinate of the internal R point in the signature > >> remains implicitly square: for R the squaredness gives an actual > >> performance gain at validation time, but this is not true for public > >> keys. Conversely, for public keys integration with existing > >> infrastructure matters, but R points are purely internal. > >> > >> This affects BIP 340 and 341. > >> > >> 2. Nonce generation > >> > >> All other semantical changes are around more secure nonce generation > >> in BIP 340, dealing with various failure cases: > >> > >> * Since the public key signed for is included in the signature > >> challenge hash, implementers will likely be eager to use precomputed > >> values for these (otherwise an additional EC multiplication is > >> necessary at signing time). If that public key data happens to be > >> gathered from untrusted sources, it can lead to trivial leakage of the > >> private key - something that Greg Maxwell started a discussion about > >> on the moderncrypto curves list: > >> https://moderncrypto.org/mail-archive/curves/2020/001012.html. We > >> believe it should therefore be best practice to include the public key > >> also in the nonce generation, which largely mitigates this problem. > >> > >> * To protect against fault injection attacks it is recommended to > >> include actual signing-time randomness into the nonce generation > >> process. This was mentioned already, but the update elaborates much > >> more about this, and integrates this randomness into the standard > >> signing process. > >> > >> * To protect against differential power analysis, a different way of > >> mixing in this randomness is used (masking the private key completely > >> with randomness before continuing, rather than hashing them together, > >> which is known in the literature to be vulnerable to DPA in some > >> scenarios). > >> > >> 3. New tagged hash tags > >> > >> To make sure that any code written for the earlier BIP text fails > >> consistently, the tags used in the tagged hashes in BIP 340 are > >> changed as well. > >> > >> What do people think? > >> > >> -- > >> Pieter > >> _______________________________________________ > >> bitcoin-dev mailing list > >> bitcoin-dev@lists.linuxfoundation.org > >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > >> > > > > > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists.linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > --000000000000c014fe059f87881b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
> Correct, except that the speedup fro= m is_even(y) over is_quadratic_residue(y) affects signing and not keypair g= eneration.

Isn't this = the same thing since in the spec it generates the public key in the signing= algorithm? If you pre-generate public key and pass it in there would be no= speedup to signing that I can see.

> It= 9;s not clear why removing these features from the spec would be an improve= ment.

It could just be me but "here's the= most minimal signing algorithm, you can add things in these ways to make i= t more robust=C2=A0 in some settings" is more intuitive than "her= e's the most robust signing algorithm, you can remove these things in t= hese ways if they don't apply to your setting". I see your point t= hat if it is likely to be misused then maybe the latter is preferable.
<= /div>

LL

On Thu, Feb 27, 2020 at 2:33 AM Jonas Nick <<= a href=3D"mailto:jonasdnick@gmail.com">jonasdnick@gmail.com> wrote:<= br>
> Let me put = change (1) into my own words.

Correct, except that the speedup from is_even(y) over is_quadratic_residue(= y)
affects signing and not keypair generation.

> With change (2), I feel like including this auxiliary random data is o= verkill
> for the spec. [...] I feel similarly about hashing the public key to g= et the
> nonce.

It's not clear why removing these features from the spec would be an im= provement.
The BIP follows a more reasonable approach: it specifies a reasonably secur= e
signing algorithm and provides the rationale behind the design choices. Thi= s
allows anyone to optimize for their use case if they choose to do so.
Importantly, "reasonably secure" includes misuse resistance which= would be
violated if the pubkey was not input to the nonce generation function.

> Perhaps they even deserve their own BIP?

Yes, a standard for nonce exfiltration protection and MuSig would be import= ant
for compatibility across wallets.


On 2/26/20 4:20 AM, Lloyd Fournier via bitcoin-dev wrote:
> Hi Pieter,
>
> Let me put change (1) into my own words. We are already computing affi= ne
> coordinates since we store public keys as the affine x-coordinate. It = is
> faster to compute is_even(y) than is_quadratic_residue(y) so we get a = speed
> up here during keypair generation. In the verification algorithm, we d= o the
> following for the public key=C2=A0 x_only =3D> affine + negate if n= ot is_even(y)
> =3D> jacobian. The minor slowdown in verification comes from the ex= tra
> evenness check and possible negation which we didn't have to be do= ne in the
> previous version. This seems like a reasonable change if it makes thin= gs
> easier for existing code bases and infrastructure.
>
> With change (2), I feel like including this auxiliary random data is > overkill for the spec. For me, the main point of the spec is the
> verification algorithm which actually affects consensus. Providing a n= ote
> that non-deterministic signatures are preferable in many cases and her= e's
> exactly how you should do that (hash then xor with private key) is
> valuable. In the end, people will want several variations of the signi= ng
> algorithm anyway (e.g. pass in public key with secret key) so I think<= br> > specifying the most minimal way to produce a signature securely is the= most
> useful thing for this document.
>
> I feel similarly about hashing the public key to get the nonce. A note= in
> the alternative signing section that "if you pass the public key = into
> `sign` along with the secret key then you should do hash(bytes(d) || > bytes(P) || m)" would suffice for me.
>
> Despite only being included in the alternative signing section, I it w= ould
> be nice to have a few of test vectors for these alternative methods an= yway.
> Perhaps they even deserve their own BIP?
>
> Cheers,
>
> LL
>
>
> On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hello list,
>>
>> Despite saying earlier that I expected no further semantical chang= es
>> to BIP 340-342, I've just opened
>> https://github.com/bitcoin/bips/pull/893 to mak= e a number of small
>> changes that I believe are still worth making.
>>
>> 1. Even public keys
>>
>> Only one change affects the validation rules: the Y coordinate of<= br> >> 32-byte public keys is changed from implicitly square to implicitl= y
>> even. This makes signing slightly faster (in the microsecond range= ),
>> though also verification negligibly slower (in the nanosecond rang= e).
>> It also simplifies integration with existing key generation
>> infrastructure. For example BIP32 produces public keys with known<= br> >> even/oddness, but squaredness would need to be computed separately= .
>> Similar arguments hold for PSBT and probably many other things. >>
>> Note that the Y coordinate of the internal R point in the signatur= e
>> remains implicitly square: for R the squaredness gives an actual >> performance gain at validation time, but this is not true for publ= ic
>> keys. Conversely, for public keys integration with existing
>> infrastructure matters, but R points are purely internal.
>>
>> This affects BIP 340 and 341.
>>
>> 2. Nonce generation
>>
>> All other semantical changes are around more secure nonce generati= on
>> in BIP 340, dealing with various failure cases:
>>
>> * Since the public key signed for is included in the signature
>> challenge hash, implementers will likely be eager to use precomput= ed
>> values for these (otherwise an additional EC multiplication is
>> necessary at signing time). If that public key data happens to be<= br> >> gathered from untrusted sources, it can lead to trivial leakage of= the
>> private key - something that Greg Maxwell started a discussion abo= ut
>> on the moderncrypto curves list:
>> https://moderncrypto.org/mail-= archive/curves/2020/001012.html. We
>> believe it should therefore be best practice to include the public= key
>> also in the nonce generation, which largely mitigates this problem= .
>>
>> * To protect against fault injection attacks it is recommended to<= br> >> include actual signing-time randomness into the nonce generation >> process. This was mentioned already, but the update elaborates muc= h
>> more about this, and integrates this randomness into the standard<= br> >> signing process.
>>
>> * To protect against differential power analysis, a different way = of
>> mixing in this randomness is used (masking the private key complet= ely
>> with randomness before continuing, rather than hashing them togeth= er,
>> which is known in the literature to be vulnerable to DPA in some >> scenarios).
>>
>> 3. New tagged hash tags
>>
>> To make sure that any code written for the earlier BIP text fails<= br> >> consistently, the tags used in the tagged hashes in BIP 340 are >> changed as well.
>>
>> What do people think?
>>
>> --
>> Pieter
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation= .org/mailman/listinfo/bitcoin-dev
>>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev
>
--000000000000c014fe059f87881b--