Repository navigation
Tracking issue for constant-time implementation problems #711
Description
draft-irtf-cfrg-rsa-guidance contains plenty of guidance for how to implement RSA in constant time correctly. This is an issue tracking what parts of its recommendations we're currently missing.
Note we have a separate issue #626 specifically to track padding defects and the lack of implicit rejection on padding failures.
- Make private-result integer-to-octet conversion fixed-width and constant-time (see §6.1, §7.2, addressed in Fix RSA constant-time padding and length checks #710)
- Ignore the first encoded-message octet when depadding OAEP (see §7)
- Apply base blinding by default across private-key operations (see §6.1, partly addressed in Blind the default PKCS#1 v1.5 / OAEP decryption paths #702)
- Audit and replace CRT reductions using division by secret primes including
rem_vartimefor mod reduce (see §6.1, §6.2) - Derive private arithmetic buffer widths from the public modulus (§6.2.1)
- Add fresh exponent blinding for each private operation (see §6.4)
- Add CRT modulus blinding (see §6.5)
- Require exactly
kciphertext octets for PKCS#1 v1.5 decryption (see §7.2, addressed in Fix RSA constant-time padding and length checks #710)
NOTE: I'd kindly request that people do NOT open PRs that try to vibe code solutions to these problems. We already have people including myself working on these issues and vibe coded PRs clutter the tracker and just generally waste my time.
Activity
tarcieri commentedon Oct 2, 2026
cc @tomato42 who authored the I-D this issue was based on
Streetblock commentedon Oct 9, 2026
Would a signing-only source audit and timing harness be useful for this tracking issue, particularly items 3, 5 and 6?
The use case is PDF/CMS signing. PdfCraft currently uses AWS-LC for native RSA private-key operations and RustCrypto for verification; we are investigating what evidence would be needed for a future pure-Rust signing backend. A signing-only API does not expose the classical Marvin decryption oracle, but still needs analysis of its private arithmetic.
A preliminary source trace of rsa 0.10.0-rc.19 (db103005) with crypto-bigint 0.7.5 found:
dthe public modulus width (encoding.rs). The constructor subsequently shrinksp/q; that affects static CRT operand widths, especially for imported unbalanced primes (key.rs).rem_vartimecalls appear in key precomputation (key.rs); the per-signature CRT message reductions use%(rsa.rs). Setup and steady-state signing therefore need separate measurements.The proposed first experiment would fix/import a synthetic key outside the signing measurement, then compare CRT/non-CRT × blinded/unblinded signing over the same messages. A separate setup experiment would exercise unbalanced factors crossing limb boundaries and swapped
p/qwith unchangedn/e/d. Results would include pinned source/dependencies, compiler/target/optimization settings and raw timing data, with public-signature correlations distinguished from private information.This preliminary review was AI-assisted. No compiled-code timing measurements have been run and no exploitable vulnerability is claimed. Before implementing the harness, is this scope useful, or is someone already covering it?
tarcieri commentedon Oct 10, 2026
@Streetblock the most important thing is correct implementations.
When it comes to a "timing harness" as a tool to perform post hoc assertions of constant-time correctness, that's probably something we'd want a more cross-cutting solution to which works across the entire project (I've investigated the BINSEC-based
cargo checkctfor this purpose, for example)tomato42 commentedon Oct 20, 2026
That's true. You can analyse if the timing of the signature correlates with secret values: if signing with different keys takes the same amount of time, or if the signing time is independent of the Hamming weight of padded message reduced modulo
porq...