From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 5E419C0177 for ; Wed, 26 Feb 2020 15:33:07 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 52E2F87726 for ; Wed, 26 Feb 2020 15:33:07 +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 ZgKkXweFycye for ; Wed, 26 Feb 2020 15:33:02 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com [209.85.221.41]) by whitealder.osuosl.org (Postfix) with ESMTPS id BE319876C0 for ; Wed, 26 Feb 2020 15:33:01 +0000 (UTC) Received: by mail-wr1-f41.google.com with SMTP id l5so3592444wrx.4 for ; Wed, 26 Feb 2020 07:33:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:subject:to:references:autocrypt:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=54QFaOHWLN+GU+5eFpuRqvqCsepDdKixL7Epay6O0sQ=; b=p0gglzkoJED20bEcbRGIN1MfHkaAHhtrtZDh96dkpTwew3om7HEZXgeeb56sTkKupO vryM1ZPodnYwp6QYBWBLwyIJ2MV8Jwdca8c6s5gpgGcXffo8H7t5Ykyx87PdYuRWVtAp F3tYUsRpOrdAcjuaXiwYRiUIGaVrROh2aH+dwPx8HNuz5nGW3ifkMJZOnSEn3PlNSXtn 19S8xJr0za19lb6TCkBXWha7xFZbEd/KyJ5eEDTvk7U4ZfZuI4+8Ej0nYghpXSc1SWUu e3rp+t+DR8ugWRNZshlOEoCSjp9GTzUKgLJY3tjjE6skYA/kbTeUPaqJGFpevOSjOWIm ohdA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:subject:to:references:autocrypt:message-id :date:user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=54QFaOHWLN+GU+5eFpuRqvqCsepDdKixL7Epay6O0sQ=; b=cxQ4TUqX6yP+dYCX+Ml2Mssc5VkCXdVirCt6VHCDRnheranSqahesq4C3yKQ/UISlh 4olp+S4c3ExJOOJmELJRzkvta5c1HzQcnWSpvL2jTO52frNm3s5gv3JeAts6+RXct7+c aHJCY6ekK02CMaGwh9+OQLnwgp0iodmEDyNpBcPNj9i3/T/1x3gWVXynZaY5yDnVz5zG jRZ5Y0UEOwMryT96WR8Wua4btshfnTVY4ihB7/YWGDgdaxAgwNcH8jSJ/uLbTY/gEtAP SbJpA5dOizrsBRo5rqS24wh/sHNts6fuoXM/oZ6EO6tHoHlxsiMPTGHfHRatbgMZCN0c SFRw== X-Gm-Message-State: APjAAAWMxLGq/JQ1AhgKikvnM0o/xxlgcqPZDiw5bTfmGpUG/u4b5pMD D+EEU6VEuB7/JDMO/uAyhYA= X-Google-Smtp-Source: APXvYqyWVjL3lbXYzMHe5LkmRITdrSrQb31YlpMmeZNNNXbXOSL1SrCz3jyqZeib3arqVRs24cZ5yg== X-Received: by 2002:a5d:538e:: with SMTP id d14mr6364047wrv.358.1582731180045; Wed, 26 Feb 2020 07:33:00 -0800 (PST) Received: from ?IPv6:2001:16b8:2026:8500:dde7:5c0f:6923:9743? (200116b820268500dde75c0f69239743.dip.versatel-1u1.de. [2001:16b8:2026:8500:dde7:5c0f:6923:9743]) by smtp.googlemail.com with ESMTPSA id g25sm9763878wmh.3.2020.02.26.07.32.58 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 26 Feb 2020 07:32:58 -0800 (PST) From: Jonas Nick X-Google-Original-From: Jonas Nick To: Lloyd Fournier , Bitcoin Protocol Discussion , Pieter Wuille References: 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: 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: Content-Type: text/plain; charset=utf-8 Content-Language: en-US-large Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Wed, 26 Feb 2020 15:44:50 +0000 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: Wed, 26 Feb 2020 15:33:07 -0000 > 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 >