Dropping RsaPrivateKey leaves the primes p and q in freed memory; PR #708 still leaks p

[junxzm1990]

Reported by Asymptotic Tech; contact: contact+pilot@asymptotic.tech.

RsaPrivateKey implements ZeroizeOnDrop, but dropping a key does not wipe all of its secrets. The primes p and q and the CRT coefficient remain in freed heap memory. Either prime is enough to recover the full private key. The program below measures this.

We tested at commit 4a6006f6 (the head of master, v0.10.0-rc.18) with the crypto-bigint 0.7.3 that its lockfile pins.

The problem

RsaPrivateKey and PrecomputedValues both implement ZeroizeOnDrop. But PrecomputedValues::zeroize wipes only dp and dq (src/key.rs#L127-L157; the rest is a commented-out TODO). So when a key drops:

• qinv is freed unwiped.
• p_params and q_params are freed unwiped. These are the Montgomery parameters for the two primes, and the parameter block contains the prime itself. precompute builds them from fresh clones of p and q (src/key.rs#L561-L577), so wiping the primes vector does not cover them.

clear_precomputed frees the same three values the same way. Either prime alone gives back the full key (q = n / p, then d). So after a drop, the freed heap holds the private key twice over.

Proof

The program below installs a tracking allocator, drops a uniquely owned 2048-bit key, and scans every freed block for each secret. Running it at 4a6006f6 prints this:

[d    (control: RsaPrivateKey::drop wipes it)] freed blocks still holding the secret: 0
[p    (prime; held by p_params, qinv)        ] freed blocks still holding the secret: 1
[q    (prime; held by q_params)              ] freed blocks still holding the secret: 1
[qinv (CRT coefficient, Montgomery residue)  ] freed blocks still holding the secret: 1

The control is d, which the destructor does wipe. The scanner never finds it in freed memory. So the scanner detects wiping when it happens, and the three hits are real.

PR #708 helps, but still leaks p

Draft PR #708 already adds the missing zeroize() calls. It depends on RustCrypto/crypto-bigint#1338, which was closed without merging, so the fix is currently stalled. And it is not complete: we ran the same program against PR #708's head (97d13b4, with its [patch.crates-io] pointing at the crypto-bigint branch):

[p    (prime; held by p_params, qinv)        ] freed blocks still holding the secret: 1
[q    (prime; held by q_params)              ] freed blocks still holding the secret: 0
[qinv (CRT coefficient, Montgomery residue)  ] freed blocks still holding the secret: 0

q and the qinv residue are now wiped. p is not. The reason: once #1338 removes the Arc, qinv owns its own copy of the Montgomery parameters for p. BoxedMontyForm::zeroize wipes the residue but skips the parameters, on purpose ("This zeroizes the value, but not the associated parameters", src/modular/boxed_monty_form.rs#L229-L235). PrecomputedValues::zeroize has no way to reach that copy through crypto-bigint's public API.

Suggested fix

Two changes, one per repository:

• crypto-bigint: what #1338 does (owned MontyParams inside BoxedMontyParams, Zeroize for it), plus one more step: BoxedMontyForm::zeroize should also wipe its parameters. After #1338 a form owns them, and a secret modulus is as sensitive as a secret residue.
• rsa: PR Complete the zeroize implementation on the Precomputed #708's three zeroize() calls, unchanged. With the crypto-bigint step above, qinv.zeroize() then also wipes qinv's copy of p.

Until both land, the ZeroizeOnDrop impls do not match the actual behavior. Removing them, or documenting the gap, would stop downstream code from relying on them.

The two patches and the regression test are at the end of this issue. The regression test drops a key and checks that no freed block still holds d, p, q, dp, dq or qinv. On current master the test fails: it finds p, q and qinv. With the two patches applied it passes. The crate's full test suite, including the Wycheproof vectors, also passes with the patches applied.

zeroize_precomputed_witness.rs — the measuring program

// Witness: dropping an RsaPrivateKey frees the CRT prime factors p and q
// un-wiped, although RsaPrivateKey and PrecomputedValues both implement
// ZeroizeOnDrop. Run as an integration test of the rsa crate:
//
//     cargo test --release --test zeroize_precomputed_witness -- --nocapture
//
// Method: a tracking global allocator scans every block AT THE MOMENT IT IS
// FREED (the memory is still valid then) for an armed needle, the first 48
// bytes past the lowest limb of one secret. The needle is armed to d (the
// private exponent, which RsaPrivateKey::drop does zeroize: the control), to
// p, to q, and to the residue of qinv, and a UNIQUELY OWNED 2048-bit key is
// dropped each time. A hit is a freed block that still held the secret.
//
// BoxedMontyParams is Arc<MontyParams<BoxedUint>> in crypto-bigint 0.7.5 and
// RsaPrivateKey is Clone, so dropping a clone would not free the params at
// all (the Arc stays alive) and would read as zero hits. The key must be the
// sole owner, which is why the needle is a copy taken through the accessor.
//
// The test PASSES exactly when the defect is present (p and q found in freed
// memory while d is not) and FAILS otherwise, so reproduce/run.sh exits
// non-zero when the defect is absent.

use std::alloc::{GlobalAlloc, Layout, System};
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};

use rand::rngs::ChaCha8Rng;
use rand_core::SeedableRng;
use rsa::traits::PrivateKeyParts;
use rsa::RsaPrivateKey;

const NEEDLE_CAP: usize = 256;
static NEEDLE: [AtomicUsize; NEEDLE_CAP] = {
    const Z: AtomicUsize = AtomicUsize::new(0);
    [Z; NEEDLE_CAP]
};
static NEEDLE_LEN: AtomicUsize = AtomicUsize::new(0);
static ARMED: AtomicBool = AtomicBool::new(false);
static HITS: AtomicUsize = AtomicUsize::new(0);

fn set_needle(bytes: &[u8]) {
    let n = bytes.len().min(NEEDLE_CAP);
    for (i, b) in bytes.iter().take(n).enumerate() {
        NEEDLE[i].store(*b as usize, Ordering::SeqCst);
    }
    NEEDLE_LEN.store(n, Ordering::SeqCst);
}

struct TrackingAlloc;
unsafe impl GlobalAlloc for TrackingAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        System.alloc(layout)
    }
    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        if ARMED.load(Ordering::SeqCst) {
            let len = NEEDLE_LEN.load(Ordering::SeqCst);
            let size = layout.size();
            if len > 0 && size >= len {
                let mut needle = [0u8; NEEDLE_CAP];
                for (i, n) in needle.iter_mut().take(len).enumerate() {
                    *n = NEEDLE[i].load(Ordering::SeqCst) as u8;
                }
                let block = std::slice::from_raw_parts(ptr, size);
                if block.windows(len).any(|w| w == &needle[..len]) {
                    HITS.fetch_add(1, Ordering::SeqCst);
                }
            }
        }
        System.dealloc(ptr, layout)
    }
}
#[global_allocator]
static ALLOC: TrackingAlloc = TrackingAlloc;

