📅 Original date posted:2020-02-26
📝 Original message:> 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 at 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 at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
Jonas Nick [ARCHIVE] /
npub1at…y3z5a
2023-06-07 18:23:03
in reply to nevent1q…yztl
Author Public Key
npub1at3pav59gkeqz9kegzqhk2v4j4r435x42ytf23pxs8crt74tuc8s2y3z5aPublished at
2023-06-07 18:23:03Event JSON
{
"id": "b3963b543434911a78eb97d7838c652752c945ffeab0194061d760e217fef7b6",
"pubkey": "eae21eb28545b20116d940817b2995954758d0d5511695442681f035faabe60f",
"created_at": 1686162183,
"kind": 1,
"tags": [
[
"e",
"ca9d02e04a0fc4710cddfdca4280d25e1c27d194ff42697786555f4f775c824e",
"",
"root"
],
[
"e",
"f23845e4bea4e46298829b4433f05701db27b2d0068e8cfefe71291d537139f1",
"",
"reply"
],
[
"p",
"b5ff7c704f90e4eebfa414c0a017a84544c32586a1bd2fc86c74c2914d03c25e"
]
],
"content": "📅 Original date posted:2020-02-26\n📝 Original message:\u003e Let me put change (1) into my own words.\n\nCorrect, except that the speedup from is_even(y) over is_quadratic_residue(y)\naffects signing and not keypair generation.\n\n\u003e With change (2), I feel like including this auxiliary random data is overkill\n\u003e for the spec. [...] I feel similarly about hashing the public key to get the\n\u003e nonce.\n\nIt's not clear why removing these features from the spec would be an improvement.\nThe BIP follows a more reasonable approach: it specifies a reasonably secure\nsigning algorithm and provides the rationale behind the design choices. This\nallows anyone to optimize for their use case if they choose to do so.\nImportantly, \"reasonably secure\" includes misuse resistance which would be\nviolated if the pubkey was not input to the nonce generation function.\n\n\u003e Perhaps they even deserve their own BIP?\n\nYes, a standard for nonce exfiltration protection and MuSig would be important\nfor compatibility across wallets.\n\n\nOn 2/26/20 4:20 AM, Lloyd Fournier via bitcoin-dev wrote:\n\u003e Hi Pieter,\n\u003e \n\u003e Let me put change (1) into my own words. We are already computing affine\n\u003e coordinates since we store public keys as the affine x-coordinate. It is\n\u003e faster to compute is_even(y) than is_quadratic_residue(y) so we get a speed\n\u003e up here during keypair generation. In the verification algorithm, we do the\n\u003e following for the public key x_only =\u003e affine + negate if not is_even(y)\n\u003e =\u003e jacobian. The minor slowdown in verification comes from the extra\n\u003e evenness check and possible negation which we didn't have to be done in the\n\u003e previous version. This seems like a reasonable change if it makes things\n\u003e easier for existing code bases and infrastructure.\n\u003e \n\u003e With change (2), I feel like including this auxiliary random data is\n\u003e overkill for the spec. For me, the main point of the spec is the\n\u003e verification algorithm which actually affects consensus. Providing a note\n\u003e that non-deterministic signatures are preferable in many cases and here's\n\u003e exactly how you should do that (hash then xor with private key) is\n\u003e valuable. In the end, people will want several variations of the signing\n\u003e algorithm anyway (e.g. pass in public key with secret key) so I think\n\u003e specifying the most minimal way to produce a signature securely is the most\n\u003e useful thing for this document.\n\u003e \n\u003e I feel similarly about hashing the public key to get the nonce. A note in\n\u003e the alternative signing section that \"if you pass the public key into\n\u003e `sign` along with the secret key then you should do hash(bytes(d) ||\n\u003e bytes(P) || m)\" would suffice for me.\n\u003e \n\u003e Despite only being included in the alternative signing section, I it would\n\u003e be nice to have a few of test vectors for these alternative methods anyway.\n\u003e Perhaps they even deserve their own BIP?\n\u003e \n\u003e Cheers,\n\u003e \n\u003e LL\n\u003e \n\u003e \n\u003e On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e \n\u003e\u003e Hello list,\n\u003e\u003e\n\u003e\u003e Despite saying earlier that I expected no further semantical changes\n\u003e\u003e to BIP 340-342, I've just opened\n\u003e\u003e https://github.com/bitcoin/bips/pull/893 to make a number of small\n\u003e\u003e changes that I believe are still worth making.\n\u003e\u003e\n\u003e\u003e 1. Even public keys\n\u003e\u003e\n\u003e\u003e Only one change affects the validation rules: the Y coordinate of\n\u003e\u003e 32-byte public keys is changed from implicitly square to implicitly\n\u003e\u003e even. This makes signing slightly faster (in the microsecond range),\n\u003e\u003e though also verification negligibly slower (in the nanosecond range).\n\u003e\u003e It also simplifies integration with existing key generation\n\u003e\u003e infrastructure. For example BIP32 produces public keys with known\n\u003e\u003e even/oddness, but squaredness would need to be computed separately.\n\u003e\u003e Similar arguments hold for PSBT and probably many other things.\n\u003e\u003e\n\u003e\u003e Note that the Y coordinate of the internal R point in the signature\n\u003e\u003e remains implicitly square: for R the squaredness gives an actual\n\u003e\u003e performance gain at validation time, but this is not true for public\n\u003e\u003e keys. Conversely, for public keys integration with existing\n\u003e\u003e infrastructure matters, but R points are purely internal.\n\u003e\u003e\n\u003e\u003e This affects BIP 340 and 341.\n\u003e\u003e\n\u003e\u003e 2. Nonce generation\n\u003e\u003e\n\u003e\u003e All other semantical changes are around more secure nonce generation\n\u003e\u003e in BIP 340, dealing with various failure cases:\n\u003e\u003e\n\u003e\u003e * Since the public key signed for is included in the signature\n\u003e\u003e challenge hash, implementers will likely be eager to use precomputed\n\u003e\u003e values for these (otherwise an additional EC multiplication is\n\u003e\u003e necessary at signing time). If that public key data happens to be\n\u003e\u003e gathered from untrusted sources, it can lead to trivial leakage of the\n\u003e\u003e private key - something that Greg Maxwell started a discussion about\n\u003e\u003e on the moderncrypto curves list:\n\u003e\u003e https://moderncrypto.org/mail-archive/curves/2020/001012.html. We\n\u003e\u003e believe it should therefore be best practice to include the public key\n\u003e\u003e also in the nonce generation, which largely mitigates this problem.\n\u003e\u003e\n\u003e\u003e * To protect against fault injection attacks it is recommended to\n\u003e\u003e include actual signing-time randomness into the nonce generation\n\u003e\u003e process. This was mentioned already, but the update elaborates much\n\u003e\u003e more about this, and integrates this randomness into the standard\n\u003e\u003e signing process.\n\u003e\u003e\n\u003e\u003e * To protect against differential power analysis, a different way of\n\u003e\u003e mixing in this randomness is used (masking the private key completely\n\u003e\u003e with randomness before continuing, rather than hashing them together,\n\u003e\u003e which is known in the literature to be vulnerable to DPA in some\n\u003e\u003e scenarios).\n\u003e\u003e\n\u003e\u003e 3. New tagged hash tags\n\u003e\u003e\n\u003e\u003e To make sure that any code written for the earlier BIP text fails\n\u003e\u003e consistently, the tags used in the tagged hashes in BIP 340 are\n\u003e\u003e changed as well.\n\u003e\u003e\n\u003e\u003e What do people think?\n\u003e\u003e\n\u003e\u003e --\n\u003e\u003e Pieter\n\u003e\u003e _______________________________________________\n\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e\n\u003e \n\u003e \n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e",
"sig": "c40e34b76b9cd661a7e3dbd3cdaef5c95cd6eee5c89824a9643c0c6b34593f7a1c57e0a4e4d0d1f9f6ff8a7c46d58a24254c15d7f9147168a8487101cb863b99"
}