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: pq-crystals/kyber@dda29cc

It would probably be good to do something similar, e.g.

kyber/src/reference/polyvec.rs

Line 63 in 476e22c

t[k] = (((((t[k] as u32) << 10) + KYBER_Q as u32 / 2) / KYBER_Q as u32) & 0x3ff)

[xvzcf]

This division by Q also occurs when compressing a polynomial ring element into a (secret) message during decapsulation:

kyber/src/reference/poly.rs

Line 310 in 476e22c

t = (((t << 1) + KYBER_Q as i16 / 2) / KYBER_Q as i16) & 1;

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. bwesterb@b5c6ad1

[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.