search

FiloSottile / edwards25519

filippo.io/edwards25519 — A safer, faster, and more powerful low-level edwards25519 Go implementation.
https://filippo.io/edwards25519
BSD 3-Clause "New" or "Revised" License
139 stars 30 forks source link

Variable-time scalar multiplication methods use constant-time table lookups #10

Closed hdevalence closed 3 years ago

hdevalence commented 3 years ago

The variable-time scalar multiplication methods,

VarTimeMultiScalarMult

https://github.com/FiloSottile/edwards25519/blob/main/scalarmult.go#L262-L270

and VarTimeDoubleScalarBaseMult

https://github.com/FiloSottile/edwards25519/blob/main/scalarmult.go#L197-L215

both use the SelectInto method on the lookup tables, which performs a constant-time table lookup. But here we're already in a variable-time context, so we don't need to spend extra time to protect the table lookups. These calls could be replaced with direct array accesses for better performance.

In fact, the SelectInto methods could be removed entirely for the nafLookupTableN structures, since these structures are only useful in variable-time contexts, as computing the NAF is a variable-time computation.

FiloSottile commented 3 years ago

Unfortunately(?), those SelectInto methods are already implemented as variable time lookups, and are getting inlined, so there is no extra performance to squeeze there.

https://github.com/FiloSottile/edwards25519/blob/8cc8037b17d3c01c3fdf880a2591b7867c3c555b/tables.go#L121-L129