Possible variable-time division when decapsulating in Kyber

[xvzcf]

This bit of code is used in compressing a polynomial ring element into a (secret) message:

crystals-go/crystals-kyber/poly.go

Line 174 in 14b89bf

t = (((uint16(p[8*i+j]) << 1) + uint16(q/2)) / uint16(q)) & 1

To do so, it performs 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

[tgkudelski]

Hello and thanks for reporting. Please notice that this repository is not maintained anymore, it was part of a MsC thesis project but it was not correctly marked as "unmaintained". Kudelski Security does not use this library in any commercial offering or services, it was just meant for testing and fun. I have now updated the README file to clarify this, and I will now archive this repository to avoid further issues. Anyway, out of excess caution and because people might still pick it up by mistake, we have now implemented the patch as you suggested. Thanks again!