Skip to content

Possible variable-time division when decapsulating in Kyber #3844

@xvzcf

Description

@xvzcf

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

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

Metadata

Metadata

Assignees

Labels

Projects

No projects

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions