Wagner's k-sum attack

[burdges]

If I understand, your code implements two round Schnorr multi-signature, much as https://github.com/KZen-networks/multi-party-schnorr/blob/master/papers/accountable_subgroups_multisignatures.pdf describes.

There is a somewhat viable forgery attack against all known two round Schnorr threshold/multi/etc. signatures given in https://eprint.iacr.org/2018/417.pdf that works by doing a roughly 2^40 computation while holding open 127 parallel signing queries.

We've an approach for a fix, but so far failed to prove security. We're still recommending the three round trip version as implemented in https://github.com/w3f/schnorrkel/blob/master/src/musig.rs but maybe that'll change in 2020 if we fix our fix. ;)

As an aside, you should manage MPCs with session types that encode the protocol's security requirements when using Rust, because even highly skilled developers routinely miss-use MPC libraries. These session types cannot be cloned, copied, serialized, etc. and can only be either dropped or consumed by value when advancing the state machine, like in https://github.com/w3f/schnorrkel/blob/master/src/musig.rs#L403

[omershlo]

Hi Jeff,
First of all - thank you for taking the time to review this repo.
Your comments as always are valuable and we will study both topics carefully

concretely,

1. non of our 3 implementations is using 2 rounds. only >3. The Micali paper is basically an older Musig protocol (referenced heavily in the Musig paper) that tries to add accountability by adding another data structure and overall not as efficient as Musig. However, it is secure and does not follow the same idea that led to the 2 round Musig version.
2. We argue that our implementation is derived from a state machine and that you can't misuse it (for example use some result of one round in a different round than the consecutive round ). We have a wrapper for this library that consumes it and creates an API for developers (see https://github.com/KZen-networks/kms-secp256k1/blob/master/src/schnorr/two_party/test.rs#L574 for example). This is the way we intended this library to be used. However, we do recognise that there are perhaps better way to approach to this problem and as said we will learn more thouroughly the topic. We found this paper: http://munksgaard.me/papers/laumann-munksgaard-larsen.pdf , do you recommend it or have other reading material you can refer us to ?

[burdges]

Three rounds means six-seven moves:

• everyone receives signature startup message
• everyone broadcasts their randomness commitment
• everyone receives all the randomness commitments
• everyone broadcasts their randomness
• everyone receives all the randomness
• everyone sends their part of the signature
• anyone receives and combines all the signature parts

There are no randomness commitment phases in any of your protocols. Any known Schnorr multi-signature without randomness commitments is vulnerable.

[omershlo]

Can you please provide a reference?
There are randomness commitment phases in ALL our protocols.
In the Micali protocol you mention, see for example:
https://github.com/KZen-networks/multi-party-schnorr/blob/master/src/protocols/multisig/test.rs#L57
for Musig for example:
https://github.com/KZen-networks/multi-party-schnorr/blob/master/src/protocols/aggsig/test.rs#L38

[burdges]

If I understand, EphKey::gen_commit it returns an EphKey which is the randomness scalar itself, not any sort of key, and you send the corresponding elliptic curve point directly.

I've a MuSig::new in https://github.com/w3f/schnorrkel/blob/master/src/musig.rs#L368 that does the same thing, but it does not return access to the elliptic curve point R_me. Instead, you obtain only a MuSig<merlin::Transcript,CommitStage<&'k Keypair>> or similar so the only public methods are our_commitment and add_their_commitment that handle only hashes of R_me/Rs, and reveal_stage that stops accepting new signers and Rs, well except for add_trusted. This is a session type.

[omershlo]

You are mixing two protocols. You compare our implementation of Micali protocol to your implementation of MuSig. We also have a MuSig implementation that follows the MuSig protocol 1:1.

About Micali protocol, a public key is a non hiding commitment. This steps follows signing step 1, page 11 in the paper:

[burdges]

It still roughly Schnorr though, right? All Schnorr-like signatures are vulnerable, not sure about ECDSA.

In fact, the "not currently involved in another signing protocol" assumption makes this secure, but that's unenforceable.

[burdges]

I took a closer look. :)

At least in https://github.com/KZen-networks/multi-party-schnorr/blob/master/src/protocols/aggsig/mod.rs there is a hashed commitment and EphemeralKey::test_com that tests the commitment. I'm convinced almost all developers would simply omit that test or handle it in the same trip though.

Yes, the protocol by Micali, et al. survives because nonces/witnesses never get combined. It only reduces signature size by 50% over doing separate signatures, which requires only one trip. If you're trading trips for size then you'd accept three trips for 1 bit per signer. I'm therefore dubious this particular trade off ever makes sense in practice.

I'm satisfied the issue I raise here no longer applies though..

[omershlo]

I agree with both statements above.
The first issue was actually raised before. I conclude that we need to sort it out. We will try to do it with Session Types per your suggestion.

Thank you @burdges

[burdges]

You could take https://github.com/w3f/schnorrkel/blob/master/src/musig.rs and replace all the underlying hashing, curve operations, delinearization, error types, etc. with stuff from your existing code.

It still permits a two round trip use case, via add_trusted, but at least the method's name sticks out and its doc comment says "don't use me".

I'll add our proposed fix into this in January with or without a security proof, well it'll make add_trusted less risky anyways.

At some point I'd love to make some version of schnorkel to work on JubJubEngine or similar, which means making the signatures into RedDSA signatures, but mostly means waiting on their trait churn.