[Cryptography] Schnorr multisignatures based on ED22519 Crypto
I have heard it said that ED25519 supports Schnorr multisignatures, The Libsodium documentation contains no mention of multi signatures, and, because ED25519 is nonprime group, it seems to me that implementing Schnorr multisignatures would require an expert in the mathematics of elliptic curves - I certainly have no idea how to even begin, and would not trust code written by someone not well known. Libsodium supports the prime group Ristretto255, though only in the development version, not yet the stable version, with which a person of ordinary skills could implement Schnorr multisignatures but it is not apparent that this would play nice with LibSodium's built in high level encryption and signing code. So, should I forget about Schnorr multisignatures, and just do what everyone else does: Tuples? Or does Libsodium support multisignatures somewhere in the documentation, and I have been looking in the wrong place? _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Hello, On 05. 05. 19 4:22, jamesd@echeque.com wrote: > I have heard it said that ED25519 supports Schnorr multisignatures, > > The Libsodium documentation contains no mention of multi signatures, > and, because ED25519 is nonprime group, it seems to me that implementing > Schnorr multisignatures would require an expert in the mathematics of > elliptic curves - I certainly have no idea how to even begin, and would > not trust code written by someone not well known. the cofactor for Ed25519 is l=8. The problem of "hitting" small subgroup is easily mitigated if you clear the 3 least-significant bits of your keys. As long as you are working with points on the curve which are eight times multiply of the generator point (i.e. 8G, 16G, 24G ...) you are safe. Regarding the multisignatures - I vaguely recall there was a blockchain-based so-called "cryptocurrency" implementation that got this wrong and it was easy for attackers to empty many users' "wallets", because there were only 7 (or maybe 8, doesn't matter though) brute-force steps required to recover the private keys. Cheers, Dominik _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On Sun, May 5, 2019 at 4:52 AM <jamesd@echeque.com> wrote: > > I have heard it said that ED25519 supports Schnorr multisignatures, > > The Libsodium documentation contains no mention of multi signatures, > and, because ED25519 is nonprime group, it seems to me that implementing > Schnorr multisignatures would require an expert in the mathematics of > elliptic curves - I certainly have no idea how to even begin, and would > not trust code written by someone not well known. > > Libsodium supports the prime group Ristretto255, though only in the > development version, not yet the stable version, with which a person of > ordinary skills could implement Schnorr multisignatures but it is not > apparent that this would play nice with LibSodium's built in high level > encryption and signing code. > > So, should I forget about Schnorr multisignatures, and just do what > everyone else does: Tuples? > > Or does Libsodium support multisignatures somewhere in the > documentation, and I have been looking in the wrong place? > _______________________________________________ > The cryptography mailing list > cryptography@metzdowd.com > http://www.metzdowd.com/mailman/listinfo/cryptography Jeff Burdges implemented Schnorr signatures over the Ristretto group in Rust in the "schnorrkel" library. It includes multisignatures -- the documentation link here provides links to papers as well. https://docs.rs/schnorrkel/0.1.1/schnorrkel/musig/index.html _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On Sun, May 5, 2019 at 9:07 PM Dominik Pantůček < dominik.pantucek@trustica.cz> wrote: > Hello, > > On 05. 05. 19 4:22, jamesd@echeque.com wrote: > > I have heard it said that ED25519 supports Schnorr multisignatures, > > > > The Libsodium documentation contains no mention of multi signatures, > > and, because ED25519 is nonprime group, it seems to me that implementing > > Schnorr multisignatures would require an expert in the mathematics of > > elliptic curves - I certainly have no idea how to even begin, and would > > not trust code written by someone not well known. > > the cofactor for Ed25519 is l=8. The problem of "hitting" small subgroup > is easily mitigated if you clear the 3 least-significant bits of your > keys. As long as you are working with points on the curve which are > eight times multiply of the generator point (i.e. 8G, 16G, 24G ...) you > are safe. > > Regarding the multisignatures - I vaguely recall there was a > blockchain-based so-called "cryptocurrency" implementation that got this > wrong and it was easy for attackers to empty many users' "wallets", > because there were only 7 (or maybe 8, doesn't matter though) > brute-force steps required to recover the private keys. > I think the Schnorr signatures are really useful and important. But I would need to see a CFRG RFC and peer review before making use of them in a spec. I do use the same types of technique for encryption but that doesn't worry me because DH key agreement doesn't disclose the private key even if you do it wrong. El Gamal signatures do. It is not just disclosing the private key that is bad. There are pairs of numbers that can be disclosed that allow an attacker to create new sigs even if they don't know the private key. There is a vast amount of detail there that I just don't have swap space for in my brain right now. So lets pass it on to the people who think about nothing else and get some grad students on the problem _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
> On Sun, May 5, 2019 at 9:07 PM Dominik Pantůček > > the cofactor for Ed25519 is l=8. The problem of "hitting" small subgroup > > is easily mitigated if you clear the 3 least-significant bits of your > > keys. As long as you are working with points on the curve which are > > eight times multiply of the generator point (i.e. 8G, 16G, 24G ...) you > > are safe. On 06/05/2019 22:16, Phillip Hallam-Baker wrote: > I think the Schnorr signatures are really useful and important. But I > would need to see a CFRG RFC and peer review before making use of them > in a spec. My ignorant opinion is that you would be fine using a well known algorithm, such as Schnorr signatures, in a prime group such as ristretto255, but in a non prime group such as Ed25519, likely to shoot yourself in the foot, and if you roll your own algorithm, likely to shoot yourself in the foot even with a prime group. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Sunday, May 5, 2019 8:07 AM, Dominik Pantůček <dominik.pantucek@trustica.cz> wrote: > Hello, > > On 05. 05. 19 4:22, jamesd@echeque.com wrote: > > > I have heard it said that ED25519 supports Schnorr multisignatures, > > The Libsodium documentation contains no mention of multi signatures, > > and, because ED25519 is nonprime group, it seems to me that implementing > > Schnorr multisignatures would require an expert in the mathematics of > > elliptic curves - I certainly have no idea how to even begin, and would > > not trust code written by someone not well known. > > the cofactor for Ed25519 is l=8. The problem of "hitting" small subgroup > is easily mitigated if you clear the 3 least-significant bits of your > keys. As long as you are working with points on the curve which are > eight times multiply of the generator point (i.e. 8G, 16G, 24G ...) you > are safe. > This isn't sufficient in cases where the attacker is providing a point on the curve instead of a scalar. > Regarding the multisignatures - I vaguely recall there was a > blockchain-based so-called "cryptocurrency" implementation that got this > wrong and it was easy for attackers to empty many users' "wallets", > because there were only 7 (or maybe 8, doesn't matter though) > brute-force steps required to recover the private keys. > > Cheers, > Dominik > Lee _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Tuesday, May 7, 2019 7:06 AM, <jamesd@echeque.com> wrote: > > On Sun, May 5, 2019 at 9:07 PM Dominik Pantůček > > > > the cofactor for Ed25519 is l=8. The problem of "hitting" small subgroup > > > is easily mitigated if you clear the 3 least-significant bits of your > > > keys. As long as you are working with points on the curve which are > > > eight times multiply of the generator point (i.e. 8G, 16G, 24G ...) you > > > are safe. > > > > > On 06/05/2019 22:16, Phillip Hallam-Baker wrote: > > > I think the Schnorr signatures are really useful and important. But I > > would need to see a CFRG RFC and peer review before making use of them > > in a spec. > > My ignorant opinion is that you would be fine using a well known > algorithm, such as Schnorr signatures, in a prime group such as > ristretto255, but in a non prime group such as Ed25519, likely to shoot > yourself in the foot, and if you roll your own algorithm, likely to > shoot yourself in the foot even with a prime group. > An excerpt taken directly from the Ed25519 paper[1]: Our verification equation is the same as Schnorr’s verification equation with double-size hashing instead of half-size hashing, with A inserted as an extra hash input, and without Schnorr’s compression of R. The EdDSA equations used for the Ed25519 curve are similar to the equations for Schnorr signatures. ECDSA uses the group order _directly_ in signature verification/generation, but Schnorr and EdDSA do not. There is some existing information [2][3] on how to construct Ed25519 multisig schemes. The nice part is that the verification portion does not need to change (unless the pubkeys participating need to be listed explicitly). The difficulty isn't really with the cofactor of Ed25519, its preventing leakage of a participants private key. The implementation _must_ ensure that the signing point includes the users "random" (or deterministically hashed) value. Lee [1] https://ed25519.cr.yp.to/ed25519-20110926.pdf [2] https://datatracker.ietf.org/doc/draft-ford-cfrg-cosi/ [3] https://crypto.stackexchange.com/questions/50448/schnorr-signatures-multisignature-support _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
There are real world in vivo applications of Schnorr with lots of value riding on them that can always be reviewed for correctness, curve selection, multisig operations, implementation bugs, etc. Here's one application example... https://github.com/bitcoincashorg/bitcoincash.org/blob/master/spec/2019-05-15-schnorr.md https://github.com/Bitcoin-ABC/bitcoin-abc https://reviews.bitcoinabc.org/T527 https://reviews.bitcoinabc.org/maniphest/query/487xmasKpdn4 https://reviews.bitcoinabc.org/search/query/ChXUt.xy93mP https://reviews.bitcoinabc.org/source/bitcoin-abc/browse/master/?grep=schnorr https://github.com/Electron-Cash/Electron-Cash/pull/1331 https://github.com/gcash/bchd/pull/180 https://safecurves.cr.yp.to/ https://bitcoin.stackexchange.com/questions/34288/what-are-the-implications-of-schnorr-signatures _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
89.2 MB — 3,873 messages
Last sync: 15 July 2019 22:44

Move Messages

Save

Apply Labels


Warning: Unknown: write failed: No space left on device (28) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php/sessions) in Unknown on line 0