Detect user-installed roots more efficiently on Android.

net/android/java/src/org/chromium/net/X509Util.java

Index: net/android/java/src/org/chromium/net/X509Util.java
diff --git a/net/android/java/src/org/chromium/net/X509Util.java b/net/android/java/src/org/chromium/net/X509Util.java
index 5c478a27f4a430445d5564c6fd5f02ac3dcaf985..c58346583f7e9eb4b608f2b5b4e39f39f80720f5 100644
--- a/net/android/java/src/org/chromium/net/X509Util.java
+++ b/net/android/java/src/org/chromium/net/X509Util.java
@@ -13,14 +13,19 @@ import android.net.http.X509TrustManagerExtensions;
 import android.os.Build;
 import android.security.KeyChain;
 import android.util.Log;
+import android.util.Pair;
 
 import org.chromium.base.JNINamespace;
 
 import java.io.ByteArrayInputStream;
+import java.io.File;
 import java.io.IOException;
 import java.security.KeyStore;
 import java.security.KeyStoreException;
+import java.security.MessageDigest;
 import java.security.NoSuchAlgorithmException;
+import java.security.PublicKey;
+import java.security.cert.Certificate;
 import java.security.cert.CertificateException;
 import java.security.cert.CertificateExpiredException;
 import java.security.cert.CertificateFactory;
@@ -28,11 +33,14 @@ import java.security.cert.CertificateNotYetValidException;
 import java.security.cert.X509Certificate;
 import java.util.Arrays;
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 
 import javax.net.ssl.TrustManager;
 import javax.net.ssl.TrustManagerFactory;
 import javax.net.ssl.X509TrustManager;
+import javax.security.auth.x500.X500Principal;
 
 /**
  * Utility functions for verifying X.509 certificates.
@@ -134,6 +142,33 @@ public class X509Util {
     private static KeyStore sTestKeyStore;
 
     /**
+     * The system key store. This is used to determine whether a trust anchor is a system trust
+     * anchor or user-installed.
+     */
+    private static KeyStore sSystemKeyStore;
+
+    /**
+     * The directory where system certificates are stored. This is used to determine whether a
+     * trust anchor is a system trust anchor or user-installed. The KeyStore API alone is not
+     * sufficient to efficiently query whether a given X500Principal, PublicKey pair is a trust
+     * anchor.
+     */
+    private static File sSystemCertificateDirectory;
+
+    /**
+     * An in-memory cache of which trust anchors are system trust roots. This avoids reading and
+     * decoding the root from disk on every verification. Mirrors a similar in-memory cache in
+     * Conscrypt's X509TrustManager implementation.
+     */
+    private static Set<Pair<X500Principal, PublicKey>> sSystemTrustAnchorCache;
+
+    /**
+     * True if the system key store has been loaded. If the "AndroidCAStore" KeyStore instance
+     * was not found, sSystemKeyStore may be null while sLoadedSystemKeyStore is true.
+     */
+    private static boolean sLoadedSystemKeyStore;
+
+    /**
      * Lock object used to synchronize all calls that modify or depend on the trust managers.
      */
     private static final Object sLock = new Object();
