diff --git a/core/java/com/android/internal/widget/LockPatternUtils.java b/core/java/com/android/internal/widget/LockPatternUtils.java
index a3e0016..28fd2b4 100644
--- a/core/java/com/android/internal/widget/LockPatternUtils.java
+++ b/core/java/com/android/internal/widget/LockPatternUtils.java
@@ -1936,7 +1936,8 @@
      * If the user is not secured, ie doesn't have an LSKF, then decrypt the user's synthetic
      * password and use it to unlock various cryptographic keys associated with the user.  This
      * primarily includes unlocking the user's credential-encrypted (CE) storage.  It also includes
-     * deriving or decrypting the vendor auth secret and sending it to the AuthSecret HAL.
+     * unlocking the user's Keystore super keys, and deriving or decrypting the vendor auth secret
+     * and sending it to the AuthSecret HAL in order to unlock Secure Element firmware updates.
      * <p>
      * These tasks would normally be done when the LSKF is verified.  This method is where these
      * tasks are done when the user doesn't have an LSKF.  It's called when the user is started.
diff --git a/keystore/java/android/security/AndroidKeyStoreMaintenance.java b/keystore/java/android/security/AndroidKeyStoreMaintenance.java
index b7ea04f..2beb434 100644
--- a/keystore/java/android/security/AndroidKeyStoreMaintenance.java
+++ b/keystore/java/android/security/AndroidKeyStoreMaintenance.java
@@ -51,7 +51,7 @@
      * @return 0 if successful or a {@code ResponseCode}
      * @hide
      */
