Add key rotation.

Change certificate checks to also consider the possibility of
signing certificate rotation by checking the
SigningDetails#pastSigningCertificates field.  In particular, add a
SigningDetails#checkCapability method which reports whether or not
the older SigningDetails is an ancestor of the current one, and
queries whether or not the old one has been granted capabilities,
such as being a sharedUser.

Bug: 64686581
Test: Builds, boots, browser and camera work, all with v3 signing.

Change-Id: I4199ff3f2d9ae959325b117b28e666ae31889800
diff --git a/core/java/android/content/pm/PackageParser.java b/core/java/android/content/pm/PackageParser.java
index 3d26af1..2da8937 100644
--- a/core/java/android/content/pm/PackageParser.java
+++ b/core/java/android/content/pm/PackageParser.java
@@ -78,8 +78,10 @@
 import android.util.ArraySet;
 import android.util.AttributeSet;
 import android.util.Base64;
+import android.util.ByteStringUtils;
 import android.util.DisplayMetrics;
 import android.util.Log;
+import android.util.PackageUtils;
 import android.util.Pair;
 import android.util.Slog;
 import android.util.SparseArray;
@@ -5683,7 +5685,10 @@
         return true;
     }
 
-    /** A container for signing-related data of an application package. */
+    /**
+     *  A container for signing-related data of an application package.
+     * @hide
+     */
     public static final class SigningDetails implements Parcelable {
 
         @IntDef({SigningDetails.SignatureSchemeVersion.UNKNOWN,
@@ -5705,15 +5710,54 @@
         public final ArraySet<PublicKey> publicKeys;
 
         /**
-         * Collection of {@code Signature} objects, each of which is formed from a former signing
-         * certificate of this APK before it was changed by signing certificate rotation.
+         * APK Signature Scheme v3 includes support for adding a proof-of-rotation record that
+         * contains two pieces of information:
+         *   1) the past signing certificates
+         *   2) the flags that APK wants to assign to each of the past signing certificates.
+         *
+         * This collection of {@code Signature} objects, each of which is formed from a former
+         * signing certificate of this APK before it was changed by signing certificate rotation,
+         * represents the first piece of information.  It is the APK saying to the rest of the
+         * world: "hey if you trust the old cert, you can trust me!"  This is useful, if for
+         * instance, the platform would like to determine whether or not to allow this APK to do
+         * something it would've allowed it to do under the old cert (like upgrade).
          */
         @Nullable
         public final Signature[] pastSigningCertificates;
 
+        /** special value used to see if cert is in package - not exposed to callers */
+        private static final int PAST_CERT_EXISTS = 0;
+
+        @IntDef(
+                flag = true,
+                value = {CertCapabilities.INSTALLED_DATA,
+                        CertCapabilities.SHARED_USER_ID,
+                        CertCapabilities.PERMISSION })
+        public @interface CertCapabilities {
+
+            /** accept data from already installed pkg with this cert */
+            int INSTALLED_DATA = 1;
+
+            /** accept sharedUserId with pkg with this cert */
+            int SHARED_USER_ID = 2;
+
+            /** grant SIGNATURE permissions to pkgs with this cert */
+            int PERMISSION = 4;
+        }
+
         /**
-         * Flags for the {@code pastSigningCertificates} collection, which indicate the capabilities
-         * the including APK wishes to grant to its past signing certificates.
+         * APK Signature Scheme v3 includes support for adding a proof-of-rotation record that
+         * contains two pieces of information:
+         *   1) the past signing certificates
+         *   2) the flags that APK wants to assign to each of the past signing certificates.
+         *
+         * These flags, which have a one-to-one relationship for the {@code pastSigningCertificates}
+         * collection, represent the second piece of information and are viewed as capabilities.
+         * They are an APK's way of telling the platform: "this is how I want to trust my old certs,
+         * please enforce that." This is useful for situation where this app itself is using its
+         * signing certificate as an authorization mechanism, like whether or not to allow another
+         * app to have its SIGNATURE permission.  An app could specify whether to allow other apps
+         * signed by its old cert 'X' to still get a signature permission it defines, for example.
          */
         @Nullable
         public final int[] pastSigningCertificatesFlags;
@@ -5784,6 +5828,244 @@
             return pastSigningCertificates != null && pastSigningCertificates.length > 0;
         }
 
+        /**
+         * Determines if the provided {@code oldDetails} is an ancestor of or the same as this one.
+         * If the {@code oldDetails} signing certificate appears in our pastSigningCertificates,
+         * then that means it has authorized a signing certificate rotation, which eventually leads
+         * to our certificate, and thus can be trusted. If this method evaluates to true, this
+         * SigningDetails object should be trusted if the previous one is.
+         */
+        public boolean hasAncestorOrSelf(SigningDetails oldDetails) {
+            if (this == UNKNOWN || oldDetails == UNKNOWN) {
+                return false;
+            }
+            if (oldDetails.signatures.length > 1) {
+
+                // multiple-signer packages cannot rotate signing certs, so we just compare current
+                // signers for an exact match
+                return signaturesMatchExactly(oldDetails);
+            } else {
+
+                // we may have signing certificate rotation history, check to see if the oldDetails
+                // was one of our old signing certificates
+                return hasCertificate(oldDetails.signatures[0]);
+            }
+        }
+
+        /**
+         * Similar to {@code hasAncestorOrSelf}.  Returns true only if this {@code SigningDetails}
+         * is a descendant of {@code oldDetails}, not if they're the same.  This is used to
+         * determine if this object is newer than the provided one.
+         */
+        public boolean hasAncestor(SigningDetails oldDetails) {
+            if (this == UNKNOWN || oldDetails == UNKNOWN) {
+                return false;
+            }
+            if (this.hasPastSigningCertificates() && oldDetails.signatures.length == 1) {
+
+                // the last entry in pastSigningCertificates is the current signer, ignore it
+                for (int i = 0; i < pastSigningCertificates.length - 1; i++) {
+                    if (pastSigningCertificates[i].equals(oldDetails.signatures[i])) {
+                        return true;
+                    }
+                }
+            }
+            return false;
+        }
+
+        /**
+         * Determines if the provided {@code oldDetails} is an ancestor of this one, and whether or
+         * not this one grants it the provided capability, represented by the {@code flags}
+         * parameter.  In the event of signing certificate rotation, a package may still interact
+         * with entities signed by its old signing certificate and not want to break previously
+         * functioning behavior.  The {@code flags} value determines which capabilities the app
+         * signed by the newer signing certificate would like to continue to give to its previous
+         * signing certificate(s).
+         */
+        public boolean checkCapability(SigningDetails oldDetails, @CertCapabilities int flags) {
+            if (this == UNKNOWN || oldDetails == UNKNOWN) {
+                return false;
+            }
+            if (oldDetails.signatures.length > 1) {
+
+                // multiple-signer packages cannot rotate signing certs, so we must have an exact
+                // match, which also means all capabilities are granted
+                return signaturesMatchExactly(oldDetails);
+            } else {
+
+                // we may have signing certificate rotation history, check to see if the oldDetails
+                // was one of our old signing certificates, and if we grant it the capability it's
+                // requesting
+                return hasCertificate(oldDetails.signatures[0], flags);
+            }
+        }
+
+        /**
+         * A special case of {@code checkCapability} which re-encodes both sets of signing
+         * certificates to counteract a previous re-encoding.
+         */
+        public boolean checkCapabilityRecover(SigningDetails oldDetails,
+                @CertCapabilities int flags) throws CertificateException {
+            if (oldDetails == UNKNOWN || this == UNKNOWN) {
+                return false;
+            }
+            if (hasPastSigningCertificates() && oldDetails.signatures.length == 1) {
+
+                // signing certificates may have rotated, check entire history for effective match
+                for (int i = 0; i < pastSigningCertificates.length; i++) {
+                    if (Signature.areEffectiveMatch(
+                            oldDetails.signatures[0],
+                            pastSigningCertificates[i])
+                            && pastSigningCertificatesFlags[i] == flags) {
+                        return true;
+                    }
+                }
+            } else {
+                return Signature.areEffectiveMatch(oldDetails.signatures, signatures);
+            }
+            return false;
+        }
+
+        /**
+         * Determine if {@code signature} is in this SigningDetails' signing certificate history,
+         * including the current signer.  Automatically returns false if this object has multiple
+         * signing certificates, since rotation is only supported for single-signers; this is
+         * enforced by {@code hasCertificateInternal}.
+         */
+        public boolean hasCertificate(Signature signature) {
+            return hasCertificateInternal(signature, PAST_CERT_EXISTS);
+        }
+
+        /**
+         * Determine if {@code signature} is in this SigningDetails' signing certificate history,
+         * including the current signer, and whether or not it has the given permission.
+         * Certificates which match our current signer automatically get all capabilities.
+         * Automatically returns false if this object has multiple signing certificates, since
+         * rotation is only supported for single-signers.
+         */
+        public boolean hasCertificate(Signature signature, @CertCapabilities int flags) {
+            return hasCertificateInternal(signature, flags);
+        }
+
+        /** Convenient wrapper for calling {@code hasCertificate} with certificate's raw bytes. */
+        public boolean hasCertificate(byte[] certificate) {
+            Signature signature = new Signature(certificate);
+            return hasCertificate(signature);
+        }
+
+        private boolean hasCertificateInternal(Signature signature, int flags) {
+            if (this == UNKNOWN) {
+                return false;
+            }
+
+            // only single-signed apps can have pastSigningCertificates
+            if (hasPastSigningCertificates()) {
+
+                // check all past certs, except for the current one, which automatically gets all
+                // capabilities, since it is the same as the current signature
+                for (int i = 0; i < pastSigningCertificates.length - 1; i++) {
+                    if (pastSigningCertificates[i].equals(signature)) {
+                        if (flags == PAST_CERT_EXISTS
+                                || (flags & pastSigningCertificatesFlags[i]) == flags) {
+                            return true;
+                        }
+                    }
+                }
+            }
+
+            // not in previous certs signing history, just check the current signer and make sure
+            // we are singly-signed
+            return signatures.length == 1 && signatures[0].equals(signature);
+        }
+
+        /**
+         * Determines if the provided {@code sha256String} is an ancestor of this one, and whether
+         * or not this one grants it the provided capability, represented by the {@code flags}
+         * parameter.  In the event of signing certificate rotation, a package may still interact
+         * with entities signed by its old signing certificate and not want to break previously
+         * functioning behavior.  The {@code flags} value determines which capabilities the app
+         * signed by the newer signing certificate would like to continue to give to its previous
+         * signing certificate(s).
+         *
+         * @param sha256String A hex-encoded representation of a sha256 digest.  In the case of an
+         *                     app with multiple signers, this represents the hex-encoded sha256
+         *                     digest of the combined hex-encoded sha256 digests of each individual
+         *                     signing certificate according to {@link
+         *                     PackageUtils#computeSignaturesSha256Digest(Signature[])}
+         */
+        public boolean checkCapability(String sha256String, @CertCapabilities int flags) {
+            if (this == UNKNOWN) {
+                return false;
+            }
+
+            // first see if the hash represents a single-signer in our signing history
+            byte[] sha256Bytes = ByteStringUtils.fromHexToByteArray(sha256String);
+            if (hasSha256Certificate(sha256Bytes, flags)) {
+                return true;
+            }
+
+            // Not in signing history, either represents multiple signatures or not a match.
+            // Multiple signers can't rotate, so no need to check flags, just see if the SHAs match.
+            // We already check the single-signer case above as part of hasSha256Certificate, so no
+            // need to verify we have multiple signers, just run the old check
+            // just consider current signing certs
+            final String[] mSignaturesSha256Digests =
+                    PackageUtils.computeSignaturesSha256Digests(signatures);
+            final String mSignaturesSha256Digest =
+                    PackageUtils.computeSignaturesSha256Digest(mSignaturesSha256Digests);
+            return mSignaturesSha256Digest.equals(sha256String);
+        }
+
+        /**
+         * Determine if the {@code sha256Certificate} is in this SigningDetails' signing certificate
+         * history, including the current signer.  Automatically returns false if this object has
+         * multiple signing certificates, since rotation is only supported for single-signers.
+         */
+        public boolean hasSha256Certificate(byte[] sha256Certificate) {
+            return hasSha256CertificateInternal(sha256Certificate, PAST_CERT_EXISTS);
+        }
+
+        /**
+         * Determine if the {@code sha256Certificate} certificate hash corresponds to a signing
+         * certificate in this SigningDetails' signing certificate history, including the current
+         * signer, and whether or not it has the given permission.  Certificates which match our
+         * current signer automatically get all capabilities. Automatically returns false if this
+         * object has multiple signing certificates, since rotation is only supported for
+         * single-signers.
+         */
+        public boolean hasSha256Certificate(byte[] sha256Certificate, @CertCapabilities int flags) {
+            return hasSha256CertificateInternal(sha256Certificate, flags);
+        }
+
+        private boolean hasSha256CertificateInternal(byte[] sha256Certificate, int flags) {
+            if (this == UNKNOWN) {
+                return false;
+            }
+            if (hasPastSigningCertificates()) {
+
+                // check all past certs, except for the last one, which automatically gets all
+                // capabilities, since it is the same as the current signature, and is checked below
+                for (int i = 0; i < pastSigningCertificates.length - 1; i++) {
+                    byte[] digest = PackageUtils.computeSha256DigestBytes(
+                            pastSigningCertificates[i].toByteArray());
+                    if (Arrays.equals(sha256Certificate, digest)) {
+                        if (flags == PAST_CERT_EXISTS
+                                || (flags & pastSigningCertificatesFlags[i]) == flags) {
+                            return true;
+                        }
+                    }
+                }
+            }
+
+            // not in previous certs signing history, just check the current signer
+            if (signatures.length == 1) {
+                byte[] digest =
+                        PackageUtils.computeSha256DigestBytes(signatures[0].toByteArray());
+                return Arrays.equals(sha256Certificate, digest);
+            }
+            return false;
+        }
+
         /** Returns true if the signatures in this and other match exactly. */
         public boolean signaturesMatchExactly(SigningDetails other) {
             return Signature.areExactMatch(this.signatures, other.signatures);
diff --git a/core/java/android/content/pm/Signature.java b/core/java/android/content/pm/Signature.java
index fdc54ae..a2a14ed 100644
--- a/core/java/android/content/pm/Signature.java
+++ b/core/java/android/content/pm/Signature.java
@@ -285,6 +285,29 @@
     }
 
     /**
+     * Test if given {@link Signature} objects are effectively equal. In rare
+     * cases, certificates can have slightly malformed encoding which causes
+     * exact-byte checks to fail.
+     * <p>
+     * To identify effective equality, we bounce the certificates through an
+     * decode/encode pass before doing the exact-byte check. To reduce attack
+     * surface area, we only allow a byte size delta of a few bytes.
+     *
+     * @throws CertificateException if the before/after length differs
+     *             substantially, usually a signal of something fishy going on.
+     * @hide
+     */
+    public static boolean areEffectiveMatch(Signature a, Signature b)
+            throws CertificateException {
+        final CertificateFactory cf = CertificateFactory.getInstance("X.509");
+
+        final Signature aPrime = bounce(cf, a);
+        final Signature bPrime = bounce(cf, b);
+
+        return aPrime.equals(bPrime);
+    }
+
+    /**
      * Bounce the given {@link Signature} through a decode/encode cycle.
      *
      * @throws CertificateException if the before/after length differs
diff --git a/services/core/java/com/android/server/pm/InstantAppRegistry.java b/services/core/java/com/android/server/pm/InstantAppRegistry.java
index af20cd7..30088dd 100644
--- a/services/core/java/com/android/server/pm/InstantAppRegistry.java
+++ b/services/core/java/com/android/server/pm/InstantAppRegistry.java
@@ -44,6 +44,7 @@
 import android.util.SparseArray;
 import android.util.SparseBooleanArray;
 import android.util.Xml;
+
 import com.android.internal.annotations.GuardedBy;
 import com.android.internal.os.BackgroundThread;
 import com.android.internal.os.SomeArgs;
@@ -51,6 +52,7 @@
 import com.android.internal.util.XmlUtils;
 
 import libcore.io.IoUtils;
+
 import org.xmlpull.v1.XmlPullParser;
 import org.xmlpull.v1.XmlPullParserException;
 import org.xmlpull.v1.XmlSerializer;
@@ -295,25 +297,26 @@
                 continue;
             }
 
+            String cookieName = currentCookieFile.getName();
+            String currentCookieSha256 =
+                    cookieName.substring(INSTANT_APP_COOKIE_FILE_PREFIX.length(),
+                            cookieName.length() - INSTANT_APP_COOKIE_FILE_SIFFIX.length());
+
             // Before we used only the first signature to compute the SHA 256 but some
             // apps could be singed by multiple certs and the cert order is undefined.
             // We prefer the modern computation procedure where all certs are taken
             // into account but also allow the value from the old computation to avoid
             // data loss.
-            final String[] signaturesSha256Digests = PackageUtils.computeSignaturesSha256Digests(
-                    pkg.mSigningDetails.signatures);
-            final String signaturesSha256Digest = PackageUtils.computeSignaturesSha256Digest(
-                    signaturesSha256Digests);
-
-            // We prefer a match based on all signatures
-            if (currentCookieFile.equals(computeInstantCookieFile(pkg.packageName,
-                    signaturesSha256Digest, userId))) {
+            if (pkg.mSigningDetails.checkCapability(currentCookieSha256,
+                    PackageParser.SigningDetails.CertCapabilities.INSTALLED_DATA)) {
                 return;
             }
 
-            // For backwards compatibility we accept match based on first signature
-            if (pkg.mSigningDetails.signatures.length > 1 && currentCookieFile.equals(computeInstantCookieFile(
-                    pkg.packageName, signaturesSha256Digests[0], userId))) {
+            // For backwards compatibility we accept match based on first signature only in the case
+            // of multiply-signed packagse
+            final String[] signaturesSha256Digests =
+                    PackageUtils.computeSignaturesSha256Digests(pkg.mSigningDetails.signatures);
+            if (signaturesSha256Digests[0].equals(currentCookieSha256)) {
                 return;
             }
 
diff --git a/services/core/java/com/android/server/pm/PackageManagerService.java b/services/core/java/com/android/server/pm/PackageManagerService.java
index fdb157e..941b4e6 100644
--- a/services/core/java/com/android/server/pm/PackageManagerService.java
+++ b/services/core/java/com/android/server/pm/PackageManagerService.java
@@ -108,8 +108,6 @@
 import static com.android.server.pm.PackageManagerServiceUtils.getCompressedFiles;
 import static com.android.server.pm.PackageManagerServiceUtils.getLastModifiedTime;
 import static com.android.server.pm.PackageManagerServiceUtils.logCriticalInfo;
-import static com.android.server.pm.PackageManagerServiceUtils.signingDetailsHasCertificate;
-import static com.android.server.pm.PackageManagerServiceUtils.signingDetailsHasSha256Certificate;
 import static com.android.server.pm.PackageManagerServiceUtils.verifySignatures;
 import static com.android.server.pm.permission.PermissionsState.PERMISSION_OPERATION_FAILURE;
 import static com.android.server.pm.permission.PermissionsState.PERMISSION_OPERATION_SUCCESS;
@@ -246,6 +244,7 @@
 import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.Base64;
+import android.util.ByteStringUtils;
 import android.util.DisplayMetrics;
 import android.util.EventLog;
 import android.util.ExceptionUtils;
@@ -5546,9 +5545,9 @@
             }
             switch (type) {
                 case CERT_INPUT_RAW_X509:
-                    return signingDetailsHasCertificate(certificate, p.mSigningDetails);
+                    return p.mSigningDetails.hasCertificate(certificate);
                 case CERT_INPUT_SHA256:
-                    return signingDetailsHasSha256Certificate(certificate, p.mSigningDetails);
+                    return p.mSigningDetails.hasSha256Certificate(certificate);
                 default:
                     return false;
             }
@@ -5587,9 +5586,9 @@
             }
             switch (type) {
                 case CERT_INPUT_RAW_X509:
-                    return signingDetailsHasCertificate(certificate, signingDetails);
+                    return signingDetails.hasCertificate(certificate);
                 case CERT_INPUT_SHA256:
-                    return signingDetailsHasSha256Certificate(certificate, signingDetails);
+                    return signingDetails.hasSha256Certificate(certificate);
                 default:
                     return false;
             }
@@ -8757,10 +8756,9 @@
         // the application installed on /data.
         if (scanSystemPartition && !isSystemPkgUpdated && pkgAlreadyExists
                 && !pkgSetting.isSystem()) {
-            // if the signatures don't match, wipe the installed application and its data
-            if (compareSignatures(pkgSetting.signatures.mSigningDetails.signatures,
-                    pkg.mSigningDetails.signatures)
-                            != PackageManager.SIGNATURE_MATCH) {
+
+            if (!pkg.mSigningDetails.checkCapability(pkgSetting.signatures.mSigningDetails,
+                    PackageParser.SigningDetails.CertCapabilities.INSTALLED_DATA)) {
                 logCriticalInfo(Log.WARN,
                         "System package signature mismatch;"
                         + " name: " + pkgSetting.name);
@@ -9725,34 +9723,51 @@
                     }
 
                     final String[] expectedCertDigests = requiredCertDigests[i];
-                    // For apps targeting O MR1 we require explicit enumeration of all certs.
-                    final String[] libCertDigests = (targetSdk > Build.VERSION_CODES.O)
-                            ? PackageUtils.computeSignaturesSha256Digests(
-                            libPkg.mSigningDetails.signatures)
-                            : PackageUtils.computeSignaturesSha256Digests(
-                                    new Signature[]{libPkg.mSigningDetails.signatures[0]});
 
-                    // Take a shortcut if sizes don't match. Note that if an app doesn't
-                    // target O we don't parse the "additional-certificate" tags similarly
-                    // how we only consider all certs only for apps targeting O (see above).
-                    // Therefore, the size check is safe to make.
-                    if (expectedCertDigests.length != libCertDigests.length) {
-                        throw new PackageManagerException(INSTALL_FAILED_MISSING_SHARED_LIBRARY,
-                                "Package " + packageName + " requires differently signed" +
-                                        " static shared library; failing!");
-                    }
 
-                    // Use a predictable order as signature order may vary
-                    Arrays.sort(libCertDigests);
-                    Arrays.sort(expectedCertDigests);
+                    if (expectedCertDigests.length > 1) {
 
-                    final int certCount = libCertDigests.length;
-                    for (int j = 0; j < certCount; j++) {
-                        if (!libCertDigests[j].equalsIgnoreCase(expectedCertDigests[j])) {
+                        // For apps targeting O MR1 we require explicit enumeration of all certs.
+                        final String[] libCertDigests = (targetSdk > Build.VERSION_CODES.O)
+                                ? PackageUtils.computeSignaturesSha256Digests(
+                                libPkg.mSigningDetails.signatures)
+                                : PackageUtils.computeSignaturesSha256Digests(
+                                        new Signature[]{libPkg.mSigningDetails.signatures[0]});
+
+                        // Take a shortcut if sizes don't match. Note that if an app doesn't
+                        // target O we don't parse the "additional-certificate" tags similarly
+                        // how we only consider all certs only for apps targeting O (see above).
+                        // Therefore, the size check is safe to make.
+                        if (expectedCertDigests.length != libCertDigests.length) {
                             throw new PackageManagerException(INSTALL_FAILED_MISSING_SHARED_LIBRARY,
                                     "Package " + packageName + " requires differently signed" +
                                             " static shared library; failing!");
                         }
+
+                        // Use a predictable order as signature order may vary
+                        Arrays.sort(libCertDigests);
+                        Arrays.sort(expectedCertDigests);
+
+                        final int certCount = libCertDigests.length;
+                        for (int j = 0; j < certCount; j++) {
+                            if (!libCertDigests[j].equalsIgnoreCase(expectedCertDigests[j])) {
+                                throw new PackageManagerException(
+                                        INSTALL_FAILED_MISSING_SHARED_LIBRARY,
+                                        "Package " + packageName + " requires differently signed" +
+                                                " static shared library; failing!");
+                            }
+                        }
+                    } else {
+
+                        // lib signing cert could have rotated beyond the one expected, check to see
+                        // if the new one has been blessed by the old
+                        if (!libPkg.mSigningDetails.hasSha256Certificate(
+                                ByteStringUtils.fromHexToByteArray(expectedCertDigests[0]))) {
+                            throw new PackageManagerException(
+                                    INSTALL_FAILED_MISSING_SHARED_LIBRARY,
+                                    "Package " + packageName + " requires differently signed" +
+                                            " static shared library; failing!");
+                        }
                     }
                 }
 
@@ -10169,6 +10184,15 @@
                 // We just determined the app is signed correctly, so bring
                 // over the latest parsed certs.
                 pkgSetting.signatures.mSigningDetails = pkg.mSigningDetails;
+
+
+                // if this is is a sharedUser, check to see if the new package is signed by a newer
+                // signing certificate than the existing one, and if so, copy over the new details
+                if (signatureCheckPs.sharedUser != null
+                        && pkg.mSigningDetails.hasAncestor(
+                                signatureCheckPs.sharedUser.signatures.mSigningDetails)) {
+                    signatureCheckPs.sharedUser.signatures.mSigningDetails = pkg.mSigningDetails;
+                }
             } catch (PackageManagerException e) {
                 if ((parseFlags & PackageParser.PARSE_IS_SYSTEM_DIR) == 0) {
                     throw e;
@@ -10195,6 +10219,13 @@
                 String msg = "System package " + pkg.packageName
                         + " signature changed; retaining data.";
                 reportSettingsProblem(Log.WARN, msg);
+            } catch (IllegalArgumentException e) {
+
+                // should never happen: certs matched when checking, but not when comparing
+                // old to new for sharedUser
+                throw new PackageManagerException(INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES,
+                        "Signing certificates comparison made on incomparable signing details"
+                        + " but somehow passed verifySignatures!");
             }
         }
 
@@ -16061,10 +16092,10 @@
                     return;
                 }
             } else {
+
                 // default to original signature matching
-                if (compareSignatures(oldPackage.mSigningDetails.signatures,
-                        pkg.mSigningDetails.signatures)
-                        != PackageManager.SIGNATURE_MATCH) {
+                if (!pkg.mSigningDetails.checkCapability(oldPackage.mSigningDetails,
+                        PackageParser.SigningDetails.CertCapabilities.INSTALLED_DATA)) {
                     res.setError(INSTALL_FAILED_UPDATE_INCOMPATIBLE,
                             "New package has a different signature: " + pkgName);
                     return;
@@ -17058,9 +17089,25 @@
                                     sourcePackageSetting, scanFlags))) {
                         sigsOk = ksms.checkUpgradeKeySetLocked(sourcePackageSetting, pkg);
                     } else {
-                        sigsOk = compareSignatures(
-                                sourcePackageSetting.signatures.mSigningDetails.signatures,
-                                pkg.mSigningDetails.signatures) == PackageManager.SIGNATURE_MATCH;
+
+                        // in the event of signing certificate rotation, we need to see if the
+                        // package's certificate has rotated from the current one, or if it is an
+                        // older certificate with which the current is ok with sharing permissions
+                        if (sourcePackageSetting.signatures.mSigningDetails.checkCapability(
+                                        pkg.mSigningDetails,
+                                        PackageParser.SigningDetails.CertCapabilities.PERMISSION)) {
+                            sigsOk = true;
+                        } else if (pkg.mSigningDetails.checkCapability(
+                                        sourcePackageSetting.signatures.mSigningDetails,
+                                        PackageParser.SigningDetails.CertCapabilities.PERMISSION)) {
+
+                            // the scanned package checks out, has signing certificate rotation
+                            // history, and is newer; bring it over
+                            sourcePackageSetting.signatures.mSigningDetails = pkg.mSigningDetails;
+                            sigsOk = true;
+                        } else {
+                            sigsOk = false;
+                        }
                     }
                     if (!sigsOk) {
                         // If the owning package is the system itself, we log but allow
diff --git a/services/core/java/com/android/server/pm/PackageManagerServiceUtils.java b/services/core/java/com/android/server/pm/PackageManagerServiceUtils.java
index 76c199b..c02331d 100644
--- a/services/core/java/com/android/server/pm/PackageManagerServiceUtils.java
+++ b/services/core/java/com/android/server/pm/PackageManagerServiceUtils.java
@@ -531,18 +531,29 @@
             // migrate the old signatures to the new scheme
             packageSignatures.mSigningDetails = parsedSignatures;
             return true;
+        } else if (parsedSignatures.hasPastSigningCertificates()) {
+
+            // well this sucks: the parsed package has probably rotated signing certificates, but
+            // we don't have enough information to determine if the new signing certificate was
+            // blessed by the old one
+            logCriticalInfo(Log.INFO, "Existing package " + packageName + " has flattened signing "
+                    + "certificate chain. Unable to install newer version with rotated signing "
+                    + "certificate.");
         }
         return false;
     }
 
-    private static boolean matchSignaturesRecover(String packageName,
-            Signature[] existingSignatures, Signature[] parsedSignatures) {
+    private static boolean matchSignaturesRecover(
+            String packageName,
+            PackageParser.SigningDetails existingSignatures,
+            PackageParser.SigningDetails parsedSignatures,
+            @PackageParser.SigningDetails.CertCapabilities int flags) {
         String msg = null;
         try {
-            if (Signature.areEffectiveMatch(existingSignatures, parsedSignatures)) {
-                logCriticalInfo(Log.INFO,
-                        "Recovered effectively matching certificates for " + packageName);
-                return true;
+            if (parsedSignatures.checkCapabilityRecover(existingSignatures, flags)) {
+                logCriticalInfo(Log.INFO, "Recovered effectively matching certificates for "
+                        + packageName);
+                    return true;
             }
         } catch (CertificateException e) {
             msg = e.getMessage();
@@ -563,9 +574,11 @@
             PackageSetting disabledPkgSetting) {
         try {
             PackageParser.collectCertificates(disabledPkgSetting.pkg, true /* skipVerify */);
-            if (compareSignatures(pkgSetting.signatures.mSigningDetails.signatures,
-                        disabledPkgSetting.signatures.mSigningDetails.signatures)
-                    != PackageManager.SIGNATURE_MATCH) {
+            if (pkgSetting.signatures.mSigningDetails.checkCapability(
+                    disabledPkgSetting.signatures.mSigningDetails,
+                    PackageParser.SigningDetails.CertCapabilities.INSTALLED_DATA)) {
+                return true;
+            } else {
                 logCriticalInfo(Log.ERROR, "Updated system app mismatches cert on /system: " +
                         pkgSetting.name);
                 return false;
@@ -575,69 +588,6 @@
                     e.getMessage());
             return false;
         }
-        return true;
-    }
-
-    /**
-     * Checks the signing certificates to see if the provided certificate is a member.  Invalid for
-     * {@code SigningDetails} with multiple signing certificates.
-     * @param certificate certificate to check for membership
-     * @param signingDetails signing certificates record whose members are to be searched
-     * @return true if {@code certificate} is in {@code signingDetails}
-     */
-    public static boolean signingDetailsHasCertificate(
-            byte[] certificate, PackageParser.SigningDetails signingDetails) {
-        if (signingDetails == PackageParser.SigningDetails.UNKNOWN) {
-            return false;
-        }
-        Signature signature = new Signature(certificate);
-        if (signingDetails.hasPastSigningCertificates()) {
-            for (int i = 0; i < signingDetails.pastSigningCertificates.length; i++) {
-                if (signingDetails.pastSigningCertificates[i].equals(signature)) {
-                    return true;
-                }
-            }
-        } else {
-            // no signing history, just check the current signer
-            if (signingDetails.signatures.length == 1
-                    && signingDetails.signatures[0].equals(signature)) {
-                return true;
-            }
-        }
-        return false;
-    }
-
-    /**
-     * Checks the signing certificates to see if the provided certificate is a member.  Invalid for
-     * {@code SigningDetails} with multiple signing certificaes.
-     * @param sha256Certificate certificate to check for membership
-     * @param signingDetails signing certificates record whose members are to be searched
-     * @return true if {@code certificate} is in {@code signingDetails}
-     */
-    public static boolean signingDetailsHasSha256Certificate(
-            byte[] sha256Certificate, PackageParser.SigningDetails signingDetails ) {
-        if (signingDetails == PackageParser.SigningDetails.UNKNOWN) {
-            return false;
-        }
-        if (signingDetails.hasPastSigningCertificates()) {
-            for (int i = 0; i < signingDetails.pastSigningCertificates.length; i++) {
-                byte[] digest = PackageUtils.computeSha256DigestBytes(
-                        signingDetails.pastSigningCertificates[i].toByteArray());
-                if (Arrays.equals(sha256Certificate, digest)) {
-                    return true;
-                }
-            }
-        } else {
-            // no signing history, just check the current signer
-            if (signingDetails.signatures.length == 1) {
-                byte[] digest = PackageUtils.computeSha256DigestBytes(
-                        signingDetails.signatures[0].toByteArray());
-                if (Arrays.equals(sha256Certificate, digest)) {
-                    return true;
-                }
-            }
-        }
-        return false;
     }
 
     /** Returns true if APK Verity is enabled. */
@@ -662,10 +612,11 @@
         final String packageName = pkgSetting.name;
         boolean compatMatch = false;
         if (pkgSetting.signatures.mSigningDetails.signatures != null) {
+
             // Already existing package. Make sure signatures match
-            boolean match = compareSignatures(pkgSetting.signatures.mSigningDetails.signatures,
-                    parsedSignatures.signatures)
-                    == PackageManager.SIGNATURE_MATCH;
+            boolean match = parsedSignatures.checkCapability(
+                    pkgSetting.signatures.mSigningDetails,
+                    PackageParser.SigningDetails.CertCapabilities.INSTALLED_DATA);
             if (!match && compareCompat) {
                 match = matchSignaturesCompat(packageName, pkgSetting.signatures,
                         parsedSignatures);
@@ -673,8 +624,10 @@
             }
             if (!match && compareRecover) {
                 match = matchSignaturesRecover(
-                        packageName, pkgSetting.signatures.mSigningDetails.signatures,
-                        parsedSignatures.signatures);
+                        packageName,
+                        pkgSetting.signatures.mSigningDetails,
+                        parsedSignatures,
+                        PackageParser.SigningDetails.CertCapabilities.INSTALLED_DATA);
             }
 
             if (!match && isApkVerificationForced(disabledPkgSetting)) {
@@ -689,20 +642,35 @@
         }
         // Check for shared user signatures
         if (pkgSetting.sharedUser != null
-                && pkgSetting.sharedUser.signatures.mSigningDetails.signatures != null) {
-            // Already existing package. Make sure signatures match
+                && pkgSetting.sharedUser.signatures.mSigningDetails
+                        != PackageParser.SigningDetails.UNKNOWN) {
+
+            // Already existing package. Make sure signatures match.  In case of signing certificate
+            // rotation, the packages with newer certs need to be ok with being sharedUserId with
+            // the older ones.  We check to see if either the new package is signed by an older cert
+            // with which the current sharedUser is ok, or if it is signed by a newer one, and is ok
+            // with being sharedUser with the existing signing cert.
             boolean match =
-                    compareSignatures(
-                            pkgSetting.sharedUser.signatures.mSigningDetails.signatures,
-                            parsedSignatures.signatures) == PackageManager.SIGNATURE_MATCH;
+                    parsedSignatures.checkCapability(
+                            pkgSetting.sharedUser.signatures.mSigningDetails,
+                            PackageParser.SigningDetails.CertCapabilities.SHARED_USER_ID)
+                    || pkgSetting.sharedUser.signatures.mSigningDetails.checkCapability(
+                            parsedSignatures,
+                            PackageParser.SigningDetails.CertCapabilities.SHARED_USER_ID);
             if (!match && compareCompat) {
                 match = matchSignaturesCompat(
                         packageName, pkgSetting.sharedUser.signatures, parsedSignatures);
             }
             if (!match && compareRecover) {
-                match = matchSignaturesRecover(packageName,
-                        pkgSetting.sharedUser.signatures.mSigningDetails.signatures,
-                        parsedSignatures.signatures);
+                match =
+                        matchSignaturesRecover(packageName,
+                                pkgSetting.sharedUser.signatures.mSigningDetails,
+                                parsedSignatures,
+                                PackageParser.SigningDetails.CertCapabilities.SHARED_USER_ID)
+                        || matchSignaturesRecover(packageName,
+                                parsedSignatures,
+                                pkgSetting.sharedUser.signatures.mSigningDetails,
+                                PackageParser.SigningDetails.CertCapabilities.SHARED_USER_ID);
                 compatMatch |= match;
             }
             if (!match) {
diff --git a/services/core/java/com/android/server/pm/PackageSettingBase.java b/services/core/java/com/android/server/pm/PackageSettingBase.java
index 18356c5..f14a684 100644
--- a/services/core/java/com/android/server/pm/PackageSettingBase.java
+++ b/services/core/java/com/android/server/pm/PackageSettingBase.java
@@ -23,6 +23,7 @@
 import android.content.pm.ApplicationInfo;
 import android.content.pm.IntentFilterVerificationInfo;
 import android.content.pm.PackageManager;
+import android.content.pm.PackageParser;
 import android.content.pm.PackageUserState;
 import android.content.pm.Signature;
 import android.service.pm.PackageProto;
@@ -236,6 +237,10 @@
         return signatures.mSigningDetails.signatures;
     }
 
+    public PackageParser.SigningDetails getSigningDetails() {
+        return signatures.mSigningDetails;
+    }
+
     /**
      * Makes a shallow copy of the given package settings.
      *
diff --git a/services/core/java/com/android/server/pm/SELinuxMMAC.java b/services/core/java/com/android/server/pm/SELinuxMMAC.java
index 2552643..79f702b 100644
--- a/services/core/java/com/android/server/pm/SELinuxMMAC.java
+++ b/services/core/java/com/android/server/pm/SELinuxMMAC.java
@@ -454,7 +454,11 @@
         Signature[] certs = mCerts.toArray(new Signature[0]);
         if (pkg.mSigningDetails != SigningDetails.UNKNOWN
                 && !Signature.areExactMatch(certs, pkg.mSigningDetails.signatures)) {
-            return null;
+
+            // certs aren't exact match, but the package may have rotated from the known system cert
+            if (certs.length > 1 || !pkg.mSigningDetails.hasCertificate(certs[0])) {
+                return null;
+            }
         }
 
         // Check for inner package name matches given that the
diff --git a/services/core/java/com/android/server/pm/permission/DefaultPermissionGrantPolicy.java b/services/core/java/com/android/server/pm/permission/DefaultPermissionGrantPolicy.java
index e2123c2..6308766 100644
--- a/services/core/java/com/android/server/pm/permission/DefaultPermissionGrantPolicy.java
+++ b/services/core/java/com/android/server/pm/permission/DefaultPermissionGrantPolicy.java
@@ -1166,9 +1166,9 @@
         final String systemPackageName = mServiceInternal.getKnownPackageName(
                 PackageManagerInternal.PACKAGE_SYSTEM, UserHandle.USER_SYSTEM);
         final PackageParser.Package systemPackage = getPackage(systemPackageName);
-        return compareSignatures(systemPackage.mSigningDetails.signatures,
-                pkg.mSigningDetails.signatures)
-                == PackageManager.SIGNATURE_MATCH;
+        return pkg.mSigningDetails.hasAncestorOrSelf(systemPackage.mSigningDetails)
+                || systemPackage.mSigningDetails.checkCapability(pkg.mSigningDetails,
+                        PackageParser.SigningDetails.CertCapabilities.PERMISSION);
     }
 
     private void grantDefaultPermissionExceptions(int userId) {
diff --git a/services/core/java/com/android/server/pm/permission/PermissionManagerService.java b/services/core/java/com/android/server/pm/permission/PermissionManagerService.java
index cb3b107..08f8bbd 100644
--- a/services/core/java/com/android/server/pm/permission/PermissionManagerService.java
+++ b/services/core/java/com/android/server/pm/permission/PermissionManagerService.java
@@ -1022,12 +1022,24 @@
                 PackageManagerInternal.PACKAGE_SYSTEM, UserHandle.USER_SYSTEM);
         final PackageParser.Package systemPackage =
                 mPackageManagerInt.getPackage(systemPackageName);
-        boolean allowed = (PackageManagerServiceUtils.compareSignatures(
-                                bp.getSourceSignatures(), pkg.mSigningDetails.signatures)
-                        == PackageManager.SIGNATURE_MATCH)
-                || (PackageManagerServiceUtils.compareSignatures(
-                systemPackage.mSigningDetails.signatures, pkg.mSigningDetails.signatures)
-                        == PackageManager.SIGNATURE_MATCH);
+
+        // check if the package is allow to use this signature permission.  A package is allowed to
+        // use a signature permission if:
+        //     - it has the same set of signing certificates as the source package
+        //     - or its signing certificate was rotated from the source package's certificate
+        //     - or its signing certificate is a previous signing certificate of the defining
+        //       package, and the defining package still trusts the old certificate for permissions
+        //     - or it shares the above relationships with the system package
+        boolean allowed =
+                pkg.mSigningDetails.hasAncestorOrSelf(
+                        bp.getSourcePackageSetting().getSigningDetails())
+                || bp.getSourcePackageSetting().getSigningDetails().checkCapability(
+                        pkg.mSigningDetails,
+                        PackageParser.SigningDetails.CertCapabilities.PERMISSION)
+                || pkg.mSigningDetails.hasAncestorOrSelf(systemPackage.mSigningDetails)
+                || systemPackage.mSigningDetails.checkCapability(
+                        pkg.mSigningDetails,
+                        PackageParser.SigningDetails.CertCapabilities.PERMISSION);
         if (!allowed && (privilegedPermission || oemPermission)) {
             if (pkg.isSystem()) {
                 // For updated system applications, a privileged/oem permission