search

Argyle-Software / kyber

A rust implementation of the Kyber post-quantum KEM
https://docs.rs/pqc_kyber/
Apache License 2.0
163 stars 37 forks source link

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

Open tarcieri opened 6 months ago

tarcieri commented 6 months ago

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 commented 6 months ago

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 commented 6 months ago

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

tarcieri commented 5 months ago

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 commented 4 months ago

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.