openpgp: Fix RSA key generation with OpenSSL and RustCrypto.

  - Previously, there was a chance that we generated keys with p > q.
    Add a test.

5 files changed, 109 insertions, 1 deletions

diff --git a/openpgp/NEWS b/openpgp/NEWS
index cf406f9e..382888ce 100644
--- a/openpgp/NEWS
+++ b/openpgp/NEWS
@@ -20,6 +20,9 @@
      curve P-521.
    - CipherSuite::variants.
 ** Notable fixes
+   - Sequoia built with the OpenSSL backend or the RustCrypto backend
+     will now make sure that the secret primes of generated RSA keys
+     are ordered the way OpenPGP demands (i.e. `p` < `q`).
    - Sequoia built with the OpenSSL backend, the CNG backend, or the
      RustCrypto backend will now make sure that the secret primes of
      imported RSA keys are ordered the way OpenPGP demands.
diff --git a/openpgp/src/crypto/backend/cng/asymmetric.rs b/openpgp/src/crypto/backend/cng/asymmetric.rs
index 6eb81c51..4bd8fa70 100644
--- a/openpgp/src/crypto/backend/cng/asymmetric.rs
+++ b/openpgp/src/crypto/backend/cng/asymmetric.rs
@@ -812,7 +812,7 @@ where
         let q = mpi::MPI::new(blob.prime2());
         // RSA prime generation in CNG returns them in arbitrary order but
         // RFC 4880 expects `p < q`
-        let (p, q) = if p < q { (p, q) } else { (q, p) };
+        let (p, q) = rsa_sort_pq(p, q);
         // CNG `coeff` is `prime1`^-1 mod `prime2` so adjust for possible p,q reorder
         let big_p = BigUint::from_bytes_be(p.value());
         let big_q = BigUint::from_bytes_be(q.value());
@@ -913,6 +913,25 @@ fn round_up_to_multiple_of(n: usize, m: usize) -> usize {
     ((n + m - 1) / m) * m
 }
 
+/// Given the secret prime values `p` and `q`, returns the pair of
+/// primes so that the smaller one comes first.
+///
+/// Section 5.5.3 of RFC4880 demands that `p < q`.  This function can
+/// be used to order `p` and `q` accordingly.
+///
+/// Note: even though this function seems trivial, we introduce it as
+/// explicit abstraction.  The reason is that the function's
+/// expression also "works" (as in it compiles) for byte slices, but
+/// does the wrong thing, see [`crate::crypto::rsa_sort_raw_pq`].
+fn rsa_sort_pq(p: mpi::MPI, q: mpi::MPI)
+               -> (mpi::MPI, mpi::MPI)
+{
+    if p < q {
+        (p, q)
+    } else {
+        (q, p)
+    }
+}
 
 #[cfg(test)]
 mod tests {
diff --git a/openpgp/src/crypto/backend/openssl/asymmetric.rs b/openpgp/src/crypto/backend/openssl/asymmetric.rs
index 7d82732c..65ea8ef6 100644
--- a/openpgp/src/crypto/backend/openssl/asymmetric.rs
+++ b/openpgp/src/crypto/backend/openssl/asymmetric.rs
@@ -505,6 +505,8 @@ where
         let q = key
             .q()
             .ok_or_else(|| crate::Error::InvalidOperation("q".into()))?;
+        // RFC 4880: `p < q`
+        let (p, q) = rsa_sort_pq(p, q);
 
         let mut ctx = BigNumContext::new_secure()?;
         let mut u = BigNum::new_secure()?;
@@ -573,3 +575,23 @@ where
         }
     }
 }