-    public static int onUserAdded(@NonNull int userId) {
+    public static int onUserAdded(int userId) {
         StrictMode.noteDiskWrite();
         try {
             getService().onUserAdded(userId);
@@ -66,6 +66,30 @@
     }
 
     /**
+     * Tells Keystore to create a user's super keys and store them encrypted by the given secret.
+     *
+     * @param userId - Android user id of the user
+     * @param password - a secret derived from the user's synthetic password
+     * @param allowExisting - true if the keys already existing should not be considered an error
+     * @return 0 if successful or a {@code ResponseCode}
+     * @hide
+     */
+    public static int initUserSuperKeys(int userId, @NonNull byte[] password,
+            boolean allowExisting) {
+        StrictMode.noteDiskWrite();
+        try {
+            getService().initUserSuperKeys(userId, password, allowExisting);
+            return 0;
+        } catch (ServiceSpecificException e) {
+            Log.e(TAG, "initUserSuperKeys failed", e);
+            return e.errorCode;
+        } catch (Exception e) {
+            Log.e(TAG, "Can not connect to keystore", e);
+            return SYSTEM_ERROR;
+        }
+    }
+
+    /**
      * Informs Keystore 2.0 about removing a user
      *
      * @param userId - Android user id of the user being removed
@@ -110,6 +134,28 @@
     }
 
     /**
+     * Tells Keystore that a user's LSKF is being removed, ie the user's lock screen is changing to
+     * Swipe or None.  Keystore uses this notification to delete the user's auth-bound keys.
+     *
+     * @param userId - Android user id of the user
+     * @return 0 if successful or a {@code ResponseCode}
+     * @hide
+     */
+    public static int onUserLskfRemoved(int userId) {
+        StrictMode.noteDiskWrite();
+        try {
+            getService().onUserLskfRemoved(userId);
+            return 0;
+        } catch (ServiceSpecificException e) {
+            Log.e(TAG, "onUserLskfRemoved failed", e);
+            return e.errorCode;
+        } catch (Exception e) {
+            Log.e(TAG, "Can not connect to keystore", e);
+            return SYSTEM_ERROR;
+        }
+    }
+
+    /**
      * Informs Keystore 2.0 that an app was uninstalled and the corresponding namespace is to
      * be cleared.
      */
diff --git a/services/core/java/com/android/server/locksettings/LockSettingsService.java b/services/core/java/com/android/server/locksettings/LockSettingsService.java
index fa95a34..ec7f561 100644
--- a/services/core/java/com/android/server/locksettings/LockSettingsService.java
+++ b/services/core/java/com/android/server/locksettings/LockSettingsService.java
@@ -243,6 +243,10 @@
     private static final String MIGRATED_FRP2 = "migrated_frp2";
     private static final String MIGRATED_KEYSTORE_NS = "migrated_keystore_namespace";
     private static final String MIGRATED_SP_CE_ONLY = "migrated_all_users_to_sp_and_bound_ce";
+    private static final String MIGRATED_SP_FULL = "migrated_all_users_to_sp_and_bound_keys";
+
+    private static final boolean FIX_UNLOCKED_DEVICE_REQUIRED_KEYS =
+            android.security.Flags.fixUnlockedDeviceRequiredKeys();
 
     // Duration that LockSettingsService will store the gatekeeper password for. This allows
     // multiple biometric enrollments without prompting the user to enter their password via
@@ -853,9 +857,11 @@
         @Override
         public void onReceive(Context context, Intent intent) {
             if (Intent.ACTION_USER_ADDED.equals(intent.getAction())) {
-                // Notify keystore that a new user was added.
-                final int userHandle = intent.getIntExtra(Intent.EXTRA_USER_HANDLE, 0);
-                AndroidKeyStoreMaintenance.onUserAdded(userHandle);
+                if (!FIX_UNLOCKED_DEVICE_REQUIRED_KEYS) {
+                    // Notify keystore that a new user was added.
+                    final int userHandle = intent.getIntExtra(Intent.EXTRA_USER_HANDLE, 0);
+                    AndroidKeyStoreMaintenance.onUserAdded(userHandle);
+                }
             } else if (Intent.ACTION_USER_STARTING.equals(intent.getAction())) {
                 final int userHandle = intent.getIntExtra(Intent.EXTRA_USER_HANDLE, 0);
                 mStorage.prefetchUser(userHandle);
@@ -1019,24 +1025,53 @@
             }
             mEarlyCreatedUsers = null; // no longer needed
 
-            // Also do a one-time migration of all users to SP-based credentials with the CE key
-            // encrypted by the SP.  This is needed for the system user on the first boot of a
-            // device, as the system user is special and never goes through the user creation flow
-            // that other users do.  It is also needed for existing users on a device upgraded from
-            // Android 13 or earlier, where users with no LSKF didn't necessarily have an SP, and if
-            // they did have an SP then their CE key wasn't encrypted by it.
+            // Do a one-time migration for any unsecured users: create the user's synthetic password
+            // if not already done, encrypt the user's CE key with the synthetic password if not
+            // already done, and create the user's Keystore super keys if not already done.
             //
-            // If this gets interrupted (e.g. by the device powering off), there shouldn't be a
-            // problem since this will run again on the next boot, and setCeStorageProtection() is
-            // okay with the CE key being already protected by the given secret.
-            if (getString(MIGRATED_SP_CE_ONLY, null, 0) == null) {
-                for (UserInfo user : mUserManager.getAliveUsers()) {
-                    removeStateForReusedUserIdIfNecessary(user.id, user.serialNumber);
-                    synchronized (mSpManager) {
-                        migrateUserToSpWithBoundCeKeyLocked(user.id);
+            // This is needed for the following cases:
+            //
+            // - Finalizing the creation of the system user on the first boot of a device, as the
+            //   system user is special and doesn't go through the normal user creation flow.
+            //
+            // - Upgrading from Android 13 or earlier, where unsecured users didn't necessarily have
+            //   a synthetic password, and if they did have a synthetic password their CE key wasn't
+            //   encrypted by it.  Also, unsecured users didn't have Keystore super keys.
+            //
+            // - Upgrading from Android 14, where unsecured users didn't have Keystore super keys.
+            //
+            // The end result is that all users, regardless of whether they are secured or not, have
+            // a synthetic password with all keys initialized and protected by it.
+            //
+            // Note: if this migration gets interrupted (e.g. by the device powering off), there
+            // shouldn't be a problem since this will run again on the next boot, and
+            // setCeStorageProtection() and initKeystoreSuperKeys(..., true) are idempotent.
+            if (FIX_UNLOCKED_DEVICE_REQUIRED_KEYS) {
+                if (!getBoolean(MIGRATED_SP_FULL, false, 0)) {
+                    for (UserInfo user : mUserManager.getAliveUsers()) {
+                        removeStateForReusedUserIdIfNecessary(user.id, user.serialNumber);
+                        synchronized (mSpManager) {
+                            migrateUserToSpWithBoundKeysLocked(user.id);
+                        }
                     }
+                    setBoolean(MIGRATED_SP_FULL, true, 0);
                 }
-                setString(MIGRATED_SP_CE_ONLY, "true", 0);
+            } else {
+                if (getString(MIGRATED_SP_CE_ONLY, null, 0) == null) {
+                    for (UserInfo user : mUserManager.getAliveUsers()) {
+                        removeStateForReusedUserIdIfNecessary(user.id, user.serialNumber);
+                        synchronized (mSpManager) {
+                            migrateUserToSpWithBoundCeKeyLocked(user.id);
+                        }
+                    }
+                    setString(MIGRATED_SP_CE_ONLY, "true", 0);
+                }
+
+                if (getBoolean(MIGRATED_SP_FULL, false, 0)) {
+                    // The FIX_UNLOCKED_DEVICE_REQUIRED_KEYS flag was enabled but then got disabled.
+                    // Ensure the full migration runs again the next time the flag is enabled...
+                    setBoolean(MIGRATED_SP_FULL, false, 0);
+                }
             }
 
             mThirdPartyAppsStarted = true;
@@ -1067,6 +1102,37 @@
         }
     }
 
+    @GuardedBy("mSpManager")
+    private void migrateUserToSpWithBoundKeysLocked(@UserIdInt int userId) {
+        if (isUserSecure(userId)) {
+            Slogf.d(TAG, "User %d is secured; no migration needed", userId);
+            return;
+        }
+        long protectorId = getCurrentLskfBasedProtectorId(userId);
+        if (protectorId == SyntheticPasswordManager.NULL_PROTECTOR_ID) {
+            Slogf.i(TAG, "Migrating unsecured user %d to SP-based credential", userId);
+            initializeSyntheticPassword(userId);
+            return;
+        }
+        Slogf.i(TAG, "Existing unsecured user %d has a synthetic password", userId);
+        AuthenticationResult result = mSpManager.unlockLskfBasedProtector(
+                getGateKeeperService(), protectorId, LockscreenCredential.createNone(), userId,
+                null);
+        SyntheticPassword sp = result.syntheticPassword;
+        if (sp == null) {
+            Slogf.wtf(TAG, "Failed to unwrap synthetic password for unsecured user %d", userId);
+            return;
+        }
+        // While setCeStorageProtection() is idempotent, it does log some error messages when called
+        // again.  Skip it if we know it was already handled by an earlier upgrade to Android 14.
+        if (getString(MIGRATED_SP_CE_ONLY, null, 0) == null) {
+            Slogf.i(TAG, "Encrypting CE key of user %d with synthetic password", userId);
+            setCeStorageProtection(userId, sp);
+        }
+        Slogf.i(TAG, "Initializing Keystore super keys for user %d", userId);
+        initKeystoreSuperKeys(userId, sp, /* allowExisting= */ true);
+    }
+
     /**
      * Returns the lowest password quality that still presents the same UI for entering it.
      *
@@ -1348,6 +1414,20 @@
         AndroidKeyStoreMaintenance.onUserPasswordChanged(userHandle, password);
     }
 
+    @VisibleForTesting /** Note: this method is overridden in unit tests */
+    void initKeystoreSuperKeys(@UserIdInt int userId, SyntheticPassword sp, boolean allowExisting) {
+        final byte[] password = sp.deriveKeyStorePassword();
+        try {
+            int res = AndroidKeyStoreMaintenance.initUserSuperKeys(userId, password, allowExisting);
+            if (res != 0) {
+                throw new IllegalStateException("Failed to initialize Keystore super keys for user "
+                        + userId);
+            }
+        } finally {
+            Arrays.fill(password, (byte) 0);
+        }
+    }
+
     private void unlockKeystore(int userId, SyntheticPassword sp) {
         Authorization.onLockScreenEvent(false, userId, sp.deriveKeyStorePassword(), null);
     }
@@ -2071,6 +2151,9 @@
                 return;
             }
             onSyntheticPasswordUnlocked(userId, result.syntheticPassword);
+            if (FIX_UNLOCKED_DEVICE_REQUIRED_KEYS) {
+                unlockKeystore(userId, result.syntheticPassword);
+            }
             unlockCeStorage(userId, result.syntheticPassword);
         }
     }
@@ -2350,6 +2433,16 @@
     }
 
     private void createNewUser(@UserIdInt int userId, int userSerialNumber) {
+
+        // Delete all Keystore keys for userId, just in case any were left around from a removed
+        // user with the same userId.  This should be unnecessary, but we've been doing this for a
+        // long time, so for now we keep doing it just in case it's ever important.  Don't wait
+        // until initKeystoreSuperKeys() to do this; that can be delayed if the user is being
+        // created during early boot, and maybe something will use Keystore before then.
+        if (FIX_UNLOCKED_DEVICE_REQUIRED_KEYS) {
+            AndroidKeyStoreMaintenance.onUserAdded(userId);
+        }
+
         synchronized (mUserCreationAndRemovalLock) {
             // During early boot, don't actually create the synthetic password yet, but rather
             // automatically delay it to later.  We do this because protecting the synthetic
@@ -2756,7 +2849,7 @@
 
     /**
      * Creates the synthetic password (SP) for the given user, protects it with an empty LSKF, and
-     * protects the user's CE key with a key derived from the SP.
+     * protects the user's CE storage key and Keystore super keys with keys derived from the SP.
      *
      * <p>This is called just once in the lifetime of the user: at user creation time (possibly
      * delayed until the time when Weaver is guaranteed to be available), or when upgrading from
@@ -2775,6 +2868,9 @@
                     LockscreenCredential.createNone(), sp, userId);
             setCurrentLskfBasedProtectorId(protectorId, userId);
             setCeStorageProtection(userId, sp);
+            if (FIX_UNLOCKED_DEVICE_REQUIRED_KEYS) {
+                initKeystoreSuperKeys(userId, sp, /* allowExisting= */ false);
+            }
             onSyntheticPasswordCreated(userId, sp);
             Slogf.i(TAG, "Successfully initialized synthetic password for user %d", userId);
             return sp;
