Playing with Schnorr-like signatures

[oryhp]

If you're the type that likes thinking about solutions and checking if they work, then I have a riddle for you.

Recently I was playing with signatures to get a feel of what happens when you change their definition. Here's an example of a possible signature along with some claims about it.
I hope you find it at least half as fun as I have in telling whether it works or not.

Riddle: https://gist.github.com/phyro/c8213747fcf288ff64ed97f4dc1f2192

Those of you who are more experienced with this will find it easy to prove it correct/incorrect.

If this isn't the type of a post the moderators would like to see here, then I apologize and you can close/remove it.

Cheers

P.S. If it is possible to embed markdown in this post let me know and I'll edit it.

[NotATether]

The scheme in https://phyro.github.io/grinvestigation/schnorr.html has one big vulnerability in it and that is that since Alice computes e = H(R | M) and both Alice and Bob already know both R and M, Alice (or Bob, depending on who handles the message after it's verified) could carry out a length extension attack using H(R) and the length of R to make arbitrary malicious messages M that match the signature.

You could change the challenges in your example to be e1 = H(M | P1 | P2) (*fixed) and e2 = H(M | P2 | P1) respectively and an attacker won't be able to produce arbitrary messages for that. If only the side doing the verification knows P1 and P2 then it becomes impossible for the party requesting verification to carry out a length extension attack. And the other party will not be able to fake a message M either because the flaw assumes that the left side of the concatenation isn't known to the attacker.

However, this might be abused by the verifying party to craft a P1 and P2 that equal a completely different pubkey and showing the message as verified from that pubkey i.e. faking ownership. This is why I think that P1 and P2 should be exposed because even if the party asking for the verification knows them, they still won't be able to fake M, the message. And the public will be able to verify if P1 and P2 really do add up to the original pubkey P hence matching the signature.

[gmaxwell]

I only glanced at the multisig section.

The scheme there is grievously insecure, and you should put a more explicit warning on your tutorial because people will follow stuff like it even with notices that it hasn't been reviewed.

Imagine Alice has pubkey P_a, then Bob sets his pubkey P_b =  P_c - P_a.

If you make a combined pubkey P = P_a + P_b then P = P_a + P_c - P_a = P_c.  Bob can sign without Alice's help.

The same also applies to the nonces:  If Bob sees R_a first he can set R_b based on it and cause alice to make a signature with a known nonce, and then he can extract the private key.

Secure multisignatures are possible but what you've described isn't one.

https://eprint.iacr.org/2018/068

https://eprint.iacr.org/2020/1057

Give secure and peer reviewed schemes.

[oryhp]

Thank you both for taking the time to answer! The whole post was supposed to be a journey through completely unsafe schemes towards safer ones, but not necessarily safe - though I admittedly should have made it more obvious we have not necessarily achieved something safe.

The scheme in https://phyro.github.io/grinvestigation/schnorr.html has one big vulnerability in it and that is that since Alice computes e = H(R | M)

Thanks! I did describe at the end why you have to also commit to `P`, but I was not familiar with the attack you described.

You could change the challenges in your example to be e2 = H(M | P2 | P1) and e2 = H(M | P2 | P1) respectively

Did you perhaps forget to edit the pasted challenge?

Secure multisignatures are possible but what you've described isn't one.

Thank you for taking the time to show an example of an attack and linking to safe schemes.

The scheme there is grievously insecure, and you should put a more explicit warning on your tutorial because people will follow stuff like it even with notices that it hasn't been reviewed.

Sadly, this is more true than I would have wanted. I have a horror story to share where one crypto project took something I wrote and almost used it in code despite having a note on the site that the ideas are probably flawed and that I'm not a cryptographer. And the idea
had a very obvious flaw which I knew, but never thought anyone would read my posts (it was shared very locally) let alone people I've never heard of trying to use this as something safe in production... mad world. I have now added a much more obvious note on the site to avoid
any such events in the future.

[NotATether]

You could change the challenges in your example to be e2 = H(M | P2 | P1) and e2 = H(M | P2 | P1) respectively

Did you perhaps forget to edit the pasted challenge?

If you look closer, you can see that the M is now on the left of both concatenations instead of on the far right. This prevents someone from meddling with M to get a colliding hash with the original input.

[oryhp]

If you look closer, you can see that the M is now on the left of both concatenations instead of on the far right. This prevents someone from meddling with M to get a colliding hash with the original input.

Oh, I see now.

P.S. you did write the same challenge twice which is why I thought it was a copy paste from my gist.