+
+/// Given the secret prime values `p` and `q`, returns the pair of
+/// primes so that the smaller one comes first.
+///
+/// Section 5.5.3 of RFC4880 demands that `p < q`.  This function can
+/// be used to order `p` and `q` accordingly.
+///
+/// Note: even though this function seems trivial, we introduce it as
+/// explicit abstraction.  The reason is that the function's
+/// expression also "works" (as in it compiles) for byte slices, but
+/// does the wrong thing, see [`crate::crypto::rsa_sort_raw_pq`].
+fn rsa_sort_pq<'a>(p: &'a BigNumRef, q: &'a BigNumRef)
+                   -> (&'a BigNumRef, &'a BigNumRef)
+{
+    if p < q {
+        (p, q)
+    } else {
+        (q, p)
+    }
+}
diff --git a/openpgp/src/crypto/backend/rust/asymmetric.rs b/openpgp/src/crypto/backend/rust/asymmetric.rs
index 0d214edd..3c6e4d68 100644
--- a/openpgp/src/crypto/backend/rust/asymmetric.rs
+++ b/openpgp/src/crypto/backend/rust/asymmetric.rs
@@ -613,6 +613,8 @@ impl<R> Key4<SecretParts, R>
             [p, q] => (p, q),
             _ => panic!("RSA key generation resulted in wrong number of primes"),
         };
+        // RFC 4880: `p < q`
+        let (p, q) = rsa_sort_pq(p, q);
         let u = p.mod_inverse(q) // RFC 4880: u ≡ p⁻¹ (mod q)
             .and_then(|x| x.to_biguint())
             .expect("rsa crate did not generate coprime p and q");
@@ -780,3 +782,22 @@ impl<R> Key4<SecretParts, R>
     }
 }
 
+/// Given the secret prime values `p` and `q`, returns the pair of
+/// primes so that the smaller one comes first.
+///
+/// Section 5.5.3 of RFC4880 demands that `p < q`.  This function can
+/// be used to order `p` and `q` accordingly.
+///
+/// Note: even though this function seems trivial, we introduce it as
+/// explicit abstraction.  The reason is that the function's
+/// expression also "works" (as in it compiles) for byte slices, but
+/// does the wrong thing, see [`crate::crypto::rsa_sort_raw_pq`].
+fn rsa_sort_pq<'a>(p: &'a BigUint, q: &'a BigUint)
+                   -> (&'a BigUint, &'a BigUint)
+{
+    if p < q {
+        (p, q)
+    } else {
+        (q, p)
+    }
+}
diff --git a/openpgp/src/crypto/tests/rsa.rs b/openpgp/src/crypto/tests/rsa.rs
index 9bb82aad..948496ad 100644
--- a/openpgp/src/crypto/tests/rsa.rs
+++ b/openpgp/src/crypto/tests/rsa.rs
@@ -6,6 +6,49 @@ use crate::packet::{prelude::*, signature::subpacket::*};
 use crate::types::*;
 
 #[test]
+fn p_less_than_q() -> Result<()> {
+    use std::cmp::Ordering;
+    use crate::crypto::raw_bigint_cmp;
+
+    // Repeat four times to increase the sensitivity.
+    for _ in 0..4 {
+        // Check that p < q holds when generating an RSA key.
+        let key0 = Key4::generate_rsa(1024)?;
+        let t = key0.creation_time();
+        let (d0, p, q, u0) = extract(&key0);
+        assert_eq!(raw_bigint_cmp(&p, &q), Ordering::Less);
+
+        // Check that p < q holds when importing an RSA key.
+        //
+        // Note: p and q are swapped, i.e. p < q doesn't hold in the
+        // arguments of import_secret_rsa:
+        let key1 = Key4::import_secret_rsa(&d0, &q, &p, t)?;
+        let (d1, p, q, u1) = extract(&key1);
+        assert_eq!(raw_bigint_cmp(&p, &q), Ordering::Less);
+        assert_eq!(d0, d1);
+        assert_eq!(u0, u1);
+    }
+
+    fn extract(key: &Key4<key::SecretParts, key::PrimaryRole>)
+               -> (Vec<u8>, Vec<u8>, Vec<u8>, Vec<u8>)
+    {
+        match key.secret() {
+            SecretKeyMaterial::Unencrypted(s) => s.map(|s| match s {
+                mpi::SecretKeyMaterial::RSA { d, p, q, u } =>
+                    (d.value().into(),
+                     p.value().into(),
+                     q.value().into(),
+                     u.value().into()),
+                _ => unreachable!(),
+            }),
+            _ => unreachable!(),
+        }
+    }
+
+    Ok(())
+}
+
+#[test]
 fn fips_186_3_verification() -> Result<()> {
     if ! PublicKeyAlgorithm::RSAEncryptSign.is_supported() {
         eprintln!("Skipping because RSA is not supported.");