bromberg_sl2 icon indicating copy to clipboard operation
bromberg_sl2 copied to clipboard

Probably everything in here should be constant-time

Open benwr opened this issue 3 years ago • 1 comments

Right now there are some branches in the modular arithmetic; these give us ~2x speedup I think, but IIUC in general it's bad to have variable running times in crypto libraries. Probably should just kill that stuff.

If I wanted to be super careful about this I would probably also kill the 2-byte storage table? I don't really know. There are two potential problems with it:

  1. Two different tables (2-byte and 1-byte) might make the running time more dependent on parity than it should be. I think this is basically a non-problem, though, because the running time is unavoidably going to vary with the input length.
  2. Bigger tables have more cache misses, and that means more inferable state. I don't know how much this matters in practice but I'd guess it's not totally trivial for legit crypto libraries.

Sadly if I do both of these things I'll wipe out lots and lots of performance gains, which I actually do care about pretty significantly. My current state is something like "just, like, don't use this to hash data that's supposed to be secret, I guess?"

benwr avatar Feb 25 '21 02:02 benwr