Possible variable-time division when decapsulating

[xvzcf]

These bits of code are used in compressing a polynomial ring element into a (secret) message:

crystals-kyber-javascript/kyber512.js

Line 461 in 289aa07

t = (((uint16(a2[8 * i + j]) << 1) + uint16(paramsQ / 2)) / uint16(paramsQ)) & 1;

crystals-kyber-javascript/kyber768.js

Line 461 in 289aa07

t = (((uint16(a2[8 * i + j]) << 1) + uint16(paramsQ / 2)) / uint16(paramsQ)) & 1;

crystals-kyber-javascript/kyber1024.js

Line 460 in 289aa07

t = (((uint16(a2[8 * i + j]) << 1) + uint16(paramsQ / 2)) / uint16(paramsQ)) & 1;

To do so, they perform a division by Q that might not necessarily compile to a multiplication instruction: 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.

We reported a similar issue in the CRYSTALS-Kyber reference implementation; you may want to use their fix: pq-crystals/kyber@dda29cc