openpgp: When importing RSA keys, make sure that p < q.

6 files changed, 69 insertions, 3 deletions

diff --git a/openpgp/NEWS b/openpgp/NEWS
index 6d35c423..cf406f9e 100644
--- a/openpgp/NEWS
+++ b/openpgp/NEWS
@@ -20,6 +20,9 @@
      curve P-521.
    - CipherSuite::variants.
 ** Notable fixes
+   - 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.
    - Loosen trait bounds on Key::clone and Key4::clone.
 ** Deprecated functionality
    - ComponentBundle::certifications
diff --git a/openpgp/src/crypto/backend/cng/asymmetric.rs b/openpgp/src/crypto/backend/cng/asymmetric.rs
index 809ab7f7..6eb81c51 100644
--- a/openpgp/src/crypto/backend/cng/asymmetric.rs
+++ b/openpgp/src/crypto/backend/cng/asymmetric.rs
@@ -761,7 +761,7 @@ where
         T: Into<Option<SystemTime>>,
     {
         // RFC 4880: `p < q`
-        let (p, q) = if p < q { (p, q) } else { (q, p) };
+        let (p, q) = crate::crypto::rsa_sort_raw_pq(p, q);
 
         // CNG can't compute the public key from the private one, so do it ourselves
         let big_p = BigUint::from_bytes_be(p);
diff --git a/openpgp/src/crypto/backend/openssl/asymmetric.rs b/openpgp/src/crypto/backend/openssl/asymmetric.rs
index 0ae2ca15..7d82732c 100644
--- a/openpgp/src/crypto/backend/openssl/asymmetric.rs
+++ b/openpgp/src/crypto/backend/openssl/asymmetric.rs
@@ -453,7 +453,7 @@ where
         T: Into<Option<SystemTime>>,
     {
         // RFC 4880: `p < q`
-        let (p, q) = if p < q { (p, q) } else { (q, p) };
+        let (p, q) = crate::crypto::rsa_sort_raw_pq(p, q);
 
         let mut big_p = BigNum::new_secure()?;
         big_p.copy_from_slice(p)?;
diff --git a/openpgp/src/crypto/backend/rust/asymmetric.rs b/openpgp/src/crypto/backend/rust/asymmetric.rs
index a5a434f8..0d214edd 100644
--- a/openpgp/src/crypto/backend/rust/asymmetric.rs
+++ b/openpgp/src/crypto/backend/rust/asymmetric.rs
@@ -573,7 +573,7 @@ impl<R> Key4<SecretParts, R>
         -> Result<Self> where T: Into<Option<SystemTime>>
     {
         // RFC 4880: `p < q`
-        let (p, q) = if p < q { (p, q) } else { (q, p) };
+        let (p, q) = crate::crypto::rsa_sort_raw_pq(p, q);
 
         // RustCrypto can't compute the public key from the private one, so do it ourselves
         let big_p = BigUint::from_bytes_be(p);
diff --git a/openpgp/src/crypto/mod.rs b/openpgp/src/crypto/mod.rs
index 1c136102..09b18c9a 100644
--- a/openpgp/src/crypto/mod.rs
+++ b/openpgp/src/crypto/mod.rs
@@ -324,3 +324,41 @@ pub(crate) fn pad_truncating(value: &[u8], to: usize) -> Cow<[u8]>
         Cow::Owned(v)
     }
 }
+
+/// Compares two arbitrary-sized big-endian integers.
+///
+/// Note that the tempting `a < b` doesn't work: it computes the
+/// lexicographical order, so that `[2] > [1, 2]`, whereas we want
+/// `[2] < [1, 2]`.
+pub(crate) fn raw_bigint_cmp(mut a: &[u8], mut b: &[u8]) -> Ordering {
+    // First, trim leading zeros.
+    while a.get(0) == Some(&0) {
+        a = &a[1..];
+    }
+
+    while b.get(0) == Some(&0) {
+        b = &b[1..];
+    }
+
+    // Then, compare their length.  Shorter integers are also smaller.
+    a.len().cmp(&b.len())
+        // Finally, if their length is equal, do a lexicographical
+        // comparison.
+        .then_with(|| a.cmp(b))
+}
+
+/// 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.
+#[allow(dead_code)]
+pub(crate) fn rsa_sort_raw_pq<'a>(p: &'a [u8], q: &'a [u8])
+                                  -> (&'a [u8], &'a [u8])
+{
+    match raw_bigint_cmp(p, q) {
+        Ordering::Less => (p, q),
+        Ordering::Equal => (p, q),
+        Ordering::Greater => (q, p),
+    }
+}
diff --git a/openpgp/src/crypto/tests.rs b/openpgp/src/crypto/tests.rs
index 91cdc0c6..68f6ee7a 100644
--- a/openpgp/src/crypto/tests.rs
+++ b/openpgp/src/crypto/tests.rs
@@ -3,3 +3,28 @@
 mod rsa;
 mod dsa;
 mod ecdsa;
+
+#[test]
+fn raw_bigint_cmp() {
+    use std::cmp::Ordering;
+    use crate::crypto::raw_bigint_cmp as cmp;
+
+    assert_eq!(cmp(&[], &[]), Ordering::Equal);
+    assert_eq!(cmp(&[], &[1]), Ordering::Less);
+    assert_eq!(cmp(&[1], &[]), Ordering::Greater);
+    assert_eq!(cmp(&[1], &[1]), Ordering::Equal);
+    assert_eq!(cmp(&[1], &[2]), Ordering::Less);
+    assert_eq!(cmp(&[2], &[1]), Ordering::Greater);
+    assert_eq!(cmp(&[1], &[1, 2]), Ordering::Less);
+    assert_eq!(cmp(&[1, 2], &[1]), Ordering::Greater);
+    assert_eq!(cmp(&[1], &[2, 1]), Ordering::Less);
+    assert_eq!(cmp(&[2, 1], &[1]), Ordering::Greater);
+
+    assert_eq!(cmp(&[0], &[]), Ordering::Equal);
+    assert_eq!(cmp(&[0], &[1]), Ordering::Less);
+    assert_eq!(cmp(&[0, 1], &[]), Ordering::Greater);
+
+    assert_eq!(cmp(&[], &[0]), Ordering::Equal);
+    assert_eq!(cmp(&[], &[0, 1]), Ordering::Less);
+    assert_eq!(cmp(&[1], &[0]), Ordering::Greater);
+}