modpow implementation is not constant-time

[phayes]

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 20d90c8af42aac9b1ee53dc9a0187201 takes 549894 instructions to encrypt, while the message 5a28cec68d47f6fe3b1df54c9f320f6d takes 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:

sidefuzz check ./target/wasm32-unknown-unknown/release/rsa_encrypt_message.wasm 5a28cec68d47f6fe3b1df54c9f320f6d 20d90c8af42aac9b1ee53dc9a0187201
samples: 20000, t-value: 219771.0790572351, confidence: 100%
Found timing difference of 2533 instructions between these two inputs with 100% confidence:
input 1: 5a28cec68d47f6fe3b1df54c9f320f6d (552427 instructions)
input 2: 20d90c8af42aac9b1ee53dc9a0187201 (549894 instructions)

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.

[newpavlov]

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.

[phayes]

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.

[dignifiedquire]

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.

[jedisct1]

• 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.

[tarcieri]

crypto-bigint now has a constant-time modpow implementation in the form of DynResidue::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 (and dsa) we probably need to add a new Uint type like UintVec which uses a number of limbs chosen at runtime as a proper num_bigint_dig::BigUint replacement.

Edit: work on crypto_bigint::BoxedUint has started.

[tarcieri]

Until this is addressed it seems like something we should more prominently highlight in security-related documentation.

Edit: opened #373 (and merged!)

[tomato42]

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_4

explanations 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.

[tarcieri]

@tomato42 indeed that's using PKCS#1v1.5 without random blinding, so with modpow being non-constant-time, it's to be expected. We should definitely get rid of any APIs which permit private key use without random blinding.

[tarcieri]

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.

[tomato42]

@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.

[tarcieri]

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