@@ -2867,11 +2963,10 @@
     /**
      * Changes the user's LSKF by creating an LSKF-based protector that uses the new LSKF (which may
      * be empty) and replacing the old LSKF-based protector with it.  The SP itself is not changed.
-     *
-     * Also maintains the invariants described in {@link SyntheticPasswordManager} by
-     * setting/clearing the protection (by the SP) on the user's auth-bound Keystore keys when the
-     * LSKF is added/removed, respectively.  If an LSKF is being added, then the Gatekeeper auth
-     * token is also refreshed.
+     * <p>
+     * Also maintains the invariants described in {@link SyntheticPasswordManager} by enrolling /
+     * deleting the synthetic password into Gatekeeper as the LSKF is set / cleared, and asking
+     * Keystore to delete the user's auth-bound keys when the LSKF is cleared.
      */
     @GuardedBy("mSpManager")
     private long setLockCredentialWithSpLocked(LockscreenCredential credential,
@@ -2890,7 +2985,9 @@
             if (!mSpManager.hasSidForUser(userId)) {
                 mSpManager.newSidForUser(getGateKeeperService(), sp, userId);
                 mSpManager.verifyChallenge(getGateKeeperService(), sp, 0L, userId);
-                setKeystorePassword(sp.deriveKeyStorePassword(), userId);
+                if (!FIX_UNLOCKED_DEVICE_REQUIRED_KEYS) {
+                    setKeystorePassword(sp.deriveKeyStorePassword(), userId);
+                }
             }
         } else {
             // Cache all profile password if they use unified work challenge. This will later be
@@ -2901,7 +2998,11 @@
             gateKeeperClearSecureUserId(userId);
             unlockCeStorage(userId, sp);
             unlockKeystore(userId, sp);
-            setKeystorePassword(null, userId);
+            if (FIX_UNLOCKED_DEVICE_REQUIRED_KEYS) {
+                AndroidKeyStoreMaintenance.onUserLskfRemoved(userId);
+            } else {
+                setKeystorePassword(null, userId);
+            }
             removeBiometricsForUser(userId);
         }
         setCurrentLskfBasedProtectorId(newProtectorId, userId);
