Potential security vulnerability: non-constant-time usages of division

[tarcieri]

The Kyber reference implementation has been updated to eliminate usages of division out of timing-variability concerns: https://github.com/pq-crystals/kyber/commit/dda29cc63af721981ee2c831cf00822e69be3220

It would probably be good to do something similar, e.g. https://github.com/Argyle-Software/kyber/blob/476e22c1a1ed579f3030e1ae46077036dc384d7f/src/reference/polyvec.rs#L63

[xvzcf]

This division by Q also occurs when compressing a polynomial ring element into a (secret) message during decapsulation: https://github.com/Argyle-Software/kyber/blob/476e22c1a1ed579f3030e1ae46077036dc384d7f/src/reference/poly.rs#L310

Looking at the output of some C compilers using https://godbolt.org/z/sKn3TKKGq and https://godbolt.org/z/8GqKoTfYh for example, a division instruction is emitted even when -O3 is specified. Should a division instruction be emitted, its execution time would likely be variable and leak information about its secret input.

[bwesterb]

Fixed in this fork. https://github.com/bwesterb/argyle-kyber/commit/b5c6ad13f4eece80e59c6ebeafd787ba1519f5f6

[tarcieri]

We have a request to file a RUSTSEC advisory for this vulnerability, although we'll wait to hear back on a potential fix before publishing it: https://github.com/rustsec/advisory-db/pull/1872/files

[Shnatsel]

Heads up: this issue has been included in the RustSec advisory database. It will be surfaced by tools such as cargo-audit or Dependabot from now on.

Once a fix is released to crates.io, please open a pull request to update the advisory with the patched version, or file an issue on the advisory database repository.