4 ms·

Filippo describes how evolutions in the source code and hidden assumptions caused a bug in a special case implementation he kept for performance reasons. This i

by feb 3y ago

Filippo describes how evolutions in the source code and hidden assumptions caused a bug in a special case implementation he kept for performance reasons. This is a great example of how the incompleteness of the old Weierstrass curves multiplication formulas still bites us and how he uses the opportunity to get valuable lessons from this accident. It also shows again how optimizing for performance can cost security and hurt maintainability.

dan-robertson 3y ago
Was the asm for performance or constantish time?
- eptcyka 3y ago
  Constant time.
  - WakoMan12 3y ago
    O(nlogn)
    - consp 3y ago
      That would more likely be a tight bound, not an upper bound.
    - eptcyka 3y ago
      Yes, but it ensures that for all inputs of a given size, runtime will be the same.
- FiloSottile 3y ago
  The assembly is there for performance. Other curves are implemented in constant time pure Go. (It's actually more robust than constant time C, because the Go compiler is less creative in "optimizing" things into branches.)
  - twic 3y ago
    > It's actually more robust than constant time C, because the Go compiler is less creative in "optimizing" things into branches. Today's Go compiler. This feels like a belief with a lot of potential for generating near misses of its own.
    - FiloSottile 3y ago
      Heh, I used to joke that in Go it's safer because I know where the compiler team sits, but I think there's also a fundamental design reason: the Go compiler has speed as a primary goal. I don't know if that's still true, but there used to be a rule of thumb that a new optimization had to speed up the compiler enough to make up for its cost to be added. It's unlikely that unwinding bit masks into branches would be worth adding. Anyway, we're not moving all cryptography to assembly anytime soon, and I'm positive that would not be a net increase in security, even if it would mitigate the hypothetical risk of compiler-introduced side-channels.

by feb 3y ago

dan-robertson 3y ago

Was the asm for performance or constantish time?

eptcyka 3y ago
Constant time.
- WakoMan12 3y ago
  O(nlogn)
  - consp 3y ago
    That would more likely be a tight bound, not an upper bound.
  - eptcyka 3y ago
    Yes, but it ensures that for all inputs of a given size, runtime will be the same.
FiloSottile 3y ago
The assembly is there for performance. Other curves are implemented in constant time pure Go. (It's actually more robust than constant time C, because the Go compiler is less creative in "optimizing" things into branches.)
- twic 3y ago
  > It's actually more robust than constant time C, because the Go compiler is less creative in "optimizing" things into branches. Today's Go compiler. This feels like a belief with a lot of potential for generating near misses of its own.
  - FiloSottile 3y ago
    Heh, I used to joke that in Go it's safer because I know where the compiler team sits, but I think there's also a fundamental design reason: the Go compiler has speed as a primary goal. I don't know if that's still true, but there used to be a rule of thumb that a new optimization had to speed up the compiler enough to make up for its cost to be added. It's unlikely that unwinding bit masks into branches would be worth adding. Anyway, we're not moving all cryptography to assembly anytime soon, and I'm positive that would not be a net increase in security, even if it would mitigate the hypothetical risk of compiler-introduced side-channels.