Full Report
Constant time cryptography is a method of preventing side channel leaks via timing differences on various operations. Without this, it'd be possible to learn about the cryptographic operations that are occurring. Compilers transform source code into machine code. The machine code is where the timing matters but we typically don't read this. While auditing ML-KEM, they noticed that Clang undid some of the constant time measuring in the name of optimization. The authors posted a demo of exploiting the timing differences in the key encapsulation to extract the key. Overall, this brings up an interesting issue - where do our compilers fail? Most code-level things are correct but it cannot understand what sections can't be optimized.
Analysis Summary
# Vulnerability: Compiler-Induced Timing Leaks in ML-KEM (Kyber) Reference Implementation
## CVE Details
- **CVE ID**: Not yet assigned (Discovered/Reported March 2024).
- **CVSS Score**: Not officially scored, but impact is rated as **Critical** if a binary is affected.
- **CWE**: CWE-385: Reliance on Timing Avoidance Actions / CWE-1038: Insecure Automated Optimizations.
## Affected Systems
- **Products**: Cryptographic libraries utilizing the ML-KEM (Kyber) reference implementation.
- **Affected Libraries**:
- [Kyber Reference Implementation](https://github.com/pq-crystals/kyber)
- [liboqs](https://github.com/open-quantum-safe/liboqs)
- [aws-lc](https://github.com/aws/aws-lc)
- [PQClean](https://github.com/PQClean/PQClean)
- [wolfSSL](https://github.com/wolfSSL/wolfssl)
- [rustpq/pqcrypto](https://github.com/rustpq/pqcrypto)
- **Versions**: Versions prior to March 2024 updates.
- **Configurations**: Specifically systems compiled using **Clang/LLVM** with high optimization levels where the compiler "undoes" constant-time bitmasking within the `poly_frommsg` function.
## Vulnerability Description
The vulnerability arises from an "optimization" performed by modern compilers (predominantly Clang). To prevent side-channel timing attacks, developers use constant-time coding techniques (e.g., bitmasks) to avoid conditional branches (`if/else`) based on secret data.
In the Kyber reference implementation of `poly_frommsg`, the compiler identified that a constant-time bitmask was being used to select between two values. Clang optimized this back into a logical branch in the resulting machine code. Because the execution time of a branch depends on the value of the secret bit, the implementation becomes vulnerable to timing-based side-channel analysis.
## Exploitation
- **Status**: PoC available. A demo was created showing successful key extraction in under 10 minutes on a standard laptop.
- **Complexity**: High (Requires precise timing measurements).
- **Attack Vector**: Local or Network (depending on whether the application timing is observable over the wire).
## Impact
- **Confidentiality**: **Critical**. An attacker can potentially extract secret cryptographic keys or sensitive message data by observing timing differences during the Decapsulation process.
- **Integrity**: None directly.
- **Availability**: None directly.
## Remediation
### Patches
- The **Kyber Reference Implementation** has been patched. The fix involves moving the conditional move (the sensitive operation) into a separate function in a different file. This prevents the compiler from performing the cross-file optimization that recognized the binary nature of the condition flag.
- Update the following libraries to their latest versions:
- **liboqs**: Updated via recent commits.
- **aws-lc**: Addressed in latest releases.
- **wolfSSL**: Patched and coordinated with the Kyber team.
- **PQClean / rustpq**: Publicly disclosed and updated.
### Workarounds
- Developers can manually disable specific compiler optimizations (e.g., using `-O0` or specific pragmas), though this may significantly impact performance.
- Use compiler-intrinsic "barriers" or assembly wrappers for sensitive bitmasking operations to prevent the compiler from re-introducing branches.
## Detection
- **Indicators of Compromise**: No standard IOCs exist as this is a side-channel leak.
- **Detection Methods**:
- **Binary Analysis**: Inspecting the compiled machine code for unexpected `JNE`, `JE`, or other conditional jump instructions in sensitive cryptographic routines.
- **Timing Analysis Tools**: Using tools like `dudect` or `T-test` to detect non-constant time behavior in the final compiled binary.
## References
- PQShield Technical Blog: hxxps://pqshield[.]com/pqshield-plugs-timing-leaks-in-kyber-ml-kem-to-improve-pqc-implementation-maturity/
- Kyber GitHub Repository: hxxps://github[.]com/pq-crystals/kyber
- PQClean: hxxps://github[.]com/PQClean/PQClean