botan icon indicating copy to clipboard operation
botan copied to clipboard

Kyber constant time division

Open FAlbertDev opened this issue 1 year ago • 3 comments

Pull request dependencies

  • #3887

This PR adds logic to perform constant-time division by replacing division with a multiplication and right-shift. Instead of using magic numbers for division and right-shift for the specific Kyber constant Q, we compute them on compile time using an algorithm from Hacker's Delight, Chapter 10 - 9.

Also, to ensure the algorithm's correctness, we added a test covering all possible numerators that may occur in Kyber's computation.

Commit: 58a9962

FAlbertDev avatar Jan 24 '24 15:01 FAlbertDev

Coverage Status

coverage: 92.006%. remained the same when pulling 9bbdc6a5bcb8316f167428b376e81c3f8e3c2f28 on Rohde-Schwarz:kyber-ct-div into 13c7e5f1d29455bde2865fd287abc06e747fe389 on randombit:master.

coveralls avatar Jan 24 '24 16:01 coveralls

Perhaps describe the counter measure in side_channel.rst?

reneme avatar Feb 02 '24 10:02 reneme

Rebased and resolved conflicts after #3874 was merged and #3887 was adapted to it.

reneme avatar Feb 16 '24 15:02 reneme

Closed. See #3959.

FAlbertDev avatar Apr 05 '24 08:04 FAlbertDev