Repository navigation
modpow implementation is not constant-time #19
Description
Activity
IIRC RSA blinding (which I believe is used in this implementation) uses random number, so while execution time is still variable, it does not correlate with a protected secret.
Hi @newpavlov ,
I don't think that's the case here. The fuzzing target is directly testing this function:
/// Raw RSA encryption of m with the public key. No padding is performed. #[inline] pub fn encrypt<K: PublicKey>(key: &K, m: &BigUint) -> BigUint { m.modpow(key.e(), key.n())So the problem is going to be in the implementation of
modpow.I've also got another fuzzing target that does full pkcs1v15 padding with a statically seeded CPRNG. It displays the same variable-time behavior (with a statically seeded deterministic PRNG mind-you), but the first fuzzing target was the more minimal case, so that's what I reported. (sidefuzz also accounts for RNGs by repeated sampling and taking a t-value, but this doesn't apply here)
Admittedly, this could also be an artifact of the fuzzer (which would be a bug in the fuzzer), but I don't think that's the case here either.
Reacted by Konrad Komorowski- thank you for the report. I have not hardned the underlying modpow impl for const timing yet, so I am not surprised. I will look into it as soon as I find the time.…On 30. Apr 2019, 22:55 +0200, Patrick D Hayes ***@***.***>, wrote: Hi @newpavlov , I don't think that's the case here. The fuzzing target is directly testing this function: /// Raw RSA encryption of m with the public key. No padding is performed. #[inline] pub fn encrypt<K: PublicKey>(key: &K, m: &BigUint) -> BigUint { m.modpow(key.e(), key.n()) So the problem is going to be in the implementation of modpow, which only takes secret data as input. I've also got another fuzzing target that does full pkcs1v15 padding with a statically seeded CPRNG. It displays the same variable-time behavior (with a statically seeded PRNG mind-you), but the first fuzzing target was the more minimal case, so that's what I reported. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.Reacted by Patrick Hayes, holger krekel , Ivan Smirnov, Konrad Komorowski, biørn, Jacob Adam, AMS21 and Daniel Brát
- https://github.com/rust-num/num-bigint/blob/7562ab24330792817e42b808f60b0cac51ca261a/src/monty.rs#L69-L73
- https://github.com/rust-num/num-bigint/blob/7562ab24330792817e42b808f60b0cac51ca261a/src/monty.rs#L121
- https://github.com/rust-num/num-bigint/blob/7562ab24330792817e42b808f60b0cac51ca261a/src/monty.rs#L207-L219
may be causing this.
- changed the title
[-]Potential timing vulnerability[/-][+]modpow implementation is not constant-time[/+]on Apr 25, 2023 crypto-bigintnow has a constant-time modpow implementation in the form ofDynResidue::pow, however it uses Montgomery form internally so it may not be the fastest option for straight modpow since converting in/out of Montgomery form is costly, and it still monomorphizes around a fixed number of limbs.For the purposes of
rsa(anddsa) we probably need to add a newUinttype likeUintVecwhich uses a number of limbs chosen at runtime as a propernum_bigint_dig::BigUintreplacement.Edit: work on
crypto_bigint::BoxedUinthas started.Hi! 👋
I've recently been working on RSA side-channel attacks, and found that many implementations are vulnerable. That's described in the Marvin Attack.
Thanks to help by @ueno, who contributed the test harness, I was able to run the test against rust-crypto (exact versions of all packages are in the PR).
Unfortunately I have to report that the side-channel leakage from the numerical library is very substantial and easily detectable over the network. As such, I consider RustCrypto RSA to be vulnerable and exploitable.
Test results from a run with 100k repeats per probe on an i9-12900KS @ 5.225GHz:
Sign test mean p-value: 0.2189, median p-value: 0.06354, min p-value: 3.946e-60 Friedman test (chisquare approximation) for all samples p-value: 8.827139162990364e-108 Worst pair: 2(no_padding_48), 4(signature_padding_8) Mean of differences: -8.07298e-07s, 95% CI: -9.06918e-07s, -7.019407e-07s (±1.025e-07s) Median of differences: -8.44500e-07s, 95% CI: -9.78000e-07s, -7.200000e-07s (±1.290e-07s) Trimmed mean (5%) of differences: -7.27307e-07s, 95% CI: -8.13648e-07s, -6.316737e-07s (±9.099e-08s) Trimmed mean (25%) of differences: -8.48652e-07s, 95% CI: -9.17708e-07s, -7.769631e-07s (±7.037e-08s) Trimmed mean (45%) of differences: -9.56301e-07s, 95% CI: -1.05768e-06s, -8.603802e-07s (±9.865e-08s) Trimean of differences: -4.72000e-07s, 95% CI: -5.76750e-07s, -3.635625e-07s (±1.066e-07s)pairwise results are in report.txt
confidence intervals for the measurements are as follows:
legend:
ID,Name 0,header_only 1,no_header_with_payload_48 2,no_padding_48 3,no_structure 4,signature_padding_8 5,valid_0 6,valid_48 7,valid_192 8,valid_246 9,valid_repeated_byte_payload_246_1 10,valid_repeated_byte_payload_246_255 11,zero_byte_in_padding_48_4explanations of that are in the step2.py script in marvin-toolkit repo.
In other words, the protection from adding blinding is not sufficient, and Rust Crypto has at least the same issue as the CVE-2022-4304 in OpenSSL.
Reacted by ayyildiz, Eric Joldasov and Kacper PotyrałaAlso just a note for the future, per our SECURITY.md we would've appreciated an advisory for this opened under a private security disclosure.
@tarcieri If the de-blinding isn't performed using constant-time code, then use of blinding won't remove the side-channel signal, that's what the bug in OpenSSL was about: removal of the blinder and conversion to the constant-length bytes needs to be side-channel free too.
Also just a note for the future, per our SECURITY.md we would've appreciated an advisory for this opened under a private security disclosure.
ah, sorry about that; since this was linked as a security issue, I've assumed that the effect of it on security of RSA decryption was assumed public too.
Our answer until now has been that the application of random blinding prevented such sidechannels, so the fact that isn't the case is news to us
sorry, I'm confused, on one hand you say that the the
privkey.decrypt(Pkcs1v15Encrypt, &buffer);won't use blinding, yet that's the public API that you say is protected by use of blinding inREADME.md...?The README.md is wrong in that case.
(Also I'm just discovering this and haven't had time to look over any code yet to confirm specific details)
105 remaining items
- added a commit that references this issue
on Jan 27, 2026 - added a commit that references this issue
on May 2, 2026 - added a commit that references this issue
on May 12, 2026 - added a commit that references this issue
on May 17, 2026 - added a commit that references this issue
on Jun 2, 2026
Hi there,
I'm the author of sidefuzz (https://github.com/phayes/sidefuzz) and I have found what appears to be variable-time behavior in the
rsa::internals::encrypt()function. Specifically,rsa::internals::encrypt()appears to be variable-time in relation to the message. Note that I haven't worked this up into an actual exploit, but merely demonstrated that this function isn't constant-time in relation to the message inputed.Specifically, the message
20d90c8af42aac9b1ee53dc9a0187201takes 549894 instructions to encrypt, while the message5a28cec68d47f6fe3b1df54c9f320f6dtakes 552427 instruction to encrypt. This is a difference of 2533 instructions, or about 0.5%. So it's a slight difference, but probably exploitable with sufficient sampling.I have crated a fuzzing targets here: https://github.com/phayes/sidefuzz-targets
You can confirm this difference with the sidefuzz tool like so:
My first suspicion was that this was due to
num_bigint_dig::BigUint::from_bytes_be()being variable-time, but fuzzing that function specifically results in what appears to be constant-time behavior. So I'm not actually sure where the problem is.