bug 1530545 - store preloaded intermediates in cert_storage r=mgoodwin,myk
authorDana Keeler <dkeeler@mozilla.com>
Tue, 30 Apr 2019 00:00:48 +0000
changeset 530658 70463f459a9c740f7b2f3c3fad5c88b017956507
parent 530657 2e7aeeb20cbc92614bd354955a5b847acce224a9
child 530659 d89587999df100be804a749694ac08fffd5ab39d
push id11265
push userffxbld-merge
push dateMon, 13 May 2019 10:53:39 +0000
treeherdermozilla-beta@77e0fe8dbdd3 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmgoodwin, myk
bugs1530545
milestone68.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
bug 1530545 - store preloaded intermediates in cert_storage r=mgoodwin,myk This updates cert_storage to be able to store certificates indexed by subject DN for easy lookup by NSSCertDBTrustDomain during path building. This also updates RemoteSecuritySettings to store newly-downloaded preloaded intermediates in cert_storage. Differential Revision: https://phabricator.services.mozilla.com/D27991
Cargo.lock
security/certverifier/NSSCertDBTrustDomain.cpp
security/certverifier/NSSCertDBTrustDomain.h
security/manager/ssl/RemoteSecuritySettings.jsm
security/manager/ssl/X509.jsm
security/manager/ssl/cert_storage/Cargo.toml
security/manager/ssl/cert_storage/src/lib.rs
security/manager/ssl/moz.build
security/manager/ssl/nsICertStorage.idl
security/manager/ssl/tests/unit/test_cert_storage_direct.js
security/manager/ssl/tests/unit/test_der.js
security/manager/ssl/tests/unit/test_intermediate_preloads.js
security/manager/ssl/tests/unit/test_x509.js
security/manager/ssl/tests/unit/xpcshell.ini
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -426,16 +426,17 @@ name = "cc"
 version = "1.0.34"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "cert_storage"
 version = "0.0.1"
 dependencies = [
  "base64 0.10.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "byteorder 1.2.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "crossbeam-utils 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "lmdb-rkv 0.11.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "moz_task 0.1.0",
  "nserror 0.1.0",
  "nsstring 0.1.0",
  "rkv 0.9.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "sha2 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
--- a/security/certverifier/NSSCertDBTrustDomain.cpp
+++ b/security/certverifier/NSSCertDBTrustDomain.cpp
@@ -83,26 +83,51 @@ NSSCertDBTrustDomain::NSSCertDBTrustDoma
       mDistrustedCAPolicy(distrustedCAPolicy),
       mSawDistrustedCAByPolicyError(false),
       mOriginAttributes(originAttributes),
       mThirdPartyRootInputs(thirdPartyRootInputs),
       mThirdPartyIntermediateInputs(thirdPartyIntermediateInputs),
       mBuiltChain(builtChain),
       mPinningTelemetryInfo(pinningTelemetryInfo),
       mHostname(hostname),
-      mCertBlocklist(do_GetService(NS_CERT_STORAGE_CID)),
+      mCertStorage(do_GetService(NS_CERT_STORAGE_CID)),
       mOCSPStaplingStatus(CertVerifier::OCSP_STAPLING_NEVER_CHECKED),
       mSCTListFromCertificate(),
       mSCTListFromOCSPStapling() {}
 
 Result NSSCertDBTrustDomain::FindIssuer(Input encodedIssuerName,
                                         IssuerChecker& checker, Time) {
   Vector<Input> rootCandidates;
   Vector<Input> intermediateCandidates;
 
+  if (!mCertStorage) {
+    return Result::FATAL_ERROR_LIBRARY_FAILURE;
+  }
+  nsTArray<uint8_t> subject;
+  if (!subject.AppendElements(encodedIssuerName.UnsafeGetData(),
+                              encodedIssuerName.GetLength())) {
+    return Result::FATAL_ERROR_NO_MEMORY;
+  }
+  nsTArray<nsTArray<uint8_t>> certs;
+  nsresult rv = mCertStorage->FindCertsBySubject(subject, certs);
+  if (NS_FAILED(rv)) {
+    return Result::FATAL_ERROR_LIBRARY_FAILURE;
+  }
+  for (auto& cert : certs) {
+    Input certDER;
+    Result rv = certDER.Init(cert.Elements(), cert.Length());
+    if (rv != Success) {
+      continue;  // probably too big
+    }
+    // Currently we're only expecting intermediate certificates in cert storage.
+    if (!intermediateCandidates.append(certDER)) {
+      return Result::FATAL_ERROR_NO_MEMORY;
+    }
+  }
+
   SECItem encodedIssuerNameItem = UnsafeMapInputToSECItem(encodedIssuerName);
 
   // NSS seems not to differentiate between "no potential issuers found" and
   // "there was an error trying to retrieve the potential issuers." We assume
   // there was no error if CERT_CreateSubjectCertList returns nullptr.
   UniqueCERTCertList candidates(CERT_CreateSubjectCertList(
       nullptr, CERT_GetDefaultCertDB(), &encodedIssuerNameItem, 0, false));
   if (candidates) {
@@ -186,17 +211,17 @@ Result NSSCertDBTrustDomain::GetCertTrus
   SECItem candidateCertDERSECItem = UnsafeMapInputToSECItem(candidateCertDER);
   UniqueCERTCertificate candidateCert(CERT_NewTempCertificate(
       CERT_GetDefaultCertDB(), &candidateCertDERSECItem, nullptr, false, true));
   if (!candidateCert) {
     return MapPRErrorCodeToResult(PR_GetError());
   }
 
   // Check the certificate against the OneCRL cert blocklist
-  if (!mCertBlocklist) {
+  if (!mCertStorage) {
     return Result::FATAL_ERROR_LIBRARY_FAILURE;
   }
 
   // The certificate blocklist currently only applies to TLS server
   // certificates.
   if (mCertDBTrustType == trustSSL) {
     int16_t revocationState;
 
@@ -207,17 +232,17 @@ Result NSSCertDBTrustDomain::GetCertTrus
 
     nsresult nsrv = BuildRevocationCheckArrays(
         candidateCert, issuerBytes, serialBytes, subjectBytes, pubKeyBytes);
 
     if (NS_FAILED(nsrv)) {
       return Result::FATAL_ERROR_LIBRARY_FAILURE;
     }
 
-    nsrv = mCertBlocklist->GetRevocationState(
+    nsrv = mCertStorage->GetRevocationState(
         issuerBytes, serialBytes, subjectBytes, pubKeyBytes, &revocationState);
     if (NS_FAILED(nsrv)) {
       return Result::FATAL_ERROR_LIBRARY_FAILURE;
     }
 
     if (revocationState == nsICertStorage::STATE_ENFORCE) {
       MOZ_LOG(gCertVerifierLog, LogLevel::Debug,
               ("NSSCertDBTrustDomain: certificate is in blocklist"));
@@ -467,17 +492,17 @@ Result NSSCertDBTrustDomain::CheckRevoca
   }
   // At this point, if and only if cachedErrorResult is Success, there was no
   // cached response.
   MOZ_ASSERT((!cachedResponsePresent && cachedResponseResult == Success) ||
              (cachedResponsePresent && cachedResponseResult != Success));
 
   // If we have a fresh OneCRL Blocklist we can skip OCSP for CA certs
   bool blocklistIsFresh;
-  nsresult nsrv = mCertBlocklist->IsBlocklistFresh(&blocklistIsFresh);
+  nsresult nsrv = mCertStorage->IsBlocklistFresh(&blocklistIsFresh);
   if (NS_FAILED(nsrv)) {
     return Result::FATAL_ERROR_LIBRARY_FAILURE;
   }
 
   // TODO: We still need to handle the fallback for invalid stapled responses.
   // But, if/when we disable OCSP fetching by default, it would be ambiguous
   // whether security.OCSP.enable==0 means "I want the default" or "I really
   // never want you to ever fetch OCSP."
--- a/security/certverifier/NSSCertDBTrustDomain.h
+++ b/security/certverifier/NSSCertDBTrustDomain.h
@@ -227,17 +227,17 @@ class NSSCertDBTrustDomain : public mozi
   bool mSawDistrustedCAByPolicyError;
   const OriginAttributes& mOriginAttributes;
   const Vector<mozilla::pkix::Input>& mThirdPartyRootInputs;  // non-owning
   const Vector<mozilla::pkix::Input>&
       mThirdPartyIntermediateInputs;  // non-owning
   UniqueCERTCertList& mBuiltChain;    // non-owning
   PinningTelemetryInfo* mPinningTelemetryInfo;
   const char* mHostname;  // non-owning - only used for pinning checks
-  nsCOMPtr<nsICertStorage> mCertBlocklist;
+  nsCOMPtr<nsICertStorage> mCertStorage;
   CertVerifier::OCSPStaplingStatus mOCSPStaplingStatus;
   // Certificate Transparency data extracted during certificate verification
   UniqueSECItem mSCTListFromCertificate;
   UniqueSECItem mSCTListFromOCSPStapling;
 };
 
 }  // namespace psm
 }  // namespace mozilla
--- a/security/manager/ssl/RemoteSecuritySettings.jsm
+++ b/security/manager/ssl/RemoteSecuritySettings.jsm
@@ -4,16 +4,17 @@
 "use strict";
 
 const EXPORTED_SYMBOLS = ["RemoteSecuritySettings"];
 
 const {RemoteSettings} = ChromeUtils.import("resource://services-settings/remote-settings.js");
 
 const {Services} = ChromeUtils.import("resource://gre/modules/Services.jsm");
 const {XPCOMUtils} = ChromeUtils.import("resource://gre/modules/XPCOMUtils.jsm");
+const {X509} = ChromeUtils.import("resource://gre/modules/psm/X509.jsm", null);
 
 const INTERMEDIATES_BUCKET_PREF          = "security.remote_settings.intermediates.bucket";
 const INTERMEDIATES_CHECKED_SECONDS_PREF = "security.remote_settings.intermediates.checked";
 const INTERMEDIATES_COLLECTION_PREF      = "security.remote_settings.intermediates.collection";
 const INTERMEDIATES_DL_PER_POLL_PREF     = "security.remote_settings.intermediates.downloads_per_poll";
 const INTERMEDIATES_ENABLED_PREF         = "security.remote_settings.intermediates.enabled";
 const INTERMEDIATES_SIGNER_PREF          = "security.remote_settings.intermediates.signer";
 const LOGLEVEL_PREF                      = "browser.policies.loglevel";
@@ -59,19 +60,32 @@ function getHash(str) {
   let stringStream = Cc["@mozilla.org/io/string-input-stream;1"].createInstance(Ci.nsIStringInputStream);
   stringStream.data = str;
   hasher.updateFromStream(stringStream, -1);
 
   // convert the binary hash data to a hex string.
   return hexify(hasher.finish(false));
 }
 
-// Remove all colons from a string
-function stripColons(hexString) {
-  return hexString.replace(/:/g, "");
+// Converts a JS string to an array of bytes consisting of the char code at each
+// index in the string.
+function stringToBytes(s) {
+  let b = [];
+  for (let i = 0; i < s.length; i++) {
+    b.push(s.charCodeAt(i));
+  }
+  return b;
+}
+
+// Converts an array of bytes to a JS string using fromCharCode on each byte.
+function bytesToString(bytes) {
+  if (bytes.length > 65535) {
+    throw new Error("input too long for bytesToString");
+  }
+  return String.fromCharCode.apply(null, bytes);
 }
 
 this.RemoteSecuritySettings = class RemoteSecuritySettings {
     constructor() {
         this.client = RemoteSettings(Services.prefs.getCharPref(INTERMEDIATES_COLLECTION_PREF), {
           bucketNamePref: INTERMEDIATES_BUCKET_PREF,
           lastCheckTimePref: INTERMEDIATES_CHECKED_SECONDS_PREF,
           signerName: Services.prefs.getCharPref(INTERMEDIATES_SIGNER_PREF),
@@ -103,21 +117,21 @@ this.RemoteSecuritySettings = class Remo
         // certs more than once daily)
         const current = await this.client.get();
         const waiting = current.filter(record => !record.cert_import_complete);
 
         log.debug(`There are ${waiting.length} intermediates awaiting download.`);
 
         TelemetryStopwatch.start(INTERMEDIATES_UPDATE_MS_TELEMETRY);
 
-        const certdb = Cc["@mozilla.org/security/x509certdb;1"].getService(Ci.nsIX509CertDB);
+        const certStorage = Cc["@mozilla.org/security/certstorage;1"].getService(Ci.nsICertStorage);
         const col = await this.client.openCollection();
 
         Promise.all(waiting.slice(0, maxDownloadsPerRun)
-          .map(record => this.maybeDownloadAttachment(record, col, certdb))
+          .map(record => this.maybeDownloadAttachment(record, col, certStorage))
         ).then(async () => {
           const finalCurrent = await this.client.get();
           const finalWaiting = finalCurrent.filter(record => !record.cert_import_complete);
           const countPreloaded = finalCurrent.length - finalWaiting.length;
 
           TelemetryStopwatch.finish(INTERMEDIATES_UPDATE_MS_TELEMETRY);
           Services.telemetry.scalarSet(INTERMEDIATES_PRELOADED_TELEMETRY,
                                        countPreloaded);
@@ -138,29 +152,28 @@ this.RemoteSecuritySettings = class Remo
           log.warn(`Unable to update intermediate preloads: ${err}`);
 
           Services.telemetry.getHistogramById(INTERMEDIATES_ERRORS_TELEMETRY)
             .add("failedToObserve");
         }
     }
 
     // This method returns a promise to RemoteSettingsClient.maybeSync method.
-    onSync(event) {
+    async onSync(event) {
         const {
           data: {deleted},
         } = event;
 
         if (!Services.prefs.getBoolPref(INTERMEDIATES_ENABLED_PREF, true)) {
           log.debug("Intermediate Preloading is disabled");
-          return Promise.resolve();
+          return;
         }
 
         log.debug(`Removing ${deleted.length} Intermediate certificates`);
-        this.removeCerts(deleted);
-        return Promise.resolve();
+        await this.removeCerts(deleted);
     }
 
     /**
      * Downloads the attachment data of the given record. Does not retry,
      * leaving that to the caller.
      * @param  {AttachmentRecord} record The data to obtain
      * @return {Promise}          resolves to a Uint8Array on success
      */
@@ -190,114 +203,122 @@ this.RemoteSecuritySettings = class Remo
 
     /**
      * Attempts to download the attachment, assuming it's not been processed
      * already. Does not retry, and always resolves (e.g., does not reject upon
      * failure.) Errors are reported via Cu.reportError; If you need to know
      * success/failure, check record.cert_import_complete.
      * @param  {AttachmentRecord} record defines which data to obtain
      * @param  {KintoCollection}  col The kinto collection to update
-     * @param  {nsIX509CertDB}    certdb The NSS DB to update
+     * @param  {nsICertStorage}   certStorage The certificate storage to update
      * @return {Promise}          a Promise representing the transaction
      */
-    async maybeDownloadAttachment(record, col, certdb) {
+    async maybeDownloadAttachment(record, col, certStorage) {
       const {attachment: {hash, size}} = record;
 
       return this._downloadAttachmentBytes(record)
-      .then(function(attachmentData) {
+      .then(async function(attachmentData) {
         if (!attachmentData || attachmentData.length == 0) {
           // Bug 1519273 - Log telemetry for these rejections
           log.debug(`Empty attachment. Hash=${hash}`);
 
           Services.telemetry.getHistogramById(INTERMEDIATES_ERRORS_TELEMETRY)
             .add("emptyAttachment");
 
-          return Promise.reject();
+          return;
         }
 
         // check the length
         if (attachmentData.length !== size) {
           log.debug(`Unexpected attachment length. Hash=${hash} Lengths ${attachmentData.length} != ${size}`);
 
           Services.telemetry.getHistogramById(INTERMEDIATES_ERRORS_TELEMETRY)
             .add("unexpectedLength");
 
-          return Promise.reject();
+          return;
         }
 
         // check the hash
         let dataAsString = gTextDecoder.decode(attachmentData);
         let calculatedHash = getHash(dataAsString);
         if (calculatedHash !== hash) {
           log.warn(`Invalid hash. CalculatedHash=${calculatedHash}, Hash=${hash}, data=${dataAsString}`);
 
           Services.telemetry.getHistogramById(INTERMEDIATES_ERRORS_TELEMETRY)
             .add("unexpectedHash");
 
-          return Promise.reject();
+          return;
         }
 
-        // split off the header and footer, base64 decode, construct the cert
-        // from the resulting DER data.
-        let b64data = dataAsString.split("-----")[2].replace(/\s/g, "");
-        let certDer = atob(b64data);
-
+        let certBase64;
+        let subjectBase64;
         try {
-          log.debug(`Adding cert. Hash=${hash}. Size=${size}`);
+          // split off the header and footer
+          certBase64 = dataAsString.split("-----")[2].replace(/\s/g, "");
+          // get an array of bytes so we can use X509.jsm
+          let certBytes = stringToBytes(atob(certBase64));
+          let cert = new X509.Certificate();
+          cert.parse(certBytes);
+          // get the DER-encoded subject and get a base64-encoded string from it
+          // TODO(bug 1542028): add getters for _der and _bytes
+          subjectBase64 = btoa(bytesToString(cert.tbsCertificate.subject._der._bytes));
+        } catch (err) {
+          Cu.reportError(`Failed to decode cert: ${err}`);
 
-          // We can assume that roots obtained from remote-settings are part of
-          // the root program. If they aren't, they won't be used for path-
-          // building or have trust anyway, so just add it to the DB.
-          certdb.addCert(certDer, ",,");
-        } catch (err) {
-          Cu.reportError(`Failed to update CertDB: ${err}`);
-
+          // Re-purpose the "failedToUpdateNSS" telemetry tag as "failed to
+          // decode preloaded intermediate certificate"
           Services.telemetry.getHistogramById(INTERMEDIATES_ERRORS_TELEMETRY)
             .add("failedToUpdateNSS");
 
-          return Promise.reject();
+          return;
+        }
+        log.debug(`Adding cert. Hash=${hash}. Size=${size}`);
+        // We can assume that certs obtained from remote-settings are part of
+        // the root program. If they aren't, they won't be used for path-
+        // building anyway, so just add it to the DB with trust set to
+        // "inherit".
+        let result = await new Promise((resolve) => {
+          certStorage.addCertBySubject(certBase64, subjectBase64,
+                                       Ci.nsICertStorage.TRUST_INHERIT,
+                                       resolve);
+        });
+        if (result != Cr.NS_OK) {
+          Cu.reportError(`Failed to add to cert storage: ${result}`);
+          Services.telemetry.getHistogramById(INTERMEDIATES_ERRORS_TELEMETRY)
+            .add("failedToUpdateDB");
+          return;
         }
 
         record.cert_import_complete = true;
-        return col.update(record);
+        await col.update(record);
       })
       .catch(() => {
         // Don't abort the outer Promise.all because of an error. Errors were
         // sent using Cu.reportError()
         Services.telemetry.getHistogramById(INTERMEDIATES_ERRORS_TELEMETRY)
           .add("failedToDownloadMisc");
       });
     }
 
     async maybeSync(expectedTimestamp, options) {
       return this.client.maybeSync(expectedTimestamp, options);
     }
 
-    // Note that removing certificates from the DB will likely not have an
-    // effect until restart.
-    removeCerts(records) {
-      let recordsToRemove = records;
-
-      let certdb = Cc["@mozilla.org/security/x509certdb;1"].getService(Ci.nsIX509CertDB);
-
-      for (let cert of certdb.getCerts().getEnumerator()) {
-        let certHash = stripColons(cert.sha256Fingerprint);
-        for (let i = 0; i < recordsToRemove.length; i++) {
-          let record = recordsToRemove[i];
-          if (record.pubKeyHash == certHash) {
-            try {
-              certdb.deleteCertificate(cert);
-              recordsToRemove.splice(i, 1);
-            } catch (err) {
-              Cu.reportError(`Failed to remove intermediate certificate Hash=${certHash}: ${err}`);
-            }
-            break;
-          }
+    async removeCerts(recordsToRemove) {
+      let certStorage = Cc["@mozilla.org/security/certstorage;1"].getService(Ci.nsICertStorage);
+      let failures = 0;
+      for (let record of recordsToRemove) {
+        let result = await new Promise((resolve) => {
+          certStorage.removeCertByHash(record.pubKeyHash, resolve);
+        });
+        if (result != Cr.NS_OK) {
+          Cu.reportError(`Failed to remove intermediate certificate Hash=${record.pubKeyHash}: ${result}`);
+          failures++;
         }
       }
 
-      if (recordsToRemove.length > 0) {
-        Cu.reportError(`Failed to remove ${recordsToRemove.length} intermediate certificates`);
+      if (failures > 0) {
+        Cu.reportError(`Failed to remove ${failures} intermediate certificates`);
         Services.telemetry.getHistogramById(INTERMEDIATES_ERRORS_TELEMETRY)
           .add("failedToRemove");
       }
     }
 };
--- a/security/manager/ssl/X509.jsm
+++ b/security/manager/ssl/X509.jsm
@@ -1,17 +1,15 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 "use strict";
 
-// Until DER.jsm is actually used in production code, this is where we have to
-// import it from.
-var { DER } = ChromeUtils.import("resource://testing-common/psm/DER.jsm", null);
+var { DER } = ChromeUtils.import("resource://gre/modules/psm/DER.jsm", null);
 
 const ERROR_UNSUPPORTED_ASN1 = "unsupported asn.1";
 const ERROR_TIME_NOT_VALID = "Time not valid";
 const ERROR_LIBRARY_FAILURE = "library failure";
 
 const X509v3 = 2;
 
 /**
--- a/security/manager/ssl/cert_storage/Cargo.toml
+++ b/security/manager/ssl/cert_storage/Cargo.toml
@@ -1,15 +1,16 @@
 [package]
 name = "cert_storage"
 version = "0.0.1"
 authors = ["Dana Keeler <dkeeler@mozilla.com>", "Mark Goodwin <mgoodwin@mozilla.com"]
 
 [dependencies]
 base64 = "0.10"
+byteorder = "1.2.7"
 crossbeam-utils = "0.6.3"
 lmdb-rkv = "0.11"
 log = "0.4"
 moz_task = { path = "../../../../xpcom/rust/moz_task" }
 nserror = { path = "../../../../xpcom/rust/nserror" }
 nsstring = { path = "../../../../xpcom/rust/nsstring" }
 rkv = "^0.9"
 sha2 = "^0.8"
--- a/security/manager/ssl/cert_storage/src/lib.rs
+++ b/security/manager/ssl/cert_storage/src/lib.rs
@@ -1,43 +1,47 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 extern crate base64;
+extern crate byteorder;
 extern crate crossbeam_utils;
 extern crate lmdb;
 #[macro_use]
 extern crate log;
 extern crate moz_task;
 extern crate nserror;
 extern crate nsstring;
 extern crate rkv;
 extern crate sha2;
 extern crate thin_vec;
 extern crate time;
 #[macro_use]
 extern crate xpcom;
 extern crate style;
 
+use byteorder::{NetworkEndian, ReadBytesExt, WriteBytesExt};
 use crossbeam_utils::atomic::AtomicCell;
 use lmdb::EnvironmentFlags;
 use moz_task::{create_thread, is_main_thread, Task, TaskRunnable};
 use nserror::{
     nsresult, NS_ERROR_FAILURE, NS_ERROR_NOT_SAME_THREAD, NS_ERROR_NO_AGGREGATION,
     NS_ERROR_UNEXPECTED, NS_OK,
 };
 use nsstring::{nsACString, nsAString, nsCStr, nsCString, nsString};
+use rkv::error::StoreError;
 use rkv::{Rkv, SingleStore, StoreOptions, Value};
 use sha2::{Digest, Sha256};
 use std::collections::HashMap;
 use std::ffi::{CStr, CString};
 use std::fmt::Display;
 use std::fs::{create_dir_all, remove_file, File};
 use std::io::{BufRead, BufReader};
+use std::mem::size_of;
 use std::os::raw::c_char;
 use std::path::PathBuf;
 use std::slice;
 use std::str;
 use std::sync::{Arc, Mutex, RwLock};
 use std::time::{Duration, SystemTime};
 use thin_vec::ThinVec;
 use xpcom::interfaces::{
@@ -46,22 +50,27 @@ use xpcom::interfaces::{
     nsISupports, nsIThread,
 };
 use xpcom::{nsIID, GetterAddrefs, RefPtr, ThreadBoundRefPtr, XpCom};
 
 const PREFIX_REV_IS: &str = "is";
 const PREFIX_REV_SPK: &str = "spk";
 const PREFIX_CRLITE: &str = "crlite";
 const PREFIX_WL: &str = "wl";
+const PREFIX_SUBJECT: &str = "subject";
+const PREFIX_CERT: &str = "cert";
 
-fn make_key(prefix: &str, part_a: &[u8], part_b: &[u8]) -> Vec<u8> {
-    let mut key = prefix.as_bytes().to_owned();
-    key.extend_from_slice(part_a);
-    key.extend_from_slice(part_b);
-    key
+macro_rules! make_key {
+    ( $prefix:expr, $( $part:expr ),+ ) => {
+        {
+            let mut key = $prefix.as_bytes().to_owned();
+            $( key.extend_from_slice($part); )+
+            key
+        }
+    }
 }
 
 #[allow(non_camel_case_types, non_snake_case)]
 
 /// `SecurityStateError` is a type to represent errors in accessing or
 /// modifying security state.
 #[derive(Debug)]
 struct SecurityStateError {
@@ -109,17 +118,20 @@ impl SecurityState {
         if self.env_and_store.is_some() {
             return Ok(());
         }
 
         let store_path = get_store_path(&self.profile_path)?;
 
         // Open the store in read-write mode initially to create it (if needed)
         // and migrate data from the old store (if any).
-        let env = Rkv::new(store_path.as_path())?;
+        let mut builder = Rkv::environment_builder();
+        builder.set_max_dbs(2);
+        builder.set_map_size(16777216); // 16MB
+        let env = Rkv::from_env(store_path.as_path(), builder)?;
         let store = env.open_single("cert_storage", StoreOptions::create())?;
 
         // if the profile has a revocations.txt, migrate it and remove the file
         let mut revocations_path = self.profile_path.clone();
         revocations_path.push("revocations.txt");
         if revocations_path.exists() {
             SecurityState::migrate(&revocations_path, &env, &store)?;
             remove_file(revocations_path)?;
@@ -178,23 +190,23 @@ impl SecurityState {
             let l_sans_prefix = match base64::decode(&l[1..]) {
                 Ok(decoded) => decoded,
                 Err(_) => continue,
             };
             if let Some(name) = &dn {
                 if leading_char == '\t' {
                     let _ = store.put(
                         &mut writer,
-                        &make_key(PREFIX_REV_SPK, name, &l_sans_prefix),
+                        &make_key!(PREFIX_REV_SPK, name, &l_sans_prefix),
                         &value,
                     );
                 } else {
                     let _ = store.put(
                         &mut writer,
-                        &make_key(PREFIX_REV_IS, name, &l_sans_prefix),
+                        &make_key!(PREFIX_REV_IS, name, &l_sans_prefix),
                         &value,
                     );
                 }
             }
         }
 
         writer.commit()?;
         Ok(())
@@ -202,17 +214,20 @@ impl SecurityState {
 
     fn reopen_store_read_write(&mut self) -> Result<(), SecurityStateError> {
         let store_path = get_store_path(&self.profile_path)?;
 
         // Move out and drop the EnvAndStore first so we don't have
         // two LMDB environments open at the same time.
         drop(self.env_and_store.take());
 
-        let env = Rkv::new(store_path.as_path())?;
+        let mut builder = Rkv::environment_builder();
+        builder.set_max_dbs(2);
+        builder.set_map_size(16777216); // 16MB
+        let env = Rkv::from_env(store_path.as_path(), builder)?;
         let store = env.open_single("cert_storage", StoreOptions::create())?;
         self.env_and_store.replace(EnvAndStore { env, store });
         Ok(())
     }
 
     fn reopen_store_read_only(&mut self) -> Result<(), SecurityStateError> {
         let store_path = get_store_path(&self.profile_path)?;
 
@@ -255,17 +270,20 @@ impl SecurityState {
         let reader = env_and_store.env.read()?;
         match env_and_store.store.get(&reader, key) {
             Ok(Some(Value::I64(i)))
                 if i <= (std::i16::MAX as i64) && i >= (std::i16::MIN as i64) =>
             {
                 Ok(Some(i as i16))
             }
             Ok(None) => Ok(None),
-            _ => Err(SecurityStateError::from(
+            Ok(_) => Err(SecurityStateError::from(
+                "Unexpected type when trying to get a Value::I64",
+            )),
+            Err(_) => Err(SecurityStateError::from(
                 "There was a problem getting the value",
             )),
         }
     }
 
     pub fn set_revocations(
         &mut self,
         entries: &[(Vec<u8>, i16)],
@@ -291,41 +309,41 @@ impl SecurityState {
     }
 
     pub fn set_enrollment(
         &mut self,
         issuer: &[u8],
         serial: &[u8],
         state: i16,
     ) -> Result<(), SecurityStateError> {
-        self.write_entry(&make_key(PREFIX_CRLITE, issuer, serial), state)
+        self.write_entry(&make_key!(PREFIX_CRLITE, issuer, serial), state)
     }
 
     pub fn set_whitelist(
         &mut self,
         issuer: &[u8],
         serial: &[u8],
         state: i16,
     ) -> Result<(), SecurityStateError> {
-        self.write_entry(&make_key(PREFIX_WL, issuer, serial), state)
+        self.write_entry(&make_key!(PREFIX_WL, issuer, serial), state)
     }
 
     pub fn get_revocation_state(
         &self,
         issuer: &[u8],
         serial: &[u8],
         subject: &[u8],
         pub_key: &[u8],
     ) -> Result<i16, SecurityStateError> {
         let mut digest = Sha256::default();
         digest.input(pub_key);
         let pub_key_hash = digest.result();
 
-        let subject_pubkey = make_key(PREFIX_REV_SPK, subject, &pub_key_hash);
-        let issuer_serial = make_key(PREFIX_REV_IS, issuer, serial);
+        let subject_pubkey = make_key!(PREFIX_REV_SPK, subject, &pub_key_hash);
+        let issuer_serial = make_key!(PREFIX_REV_IS, issuer, serial);
 
         let st: i16 = match self.read_entry(&issuer_serial) {
             Ok(Some(value)) => value,
             Ok(None) => nsICertStorage::STATE_UNSET as i16,
             Err(_) => {
                 return Err(SecurityStateError::from(
                     "problem reading revocation state (from issuer / serial)",
                 ));
@@ -347,30 +365,30 @@ impl SecurityState {
         }
     }
 
     pub fn get_enrollment_state(
         &self,
         issuer: &[u8],
         serial: &[u8],
     ) -> Result<i16, SecurityStateError> {
-        let issuer_serial = make_key(PREFIX_CRLITE, issuer, serial);
+        let issuer_serial = make_key!(PREFIX_CRLITE, issuer, serial);
         match self.read_entry(&issuer_serial) {
             Ok(Some(value)) => Ok(value),
             Ok(None) => Ok(nsICertStorage::STATE_UNSET as i16),
             Err(_) => return Err(SecurityStateError::from("problem reading enrollment state")),
         }
     }
 
     pub fn get_whitelist_state(
         &self,
         issuer: &[u8],
         serial: &[u8],
     ) -> Result<i16, SecurityStateError> {
-        let issuer_serial = make_key(PREFIX_WL, issuer, serial);
+        let issuer_serial = make_key!(PREFIX_WL, issuer, serial);
         match self.read_entry(&issuer_serial) {
             Ok(Some(value)) => Ok(value),
             Ok(None) => Ok(nsICertStorage::STATE_UNSET as i16),
             Err(_) => Err(SecurityStateError::from("problem reading whitelist state")),
         }
     }
 
     pub fn is_data_fresh(
@@ -415,16 +433,320 @@ impl SecurityState {
             "services.blocklist.crlite.checked",
             "security.onecrl.maximum_staleness_in_seconds",
         )
     }
 
     pub fn pref_seen(&mut self, name: &str, value: u32) {
         self.int_prefs.insert(name.to_owned(), value);
     }
+
+    // To store a certificate by subject, we first create a Cert out of the given cert, subject, and
+    // trust. We hash the certificate with sha-256 to obtain a unique* key for that certificate, and
+    // we store the Cert in the database. We also look up or create a CertHashList for the given
+    // subject and add the new certificate's hash if it isn't present in the list. If it wasn't
+    // present, we write out the updated CertHashList.
+    // *By the pigeon-hole principle, there exist collisions for sha-256, so this key is not
+    // actually unique. We rely on the assumption that sha-256 is a cryptographically strong hash.
+    // If an adversary can find two different certificates with the same sha-256 hash, they can
+    // probably forge a sha-256-based signature, so assuming the keys we create here are unique is
+    // not a security issue.
+    pub fn add_cert_by_subject(
+        &mut self,
+        cert_der: &[u8],
+        subject: &[u8],
+        trust: i16,
+    ) -> Result<(), SecurityStateError> {
+        self.reopen_store_read_write()?;
+        {
+            let env_and_store = match self.env_and_store.as_mut() {
+                Some(env_and_store) => env_and_store,
+                None => return Err(SecurityStateError::from("env and store not initialized?")),
+            };
+            let mut writer = env_and_store.env.write()?;
+
+            let mut digest = Sha256::default();
+            digest.input(cert_der);
+            let cert_hash = digest.result();
+            let cert_key = make_key!(PREFIX_CERT, &cert_hash);
+            let cert = Cert::new(cert_der, subject, trust)?;
+            env_and_store
+                .store
+                .put(&mut writer, &cert_key, &Value::Blob(&cert.to_bytes()?))?;
+            let subject_key = make_key!(PREFIX_SUBJECT, subject);
+            // This reader will only be able to "see" data outside the current transaction. This is
+            // fine, though, because what we're reading has not yet been touched by this
+            // transaction.
+            let reader = env_and_store.env.read()?;
+            let empty_vec = Vec::new();
+            let old_cert_hash_list = match env_and_store.store.get(&reader, &subject_key)? {
+                Some(Value::Blob(hashes)) => hashes,
+                Some(_) => &empty_vec,
+                None => &empty_vec,
+            };
+            let new_cert_hash_list = CertHashList::add(old_cert_hash_list, &cert_hash)?;
+            if new_cert_hash_list.len() != old_cert_hash_list.len() {
+                env_and_store.store.put(
+                    &mut writer,
+                    &subject_key,
+                    &Value::Blob(&new_cert_hash_list),
+                )?;
+            }
+
+            writer.commit()?;
+        }
+        self.reopen_store_read_only()?;
+        Ok(())
+    }
+
+    // Given a certificate's sha-256 hash, we can look up its Cert entry in the database. We use
+    // this to find its subject so we can look up the CertHashList it should appear in. If that list
+    // contains the given hash, we remove it and update the CertHashList. Finally we delete the Cert
+    // entry.
+    pub fn remove_cert_by_hash(&mut self, hash: &[u8]) -> Result<(), SecurityStateError> {
+        self.reopen_store_read_write()?;
+        {
+            let env_and_store = match self.env_and_store.as_mut() {
+                Some(env_and_store) => env_and_store,
+                None => return Err(SecurityStateError::from("env and store not initialized?")),
+            };
+            let mut writer = env_and_store.env.write()?;
+
+            let reader = env_and_store.env.read()?;
+            let cert_key = make_key!(PREFIX_CERT, hash);
+            if let Some(Value::Blob(cert_bytes)) = env_and_store.store.get(&reader, &cert_key)? {
+                if let Ok(cert) = Cert::from_bytes(cert_bytes) {
+                    let subject_key = make_key!(PREFIX_SUBJECT, &cert.subject);
+                    let empty_vec = Vec::new();
+                    let old_cert_hash_list = match env_and_store.store.get(&reader, &subject_key)? {
+                        Some(Value::Blob(hashes)) => hashes,
+                        Some(_) => &empty_vec,
+                        None => &empty_vec,
+                    };
+                    let new_cert_hash_list = CertHashList::remove(old_cert_hash_list, hash)?;
+                    if new_cert_hash_list.len() != old_cert_hash_list.len() {
+                        env_and_store.store.put(
+                            &mut writer,
+                            &subject_key,
+                            &Value::Blob(&new_cert_hash_list),
+                        )?;
+                    }
+                }
+            }
+            match env_and_store.store.delete(&mut writer, &cert_key) {
+                Ok(()) => {}
+                Err(StoreError::LmdbError(lmdb::Error::NotFound)) => {}
+                Err(e) => return Err(SecurityStateError::from(e)),
+            };
+            writer.commit()?;
+        }
+        self.reopen_store_read_only()?;
+        Ok(())
+    }
+
+    // Given a certificate's subject, we look up the corresponding CertHashList. In theory, each
+    // hash in that list corresponds to a certificate with the given subject, so we look up each of
+    // these (assuming the database is consistent and contains them) and add them to the given list.
+    // If we encounter an inconsistency, we continue looking as best we can.
+    pub fn find_certs_by_subject(
+        &self,
+        subject: &[u8],
+        certs: &mut ThinVec<ThinVec<u8>>,
+    ) -> Result<(), SecurityStateError> {
+        let env_and_store = match self.env_and_store.as_ref() {
+            Some(env_and_store) => env_and_store,
+            None => return Err(SecurityStateError::from("env and store not initialized?")),
+        };
+        let reader = env_and_store.env.read()?;
+        certs.clear();
+        let subject_key = make_key!(PREFIX_SUBJECT, subject);
+        let empty_vec = Vec::new();
+        let cert_hash_list_bytes = match env_and_store.store.get(&reader, &subject_key)? {
+            Some(Value::Blob(hashes)) => hashes,
+            Some(_) => &empty_vec,
+            None => &empty_vec,
+        };
+        let cert_hash_list = CertHashList::new(cert_hash_list_bytes)?;
+        for cert_hash in cert_hash_list.into_iter() {
+            let cert_key = make_key!(PREFIX_CERT, cert_hash);
+            // If there's some inconsistency, we don't want to fail the whole operation - just go
+            // for best effort and find as many certificates as we can.
+            if let Some(Value::Blob(cert_bytes)) = env_and_store.store.get(&reader, &cert_key)? {
+                if let Ok(cert) = Cert::from_bytes(cert_bytes) {
+                    let mut thin_vec_cert = ThinVec::with_capacity(cert.der.len());
+                    thin_vec_cert.extend_from_slice(&cert.der);
+                    certs.push(thin_vec_cert);
+                }
+            }
+        }
+        Ok(())
+    }
+}
+
+const CERT_SERIALIZATION_VERSION_1: u8 = 1;
+
+// A Cert consists of its DER encoding, its DER-encoded subject, and its trust (currently
+// nsICertStorage::TRUST_INHERIT, but in the future nsICertStorage::TRUST_ANCHOR may also be used).
+// The length of each encoding must be representable by a u16 (so 65535 bytes is the longest a
+// certificate can be).
+struct Cert<'a> {
+    der: &'a [u8],
+    subject: &'a [u8],
+    trust: i16,
+}
+
+impl<'a> Cert<'a> {
+    fn new(der: &'a [u8], subject: &'a [u8], trust: i16) -> Result<Cert<'a>, SecurityStateError> {
+        if der.len() > u16::max as usize {
+            return Err(SecurityStateError::from("certificate is too long"));
+        }
+        if subject.len() > u16::max as usize {
+            return Err(SecurityStateError::from("subject is too long"));
+        }
+        Ok(Cert {
+            der,
+            subject,
+            trust,
+        })
+    }
+
+    fn from_bytes(encoded: &'a [u8]) -> Result<Cert<'a>, SecurityStateError> {
+        if encoded.len() < size_of::<u8>() {
+            return Err(SecurityStateError::from("invalid Cert: no version?"));
+        }
+        let (mut version, rest) = encoded.split_at(size_of::<u8>());
+        let version = version.read_u8()?;
+        if version != CERT_SERIALIZATION_VERSION_1 {
+            return Err(SecurityStateError::from("invalid Cert: unexpected version"));
+        }
+
+        if rest.len() < size_of::<u16>() {
+            return Err(SecurityStateError::from("invalid Cert: no der len?"));
+        }
+        let (mut der_len, rest) = rest.split_at(size_of::<u16>());
+        let der_len = der_len.read_u16::<NetworkEndian>()? as usize;
+        if rest.len() < der_len {
+            return Err(SecurityStateError::from("invalid Cert: no der?"));
+        }
+        let (der, rest) = rest.split_at(der_len);
+
+        if rest.len() < size_of::<u16>() {
+            return Err(SecurityStateError::from("invalid Cert: no subject len?"));
+        }
+        let (mut subject_len, rest) = rest.split_at(size_of::<u16>());
+        let subject_len = subject_len.read_u16::<NetworkEndian>()? as usize;
+        if rest.len() < subject_len {
+            return Err(SecurityStateError::from("invalid Cert: no subject?"));
+        }
+        let (subject, mut rest) = rest.split_at(subject_len);
+
+        if rest.len() < size_of::<i16>() {
+            return Err(SecurityStateError::from("invalid Cert: no trust?"));
+        }
+        let trust = rest.read_i16::<NetworkEndian>()?;
+        if rest.len() > 0 {
+            return Err(SecurityStateError::from("invalid Cert: trailing data?"));
+        }
+
+        Ok(Cert {
+            der,
+            subject,
+            trust,
+        })
+    }
+
+    fn to_bytes(&self) -> Result<Vec<u8>, SecurityStateError> {
+        let mut bytes = Vec::with_capacity(
+            size_of::<u8>()
+                + size_of::<u16>()
+                + self.der.len()
+                + size_of::<u16>()
+                + self.subject.len()
+                + size_of::<i16>(),
+        );
+        bytes.write_u8(CERT_SERIALIZATION_VERSION_1)?;
+        if self.der.len() > u16::max as usize {
+            return Err(SecurityStateError::from("certificate is too long"));
+        }
+        bytes.write_u16::<NetworkEndian>(self.der.len() as u16)?;
+        bytes.extend_from_slice(&self.der);
+        if self.subject.len() > u16::max as usize {
+            return Err(SecurityStateError::from("subject is too long"));
+        }
+        bytes.write_u16::<NetworkEndian>(self.subject.len() as u16)?;
+        bytes.extend_from_slice(&self.subject);
+        bytes.write_i16::<NetworkEndian>(self.trust)?;
+        Ok(bytes)
+    }
+}
+
+// A CertHashList is a list of sha-256 hashes of DER-encoded certificates.
+struct CertHashList<'a> {
+    hashes: Vec<&'a [u8]>,
+}
+
+impl<'a> CertHashList<'a> {
+    fn new(hashes_bytes: &'a [u8]) -> Result<CertHashList<'a>, SecurityStateError> {
+        if hashes_bytes.len() % Sha256::output_size() != 0 {
+            return Err(SecurityStateError::from(
+                "unexpected length for cert hash list",
+            ));
+        }
+        let mut hashes = Vec::with_capacity(hashes_bytes.len() / Sha256::output_size());
+        for hash in hashes_bytes.chunks_exact(Sha256::output_size()) {
+            hashes.push(hash);
+        }
+        Ok(CertHashList { hashes })
+    }
+
+    fn add(hashes_bytes: &[u8], new_hash: &[u8]) -> Result<Vec<u8>, SecurityStateError> {
+        if hashes_bytes.len() % Sha256::output_size() != 0 {
+            return Err(SecurityStateError::from(
+                "unexpected length for cert hash list",
+            ));
+        }
+        if new_hash.len() != Sha256::output_size() {
+            return Err(SecurityStateError::from("unexpected cert hash length"));
+        }
+        for hash in hashes_bytes.chunks_exact(Sha256::output_size()) {
+            if hash == new_hash {
+                return Ok(hashes_bytes.to_owned());
+            }
+        }
+        let mut combined = hashes_bytes.to_owned();
+        combined.extend_from_slice(new_hash);
+        Ok(combined)
+    }
+
+    fn remove(hashes_bytes: &[u8], cert_hash: &[u8]) -> Result<Vec<u8>, SecurityStateError> {
+        if hashes_bytes.len() % Sha256::output_size() != 0 {
+            return Err(SecurityStateError::from(
+                "unexpected length for cert hash list",
+            ));
+        }
+        if cert_hash.len() != Sha256::output_size() {
+            return Err(SecurityStateError::from("unexpected cert hash length"));
+        }
+        let mut result = Vec::with_capacity(hashes_bytes.len());
+        for hash in hashes_bytes.chunks_exact(Sha256::output_size()) {
+            if hash != cert_hash {
+                result.extend_from_slice(hash);
+            }
+        }
+        Ok(result)
+    }
+}
+
+impl<'a> IntoIterator for CertHashList<'a> {
+    type Item = &'a [u8];
+    type IntoIter = std::vec::IntoIter<&'a [u8]>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.hashes.into_iter()
+    }
 }
 
 fn get_path_from_directory_service(key: &str) -> Result<PathBuf, SecurityStateError> {
     let directory_service = match xpcom::services::get_DirectoryService() {
         Some(ds) => ds,
         _ => return Err(SecurityStateError::from("None")),
     };
 
@@ -534,142 +856,64 @@ fn read_int_pref(name: &str) -> Result<u
     };
     if pref_value < 0 {
         Ok(0)
     } else {
         Ok(pref_value as u32)
     }
 }
 
-// This is a helper for defining a task that will perform a specific action on a background thread.
-// Its arguments are the name of the task and the name of the function in SecurityState to call.
-macro_rules! security_state_task {
-    ($task_name:ident, $security_state_function_name:ident) => {
-        struct $task_name {
-            callback: AtomicCell<Option<ThreadBoundRefPtr<nsICertStorageCallback>>>,
-            security_state: Arc<RwLock<SecurityState>>,
-            argument_a: Vec<u8>,
-            argument_b: Vec<u8>,
-            state: i16,
-            result: AtomicCell<Option<nserror::nsresult>>,
-        }
-        impl $task_name {
-            fn new(
-                callback: &nsICertStorageCallback,
-                security_state: &Arc<RwLock<SecurityState>>,
-                argument_a: Vec<u8>,
-                argument_b: Vec<u8>,
-                state: i16,
-            ) -> $task_name {
-                $task_name {
-                    callback: AtomicCell::new(Some(ThreadBoundRefPtr::new(RefPtr::new(callback)))),
-                    security_state: Arc::clone(security_state),
-                    argument_a,
-                    argument_b,
-                    state,
-                    result: AtomicCell::new(None),
-                }
-            }
-        }
-        impl Task for $task_name {
-            fn run(&self) {
-                let mut ss = match self.security_state.write() {
-                    Ok(ss) => ss,
-                    Err(_) => {
-                        self.result.store(Some(NS_ERROR_FAILURE));
-                        return;
-                    }
-                };
-                // this is a no-op if the DB is already open
-                match ss.open_db() {
-                    Ok(()) => {}
-                    Err(_) => {
-                        self.result.store(Some(NS_ERROR_FAILURE));
-                        return;
-                    }
-                };
-                match ss.$security_state_function_name(
-                    &self.argument_a,
-                    &self.argument_b,
-                    self.state,
-                ) {
-                    Ok(_) => self.result.store(Some(NS_OK)),
-                    Err(_) => self.result.store(Some(NS_ERROR_FAILURE)),
-                };
-            }
-
-            fn done(&self) -> Result<(), nsresult> {
-                let threadbound = self.callback.swap(None).ok_or(NS_ERROR_FAILURE)?;
-                let callback = threadbound.get_ref().ok_or(NS_ERROR_FAILURE)?;
-                let nsrv = match self.result.swap(None) {
-                    Some(result) => unsafe { callback.Done(result) },
-                    None => unsafe { callback.Done(NS_ERROR_FAILURE) },
-                };
-                match nsrv {
-                    NS_OK => Ok(()),
-                    e => Err(e),
-                }
-            }
-        }
-    };
+// This is a helper for creating a task that will perform a specific action on a background thread.
+struct SecurityStateTask<F: FnOnce(&mut SecurityState) -> Result<(), SecurityStateError>> {
+    callback: AtomicCell<Option<ThreadBoundRefPtr<nsICertStorageCallback>>>,
+    security_state: Arc<RwLock<SecurityState>>,
+    result: AtomicCell<nserror::nsresult>,
+    task_action: AtomicCell<Option<F>>,
 }
 
-security_state_task!(SetEnrollmentTask, set_enrollment);
-security_state_task!(SetWhitelistTask, set_whitelist);
-
-struct SetRevocationsTask {
-    callback: AtomicCell<Option<ThreadBoundRefPtr<nsICertStorageCallback>>>,
-    security_state: Arc<RwLock<SecurityState>>,
-    entries: Vec<(Vec<u8>, i16)>,
-    result: AtomicCell<Option<nserror::nsresult>>,
-}
-impl SetRevocationsTask {
+impl<F: FnOnce(&mut SecurityState) -> Result<(), SecurityStateError>> SecurityStateTask<F> {
     fn new(
         callback: &nsICertStorageCallback,
         security_state: &Arc<RwLock<SecurityState>>,
-        entries: Vec<(Vec<u8>, i16)>,
-    ) -> SetRevocationsTask {
-        SetRevocationsTask {
+        task_action: F,
+    ) -> SecurityStateTask<F> {
+        SecurityStateTask {
             callback: AtomicCell::new(Some(ThreadBoundRefPtr::new(RefPtr::new(callback)))),
             security_state: Arc::clone(security_state),
-            entries,
-            result: AtomicCell::new(None),
+            result: AtomicCell::new(NS_ERROR_FAILURE),
+            task_action: AtomicCell::new(Some(task_action)),
         }
     }
 }
-impl Task for SetRevocationsTask {
+
+impl<F: FnOnce(&mut SecurityState) -> Result<(), SecurityStateError>> Task
+    for SecurityStateTask<F>
+{
     fn run(&self) {
         let mut ss = match self.security_state.write() {
             Ok(ss) => ss,
-            Err(_) => {
-                self.result.store(Some(NS_ERROR_FAILURE));
-                return;
-            }
+            Err(_) => return,
         };
         // this is a no-op if the DB is already open
-        match ss.open_db() {
-            Ok(()) => {}
-            Err(_) => {
-                self.result.store(Some(NS_ERROR_FAILURE));
-                return;
-            }
-        };
-        match ss.set_revocations(&self.entries) {
-            Ok(_) => self.result.store(Some(NS_OK)),
-            Err(_) => self.result.store(Some(NS_ERROR_FAILURE)),
-        };
+        if ss.open_db().is_err() {
+            return;
+        }
+        if let Some(task_action) = self.task_action.swap(None) {
+            let rv = task_action(&mut ss)
+                .and_then(|_| Ok(NS_OK))
+                .unwrap_or(NS_ERROR_FAILURE);
+            self.result.store(rv);
+        }
     }
 
     fn done(&self) -> Result<(), nsresult> {
         let threadbound = self.callback.swap(None).ok_or(NS_ERROR_FAILURE)?;
         let callback = threadbound.get_ref().ok_or(NS_ERROR_FAILURE)?;
-        let nsrv = match self.result.swap(None) {
-            Some(result) => unsafe { callback.Done(result) },
-            None => unsafe { callback.Done(NS_ERROR_FAILURE) },
-        };
+        let result = self.result.swap(NS_ERROR_FAILURE);
+        let nsrv = unsafe { callback.Done(result) };
         match nsrv {
             NS_OK => Ok(()),
             e => Err(e),
         }
     }
 }
 
 #[no_mangle]
@@ -704,16 +948,39 @@ macro_rules! try_ns {
             Err(err) => {
                 error!("{}", err);
                 continue;
             }
         }
     };
 }
 
+// This macro is a way to ensure the DB has been opened while minimizing lock acquisitions in the
+// common (read-only) case. First we acquire a read lock and see if we even need to open the DB. If
+// not, we can continue with the read lock we already have. Otherwise, we drop the read lock,
+// acquire the write lock, open the DB, drop the write lock, and re-acquire the read lock. While it
+// is possible for two or more threads to all come to the conclusion that they need to open the DB,
+// this isn't ultimately an issue - `open_db` will exit early if another thread has already done the
+// work.
+macro_rules! get_security_state {
+    ($self:expr) => {{
+        let ss_read_only = try_ns!($self.security_state.read());
+        if !ss_read_only.db_needs_opening() {
+            ss_read_only
+        } else {
+            drop(ss_read_only);
+            {
+                let mut ss_write = try_ns!($self.security_state.write());
+                try_ns!(ss_write.open_db());
+            }
+            try_ns!($self.security_state.read())
+        }
+    }};
+}
+
 #[derive(xpcom)]
 #[xpimplements(nsICertStorage, nsIObserver)]
 #[refcnt = "atomic"]
 struct InitCertStorage {
     security_state: Arc<RwLock<SecurityState>>,
     thread: Mutex<RefPtr<nsIThread>>,
 }
 
@@ -789,36 +1056,36 @@ impl CertStorage {
                 let mut issuer = nsCString::new();
                 try_ns!(revocation.GetIssuer(&mut *issuer).to_result(), or continue);
                 let issuer = try_ns!(base64::decode(&issuer), or continue);
 
                 let mut serial = nsCString::new();
                 try_ns!(revocation.GetSerial(&mut *serial).to_result(), or continue);
                 let serial = try_ns!(base64::decode(&serial), or continue);
 
-                entries.push((make_key(PREFIX_REV_IS, &issuer, &serial), state));
+                entries.push((make_key!(PREFIX_REV_IS, &issuer, &serial), state));
             } else if let Some(revocation) =
                 (*revocation).query_interface::<nsISubjectAndPubKeyRevocationState>()
             {
                 let mut subject = nsCString::new();
                 try_ns!(revocation.GetSubject(&mut *subject).to_result(), or continue);
                 let subject = try_ns!(base64::decode(&subject), or continue);
 
                 let mut pub_key_hash = nsCString::new();
                 try_ns!(revocation.GetPubKey(&mut *pub_key_hash).to_result(), or continue);
                 let pub_key_hash = try_ns!(base64::decode(&pub_key_hash), or continue);
 
-                entries.push((make_key(PREFIX_REV_SPK, &subject, &pub_key_hash), state));
+                entries.push((make_key!(PREFIX_REV_SPK, &subject, &pub_key_hash), state));
             }
         }
 
-        let task = Box::new(SetRevocationsTask::new(
+        let task = Box::new(SecurityStateTask::new(
             &*callback,
             &self.security_state,
-            entries,
+            move |ss| ss.set_revocations(&entries),
         ));
         let thread = try_ns!(self.thread.lock());
         let runnable = try_ns!(TaskRunnable::new("SetRevocations", task));
         try_ns!(runnable.dispatch(&*thread));
         NS_OK
     }
 
     unsafe fn SetEnrollment(
@@ -831,22 +1098,20 @@ impl CertStorage {
         if !is_main_thread() {
             return NS_ERROR_NOT_SAME_THREAD;
         }
         if issuer.is_null() || serial.is_null() || callback.is_null() {
             return NS_ERROR_FAILURE;
         }
         let issuer_decoded = try_ns!(base64::decode(&*issuer));
         let serial_decoded = try_ns!(base64::decode(&*serial));
-        let task = Box::new(SetEnrollmentTask::new(
+        let task = Box::new(SecurityStateTask::new(
             &*callback,
             &self.security_state,
-            issuer_decoded,
-            serial_decoded,
-            state,
+            move |ss| ss.set_enrollment(&issuer_decoded, &serial_decoded, state),
         ));
         let thread = try_ns!(self.thread.lock());
         let runnable = try_ns!(TaskRunnable::new("SetEnrollment", task));
         try_ns!(runnable.dispatch(&*thread));
         NS_OK
     }
 
     unsafe fn SetWhitelist(
@@ -859,22 +1124,20 @@ impl CertStorage {
         if !is_main_thread() {
             return NS_ERROR_NOT_SAME_THREAD;
         }
         if issuer.is_null() || serial.is_null() || callback.is_null() {
             return NS_ERROR_FAILURE;
         }
         let issuer_decoded = try_ns!(base64::decode(&*issuer));
         let serial_decoded = try_ns!(base64::decode(&*serial));
-        let task = Box::new(SetWhitelistTask::new(
+        let task = Box::new(SecurityStateTask::new(
             &*callback,
             &self.security_state,
-            issuer_decoded,
-            serial_decoded,
-            state,
+            move |ss| ss.set_whitelist(&issuer_decoded, &serial_decoded, state),
         ));
         let thread = try_ns!(self.thread.lock());
         let runnable = try_ns!(TaskRunnable::new("SetWhitelist", task));
         try_ns!(runnable.dispatch(&*thread));
         NS_OK
     }
 
     unsafe fn GetRevocationState(
@@ -886,36 +1149,17 @@ impl CertStorage {
         state: *mut i16,
     ) -> nserror::nsresult {
         // TODO (bug 1541212): We really want to restrict this to non-main-threads only, but we
         // can't do so until bug 1406854 and bug 1534600 are fixed.
         if issuer.is_null() || serial.is_null() || subject.is_null() || pub_key.is_null() {
             return NS_ERROR_FAILURE;
         }
         *state = nsICertStorage::STATE_UNSET as i16;
-        // The following is a way to ensure the DB has been opened while minimizing lock
-        // acquisitions in the common (read-only) case. First we acquire a read lock and see if we
-        // even need to open the DB. If not, we can continue with the read lock we already have.
-        // Otherwise, we drop the read lock, acquire the write lock, open the DB, drop the write
-        // lock, and re-acquire the read lock. While it is possible for two or more threads to all
-        // come to the conclusion that they need to open the DB, this isn't ultimately an issue -
-        // `open_db` will exit early if another thread has already done the work.
-        let ss = {
-            let ss_read_only = try_ns!(self.security_state.read());
-            if !ss_read_only.db_needs_opening() {
-                ss_read_only
-            } else {
-                drop(ss_read_only);
-                {
-                    let mut ss_write = try_ns!(self.security_state.write());
-                    try_ns!(ss_write.open_db());
-                }
-                try_ns!(self.security_state.read())
-            }
-        };
+        let ss = get_security_state!(self);
         match ss.get_revocation_state(&*issuer, &*serial, &*subject, &*pub_key) {
             Ok(st) => {
                 *state = st;
                 NS_OK
             }
             _ => NS_ERROR_FAILURE,
         }
     }
@@ -930,29 +1174,17 @@ impl CertStorage {
             return NS_ERROR_NOT_SAME_THREAD;
         }
         if issuer.is_null() || serial.is_null() {
             return NS_ERROR_FAILURE;
         }
         let issuer_decoded = try_ns!(base64::decode(&*issuer));
         let serial_decoded = try_ns!(base64::decode(&*serial));
         *state = nsICertStorage::STATE_UNSET as i16;
-        let ss = {
-            let ss_read_only = try_ns!(self.security_state.read());
-            if !ss_read_only.db_needs_opening() {
-                ss_read_only
-            } else {
-                drop(ss_read_only);
-                {
-                    let mut ss_write = try_ns!(self.security_state.write());
-                    try_ns!(ss_write.open_db());
-                }
-                try_ns!(self.security_state.read())
-            }
-        };
+        let ss = get_security_state!(self);
         match ss.get_enrollment_state(&issuer_decoded, &serial_decoded) {
             Ok(st) => {
                 *state = st;
                 NS_OK
             }
             _ => NS_ERROR_FAILURE,
         }
     }
@@ -967,29 +1199,17 @@ impl CertStorage {
             return NS_ERROR_NOT_SAME_THREAD;
         }
         if issuer.is_null() || serial.is_null() {
             return NS_ERROR_FAILURE;
         }
         let issuer_decoded = try_ns!(base64::decode(&*issuer));
         let serial_decoded = try_ns!(base64::decode(&*serial));
         *state = nsICertStorage::STATE_UNSET as i16;
-        let ss = {
-            let ss_read_only = try_ns!(self.security_state.read());
-            if !ss_read_only.db_needs_opening() {
-                ss_read_only
-            } else {
-                drop(ss_read_only);
-                {
-                    let mut ss_write = try_ns!(self.security_state.write());
-                    try_ns!(ss_write.open_db());
-                }
-                try_ns!(self.security_state.read())
-            }
-        };
+        let ss = get_security_state!(self);
         match ss.get_whitelist_state(&issuer_decoded, &serial_decoded) {
             Ok(st) => {
                 *state = st;
                 NS_OK
             }
             _ => NS_ERROR_FAILURE,
         }
     }
@@ -1025,16 +1245,82 @@ impl CertStorage {
         *fresh = match ss.is_enrollment_fresh() {
             Ok(is_fresh) => is_fresh,
             Err(_) => false,
         };
 
         NS_OK
     }
 
+    unsafe fn AddCertBySubject(
+        &self,
+        cert: *const nsACString,
+        subject: *const nsACString,
+        trust: i16,
+        callback: *const nsICertStorageCallback,
+    ) -> nserror::nsresult {
+        if !is_main_thread() {
+            return NS_ERROR_NOT_SAME_THREAD;
+        }
+        if cert.is_null() || subject.is_null() || callback.is_null() {
+            return NS_ERROR_FAILURE;
+        }
+        let cert_decoded = try_ns!(base64::decode(&*cert));
+        let subject_decoded = try_ns!(base64::decode(&*subject));
+        let task = Box::new(SecurityStateTask::new(
+            &*callback,
+            &self.security_state,
+            move |ss| ss.add_cert_by_subject(&cert_decoded, &subject_decoded, trust),
+        ));
+        let thread = try_ns!(self.thread.lock());
+        let runnable = try_ns!(TaskRunnable::new("AddCertBySubject", task));
+        try_ns!(runnable.dispatch(&*thread));
+        NS_OK
+    }
+
+    unsafe fn RemoveCertByHash(
+        &self,
+        hash: *const nsACString,
+        callback: *const nsICertStorageCallback,
+    ) -> nserror::nsresult {
+        if !is_main_thread() {
+            return NS_ERROR_NOT_SAME_THREAD;
+        }
+        if hash.is_null() || callback.is_null() {
+            return NS_ERROR_FAILURE;
+        }
+        let hash_decoded = try_ns!(base64::decode(&*hash));
+        let task = Box::new(SecurityStateTask::new(
+            &*callback,
+            &self.security_state,
+            move |ss| ss.remove_cert_by_hash(&hash_decoded),
+        ));
+        let thread = try_ns!(self.thread.lock());
+        let runnable = try_ns!(TaskRunnable::new("RemoveCertByHash", task));
+        try_ns!(runnable.dispatch(&*thread));
+        NS_OK
+    }
+
+    unsafe fn FindCertsBySubject(
+        &self,
+        subject: *const ThinVec<u8>,
+        certs: *mut ThinVec<ThinVec<u8>>,
+    ) -> nserror::nsresult {
+        // TODO (bug 1541212): We really want to restrict this to non-main-threads only, but we
+        // can't do so until bug 1406854 and bug 1534600 are fixed.
+        if subject.is_null() || certs.is_null() {
+            return NS_ERROR_FAILURE;
+        }
+        let ss = get_security_state!(self);
+        match ss.find_certs_by_subject(&*subject, &mut *certs) {
+            Ok(()) => NS_OK,
+            Err(_) => NS_ERROR_FAILURE,
+        }
+    }
+
     unsafe fn Observe(
         &self,
         subject: *const nsISupports,
         topic: *const c_char,
         pref_name: *const i16,
     ) -> nserror::nsresult {
         match CStr::from_ptr(topic).to_str() {
             Ok("nsPref:changed") => {
--- a/security/manager/ssl/moz.build
+++ b/security/manager/ssl/moz.build
@@ -50,27 +50,22 @@ if CONFIG['MOZ_XUL']:
     ]
 
 XPIDL_MODULE = 'pipnss'
 
 XPCOM_MANIFESTS += [
     'components.conf',
 ]
 
-# These aren't actually used in production code yet, so we don't want to
-# ship them with the browser.
-TESTING_JS_MODULES.psm += [
+EXTRA_JS_MODULES.psm += [
     'DER.jsm',
+    'RemoteSecuritySettings.jsm',
     'X509.jsm',
 ]
 
-EXTRA_JS_MODULES.psm += [
-    'RemoteSecuritySettings.jsm',
-]
-
 EXPORTS += [
     'CryptoTask.h',
     'EnterpriseRoots.h',
     'nsClientAuthRemember.h',
     'nsNSSCallbacks.h',
     'nsNSSCertificate.h',
     'nsNSSComponent.h',
     'nsNSSHelper.h',
--- a/security/manager/ssl/nsICertStorage.idl
+++ b/security/manager/ssl/nsICertStorage.idl
@@ -100,17 +100,17 @@ interface nsICertStorage : nsISupports {
   /**
    * Get the revocation state of a certificate. STATE_UNSET indicates the
    * certificate is not revoked. STATE_ENFORCE indicates the certificate is
    * revoked.
    * issuer - issuer name, DER encoded
    * serial - serial number, DER encoded
    * subject - subject name, DER encoded
    * pubkey - public key, DER encoded
-   * Must not be called from the main thread.
+   * Must not be called from the main thread. See bug 1541212.
    */
   [must_use]
   short getRevocationState(in Array<octet> issuer,
                            in Array<octet> serial,
                            in Array<octet> subject,
                            in Array<octet> pubkey);
 
   /**
@@ -154,9 +154,61 @@ interface nsICertStorage : nsISupports {
    /**
     * Check that the CRLite enrollment data is current. Specifically, that the current
     * time is no more than security.onecrl.maximum_staleness_in_seconds seconds
     * after the last crlite enrollment update (as stored in the
     * services.blocklist.crlite.checked pref)
     */
   [must_use]
   boolean isEnrollmentFresh();
+
+  /**
+   * Trust flags to use when adding a adding a certificate.
+   * TRUST_INHERIT indicates a certificate inherits trust from another
+   * certificate.
+   * TRUST_ANCHOR indicates the certificate is a root of trust.
+   */
+  const short TRUST_INHERIT = 0;
+  const short TRUST_ANCHOR = 1;
+
+  /**
+   * Asynchronously add a certificate to the backing storage.
+   * cert is the bytes of the certificate as base64-encoded DER.
+   * subject is the subject distinguished name of the certificate as
+   * base64-encoded DER (although we don't actually validate that the given
+   * certificate has the indicated subject).
+   * trust is one of the TRUST_* constants in this interface.
+   * The given callback is called with the result of the operation when it
+   * completes.
+   * Must only be called from the main thread.
+   */
+  [must_use]
+  void addCertBySubject(in ACString cert,
+                        in ACString subject,
+                        in short trust,
+                        in nsICertStorageCallback callback);
+
+  /**
+   * Asynchronously remove the certificate with the given sha-256 hash from the
+   * backing storage.
+   * hash is the base64-encoded bytes of the sha-256 hash of the certificate's
+   * bytes (DER-encoded).
+   * The given callback is called with the result of the operation when it
+   * completes.
+   * Must only be called from the main thread.
+   */
+  [must_use]
+  void removeCertByHash(in ACString hash,
+                        in nsICertStorageCallback callback);
+
+  /**
+   * Find all certificates in the backing storage with the given subject
+   * distinguished name.
+   * subject is the DER-encoded bytes of the subject distinguished name.
+   * Returns an array of arrays of bytes, where each inner array corresponds to
+   * the DER-encoded bytes of a certificate that has the given subject (although
+   * as these certificates were presumably added via addCertBySubject, this
+   * aspect is never actually valided by nsICertStorage).
+   * Must not be called from the main thread. See bug 1541212.
+   */
+  [must_use]
+  Array<Array<octet> > findCertsBySubject(in Array<octet> subject);
 };
new file mode 100644
--- /dev/null
+++ b/security/manager/ssl/tests/unit/test_cert_storage_direct.js
@@ -0,0 +1,128 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+"use strict";
+
+// This file consists of unit tests for cert_storage (whereas test_cert_storage.js is more of an
+// integration test).
+
+do_get_profile();
+
+var certStorage = Cc["@mozilla.org/security/certstorage;1"].getService(Ci.nsICertStorage);
+
+async function addCertBySubject(cert, subject) {
+  let result = await new Promise((resolve) => {
+    certStorage.addCertBySubject(btoa(cert), btoa(subject), Ci.nsICertStorage.TRUST_INHERIT,
+                                 resolve);
+  });
+  Assert.equal(result, Cr.NS_OK, "addCertBySubject should succeed");
+}
+
+async function removeCertByHash(hashBase64) {
+  let result = await new Promise((resolve) => {
+    certStorage.removeCertByHash(hashBase64, resolve);
+  });
+  Assert.equal(result, Cr.NS_OK, "removeCertByHash should succeed");
+}
+
+function stringToArray(s) {
+  let a = [];
+  for (let i = 0; i < s.length; i++) {
+    a.push(s.charCodeAt(i));
+  }
+  return a;
+}
+
+function arrayToString(a) {
+  let s = "";
+  for (let b of a) {
+    s += String.fromCharCode(b);
+  }
+  return s;
+}
+
+function getLongString(uniquePart, length) {
+  return String(uniquePart).padStart(length, "0");
+}
+
+add_task(async function test_common_subject() {
+  await addCertBySubject("some certificate bytes 1", "some common subject");
+  await addCertBySubject("some certificate bytes 2", "some common subject");
+  await addCertBySubject("some certificate bytes 3", "some common subject");
+  let storedCerts = certStorage.findCertsBySubject(stringToArray("some common subject"));
+  let storedCertsAsStrings = storedCerts.map(arrayToString);
+  let expectedCerts = ["some certificate bytes 1", "some certificate bytes 2",
+                       "some certificate bytes 3"];
+  Assert.deepEqual(storedCertsAsStrings.sort(), expectedCerts.sort(), "should find expected certs");
+
+  await addCertBySubject("some other certificate bytes", "some other subject");
+  storedCerts = certStorage.findCertsBySubject(stringToArray("some common subject"));
+  storedCertsAsStrings = storedCerts.map(arrayToString);
+  Assert.deepEqual(storedCertsAsStrings.sort(), expectedCerts.sort(),
+                   "should still find expected certs");
+
+  let storedOtherCerts = certStorage.findCertsBySubject(stringToArray("some other subject"));
+  let storedOtherCertsAsStrings = storedOtherCerts.map(arrayToString);
+  let expectedOtherCerts = ["some other certificate bytes"];
+  Assert.deepEqual(storedOtherCertsAsStrings, expectedOtherCerts, "should have other certificate");
+});
+
+add_task(async function test_many_entries() {
+  const NUM_CERTS = 500;
+  const CERT_LENGTH = 3000;
+  const SUBJECT_LENGTH = 40;
+  for (let i = 0; i < NUM_CERTS; i++) {
+    await addCertBySubject(getLongString(i, CERT_LENGTH), getLongString(i, SUBJECT_LENGTH));
+  }
+  for (let i = 0; i < NUM_CERTS; i++) {
+    let subject = stringToArray(getLongString(i, SUBJECT_LENGTH));
+    let storedCerts = certStorage.findCertsBySubject(subject);
+    Assert.equal(storedCerts.length, 1, "should have 1 certificate (lots of data test)");
+    let storedCertAsString = arrayToString(storedCerts[0]);
+    Assert.equal(storedCertAsString, getLongString(i, CERT_LENGTH),
+                 "certificate should be as expected (lots of data test)");
+  }
+});
+
+add_task(async function test_removal() {
+  // As long as cert_storage is given valid base64, attempting to delete some nonexistent
+  // certificate will "succeed" (it'll do nothing).
+  await removeCertByHash(btoa("thishashisthewrongsize"));
+
+  await addCertBySubject("removal certificate bytes 1", "common subject to remove");
+  await addCertBySubject("removal certificate bytes 2", "common subject to remove");
+  await addCertBySubject("removal certificate bytes 3", "common subject to remove");
+
+  let storedCerts = certStorage.findCertsBySubject(stringToArray("common subject to remove"));
+  let storedCertsAsStrings = storedCerts.map(arrayToString);
+  let expectedCerts = ["removal certificate bytes 1", "removal certificate bytes 2",
+                       "removal certificate bytes 3"];
+  Assert.deepEqual(storedCertsAsStrings.sort(), expectedCerts.sort(),
+                   "should find expected certs before removing them");
+
+  // echo -n "removal certificate bytes 2" | sha256sum | xxd -r -p | base64
+  await removeCertByHash("2nUPHwl5TVr1mAD1FU9FivLTlTb0BAdnVUhsYgBccN4=");
+  storedCerts = certStorage.findCertsBySubject(stringToArray("common subject to remove"));
+  storedCertsAsStrings = storedCerts.map(arrayToString);
+  expectedCerts = ["removal certificate bytes 1", "removal certificate bytes 3"];
+  Assert.deepEqual(storedCertsAsStrings.sort(), expectedCerts.sort(),
+                   "should only have first and third certificates now");
+
+  // echo -n "removal certificate bytes 1" | sha256sum | xxd -r -p | base64
+  await removeCertByHash("8zoRqHYrklr7Zx6UWpzrPuL+ol8KL1Ml6XHBQmXiaTY=");
+  storedCerts = certStorage.findCertsBySubject(stringToArray("common subject to remove"));
+  storedCertsAsStrings = storedCerts.map(arrayToString);
+  expectedCerts = ["removal certificate bytes 3"];
+  Assert.deepEqual(storedCertsAsStrings.sort(), expectedCerts.sort(),
+                   "should only have third certificate now");
+
+  // echo -n "removal certificate bytes 3" | sha256sum | xxd -r -p | base64
+  await removeCertByHash("vZn7GwDSabB/AVo0T+N26nUsfSXIIx4NgQtSi7/0p/w=");
+  storedCerts = certStorage.findCertsBySubject(stringToArray("common subject to remove"));
+  Assert.equal(storedCerts.length, 0, "shouldn't have any certificates now");
+
+  // echo -n "removal certificate bytes 3" | sha256sum | xxd -r -p | base64
+  // Again, removing a nonexistent certificate should "succeed".
+  await removeCertByHash("vZn7GwDSabB/AVo0T+N26nUsfSXIIx4NgQtSi7/0p/w=");
+});
--- a/security/manager/ssl/tests/unit/test_der.js
+++ b/security/manager/ssl/tests/unit/test_der.js
@@ -2,17 +2,17 @@
  * http://creativecommons.org/publicdomain/zero/1.0/ */
 
 "use strict";
 
 // Tests DER.jsm functionality.
 
 // Until DER.jsm is actually used in production code, this is where we have to
 // import it from.
-var { DER } = ChromeUtils.import("resource://testing-common/psm/DER.jsm", null);
+var { DER } = ChromeUtils.import("resource://gre/modules/psm/DER.jsm", null);
 
 function run_simple_tests() {
   throws(() => new DER.DER("this is not an array"), /invalid input/,
          "should throw given non-array input");
   throws(() => new DER.DER([0, "invalid input", 1]), /invalid input/,
          "should throw given non-byte data (string case)");
   throws(() => new DER.DER([31, 1, {}]), /invalid input/,
          "should throw given non-byte data (object case)");
--- a/security/manager/ssl/tests/unit/test_intermediate_preloads.js
+++ b/security/manager/ssl/tests/unit/test_intermediate_preloads.js
@@ -29,25 +29,29 @@ function* cyclingIterator(items, count =
   if (count == null) {
     count = items.length;
   }
   for (let i = 0; i < count; i++) {
     yield items[i % items.length];
   }
 }
 
-function getHash(aStr) {
+function getHashCommon(aStr, useBase64) {
   let hasher = Cc["@mozilla.org/security/hash;1"].createInstance(Ci.nsICryptoHash);
   hasher.init(Ci.nsICryptoHash.SHA256);
   let stringStream = Cc["@mozilla.org/io/string-input-stream;1"].createInstance(Ci.nsIStringInputStream);
   stringStream.data = aStr;
   hasher.updateFromStream(stringStream, -1);
 
-  // convert the binary hash data to a hex string.
-  return hexify(hasher.finish(false));
+  return hasher.finish(useBase64);
+}
+
+// Get a hexified SHA-256 hash of the given string.
+function getHash(aStr) {
+  return hexify(getHashCommon(aStr, false));
 }
 
 function countTelemetryReports(histogram) {
   let count = 0;
   for (let x in histogram.values) {
     count += histogram.values[x];
   }
   return count;
@@ -128,24 +132,21 @@ function setupKintoPreloadServer(certGen
         "Access-Control-Expose-Headers: Retry-After, Content-Length, Alert, Backoff",
         "Content-Type: application/json; charset=UTF-8",
         "Server: waitress",
         "Etag: \"1000\"",
     ]);
 
     let output = [];
     let count = 1;
-    let certDB = Cc["@mozilla.org/security/x509certdb;1"]
-                 .getService(Ci.nsIX509CertDB);
 
     let certIterator = certGenerator();
     let result = certIterator.next();
     while (!result.done) {
       let certBytes = result.value;
-      let cert = certDB.constructX509FromBase64(pemToBase64(certBytes));
 
       output.push({
         "details": {
           "who": "",
           "why": "",
           "name": "",
           "created": "",
         },
@@ -153,17 +154,18 @@ function setupKintoPreloadServer(certGen
         "attachment": {
           "hash": options.hashFunc(certBytes),
           "size": options.lengthFunc(certBytes),
           "filename": `intermediate certificate #${count}.pem`,
           "location": `int${count}`,
           "mimetype": "application/x-pem-file",
         },
         "whitelist": false,
-        "pubKeyHash": cert.sha256Fingerprint,
+        // "pubKeyHash" is actually just the hash of the DER bytes of the certificate
+        "pubKeyHash": getHashCommon(atob(pemToBase64(certBytes)), true),
         "crlite_enrolled": true,
         "id": `78cf8900-fdea-4ce5-f8fb-${count}`,
         "last_modified": Date.now(),
       });
 
       count++;
       result = certIterator.next();
     }
@@ -268,19 +270,18 @@ add_task(async function test_preload_inv
   clearTelemetry();
 
   equal(await syncAndPromiseUpdate(), "success", "Preloading update should have run");
 
   let errors_histogram = Services.telemetry
                           .getHistogramById("INTERMEDIATE_PRELOADING_ERRORS")
                           .snapshot();
 
-  equal(countTelemetryReports(errors_histogram), 2, "There should be two error reports");
+  equal(countTelemetryReports(errors_histogram), 1, "There should be one error report");
   equal(errors_histogram.values[7], 1, "There should be one invalid hash error");
-  equal(errors_histogram.values[1], 1, "There should be one generic download error");
 
   equal(countDownloadAttempts, 1, "There should have been one download attempt");
 
   let certDB = Cc["@mozilla.org/security/x509certdb;1"]
                .getService(Ci.nsIX509CertDB);
 
   // load the first root and end entity, ignore the initial intermediate
   addCertFromFile(certDB, "test_intermediate_preloads/ca.pem", "CTu,,");
@@ -308,19 +309,18 @@ add_task(async function test_preload_inv
   clearTelemetry();
 
   equal(await syncAndPromiseUpdate(), "success", "Preloading update should have run");
 
   let errors_histogram = Services.telemetry
                           .getHistogramById("INTERMEDIATE_PRELOADING_ERRORS")
                           .snapshot();
 
-  equal(countTelemetryReports(errors_histogram), 2, "There should be only two error reports");
+  equal(countTelemetryReports(errors_histogram), 1, "There should be only one error report");
   equal(errors_histogram.values[8], 1, "There should be one invalid length error");
-  equal(errors_histogram.values[1], 1, "There should be one generic download error");
 
   equal(countDownloadAttempts, 1, "There should have been one download attempt");
 
   let certDB = Cc["@mozilla.org/security/x509certdb;1"]
                .getService(Ci.nsIX509CertDB);
 
   // load the first root and end entity, ignore the initial intermediate
   addCertFromFile(certDB, "test_intermediate_preloads/ca.pem", "CTu,,");
--- a/security/manager/ssl/tests/unit/test_x509.js
+++ b/security/manager/ssl/tests/unit/test_x509.js
@@ -1,18 +1,16 @@
 /* Any copyright is dedicated to the Public Domain.
  * http://creativecommons.org/publicdomain/zero/1.0/ */
 
 "use strict";
 
 // Tests X509.jsm functionality.
 
-// Until X509.jsm is actually used in production code, this is where we have to
-// import it from.
-var { X509 } = ChromeUtils.import("resource://testing-common/psm/X509.jsm");
+var { X509 } = ChromeUtils.import("resource://gre/modules/psm/X509.jsm");
 
 function stringToBytes(s) {
   let b = [];
   for (let i = 0; i < s.length; i++) {
     b.push(s.charCodeAt(i));
   }
   return b;
 }
--- a/security/manager/ssl/tests/unit/xpcshell.ini
+++ b/security/manager/ssl/tests/unit/xpcshell.ini
@@ -43,16 +43,17 @@ support-files =
 [test_baseline_requirements_subject_common_name.js]
 [test_broken_fips.js]
 # FIPS has never been a thing on Android, so the workaround doesn't
 # exist on that platform.
 # FIPS still works on Linux/Windows, so this test doesn't make any sense there.
 skip-if = os != 'mac'
 [test_cert_storage.js]
 tags = addons psm blocklist
+[test_cert_storage_direct.js]
 [test_cert_storage_prefs.js]
 [test_cert_chains.js]
 run-sequentially = hardcoded ports
 [test_cert_dbKey.js]
 [test_cert_eku.js]
 [test_cert_embedded_null.js]
 [test_cert_expiration_canary.js]
 run-if = nightly_build