@@ -157,6 +192,27 @@ public class X509Util {
             if (sDefaultTrustManager == null) {
                 sDefaultTrustManager = X509Util.createTrustManager(null);
             }
+            if (!sLoadedSystemKeyStore) {
+                try {
+                    sSystemKeyStore = KeyStore.getInstance("AndroidCAStore");
+                    try {
+                        sSystemKeyStore.load(null);
+                    } catch (IOException e) {
+                        // No IO operation is attempted.
+                    }
+                    sSystemCertificateDirectory =
+                            new File(System.getenv("ANDROID_ROOT") + "/etc/security/cacerts");
+                } catch (KeyStoreException e) {
+                    // Could not load AndroidCAStore. Continue anyway; isKnownRoot will always
+                    // return false.
+                }
+                if (!sDisableNativeCodeForTest)
+                    nativeRecordCertVerifyCapabilitiesHistogram(sSystemKeyStore != null);
+                sLoadedSystemKeyStore = true;
+            }
+            if (sSystemTrustAnchorCache == null) {
+                sSystemTrustAnchorCache = new HashSet<Pair<X500Principal, PublicKey>>();
+            }
             if (sTestKeyStore == null) {
                 sTestKeyStore = KeyStore.getInstance(KeyStore.getDefaultType());
                 try {
@@ -218,6 +274,7 @@ public class X509Util {
     private static void reloadDefaultTrustManager() throws KeyStoreException,
             NoSuchAlgorithmException, CertificateException {
         sDefaultTrustManager = null;
+        sSystemTrustAnchorCache = null;
         nativeNotifyKeyChainChanged();
         ensureInitialized();
     }
@@ -256,6 +313,79 @@ public class X509Util {
         }
     }
 
+    private static final char[] HEX_DIGITS = {
+        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+        'a', 'b', 'c', 'd', 'e', 'f',
+    };
+
+    private static String hashPrincipal(X500Principal principal) throws NoSuchAlgorithmException {
+        // Android hashes a principal as the first four bytes of its MD5 digest, encoded in
+        // lowercase hex and reversed. Verified in 4.2, 4.3, and 4.4.
+        byte[] digest = MessageDigest.getInstance("MD5").digest(principal.getEncoded());
+        char[] hexChars = new char[8];
+        for (int i = 0; i < 4; i++) {
+            hexChars[2 * i] = HEX_DIGITS[(digest[3 - i] >> 4) & 0xf];
+            hexChars[2 * i + 1] = HEX_DIGITS[digest[3 - i] & 0xf];
+        }
+        return new String(hexChars);
+    }
+
+    private static boolean isKnownRoot(X509Certificate root)
+            throws NoSuchAlgorithmException, KeyStoreException {
+        // Could not find the system key store. Conservatively report false.
+        if (sSystemKeyStore == null)
+            return false;
+
+        // Check the in-memory cache first; avoid decoding the anchor from disk
+        // if it has been seen before.
+        Pair<X500Principal, PublicKey> key =
+            new Pair<X500Principal, PublicKey>(root.getSubjectX500Principal(), root.getPublicKey());
+        if (sSystemTrustAnchorCache.contains(key))
+            return true;
+
+        // Note: It is not sufficient to call sSystemKeyStore.getCertificiateAlias. If the server
+        // supplies a copy of a trust anchor, X509TrustManagerExtensions returns the server's
+        // version rather than the system one. getCertificiateAlias will then fail to find an anchor
+        // name. This is fixed upstream in https://android-review.googlesource.com/#/c/91605/
+        //
+        // TODO(davidben): When the change trickles into an Android release, query sSystemKeyStore
+        // directly.
+
+        // System trust anchors are stored under a hash of the principal. In case of collisions,
+        // a number is appended.
+        String hash = hashPrincipal(root.getSubjectX500Principal());
+        for (int i = 0; true; i++) {
+            String alias = hash + '.' + i;
+            if (!new File(sSystemCertificateDirectory, alias).exists())
+                break;
+
+            Certificate anchor = sSystemKeyStore.getCertificate("system:" + alias);
+            // It is possible for this to return null if the user deleted a trust anchor. In
+            // that case, the certificate remains in the system directory but is also added to
+            // another file. Continue iterating as there may be further collisions after the
+            // deleted anchor.
+            if (anchor == null)
+                continue;
+
+            if (!(anchor instanceof X509Certificate)) {
+                // This should never happen.
+                String className = anchor.getClass().getName();
+                Log.e(TAG, "Anchor " + alias + " not an X509Certificate: " + className);
+                continue;
+            }
+
+            // If the subject and public key match, this is a system root.
+            X509Certificate anchorX509 = (X509Certificate)anchor;
+            if (root.getSubjectX500Principal().equals(anchorX509.getSubjectX500Principal()) &&
+                root.getPublicKey().equals(anchorX509.getPublicKey())) {
+                sSystemTrustAnchorCache.add(key);
+                return true;
+            }
+        }
+
+        return false;
+    }
+
     /**
      * If an EKU extension is present in the end-entity certificate, it MUST contain either the
      * anyEKU or serverAuth or netscapeSGC or Microsoft SGC EKUs.
@@ -353,10 +483,12 @@ public class X509Util {
                 }
             }
 
-            // TODO(davidben): This code was removed for
-            // http://crbug.com/361166. Fix the performance regression and
-            // export it again.
             boolean isIssuedByKnownRoot = false;
+            if (verifiedChain.size() > 0) {
+                X509Certificate root = verifiedChain.get(verifiedChain.size() - 1);
+                isIssuedByKnownRoot = isKnownRoot(root);
+            }
+
             return new AndroidCertVerifyResult(CertVerifyStatusAndroid.VERIFY_OK,
                                                isIssuedByKnownRoot, verifiedChain);
         }