search

mimiclone / fips203-java

Java-based implementation of the NIST FIPS-203 Standard (Module-Lattice Key-Encapsulation Mechanism)
MIT License
6 stars 0 forks source link

Timing side channel #2

Open bwesterb opened 2 months ago

bwesterb commented 2 months ago

I think the warning in the README should be a bit stronger: this implementation is very likely insecure to use due to timing side channel issues by using big numbers and division.

mimiclone-james commented 2 months ago

Thank you for submitting this as an issue @bwesterb. I have made the warning larger and more strongly worded. Please let me know if this is satisfactory until the issues are properly resolved.

To add some context to the issue for others, the FIPS 203 standard defines algorithms to calculate zeta and gamma values which become quite large prior to applying a modulo (large enough they would overflow a primitive data type). For this reason the pre-calculated values for zeta and gamma are provided in lookup tables to make it faster and easier to produce secure implementations. However, in the process of implementing the spec, we began by implementing the algorithm directly to validate the lookup table values, which used BigInteger and introduced non-constant-time segments in the code which are susceptible to timing attacks.

The implementation was later updated to use the lookup tables directly, but the algorithms were not properly refactored to remove BigInteger and restore constant time performance.

These algorithms are being revised to provide constant time performance, but for the moment we have added a strong warning in the README to raise awareness of the issue.

mimiclone-james commented 2 months ago

@bwesterb All usage of BigInteger has now been replaced in the library with int calculations making use of constant time mod and pow functions. I have also updated several branch paths with pre-calculated path results to reduce timing leaks. Still need to do a review for any KyberSlash division vulnerabilities. Will update you when that review is complete.

bwesterb commented 2 months ago

Great. How do you implement the mod function? I only had time to look at your code for a minute: I'd advise you to get an expert to go through all code to check thoroughly for any other timing issues.

mimiclone-james commented 2 months ago

@bwesterb The mod function has been replaced by a constant time Barrett reduction algorithm, and the compiled byte code has been verified not to contain any DIV instructions.

bwesterb commented 2 months ago

Great to hear, and great turnaround time. I hope you forgive me that I do not have time to audit the code for other (timing side-channel) issues.

mimiclone-james commented 2 months ago

@bwesterb Totally understand the time constraints. I appreciate it you taking the time to point out the issue at all. We'll get this thing through a formal security audit once the issues we are aware of so far have been closed out.