Skip to content

Extremely poor performance and other annoyances #40

@Yawning

Description

@Yawning

I've been sitting on these since the last time I filed bugs because they aren't security critical, but I might as well file them so the people that do happen to use this library suffer less.

Annoyances:

  • Unlike the Rust implementation, operations that work on merlin transcripts are not side-effect free. Fixing this requires finding a different merlin implementation, or getting the merlin library to implement transcript cloning.
  • The documentation for MiniSecretKey.Public should explicitly note that it uses ExpandEd25519, instead of ExpandUniform.

Performance:

  • There is a trivial memory/time tradeoff that can be made. Since PublicKey is opaque, there is no reason not to also cache the compressed (byte-encoded) form of the public key, so that further calls to Encode can be omitted (This is why the Rust implementation has a RistrettoBoth type).
  • There should be a KeyPair type that contains both the PublicKey and SecretKey. This is both generally more useful, and allows signing without having to do a scalar-basepoint multiply + point compression (The Rust implementation has SecretKey's sign method take a public key, and defines a KeyPair type).
  • Verification calculates calculates the R step-by-step using 3 discrete constant time calls (a scalar-basepoint multiply, a scalar multiply, and a subtraction). The ristretto255 library provides VarTimeDoubleScalarBaseMult, use it (Rp := r255.NewElement().VarTimeDoubleScalarBaseMult(k, r255.NewElement().Negate(p.key), s.s) // Rp = -p.key * k + B * s.s).
  • When generating random scalars for batch verification, this implementation reads 512-bits from the entropy source, and does a wide reduction for each scalar. It is sufficient to generate 128-bit scalars, reading 128-bits from the entropy source and using FromCanonicalBytes (no reduction).
  • Batch verification uses the constant-time MultiScalarMult. VarTimeMultiScalarMult is faster.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions