diff --git a/keystore/Android.bp b/keystore/Android.bp
index 295d605..366f591 100644
--- a/keystore/Android.bp
+++ b/keystore/Android.bp
@@ -234,6 +234,7 @@
     srcs: [
         ":IKeyAttestationApplicationIdProvider.aidl",
         "auth_token_table.cpp",
+        "blob.cpp",
         "keystore_attestation_id.cpp",
         "KeyAttestationApplicationId.cpp",
         "KeyAttestationPackageInfo.cpp",
diff --git a/keystore/blob.cpp b/keystore/blob.cpp
index f08e08d..f887e80 100644
--- a/keystore/blob.cpp
+++ b/keystore/blob.cpp
@@ -559,15 +559,23 @@
  * [0-o]. Therefore in the worst case the length of a key gets doubled. Note
  * that Base64 cannot be used here due to the need of prefix match on keys. */
 
-static std::string encodeKeyName(const std::string& keyName) {
+std::string encodeKeyName(const std::string& keyName) {
     std::string encodedName;
     encodedName.reserve(keyName.size() * 2);
     auto in = keyName.begin();
     while (in != keyName.end()) {
+        // Input character needs to be encoded.
         if (*in < '0' || *in > '~') {
+            // Encode the two most-significant bits of the input char in the first
+            // output character, by counting up from 43 ('+').
             encodedName.append(1, '+' + (uint8_t(*in) >> 6));
+            // Encode the six least-significant bits of the input char in the second
+            // output character, by counting up from 48 ('0').
+            // This is safe because the maximum value is 112, which is the
+            // character 'p'.
             encodedName.append(1, '0' + (*in & 0x3F));
         } else {
+            // No need to encode input char - append as-is.
             encodedName.append(1, *in);
         }
         ++in;
@@ -575,7 +583,7 @@
     return encodedName;
 }
 
-static std::string decodeKeyName(const std::string& encodedName) {
+std::string decodeKeyName(const std::string& encodedName) {
     std::string decodedName;
     decodedName.reserve(encodedName.size());
     auto in = encodedName.begin();
@@ -583,12 +591,19 @@
     char c;
     while (in != encodedName.end()) {
         if (multichar) {
+            // Second part of a multi-character encoding. Turn off the multichar
+            // flag and set the six least-significant bits of c to the value originally
+            // encoded by counting up from '0'.
             multichar = false;
-            decodedName.append(1, c | *in);
+            decodedName.append(1, c | (uint8_t(*in) - '0'));
         } else if (*in >= '+' && *in <= '.') {
+            // First part of a multi-character encoding. Set the multichar flag
+            // and set the two most-significant bits of c to be the two bits originally
+            // encoded by counting up from '+'.
             multichar = true;
             c = (*in - '+') << 6;
         } else {
+            // Regular character, append as-is.
             decodedName.append(1, *in);
         }
         ++in;
diff --git a/keystore/blob.h b/keystore/blob.h
index a7f9fd0..92e4514 100644
--- a/keystore/blob.h
+++ b/keystore/blob.h
@@ -272,4 +272,8 @@
     inline const KeyBlobEntry* operator->() const { return entry_; }
 };
 
+// Visible for testing
+std::string encodeKeyName(const std::string& keyName);
+std::string decodeKeyName(const std::string& encodedName);
+
 #endif  // KEYSTORE_BLOB_H_
diff --git a/keystore/keymaster_worker.cpp b/keystore/keymaster_worker.cpp
index 6dc055f..2f2d8f5 100644
--- a/keystore/keymaster_worker.cpp
+++ b/keystore/keymaster_worker.cpp
@@ -339,7 +339,6 @@
                         CAPTURE_MOVE(worker_cb)]() mutable {
         // Concurrently executed
 
-        auto key = blob2hidlVec(keyBlob);
         auto& dev = keymasterDevice_;
 
         KeyCharacteristics characteristics;
@@ -384,7 +383,7 @@
         }
 
         // Create a keyid for this key.
-        auto keyid = KeymasterEnforcement::CreateKeyId(key);
+        auto keyid = KeymasterEnforcement::CreateKeyId(blob2hidlVec(keyBlob));
         if (!keyid) {
             ALOGE("Failed to create a key ID for authorization checking.");
             return worker_cb(operationFailed(ErrorCode::UNKNOWN_ERROR));
@@ -427,12 +426,26 @@
         };
 
         do {
-            rc = KS_HANDLE_HIDL_ERROR(
-                dev->begin(purpose, key, opParams.hidl_data(), authToken, hidlCb));
+            rc = KS_HANDLE_HIDL_ERROR(dev->begin(purpose, blob2hidlVec(keyBlob),
+                                                 opParams.hidl_data(), authToken, hidlCb));
             if (!rc.isOk()) {
                 LOG(ERROR) << "Got error " << rc << " from begin()";
                 return worker_cb(operationFailed(ResponseCode::SYSTEM_ERROR));
             }
+
+            if (result.resultCode == ErrorCode::KEY_REQUIRES_UPGRADE) {
+                std::tie(rc, keyBlob) = upgradeKeyBlob(lockedEntry, opParams);
+                if (!rc.isOk()) {
+                    return worker_cb(operationFailed(rc));
+                }
+
+                rc = KS_HANDLE_HIDL_ERROR(dev->begin(purpose, blob2hidlVec(keyBlob),
+                                                     opParams.hidl_data(), authToken, hidlCb));
+                if (!rc.isOk()) {
+                    LOG(ERROR) << "Got error " << rc << " from begin()";
+                    return worker_cb(operationFailed(ResponseCode::SYSTEM_ERROR));
+                }
+            }
             // If there are too many operations abort the oldest operation that was
             // started as pruneable and try again.
         } while (result.resultCode == ErrorCode::TOO_MANY_OPERATIONS && pruneOperation());
diff --git a/keystore/keystore_client_impl.cpp b/keystore/keystore_client_impl.cpp
index 18e9eb1..6fe0f31 100644
--- a/keystore/keystore_client_impl.cpp
+++ b/keystore/keystore_client_impl.cpp
@@ -436,7 +436,7 @@
     int32_t result;
     auto binder_result = keystore_->exist(key_name16, kDefaultUID, &result);
     if (!binder_result.isOk()) return false;  // binder error
-    return result;
+    return result == static_cast<int32_t>(ResponseCode::NO_ERROR);
 }
 
 bool KeystoreClientImpl::listKeys(const std::string& prefix,
diff --git a/keystore/tests/Android.bp b/keystore/tests/Android.bp
index 103fa0e..1ce1210 100644
--- a/keystore/tests/Android.bp
+++ b/keystore/tests/Android.bp
@@ -11,6 +11,7 @@
         "aaid_truncation_test.cpp",
         "auth_token_table_test.cpp",
         "auth_token_formatting_test.cpp",
+        "blob_test.cpp",
         "confirmationui_rate_limiting_test.cpp",
         "gtest_main.cpp",
     ],
diff --git a/keystore/tests/blob_test.cpp b/keystore/tests/blob_test.cpp
new file mode 100644
index 0000000..485bd88
--- /dev/null
+++ b/keystore/tests/blob_test.cpp
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <gtest/gtest.h>
+
+#include <string>
+#include <utils/String16.h>
+
+#include "../blob.h"
+
+namespace keystore {
+
+namespace test {
+
+namespace {
+
+constexpr const char* kNameToEncode = "some key name !\\ %#|\"";
+
+}  // namespace
+
+TEST(BlobTest, nameEncodingAndDecodingTest) {
+    std::string toEncode(kNameToEncode);
+    std::string decoded(decodeKeyName(encodeKeyName(toEncode)));
+
+    ASSERT_EQ(toEncode, decoded);
+}
+
+}  // namespace test
+}  // namespace keystore