test(eddsa-poseidon): Targeted tests for compatibility & security of secret scalar modulus

[artwyman]

Is your feature request related to a problem? Please describe.

This is a follow-on suggestion to #257 which added mod reduction to secret scalar generation. Existing tests confirm that this results in the same public key for one test case, but nothing to confirm that the default private key used actually causes an overflow. I suggest adding some more targeted test cases for the specific situations and vulnerabilities targeted by this change.

Describe the solution you'd like

A few things I'd suggest for additional test cases:

• Check that the secret scalar is in the intended range in all tests.
• Pick multiple secret keys which do and don't cause the overflow targeted here.
• Pick secret keys tailored to the attack scenario which motivated this (those which cause overflow but result in the same public key). Confirm they result in the same secret scalar now as well.

Describe alternatives you've considered
May be too late for this now, but an approach I've found valuable particularly with security-related bugs is based on TDD. Write a test first which will fail and prove the existence of a security bug. Then make the fix and prove the test now passes.

[ChinoCribioli]

Hey! I can work on a few tests targeting this part of the protocol.

[vplasencia]

Hey @ChinoCribioli! Thanks. I just assigned the issue to you. Feel free to ask any questions.

[ChinoCribioli]

After giving a thought to the signing algorithm and exploring the codebase, I have 2 things that I don't understand:

1. The "overflow" (the case in which the secret scalar without taking reminder mod subOrder has 252 bits, while the subOrder has 251 bits) always happens. That's because the pruneBuffer method turns off the most significant bit and turns on the second most significant bit. Therefore, after doing the right shift by 3 bits (to a 256-bit number, which ends up in a 253-bit number), we end up with a secretScalar of strictly 252 bits because we know that the most significant bit is a 0 and the second is a 1. Thus, the "overflow" case doesn't depend on the private key passed. Does this make sense?
2. I don't see what potential issue could it be with taking remainder modulo subOrder. The secret scalar is only used to then be multiplied to the base point Base8, which has order subOrder. Therefore, the points t * Base8 and (t+k*subOrder)*Base8 will always be the same. The only thing that changes when applying the modulo to the secret scalar is that you save a couple of EC point additions when doing mulPointEscalar(Base8, secretScalar), which is always a benefit if you ask me. What I mean is that the result doesn't change.

Sorry if this is a lot of info, but it is what I could take out after my analysis.