diff --git a/keystore/blob.cpp b/keystore/blob.cpp
index 7ee26f7..0e09262 100644
--- a/keystore/blob.cpp
+++ b/keystore/blob.cpp
@@ -71,12 +71,20 @@
     return mBlob.flags & KEYSTORE_FLAG_ENCRYPTED;
 }
 
+bool Blob::isSuperEncrypted() const {
+    return mBlob.flags & KEYSTORE_FLAG_SUPER_ENCRYPTED;
+}
+
+inline uint8_t setFlag(uint8_t flags, bool set, KeyStoreFlag flag) {
+    return set ? (flags | flag) : (flags & ~flag);
+}
+
 void Blob::setEncrypted(bool encrypted) {
-    if (encrypted) {
-        mBlob.flags |= KEYSTORE_FLAG_ENCRYPTED;
-    } else {
-        mBlob.flags &= ~KEYSTORE_FLAG_ENCRYPTED;
-    }
+    mBlob.flags = setFlag(mBlob.flags, encrypted, KEYSTORE_FLAG_ENCRYPTED);
+}
+
+void Blob::setSuperEncrypted(bool superEncrypted) {
+    mBlob.flags = setFlag(mBlob.flags, superEncrypted, KEYSTORE_FLAG_SUPER_ENCRYPTED);
 }
 
 void Blob::setFallback(bool fallback) {
@@ -90,7 +98,7 @@
 ResponseCode Blob::writeBlob(const char* filename, AES_KEY* aes_key, State state,
                              Entropy* entropy) {
     ALOGV("writing blob %s", filename);
-    if (isEncrypted()) {
+    if (isEncrypted() || isSuperEncrypted()) {
         if (state != STATE_NO_ERROR) {
             ALOGD("couldn't insert encrypted blob while not unlocked");
             return ResponseCode::LOCKED;
@@ -115,7 +123,7 @@
 
     mBlob.length = htonl(mBlob.length);
 
-    if (isEncrypted()) {
+    if (isEncrypted() || isSuperEncrypted()) {
         MD5(mBlob.digested, digestedLength, mBlob.digest);
 
         uint8_t vector[AES_BLOCK_SIZE];
@@ -168,7 +176,7 @@
         return ResponseCode::VALUE_CORRUPTED;
     }
 
-    if (isEncrypted() && (state != STATE_NO_ERROR)) {
+    if ((isEncrypted() || isSuperEncrypted()) && (state != STATE_NO_ERROR)) {
         return ResponseCode::LOCKED;
     }
 
diff --git a/keystore/blob.h b/keystore/blob.h
index d4b5a84..f710641 100644
--- a/keystore/blob.h
+++ b/keystore/blob.h
@@ -95,6 +95,9 @@
     bool isEncrypted() const;
     void setEncrypted(bool encrypted);
 
+    bool isSuperEncrypted() const;
+    void setSuperEncrypted(bool superEncrypted);
+
     bool isFallback() const { return mBlob.flags & KEYSTORE_FLAG_FALLBACK; }
     void setFallback(bool fallback);
 
diff --git a/keystore/include/keystore/keystore.h b/keystore/include/keystore/keystore.h
index 6f13820..6d67edb 100644
--- a/keystore/include/keystore/keystore.h
+++ b/keystore/include/keystore/keystore.h
@@ -47,10 +47,16 @@
 /*
  * All the flags for import and insert calls.
  */
-enum {
+enum KeyStoreFlag : uint8_t {
     KEYSTORE_FLAG_NONE = 0,
     KEYSTORE_FLAG_ENCRYPTED = 1 << 0,
     KEYSTORE_FLAG_FALLBACK = 1 << 1,
+    // KEYSTORE_FLAG_SUPER_ENCRYPTED is for blobs that are already encrypted by keymaster but have
+    // an additional layer of password-based encryption applied.  The same encryption scheme is used
+    // as KEYSTORE_FLAG_ENCRYPTED, but it's safe to remove super-encryption when the password is
+    // cleared, rather than deleting blobs, and the error returned when attempting to use a
+    // super-encrypted blob while keystore is locked is different.
+    KEYSTORE_FLAG_SUPER_ENCRYPTED = 1 << 2,
 };
 
 /**
diff --git a/keystore/key_store_service.cpp b/keystore/key_store_service.cpp
index cd81674..1a60be4 100644
--- a/keystore/key_store_service.cpp
+++ b/keystore/key_store_service.cpp
@@ -40,15 +40,29 @@
 #include <keystore/keystore_hidl_support.h>
 
 namespace keystore {
+
 using namespace android;
 
-const size_t MAX_OPERATIONS = 15;
+namespace {
+
+constexpr size_t MAX_OPERATIONS = 15;
 
 struct BIGNUM_Delete {
     void operator()(BIGNUM* p) const { BN_free(p); }
 };
 typedef UniquePtr<BIGNUM, BIGNUM_Delete> Unique_BIGNUM;
 
+bool containsTag(const hidl_vec<KeyParameter>& params, Tag tag) {
+    return params.end() != std::find_if(params.begin(), params.end(),
+                                        [&](auto& param) { return param.tag == tag; });
+}
+
+bool isAuthenticationBound(const hidl_vec<KeyParameter>& params) {
+    return !containsTag(params, Tag::NO_AUTH_REQUIRED);
+}
+
+}  // anonymous namespace
+
 void KeyStoreService::binderDied(const wp<IBinder>& who) {
     auto operations = mOperationMap.getOperationsForToken(who.unsafe_get());
     for (const auto& token : operations) {
@@ -642,6 +656,9 @@
 
         Blob keyBlob(&hidlKeyBlob[0], hidlKeyBlob.size(), NULL, 0, ::TYPE_KEYMASTER_10);
         keyBlob.setFallback(usingFallback);
+        if (isAuthenticationBound(params)) {
+            keyBlob.setSuperEncrypted(true);
+        }
         keyBlob.setEncrypted(flags & KEYSTORE_FLAG_ENCRYPTED);
 
         error = mKeyStore->put(filename.string(), &keyBlob, get_user_id(uid));
@@ -786,6 +803,9 @@
 
         Blob ksBlob(&keyBlob[0], keyBlob.size(), NULL, 0, ::TYPE_KEYMASTER_10);
         ksBlob.setFallback(usingFallback);
+        if (isAuthenticationBound(params)) {
+            ksBlob.setSuperEncrypted(true);
+        }
         ksBlob.setEncrypted(flags & KEYSTORE_FLAG_ENCRYPTED);
 
         error = mKeyStore->put(filename.string(), &ksBlob, get_user_id(uid));
@@ -922,6 +942,9 @@
     Blob keyBlob;
     String8 name8(name);
     result->resultCode = mKeyStore->getKeyForName(&keyBlob, name8, targetUid, TYPE_KEYMASTER_10);
+    if (result->resultCode == ResponseCode::LOCKED && keyBlob.isSuperEncrypted()) {
+        result->resultCode = ErrorCode::KEY_USER_NOT_AUTHENTICATED;
+    }
     if (!result->resultCode.isOk()) {
         return;
     }
diff --git a/keystore/keystore.cpp b/keystore/keystore.cpp
index 32667e0..bc2e0dc 100644
--- a/keystore/keystore.cpp
+++ b/keystore/keystore.cpp
@@ -175,13 +175,28 @@
             Blob blob;
             ResponseCode rc = get(filename, &blob, ::TYPE_ANY, userId);
 
-            /* get can fail if the blob is encrypted and the state is
-             * not unlocked, only skip deleting blobs that were loaded and
-             * who are not encrypted. If there are blobs we fail to read for
-             * other reasons err on the safe side and delete them since we
-             * can't tell if they're encrypted.
-             */
-            shouldDelete = !(rc == ResponseCode::NO_ERROR && !blob.isEncrypted());
+            switch (rc) {
+            case ResponseCode::SYSTEM_ERROR:
+            case ResponseCode::VALUE_CORRUPTED:
+                // If we can't read blobs, delete them.
+                shouldDelete = true;
+                break;
+
+            case ResponseCode::NO_ERROR:
+            case ResponseCode::LOCKED:
+                // Delete encrypted blobs but keep unencrypted blobs and super-encrypted blobs.  We
+                // need to keep super-encrypted blobs so we can report that the user is
+                // unauthenticated if a caller tries to use them, rather than reporting that they
+                // don't exist.
+                shouldDelete = blob.isEncrypted();
+                break;
+
+            default:
+                ALOGE("Got unexpected return code %d from KeyStore::get()", rc);
+                // This shouldn't happen.  To be on the safe side, delete it.
+                shouldDelete = true;
+                break;
+            }
         }
         if (shouldDelete) {
             del(filename, ::TYPE_ANY, userId);
@@ -272,8 +287,7 @@
             importKey(keyBlob->getValue(), keyBlob->getLength(), filename, userId,
                       keyBlob->isEncrypted() ? KEYSTORE_FLAG_ENCRYPTED : KEYSTORE_FLAG_NONE);
 
-        // The HAL allowed the import, reget the key to have the "fresh"
-        // version.
+        // The HAL allowed the import, reget the key to have the "fresh" version.
         if (imported == ResponseCode::NO_ERROR) {
             rc = get(filename, keyBlob, TYPE_KEY_PAIR, userId);
         }