diff --git a/services/core/java/com/android/server/locksettings/SyntheticPasswordManager.java b/services/core/java/com/android/server/locksettings/SyntheticPasswordManager.java
index 8e9c21f..cc205d4 100644
--- a/services/core/java/com/android/server/locksettings/SyntheticPasswordManager.java
+++ b/services/core/java/com/android/server/locksettings/SyntheticPasswordManager.java
@@ -90,10 +90,15 @@
  *
  *  - The user's credential-encrypted storage is always protected by the SP.
  *
- *  - The user's auth-bound Keystore keys are protected by the SP, but only while an LSKF is set.
- *    This works by setting the user's Keystore and Gatekeeper passwords to SP-derived secrets, but
- *    only while an LSKF is set.  When the LSKF is removed, these passwords are cleared,
- *    invalidating the user's auth-bound keys.
+ *  - The user's Keystore superencryption keys are always protected by the SP.  These in turn
+ *    protect the Keystore keys that require user authentication, an unlocked device, or both.
+ *
+ *  - A secret derived from the synthetic password is enrolled in Gatekeeper for the user, but only
+ *    while the user has a (nonempty) LSKF.  This enrollment has an associated ID called the Secure
+ *    user ID or SID.  This use of Gatekeeper, which is separate from the use of GateKeeper that may
+ *    be used in the LSKF-based protector, makes it so that unlocking the synthetic password
+ *    generates a HardwareAuthToken (but only when the user has LSKF).  That HardwareAuthToken can
+ *    be provided to KeyMint to authorize the use of the user's authentication-bound Keystore keys.
  *
  * Files stored on disk for each user:
  *   For the SP itself, stored under NULL_PROTECTOR_ID:
diff --git a/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsServiceTestable.java b/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsServiceTestable.java
index 1c33d0d..18961c0 100644
--- a/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsServiceTestable.java
+++ b/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsServiceTestable.java
@@ -34,6 +34,7 @@
 
 import com.android.internal.widget.LockscreenCredential;
 import com.android.server.ServiceThread;
+import com.android.server.locksettings.SyntheticPasswordManager.SyntheticPassword;
 import com.android.server.locksettings.recoverablekeystore.RecoverableKeyStoreManager;
 import com.android.server.pm.UserManagerInternal;
 
@@ -203,6 +204,10 @@
     }
 
     @Override
+    void initKeystoreSuperKeys(int userId, SyntheticPassword sp, boolean allowExisting) {
+    }
+
+    @Override
     protected boolean isCredentialSharableWithParent(int userId) {
         UserInfo userInfo = mUserManager.getUserInfo(userId);
         return userInfo.isCloneProfile() || userInfo.isManagedProfile();