-
Notifications
You must be signed in to change notification settings - Fork 645
Possible variable-time division when decapsulating in Kyber #3844
Description
This bit of code is used in compressing a polynomial ring element into a (secret) message:
botan/src/lib/pubkey/kyber/kyber_common/kyber.cpp
Lines 389 to 390 in 3dcf8af
| const uint16_t t = (((static_cast<uint16_t>(this->m_coeffs[8 * i + j]) << 1) + KyberConstants::Q / 2) / | |
| KyberConstants::Q); |
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