// 48 interior bytes of a secret's little-endian limbs (skipping the lowest
// limb, so that the needle never matches a small-integer artefact).
fn needle_of(le_bytes: &[u8]) -> Vec<u8> {
    le_bytes[8..56].to_vec()
}

fn hits_when_dropping(label: &str, seed: u8, select: impl Fn(&RsaPrivateKey) -> Vec<u8>) -> usize {
    let mut rng = ChaCha8Rng::from_seed([seed; 32]);
    let key = RsaPrivateKey::new(&mut rng, 2048).expect("keygen");
    let needle = select(&key);
    set_needle(&needle);
    HITS.store(0, Ordering::SeqCst);
    ARMED.store(true, Ordering::SeqCst);
    drop(key);
    ARMED.store(false, Ordering::SeqCst);
    let h = HITS.load(Ordering::SeqCst);
    std::hint::black_box(&needle);
    println!("[{label:<40}] freed blocks still holding the secret: {h}");
    h
}

#[test]
fn crt_primes_survive_drop() {
    println!("RSA-2048 RsaPrivateKey dropped while a tracking allocator scans every freed block");
    let d = hits_when_dropping("d    (control: RsaPrivateKey::drop wipes it)", 11, |k| {
        needle_of(&k.d().to_le_bytes())
    });
    let p = hits_when_dropping("p    (prime; held by p_params, qinv)", 22, |k| {
        needle_of(&k.primes()[0].to_le_bytes())
    });
    let q = hits_when_dropping("q    (prime; held by q_params)", 33, |k| {
        needle_of(&k.primes()[1].to_le_bytes())
    });
    let qinv = hits_when_dropping("qinv (CRT coefficient, Montgomery residue)", 44, |k| {
        needle_of(&k.qinv().expect("precomputed").as_montgomery().to_le_bytes())
    });
    println!();
    println!("d survived in freed memory:    {}", d > 0);
    println!("p survived in freed memory:    {}", p > 0);
    println!("q survived in freed memory:    {}", q > 0);
    println!("qinv survived in freed memory: {}", qinv > 0);
    assert_eq!(d, 0, "control failed: d was found in freed memory, the harness is not trustworthy");
    assert!(
        p > 0 && q > 0,
        "NOT REPRODUCED: p and q were not found in freed memory (p hits {p}, q hits {q})"
    );
    println!("REPRODUCED: p and q (the whole private key) are freed un-wiped; d is wiped");
}

