Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Code duplication between reddsa and redjubjub #6341

Closed
Tracked by #6277
mpguerra opened this issue Mar 16, 2023 · 8 comments · Fixed by ZcashFoundation/reddsa#63
Closed
Tracked by #6277

Code duplication between reddsa and redjubjub #6341

mpguerra opened this issue Mar 16, 2023 · 8 comments · Fixed by ZcashFoundation/reddsa#63
Assignees
Labels
A-cryptography Area: Cryptography related C-audit Category: Issues arising from audit findings C-cleanup Category: This is a cleanup S-needs-triage Status: A bug report needs triage

Comments

@mpguerra
Copy link
Contributor

mpguerra commented Mar 16, 2023

Details

The redjubjub crate implements the RedDSA signature scheme over the Jubjub curve.
The reddsa crate mostly subsumes that task and provides RedDSA support for both the Jubjub and Pallas curves; the migration of the code from redjubjub to reddsa, and its
generalization to unify support over distinct elliptic curves, are currently in an incomplete state, resulting in some code duplication. Thus, there are currently (at least) three mostly identical implementations of the multiplication of a curve point by a scalar with the w-NAF method, in redjubjub/src/scalar_mul.rs, reddsa/src/scalar_mul.rs, and reddsa/src/orchard.rs. In all three cases, the input scalar is converted to a w-NAF representation over exactly 256 digits:

Screenshot 2023-03-16 at 15 04 06

https://github.com/ZcashFoundation/redjubjub/blob/e19279f70f3999627b4076386848d1956b18560e/src/scalar_mul.rs#L66-L70

Screenshot 2023-03-16 at 15 05 53

https://github.com/ZcashFoundation/reddsa/blob/507dcdf695bbc7eccd5d6b8e3c0d62625a45e4e9/src/scalar_mul.rs#L73-L77

Screenshot 2023-03-16 at 15 06 17

https://github.com/ZcashFoundation/reddsa/blob/507dcdf695bbc7eccd5d6b8e3c0d62625a45e4e9/src/orchard.rs#L90-L94

The w-NAF representation converts an input value x into signed digits, using a window width w (expressed in bits), with the following characteristics:

  • Each digit is either zero, or an odd signed integer between -2w-1 and +2w-1.
  • Between any two non-zero digits, there are at least w digits of value zero.
  • n+1 output digits are sufficient to represent all possible x such that 0 ≤ x < 2n + 2n-w.

The non_adjacent_form() function requires that the window width w lies between 2 and 8.
The use of 256 digits is then slightly wasteful for the Jubjub and Pallas curves, where scalars are lower than the prime (sub)group order of interest:

  • Jubjub order is about 2251.85, and thus needs only 253 digits at most for w-NAF.
  • Pallas order is slightly below 2254 + 2125.1, leading to a maximum w-NAF scalar size of 255 digits.

Since the number of iterations in the multiplication loop is exactly equal to the number of digits, and each iteration includes at least a curve point doubling, then some of these doublings are wasted (they will repeatedly double the initial value of the accumulator point, i.e. the curve identity point). On the other hand, if the non_adjacent_form() and optional_multiscalar_mul() functions are turned into generic functions that handle arbitrary curves whose scalars fit on 32 bytes, then 256 digits are not enough: a curve whose order is greater than 2255 +2247 (e.g. secp256k1, or NIST’s P-256) may need up to 257 digits for its scalars in w-NAF representation.

@mpguerra mpguerra added this to Zebra Mar 16, 2023
@github-project-automation github-project-automation bot moved this to 🆕 New in Zebra Mar 16, 2023
@mpguerra mpguerra added C-cleanup Category: This is a cleanup S-needs-triage Status: A bug report needs triage P-Optional ✨ A-cryptography Area: Cryptography related C-audit Category: Issues arising from audit findings labels Mar 16, 2023
@teor2345

This comment was marked as outdated.

@teor2345
Copy link
Contributor

teor2345 commented Apr 3, 2023

Thus, there are currently (at least) three mostly identical implementations of the multiplication of a curve point by a scalar with the w-NAF method, in redjubjub/src/scalar_mul.rs,

As of redjubjub 0.7, the first duplicate implementation has been removed. The duplicates within reddsa still remain.

@upbqdn upbqdn self-assigned this Apr 10, 2023
@upbqdn
Copy link
Member

upbqdn commented Apr 10, 2023

As of redjubjub 0.7, the first duplicate implementation has been removed.

Nitpick: the duplicate implementation was removed in 0.6.

@upbqdn
Copy link
Member

upbqdn commented Apr 20, 2023

The description of the issue says:

Between any two non-zero digits, there are at least w digits of value zero.

I think this statement contains an off-by-one error. The correct number of zero digits should be w-1 since in a w-NAF, at most one of any w consecutive digits is nonzero.

@conradoplg
Copy link
Collaborator

The description of the issue says:

Between any two non-zero digits, there are at least w digits of value zero.

I think this statement contains an off-by-one error. The correct number of zero digits should be w-1 since in a w-NAF, at most one of any w consecutive digits is nonzero.

digs out Guide to ECC

image

You're correct!

@upbqdn
Copy link
Member

upbqdn commented Apr 21, 2023

Sorry, I should have added the full definition right away so others don't have to search for it. I only realized that now.

@mpguerra
Copy link
Contributor Author

@upbqdn can you please add a size for this issue?

@upbqdn
Copy link
Member

upbqdn commented Apr 25, 2023

Done.

@github-project-automation github-project-automation bot moved this from 🆕 New to ✅ Done in Zebra Apr 25, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-cryptography Area: Cryptography related C-audit Category: Issues arising from audit findings C-cleanup Category: This is a cleanup S-needs-triage Status: A bug report needs triage
Projects
Archived in project
Development

Successfully merging a pull request may close this issue.

4 participants