RSA: modpow implementation is not constant-time

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 notifications@github.com, 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.

The algorithm is already implemented and shipped in NSS and OpenSSL, so bearing something catastrophic discovered during review, I consider the algorithm final.

due to the application performing a different action based on if the padding is valid or not) or returning a randomly generated string as a rejection symbol.

and that’s why with implicit rejection on the PKCS#1v1.5 level, the one described in https://datatracker.ietf.org/doc/draft-kario-rsa-guidance/ and in the Marvin paper, the API call always returns a message, and for every key-ciphertext pair, it will return the same ciphertext over and over, even if in actuality the PKCS#1v1.5 padding check failed. Thus the attacker has no oracle to tell which ones are good and which ones are bad, as all “look good”.

(TBH though, I don’t at all see why this would be the case or how mixing in the server random would change the situation.)

because we have two cases:

1. good padding, decrypts to a message, unexpected value (e.g. not matching the AES ciphertext), but the same value every time
2. bad padding, decrypts to a random message on every try

so the behaviour of application in case 1 will be consistent for every try, while in case 2 it will be more random (in case of aes-cbc there’s 1 in 256 chance that that padding check passes, which will provide huge difference in behaviour)

in case of TLS, those two different situations are also combined with the ServerHello.random, which is different for every try, so the subsequent actions based on that random value will also be random, independent if the decryption returns the same value every time or if it returns random value every time

@tarcieri Thanks! CVE added to the page.

we’ll need to start handling padding failures via implicit rejection (producing a pseudorandom output)? My only familiarity with that approach is from Kyber

if you consider deprecation of PKCS#1 v1.5 encryption padding to be not a realistic option, then yes, that’s the best way to provide an API that’s about as safe to use as one for OAEP

To consumers of the rsa crate

While the attack requires the attacker to measure precisely the processing time of the ciphertext, one of the main contributions of the Marvin Attack paper is that it’s is possible to measure differences of just few nanoseconds (billionth’s of a second) even over the network. The ability to do that depends only of the number of measurements the attacker is able to perform, not on the size of the side channel.

The old wisdom of “side channels smaller than 100ns are not attackable over the network” is incorrect, see the vulnerability page for details.

Thanks for the mention, yes, I’ve seen it. If you want, I can add it, but I planned to wait for CVE assignment.

I’ve opened a WIP @RustSec advisory here: https://github.com/rustsec/advisory-db/pull/1825

The branch containing that code has disappeared: https://github.com/ueno/marvin-toolkit/tree/wip/rust-crypto

You can test the low-level “hazmat” API: https://docs.rs/rsa/latest/rsa/hazmat/fn.rsa_decrypt.html

It would look something like:

https://github.com/tomato42/marvin-toolkit/pull/4/files#diff-c0f6b76f1d52cf643fb2f30ef85b81b20ace1aa7577d1f4603db0e091e052d66R50-R63

…replaced with:

    loop {
        let mut buffer = vec![0; args.size];
        let n = infile.read(&mut buffer)?;
        if n == 0 {
            break;
        }

        assert!(n == buffer.len());

        let now = Instant::now();
        let c = rsa::BigUint::from_bytes_be(&buffer);
        let _ =  rsa::hazmat::rsa_decrypt(Some(&mut rand_core::OsRng), &privkey, &c);
        writeln!(outfile, "{}", now.elapsed().as_nanos())?;
    }

Note you’ll need to add rand_core as a dependency and enable the hazmat feature of rsa:

https://github.com/tomato42/marvin-toolkit/pull/4/files#diff-76856434fe4ad8f1f778ba0452c8d8e49e764d25adf1374d385634cd251e1ca2R6-R9

[dependencies]
anyhow = "1"
clap = { version = "4", features = ["derive"] }
rand_core = { version = "0.6", features = ["getrandom"] }
rsa = { version = "0.9", features = ["hazmat"] }

Sorry, I’m not a rust developer, you will need to hand-hold me (provide the complete code to execute) if you want me to run any tests

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.

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.