From: Jonas Nick <jonasdnick@gmail.com>
To: Lloyd Fournier <lloyd.fourn@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 Pieter Wuille <pieter.wuille@gmail.com>
References: <CAPg+sBgxvRM5ncQAnbNLN=4bdkQrM+-DxibMoTG+6gqk7EY9hQ@mail.gmail.com>
 <CAH5Bsr0ws2GT12+1rXTAXUkrpJXaeDqDgkfW_sdz7CqvwRCEkg@mail.gmail.com>
Autocrypt: addr=jonasd.nick@gmail.com; prefer-encrypt=mutual; keydata=
 mQINBFQ2o3oBEACv5N5WajlYk+i/4B8FmniipCB4biIKg38spMNt1EYM6RzTu+hbOrVOlJW8
 fq/ih+dvlpreGxRPQlX4jr75kwoJCykd3geywTUl3KPLeJ/JRQJ8fVkine4Wr5qB5Jwo3+wt
 inDVooaaF32Y0HolNacXVzT1x9uwn83Bz/ifg+iGATn/e1Si3ga/ytY5wYDzFz6aUDRW8ulu
 DcG8ARMAgtzmi66EuyQyIWwSyoWFU8wJ98slU9LKuTu23r6HdxFuV+P2H1omJm+z8cd4QBMj
 I23uHst0Wx1MyTeVhZCnQAghyasA3oopwzqRf5wwECAui1oZhr59R4R1DHJjn0PeWZXBSnOo
 XPQ1ERjz4nQrODiIDEabD5DClPHZ1bte0tswm1aYBtD8/me9ck+SJdoH5r0DJrXCTtNl1XG1
 9TTUINQe0eaQUOTakZmVaneCeSrw/pKOknkzudOCNCbmngKa2oJQOynrdsBuoigIYY+NQdot
 fk1nJljrBzyTh4sFktbHyA24x/hCykMX6FnIQxDnsGR+S3I+vzADBLBBMQQtZsUA+xnvPu4l
 6You5SZMVhgprQy38bKybeIGxSZtmPNtBf8ouKhAUpbIfOaq6BoP4EtueXk/vyieFxXiIkbF
 N6b3pjhkG7wVG17HqCqeVeHz1ZAQJUPcqDQAPaelBf38RXPbeQARAQABtCJKb25hcyBOaWNr
 IDxqb25hc2Qubmlja0BnbWFpbC5jb20+iQI/BBMBAgApAhsDBwsJCAcDAgEGFQgCCQoLBBYC
 AwECHgECF4AFAlu1I0QFCQtA5soACgkQsacOT43NA2Y5zA/9G1kt1ECa6zPhpEBV5iqD1omt
 ABdrZSxD8gBsZOMt2nLE1f4J0Oqy9LfMzKFzC8Kyd7usu6HVA8XM3fjVgqi+cDlEhaE+RqFi
 FVJjai7Fo1EqQGoD8QKTHDpGMNAmkfiQI7yc7OOxJ7X/nRpI8EnUsHG0slw3ieG6krrwLMfi
 rdJz5xA3P0tjdz/gRsG1IkwaB1bWnrIyh4oS9MiTSO1GZzHdRrhYZPFnJa7XiQsDWTvtTf4o
 fkbDAxqsKSqJhh99Gl79dXjJ1X9c6YfmxdOWuHZwtpJRgTFXSavaojkjPdnx4/f8lsgQg0tI
 BEaZnfroAvJCkYCqxNAPS5pSCaRaZbm+eoBl9848eFQztds/xfG3xIpn6VaOSdDNCD0+kSiO
 LrqghKLN3nPWOfCU0zPlkFuNsWX0ALvAJj6UKGbvMRfR6uj5NPZuHbA2FK9/1pOfKLjm6bHI
 2HtXeS5B0+eoAjHzoF9w/2DM4+DLU8Qbn63CpDZ3dodqK3Z7PHLv9oiiCVUFxia0J9YUZJru
 1jFHc3BA/Ado4LSxjyUbG0kDQjddvBEmQIkW5c2VrkczYv8gCOLwiUF+RPqc8PxGRs5I5SqJ
 RzcEN9nIaFcP5MTPrabbkXKLw6ZhHqc3J85qMOLoxThP5SCWM7I1SwLYIGgcWGFtL27U9IXe
 /wzNH4aerKe5Ag0EWVExqgEQAL1iVOraDIRX7bI1bres6PsbkNwz56OqIRbfSACch82x4NAK
 Jd9Gdabhv7mjX9bUGBwH79YUjpxOo2nh8Sp48SYThe9lWOmU6wo2T1ZyzuhoQp8jRtcll59Q
 o2zbfQdWt8DdRhCNzma/qjhDaAOveKa13jtXasVVqR4UdK2ZG/nIRQhPDslYq+hutV/7kTrd
 sk12GETBOrUQDh5WLbG5AbKGK/CQ3kXZWvyhSVD2I20ze18qsMrL88shgx+Tf0S9H+snQNQi
 WsB8DVe/VQj7nfam+LTVoIWpYOgTW+Y7/bU+UylMyFNUlFBykAguSCZ1JTSCxM2W9Q6zOf8u
 v9N+ht5TpTPiXvbx4mTA9UWu4Mksa7deqwy59MViuqRgBQwcH6WYgT202PYbMQzpxQSPBO4v
 N7e/ScVpAlfTT52ygwURb89+A4LQzF0tKWsRC5ZON5FfVbLg1NMplECOr1gPpruUNlbNbLOY
 nVd6nu1j/vLKvYiQL/BzoHJ4X5EvRm7BhktgdCuE5ce7eaNUGZKd9kUHNqhznKV+PeYCI78E
 ARAYNORbD09V+40wBtv5+VYPv9XMBBVYqofMOFIPbt0pT4ssbhH8UMnQcZbrtzOPxE6405Hy
 pT3gA85CSSpZXm3ziFdKodNyaYtb+eHwIGUQaC3pl3AdP8IpgVQL8K8CYNNhABEBAAGJBHIE
 GAEIACYWIQQ2xxo3ydmIveglCNmxpw5Pjc0DZgIbAgUCXRpChwUJBapEXQJAwXQgBBkBCAAd
 FiEES7uEWm9aZaad+uwjSGHb8mISNgUFAllRMaoACgkQSGHb8mISNgUtRg//aeCXBTyQ4mp/
 3szzL9qmK9zDwPtfUpEro98R/ekBTCYnnxEEv2g2Y8OTLcPc1iL2JWY4kfObBUZW6M78+qcz
 EF/GNTBkOVgczTWroN7U8j4IcXpcuqjwMtlL76EzGmI1DAa6UcOr/lAtOsOZrcxN19kGtBbo
 njU6PeZrzTqMujxCSoR5tt4gdMk204d6+5BmJXcB6usr85L4DDAXGmrUXRycmXMgZT1+8yzm
 hIEcpEB6yctoqRQgwF0nGCquJrxumtpMg1PnRvh9bJa1v+KmKfCNJptXPJh5zmp4tVzB6W0S
 dkKxEloiy7K/UDOVeOtdhI2FcoujC/gRjbTU0UTSW0MPuM4I+Z+lfPCZzwlYWLAgybfIL9FK
 d5hVF1Xcz7Hommqdx0vN3TYnoAIbxDV+gqkzVVHRPLk6BAK7Nwl64BiTx9wZYAKwf4jXl632
 JDxFH8yrNfnnTwYOmaHgsxGWx6WePVuvQDvWGisVqMy3uvNm8+4/8hMqI1FjTtBLfM4RkMTE
 bIzJnqg/iPduzIKf9PIxR8wnYr1j8WJxq6dGuMzRI332UmWFORkgbs+SZnZ2Zwex0aaeQhZP
 1/ZvwnjUvdVtxm96hAUZWeN13W6plEF14m7TYzkCfheWEAEtnSKhyLx+zgleXjlFnMnCMPBj
 PvbU/xJxYukdg2Dtcv0CoBoJELGnDk+NzQNm4F0QAKK/tTaWwfnI5mvdAd1vIbeR2LCzNau7
 Q1+oDW+GHInAlq7jhdDe/gQYrRnuyIvdV/4xQMPs5XN/HNdF0ejyo5rAPY/EihpiiKoOdkwa
 7lnzdt9TakBLhoSDThjKGTfMhwiXmTp2a107fisjmzhynwn/UU2amrZU0E22mSkR/VpqaLlw
 B3/vhwQKUUgm6oKAQWlLFqP63mJr/s/TfL0qdS8Oe8IMNXI8Qb7lTgpTd6QHkiUWVKLGZqPk
 BXXyWnTZNt/IvHgO73iox5cVEO31SRyyNmZ9mPoGacVUpuEfZK83USioHhv9lpEB/lDcbzaO
 FOHW8Bnd0dSpV3KDM+a2Axa1qp9DQ5l1wr7Zew0vH7Ua/NRECWIZ6Kmk+9ESfQ+N5zCGuUQh
 gmLq7Q307NA0127lh38ishw0bmopVugBxzxOjLS+DdwwcHVzUQswAuccHiukVuyWzh/dvH4W
 mf+z8dG0iyh9c474jHt3kcouuo9cUv+oD8bup7HUpKWGkaBSCqtjKqDEf1ldOQrJaoHOmikH
 jhTkneKwpx6GWlPMHf6fT+irDS4M5Hd2N+fR1G82FiubTOLZnC2IfpgSYf2MTwuxjYDNJ44N
 gh9qScMcKl9ZWrxvdMInNKwd4XvDhSDC2WdqzDLa+9a+Z5wQrBFHXH3XLf3SKrQ9TVJuKp1x
 63owuQINBFlRMd4BEADB+3Vb1kfonWBHtzlQ2P0lVfNMI3zntc0w0zkPqgfA+RYp/O790abf
 MtEcVt2OBW5Y6Iut+Y4SaN/zKEx72UnrOtS25z81I0XmJiKjGKayeR0hfiJLJFvROT9O/Bus
 CNoccI0V14OMvmfqGJNwvBgR9RI47Not5ZmCDwAjFCg22tumSLsZIyuTgd7WR5kzrmESfXj+
 SpbUg+D+mOmU4A5b1KUHiWtMOdgOHTkAEZsig4hiec/sfIEngityK2Fsre/Xrd+uEUlmRuKR
 Y9+H5xyHBz3m8DjF+oDGXTyMijcWk8AOtoJ0KeZaCaCSVE7IEk0jltQ87448Zv+IljNh5Uuj
 U9H/NH0sNRp3yMUkj68dheCMIPHJAFs8vxGHBq+/qRydvAFVTeKtBBv/Vr07C/YjPWam8PXC
 PX2g0w7iX2LXMSKKzIJJgxeLteBhXc0rMeZaEzvv+1RWYRQyywgtXhwszry4xxYPvV6UdDe3
 gK6Q4mAVjxVgVbYR7W+ibl6gFsmftC2WcNiRjOP4M1HRa/tRc5yV9TKrZcLawIIDOMaz5ZyH
 +KsC+gdO+La9NL86+GCM5dBVBrYvUMfsaM6njtjZipbV5nwWHwSWXZ32p1R6fFzA0vs+wlSg
 szJJp7sidEK2NIyVQMTr5cC0Mt+tzZOaUaa6x52tkdvmbE6n/AsN3QARAQABiQI8BBgBCAAm
 FiEENscaN8nZiL3oJQjZsacOT43NA2YCGwwFAl0aQqQFCQWqREYACgkQsacOT43NA2aG8RAA
 hrZkJS+kWwooSueh67hafKciCidlycZNixxtks8kwnYMCWF7z11EyRdqAGqIHr0zVuAnmVNO
 8wr+b/x/pgR0XpjzdfCJ3inNh3GLwwD+CRafkq8U3Xd+xvFQTBeFMsC+h8A45MNhBsL7IAWq
 7wkSb9dyqGKVhb4Wac0aYEbSGMu/P5BFkLw1li3E61ik7yh/x46s5FaddwbwF0P51S3fVQE+
 1Iu86LlrLTgkLkZxbK8cm1XxBirRxwIInf+RU/xQOl62V5L/ySiJHRGjSg89WXgpiLzjR1gf
 zFM8zEv4R1sE+nIw5GsaKxXUAxMyGZ6K1EFp31crZBnbZ0fhFqiyHphhH4zeF+nR/PZgsHtB
 Efd2obbJ15uG7oHUBg1xnx6CVzKoH6k6HLlkpiw6TP+KvvLCZ9sGrxfjeJm/PBXOVEC+HUH8
 Ha3u4A2Je0YWHs361qz3PBnzgzAva0fRJFv0GvOEgGMj7GTOgWn1crWiUSCoNchwiH5ajVBV
 7FcWq3e7Dgp1q56j6igE4rRBsPPA1/iCU9mB6vvI1ieMVKXfzBtiL/DYn6ytpBf+gO5nxDLf
 2bOtlx4htC2wGl90Pp/8/+mWBCWFvJMnBCld+G2b4Fv+g9Mr/7tlxBdomevSI7qXcOUJ4v0x
 Fp3434+dc5TFz4zcLJtqhMF1McajtWw02z8=
Message-ID: <ca64cabd-93ef-edf1-1e1f-7d7a48a51587@gmail.com>
Date: Wed, 26 Feb 2020 15:34:04 +0000
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.5.0
MIME-Version: 1.0
In-Reply-To: <CAH5Bsr0ws2GT12+1rXTAXUkrpJXaeDqDgkfW_sdz7CqvwRCEkg@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US-large
Content-Transfer-Encoding: 7bit
Subject: Re: [bitcoin-dev] BIP 340 updates: even pubkeys,
 more secure nonce generation
Precedence: list

> 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
>