crypto-bigint-fix.patch — the crypto-bigint change

diff --git a/src/modular/boxed_monty_form.rs b/src/modular/boxed_monty_form.rs
index e07c70b..2f895e4 100644
--- a/src/modular/boxed_monty_form.rs
+++ b/src/modular/boxed_monty_form.rs
@@ -226,11 +226,13 @@ impl MontyForm for BoxedMontyForm {
 
 impl Sealed for BoxedMontyForm {}
 
-/// NOTE: This zeroizes the value, but _not_ the associated parameters!
+/// Zeroizes the value and the associated parameters (the parameters are owned
+/// by this form, and a secret modulus is as sensitive as a secret residue).
 #[cfg(feature = "zeroize")]
 impl Zeroize for BoxedMontyForm {
     fn zeroize(&mut self) {
         self.montgomery_form.zeroize();
+        self.params.zeroize();
     }
 }
 
diff --git a/src/modular/monty_params.rs b/src/modular/monty_params.rs
index 36ad5f8..c6e6494 100644
--- a/src/modular/monty_params.rs
+++ b/src/modular/monty_params.rs
@@ -216,13 +216,15 @@ impl<const LIMBS: usize> FixedMontyParams<LIMBS> {
 pub(crate) mod boxed {
     use super::MontyParams;
     use crate::{Limb, Odd, U64, Word};
-    use alloc::sync::Arc;
     use core::fmt::{self, Debug};
 
+    #[cfg(feature = "zeroize")]
+    use zeroize::Zeroize;
+
     /// Parameters to efficiently go to/from the Montgomery form for an odd modulus whose size and value
     /// are both chosen at runtime.
     #[derive(Clone, Eq, PartialEq)]
-    pub struct BoxedMontyParams(Arc<MontyParams<crate::uint::boxed::BoxedUint>>);
+    pub struct BoxedMontyParams(MontyParams<crate::uint::boxed::BoxedUint>);
 
     impl BoxedMontyParams {
         /// Instantiates a new set of [`BoxedMontyParams`] representing the given `modulus`.
@@ -249,16 +251,13 @@ pub(crate) mod boxed {
 
             let mod_leading_zeros = modulus.as_ref().leading_zeros().min(Word::BITS - 1);
 
-            Self(
-                MontyParams {
-                    modulus,
-                    one,
-                    r2,
-                    mod_inv,
-                    mod_leading_zeros,
-                }
-                .into(),
-            )
+            Self(MontyParams {
+                modulus,
+                one,
+                r2,
+                mod_inv,
+                mod_leading_zeros,
+            })
         }
 
         /// Instantiates a new set of [`BoxedMontyParams`] representing the given `modulus`.
@@ -286,16 +285,13 @@ pub(crate) mod boxed {
 
             let mod_leading_zeros = modulus.as_ref().leading_zeros().min(Word::BITS - 1);
 
-            Self(
-                MontyParams {
-                    modulus,
-                    one,
-                    r2,
-                    mod_inv,
-                    mod_leading_zeros,
-                }
-                .into(),
-            )
+            Self(MontyParams {
+                modulus,
+                one,
+                r2,
+                mod_inv,
+                mod_leading_zeros,
+            })
         }
 
         /// Modulus value.
@@ -345,7 +341,14 @@ pub(crate) mod boxed {
 
     impl From<MontyParams<crate::uint::boxed::BoxedUint>> for BoxedMontyParams {
         fn from(params: MontyParams<crate::uint::boxed::BoxedUint>) -> Self {
-            Self(params.into())
+            Self(params)
+        }
+    }
+
+    #[cfg(feature = "zeroize")]
+    impl Zeroize for BoxedMontyParams {
+        fn zeroize(&mut self) {
+            self.0.zeroize();
         }
     }
 }

rsa-fix.patch — the rsa change

diff --git a/src/key.rs b/src/key.rs
index b5d7e25..19cbb06 100644
--- a/src/key.rs
+++ b/src/key.rs
@@ -144,9 +144,11 @@ impl Zeroize for PrecomputedValues {
     fn zeroize(&mut self) {
         self.dp.zeroize();
         self.dq.zeroize();
-        // TODO: once these have landed in crypto-bigint
-        // self.p_params.zeroize();
-        // self.q_params.zeroize();
+        // `qinv` carries its own copy of the Montgomery parameters for `p`;
+        // wiping it also wipes that copy (crypto-bigint `BoxedMontyForm`).
+        self.qinv.zeroize();
+        self.p_params.zeroize();
+        self.q_params.zeroize();
     }
 }

zeroize_precomputed test — the regression test

diff --git a/tests/zeroize_precomputed.rs b/tests/zeroize_precomputed.rs
new file mode 100644
index 0000000..3855b11
--- /dev/null
+++ b/tests/zeroize_precomputed.rs
@@ -0,0 +1,95 @@
+// Regression test: dropping an RsaPrivateKey must not leave any of its secret
+// components in freed heap memory. A tracking global allocator scans every
+// block at the moment it is freed for a 48-byte needle taken from one secret;
+// a uniquely owned key is dropped per secret. All counts must be zero.
+//
+// Before the fix (rsa 4a6006f6 with crypto-bigint 0.7.x): p, q and the qinv
+// residue are found in freed blocks (p_params, q_params and qinv are not
+// zeroized). After the fix they are not.
+
+use std::alloc::{GlobalAlloc, Layout, System};
+use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
+
+use rand::rngs::ChaCha8Rng;
+use rand_core::SeedableRng;
+use rsa::traits::PrivateKeyParts;
+use rsa::RsaPrivateKey;
+
+const NEEDLE_CAP: usize = 256;
+static NEEDLE: [AtomicUsize; NEEDLE_CAP] = {
+    const Z: AtomicUsize = AtomicUsize::new(0);
+    [Z; NEEDLE_CAP]
+};
+static NEEDLE_LEN: AtomicUsize = AtomicUsize::new(0);
+static ARMED: AtomicBool = AtomicBool::new(false);
+static HITS: AtomicUsize = AtomicUsize::new(0);
+
+fn set_needle(bytes: &[u8]) {
+    let n = bytes.len().min(NEEDLE_CAP);
+    for (i, b) in bytes.iter().take(n).enumerate() {
+        NEEDLE[i].store(*b as usize, Ordering::SeqCst);
+    }
+    NEEDLE_LEN.store(n, Ordering::SeqCst);
+}
+
+struct TrackingAlloc;
+unsafe impl GlobalAlloc for TrackingAlloc {
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        System.alloc(layout)
+    }
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        if ARMED.load(Ordering::SeqCst) {
+            let len = NEEDLE_LEN.load(Ordering::SeqCst);
+            let size = layout.size();
+            if len > 0 && size >= len {
+                let mut needle = [0u8; NEEDLE_CAP];
+                for (i, n) in needle.iter_mut().take(len).enumerate() {
+                    *n = NEEDLE[i].load(Ordering::SeqCst) as u8;
+                }
+                let block = std::slice::from_raw_parts(ptr, size);
+                if block.windows(len).any(|w| w == &needle[..len]) {
+                    HITS.fetch_add(1, Ordering::SeqCst);
+                }
+            }
+        }
+        System.dealloc(ptr, layout)
+    }
+}
+#[global_allocator]
+static ALLOC: TrackingAlloc = TrackingAlloc;
+
+fn needle_of(le_bytes: &[u8]) -> Vec<u8> {
+    le_bytes[8..56].to_vec()
+}
+
+fn hits_when_dropping(seed: u8, select: impl Fn(&RsaPrivateKey) -> Vec<u8>) -> usize {
+    let mut rng = ChaCha8Rng::from_seed([seed; 32]);
+    let key = RsaPrivateKey::new(&mut rng, 2048).expect("keygen");
+    let needle = select(&key);
+    set_needle(&needle);
+    HITS.store(0, Ordering::SeqCst);
+    ARMED.store(true, Ordering::SeqCst);
+    drop(key);
+    ARMED.store(false, Ordering::SeqCst);
+    std::hint::black_box(&needle);
+    HITS.load(Ordering::SeqCst)
+}
+
+#[test]
+fn no_secret_component_survives_drop() {
+    let hits = [
+        ("d", hits_when_dropping(11, |k| needle_of(&k.d().to_le_bytes()))),
+        ("p", hits_when_dropping(22, |k| needle_of(&k.primes()[0].to_le_bytes()))),
+        ("q", hits_when_dropping(33, |k| needle_of(&k.primes()[1].to_le_bytes()))),
+        ("dp", hits_when_dropping(44, |k| needle_of(&k.dp().unwrap().to_le_bytes()))),
+        ("dq", hits_when_dropping(55, |k| needle_of(&k.dq().unwrap().to_le_bytes()))),
+        ("qinv", hits_when_dropping(66, |k| {
+            needle_of(&k.qinv().unwrap().as_montgomery().to_le_bytes())
+        })),
+    ];
+    for (name, h) in &hits {
+        println!("{name:<4} freed blocks still holding it: {h}");
+    }
+    let leaked: Vec<&str> = hits.iter().filter(|(_, h)| *h > 0).map(|(n, _)| *n).collect();
+    assert!(leaked.is_empty(), "secret components found in freed memory after drop: {leaked:?}");
+}

[tarcieri]

Dup of #708

[junxzm1990]

Just saw this is closed, but still want to add an additional note on PR #708:

With the PR applied, p is still recoverable from freed memory. After crypto-bigint#1338, qinv owns its own copy of the Montgomery parameters for p, and BoxedMontyForm::zeroize wipes the residue but not the parameters. Our allocator test at this PR's head (97d13b4) finds p in one freed block; q and qinv in none.

[tarcieri]

That’s expected as the PR is a draft and the solution it’s trying isn’t going to work, but see my comments for the next steps

[junxzm1990]

That’s expected as the PR is a draft and the solution it’s trying isn’t going to work, but see my comments for the next steps

Sounds good!