diff --git a/Android.mk b/Android.mk
index 4cd3dd0..1c85809 100644
--- a/Android.mk
+++ b/Android.mk
@@ -38,8 +38,6 @@
 	external/scrypt/lib/crypto \
 	frameworks/native/include \
 	system/security/keystore \
-	hardware/libhardware/include/hardware \
-	system/security/softkeymaster/include/keymaster
 
 common_shared_libraries := \
 	libsysutils \
@@ -58,6 +56,7 @@
 	libhardware \
 	libsoftkeymaster \
 	libbase \
+	libsoftkeymasterdevice \
 	libkeymaster_messages \
 
 common_static_libraries := \
diff --git a/KeyStorage.cpp b/KeyStorage.cpp
index 986f403..e6c91f5 100644
--- a/KeyStorage.cpp
+++ b/KeyStorage.cpp
@@ -23,6 +23,7 @@
 #include <vector>
 
 #include <errno.h>
+#include <stdio.h>
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <sys/wait.h>
@@ -66,6 +67,7 @@
 static const std::string kStretchPrefix_scrypt = "scrypt ";
 static const char* kFn_encrypted_key = "encrypted_key";
 static const char* kFn_keymaster_key_blob = "keymaster_key_blob";
+static const char* kFn_keymaster_key_blob_upgraded = "keymaster_key_blob_upgraded";
 static const char* kFn_salt = "salt";
 static const char* kFn_secdiscardable = "secdiscardable";
 static const char* kFn_stretching = "stretching";
@@ -122,8 +124,8 @@
     return keymaster.generateKey(paramBuilder.build(), key);
 }
 
-static keymaster::AuthorizationSetBuilder beginParams(const KeyAuthentication& auth,
-                                                      const std::string& appId) {
+static keymaster::AuthorizationSet beginParams(const KeyAuthentication& auth,
+                                               const std::string& appId) {
     auto paramBuilder = keymaster::AuthorizationSetBuilder()
                             .Authorization(keymaster::TAG_BLOCK_MODE, KM_MODE_GCM)
                             .Authorization(keymaster::TAG_MAC_LENGTH, GCM_MAC_BYTES * 8)
@@ -133,45 +135,7 @@
         LOG(DEBUG) << "Supplying auth token to Keymaster";
         addStringParam(&paramBuilder, keymaster::TAG_AUTH_TOKEN, auth.token);
     }
-    return paramBuilder;
-}
-
-static bool encryptWithKeymasterKey(Keymaster& keymaster, const std::string& key,
-                                    const KeyAuthentication& auth, const std::string& appId,
-                                    const std::string& message, std::string* ciphertext) {
-    auto params = beginParams(auth, appId).build();
-    keymaster::AuthorizationSet outParams;
-    auto opHandle = keymaster.begin(KM_PURPOSE_ENCRYPT, key, params, &outParams);
-    if (!opHandle) return false;
-    keymaster_blob_t nonceBlob;
-    if (!outParams.GetTagValue(keymaster::TAG_NONCE, &nonceBlob)) {
-        LOG(ERROR) << "GCM encryption but no nonce generated";
-        return false;
-    }
-    // nonceBlob here is just a pointer into existing data, must not be freed
-    std::string nonce(reinterpret_cast<const char*>(nonceBlob.data), nonceBlob.data_length);
-    if (!checkSize("nonce", nonce.size(), GCM_NONCE_BYTES)) return false;
-    std::string body;
-    if (!opHandle.updateCompletely(message, &body)) return false;
-
-    std::string mac;
-    if (!opHandle.finishWithOutput(&mac)) return false;
-    if (!checkSize("mac", mac.size(), GCM_MAC_BYTES)) return false;
-    *ciphertext = nonce + body + mac;
-    return true;
-}
-
-static bool decryptWithKeymasterKey(Keymaster& keymaster, const std::string& key,
-                                    const KeyAuthentication& auth, const std::string& appId,
-                                    const std::string& ciphertext, std::string* message) {
-    auto nonce = ciphertext.substr(0, GCM_NONCE_BYTES);
-    auto bodyAndMac = ciphertext.substr(GCM_NONCE_BYTES);
-    auto params = addStringParam(beginParams(auth, appId), keymaster::TAG_NONCE, nonce).build();
-    auto opHandle = keymaster.begin(KM_PURPOSE_DECRYPT, key, params);
-    if (!opHandle) return false;
-    if (!opHandle.updateCompletely(bodyAndMac, message)) return false;
-    if (!opHandle.finish()) return false;
-    return true;
+    return paramBuilder.build();
 }
 
 static bool readFileToString(const std::string& filename, std::string* result) {
@@ -190,6 +154,79 @@
     return true;
 }
 
+static KeymasterOperation begin(Keymaster& keymaster, const std::string& dir,
+                                keymaster_purpose_t purpose,
+                                const keymaster::AuthorizationSet &keyParams,
+                                const keymaster::AuthorizationSet &opParams,
+                                keymaster::AuthorizationSet* outParams) {
+    auto kmKeyPath = dir + "/" + kFn_keymaster_key_blob;
+    std::string kmKey;
+    if (!readFileToString(kmKeyPath, &kmKey)) return KeymasterOperation();
+    keymaster::AuthorizationSet inParams;
+    inParams.push_back(keyParams);
+    inParams.push_back(opParams);
+    for (;;) {
+        auto opHandle = keymaster.begin(purpose, kmKey, inParams, outParams);
+        if (opHandle) {
+            return opHandle;
+        }
+        if (opHandle.error() != KM_ERROR_KEY_REQUIRES_UPGRADE) return opHandle;
+        LOG(DEBUG) << "Upgrading key: " << dir;
+        std::string newKey;
+        if (!keymaster.upgradeKey(kmKey, keyParams, &newKey)) return KeymasterOperation();
+        auto newKeyPath = dir + "/" + kFn_keymaster_key_blob_upgraded;
+        if (!writeStringToFile(newKey, newKeyPath)) return KeymasterOperation();
+        if (rename(newKeyPath.c_str(), kmKeyPath.c_str()) != 0) {
+            PLOG(ERROR) << "Unable to move upgraded key to location: " << kmKeyPath;
+            return KeymasterOperation();
+        }
+        if (!keymaster.deleteKey(kmKey)) {
+            LOG(ERROR) << "Key deletion failed during upgrade, continuing anyway: " << dir;
+        }
+        kmKey = newKey;
+        LOG(INFO) << "Key upgraded: " << dir;
+    }
+}
+
+static bool encryptWithKeymasterKey(Keymaster& keymaster, const std::string& dir,
+                                    const keymaster::AuthorizationSet &keyParams,
+                                    const std::string& message, std::string* ciphertext) {
+    keymaster::AuthorizationSet opParams;
+    keymaster::AuthorizationSet outParams;
+    auto opHandle = begin(keymaster, dir, KM_PURPOSE_ENCRYPT, keyParams, opParams, &outParams);
+    if (!opHandle) return false;
+    keymaster_blob_t nonceBlob;
+    if (!outParams.GetTagValue(keymaster::TAG_NONCE, &nonceBlob)) {
+        LOG(ERROR) << "GCM encryption but no nonce generated";
+        return false;
+    }
+    // nonceBlob here is just a pointer into existing data, must not be freed
+    std::string nonce(reinterpret_cast<const char*>(nonceBlob.data), nonceBlob.data_length);
+    if (!checkSize("nonce", nonce.size(), GCM_NONCE_BYTES)) return false;
+    std::string body;
+    if (!opHandle.updateCompletely(message, &body)) return false;
+
+    std::string mac;
+    if (!opHandle.finish(&mac)) return false;
+    if (!checkSize("mac", mac.size(), GCM_MAC_BYTES)) return false;
+    *ciphertext = nonce + body + mac;
+    return true;
+}
+
+static bool decryptWithKeymasterKey(Keymaster& keymaster, const std::string& dir,
+                                    const keymaster::AuthorizationSet &keyParams,
+                                    const std::string& ciphertext, std::string* message) {
+    auto nonce = ciphertext.substr(0, GCM_NONCE_BYTES);
+    auto bodyAndMac = ciphertext.substr(GCM_NONCE_BYTES);
+    auto opParams = addStringParam(keymaster::AuthorizationSetBuilder(),
+                                   keymaster::TAG_NONCE, nonce).build();
+    auto opHandle = begin(keymaster, dir, KM_PURPOSE_DECRYPT, keyParams, opParams, nullptr);
+    if (!opHandle) return false;
+    if (!opHandle.updateCompletely(bodyAndMac, message)) return false;
+    if (!opHandle.finish(nullptr)) return false;
+    return true;
+}
+
 static std::string getStretching() {
     char paramstr[PROPERTY_VALUE_MAX];
 
@@ -273,8 +310,9 @@
     std::string kmKey;
     if (!generateKeymasterKey(keymaster, auth, appId, &kmKey)) return false;
     if (!writeStringToFile(kmKey, dir + "/" + kFn_keymaster_key_blob)) return false;
+    auto keyParams = beginParams(auth, appId);
     std::string encryptedKey;
-    if (!encryptWithKeymasterKey(keymaster, kmKey, auth, appId, key, &encryptedKey)) return false;
+    if (!encryptWithKeymasterKey(keymaster, dir, keyParams, key, &encryptedKey)) return false;
     if (!writeStringToFile(encryptedKey, dir + "/" + kFn_encrypted_key)) return false;
     return true;
 }
@@ -296,13 +334,12 @@
     }
     std::string appId;
     if (!generateAppId(auth, stretching, salt, secdiscardable, &appId)) return false;
-    std::string kmKey;
-    if (!readFileToString(dir + "/" + kFn_keymaster_key_blob, &kmKey)) return false;
     std::string encryptedMessage;
     if (!readFileToString(dir + "/" + kFn_encrypted_key, &encryptedMessage)) return false;
     Keymaster keymaster;
     if (!keymaster) return false;
-    return decryptWithKeymasterKey(keymaster, kmKey, auth, appId, encryptedMessage, key);
+    auto keyParams = beginParams(auth, appId);
+    return decryptWithKeymasterKey(keymaster, dir, keyParams, encryptedMessage, key);
 }
 
 static bool deleteKey(const std::string& dir) {
diff --git a/Keymaster.cpp b/Keymaster.cpp
index c43613e..722d9f2 100644
--- a/Keymaster.cpp
+++ b/Keymaster.cpp
@@ -20,6 +20,7 @@
 #include <hardware/hardware.h>
 #include <hardware/keymaster1.h>
 #include <hardware/keymaster2.h>
+#include <keymaster/keymaster_configuration.h>
 
 namespace android {
 namespace vold {
@@ -31,6 +32,9 @@
     virtual keymaster_error_t generate_key(const keymaster_key_param_set_t* params,
                                            keymaster_key_blob_t* key_blob) const = 0;
     virtual keymaster_error_t delete_key(const keymaster_key_blob_t* key) const = 0;
+    virtual keymaster_error_t upgrade_key(const keymaster_key_blob_t* key_to_upgrade,
+                                         const keymaster_key_param_set_t* upgrade_params,
+                                         keymaster_key_blob_t* upgraded_key) const = 0;
     virtual keymaster_error_t begin(keymaster_purpose_t purpose, const keymaster_key_blob_t* key,
                                     const keymaster_key_param_set_t* in_params,
                                     keymaster_key_param_set_t* out_params,
@@ -88,6 +92,11 @@
   public:
     explicit Keymaster1Device(keymaster1_device_t* d) : KeymasterDevice<keymaster1_device_t>{d} {}
     ~Keymaster1Device() override final { keymaster1_close(mDevice); }
+    keymaster_error_t upgrade_key(const keymaster_key_blob_t* key_to_upgrade,
+                                  const keymaster_key_param_set_t* upgrade_params,
+                                  keymaster_key_blob_t* upgraded_key) const override final {
+        return KM_ERROR_UNIMPLEMENTED;
+    }
     keymaster_error_t finish(keymaster_operation_handle_t operation_handle,
                              const keymaster_key_param_set_t* in_params,
                              const keymaster_blob_t* signature,
@@ -101,6 +110,11 @@
   public:
     explicit Keymaster2Device(keymaster2_device_t* d) : KeymasterDevice<keymaster2_device_t>{d} {}
     ~Keymaster2Device() override final { keymaster2_close(mDevice); }
+    keymaster_error_t upgrade_key(const keymaster_key_blob_t* key_to_upgrade,
+                                  const keymaster_key_param_set_t* upgrade_params,
+                                  keymaster_key_blob_t* upgraded_key) const override final {
+        return mDevice->upgrade_key(mDevice, key_to_upgrade, upgrade_params, upgraded_key);
+    }
     keymaster_error_t finish(keymaster_operation_handle_t operation_handle,
                              const keymaster_key_param_set_t* in_params,
                              const keymaster_blob_t* signature,
@@ -142,26 +156,19 @@
     return true;
 }
 
-bool KeymasterOperation::finish() {
-    auto error = mDevice->finish(mOpHandle, nullptr, nullptr, nullptr, nullptr);
-    mDevice = nullptr;
-    if (error != KM_ERROR_OK) {
-        LOG(ERROR) << "finish failed, code " << error;
-        return false;
-    }
-    return true;
-}
-
-bool KeymasterOperation::finishWithOutput(std::string* output) {
+bool KeymasterOperation::finish(std::string* output) {
     keymaster_blob_t outputBlob;
-    auto error = mDevice->finish(mOpHandle, nullptr, nullptr, nullptr, &outputBlob);
+    auto error = mDevice->finish(mOpHandle, nullptr, nullptr, nullptr,
+        output ? &outputBlob : nullptr);
     mDevice = nullptr;
     if (error != KM_ERROR_OK) {
         LOG(ERROR) << "finish failed, code " << error;
         return false;
     }
-    output->assign(reinterpret_cast<const char*>(outputBlob.data), outputBlob.data_length);
-    free(const_cast<uint8_t*>(outputBlob.data));
+    if (output) {
+        output->assign(reinterpret_cast<const char*>(outputBlob.data), outputBlob.data_length);
+        free(const_cast<uint8_t*>(outputBlob.data));
+    }
     return true;
 }
 
@@ -173,6 +180,7 @@
         LOG(ERROR) << "hw_get_module_by_class returned " << ret;
         return;
     }
+    LOG(DEBUG) << "module_api_version is " << module->module_api_version;
     if (module->module_api_version == KEYMASTER_MODULE_API_VERSION_1_0) {
         keymaster1_device_t* device;
         ret = keymaster1_open(module, &device);
@@ -188,6 +196,11 @@
             LOG(ERROR) << "keymaster2_open returned " << ret;
             return;
         }
+        auto error = ConfigureDevice(device);
+        if (error != KM_ERROR_OK) {
+            LOG(ERROR) << "ConfigureDevice returned " << error;
+            return;
+        }
         mDevice = std::make_shared<Keymaster2Device>(device);
     } else {
         LOG(ERROR) << "module_api_version is " << module->module_api_version;
@@ -217,31 +230,37 @@
     return true;
 }
 
+bool Keymaster::upgradeKey(const std::string& oldKey, const AuthorizationSet& inParams,
+                           std::string* newKey) {
+    keymaster_key_blob_t oldKeyBlob{reinterpret_cast<const uint8_t*>(oldKey.data()), oldKey.size()};
+    keymaster_key_blob_t newKeyBlob;
+    auto error = mDevice->upgrade_key(&oldKeyBlob, &inParams, &newKeyBlob);
+    if (error != KM_ERROR_OK) {
+        LOG(ERROR) << "upgrade_key failed, code " << error;
+        return false;
+    }
+    newKey->assign(reinterpret_cast<const char*>(newKeyBlob.key_material),
+                   newKeyBlob.key_material_size);
+    free(const_cast<uint8_t*>(newKeyBlob.key_material));
+    return true;
+}
+
 KeymasterOperation Keymaster::begin(keymaster_purpose_t purpose, const std::string& key,
                                     const keymaster::AuthorizationSet& inParams,
                                     keymaster::AuthorizationSet* outParams) {
     keymaster_key_blob_t keyBlob{reinterpret_cast<const uint8_t*>(key.data()), key.size()};
     keymaster_operation_handle_t mOpHandle;
     keymaster_key_param_set_t outParams_set;
-    auto error = mDevice->begin(purpose, &keyBlob, &inParams, &outParams_set, &mOpHandle);
+    auto error = mDevice->begin(purpose, &keyBlob, &inParams,
+        outParams ? &outParams_set : nullptr, &mOpHandle);
     if (error != KM_ERROR_OK) {
         LOG(ERROR) << "begin failed, code " << error;
-        return KeymasterOperation(nullptr, mOpHandle);
+        return KeymasterOperation(error);
     }
-    outParams->Clear();
-    outParams->push_back(outParams_set);
-    keymaster_free_param_set(&outParams_set);
-    return KeymasterOperation(mDevice, mOpHandle);
-}
-
-KeymasterOperation Keymaster::begin(keymaster_purpose_t purpose, const std::string& key,
-                                    const keymaster::AuthorizationSet& inParams) {
-    keymaster_key_blob_t keyBlob{reinterpret_cast<const uint8_t*>(key.data()), key.size()};
-    keymaster_operation_handle_t mOpHandle;
-    auto error = mDevice->begin(purpose, &keyBlob, &inParams, nullptr, &mOpHandle);
-    if (error != KM_ERROR_OK) {
-        LOG(ERROR) << "begin failed, code " << error;
-        return KeymasterOperation(nullptr, mOpHandle);
+    if (outParams) {
+        outParams->Clear();
+        outParams->push_back(outParams_set);
+        keymaster_free_param_set(&outParams_set);
     }
     return KeymasterOperation(mDevice, mOpHandle);
 }
diff --git a/Keymaster.h b/Keymaster.h
index 412110c..e314ee1 100644
--- a/Keymaster.h
+++ b/Keymaster.h
@@ -45,25 +45,31 @@
     ~KeymasterOperation();
     // Is this instance valid? This is false if creation fails, and becomes
     // false on finish or if an update fails.
-    explicit operator bool() { return mDevice != nullptr; }
+    explicit operator bool() { return mError == KM_ERROR_OK; }
+    keymaster_error_t error() { return mError; }
     // Call "update" repeatedly until all of the input is consumed, and
     // concatenate the output. Return true on success.
     bool updateCompletely(const std::string& input, std::string* output);
-    // Finish; pass nullptr for the "output" param.
-    bool finish();
-    // Finish and write the output to this string.
-    bool finishWithOutput(std::string* output);
+    // Finish and write the output to this string, unless pointer is null.
+    bool finish(std::string* output);
     // Move constructor
     KeymasterOperation(KeymasterOperation&& rhs) {
-        mOpHandle = std::move(rhs.mOpHandle);
         mDevice = std::move(rhs.mDevice);
+        mOpHandle = std::move(rhs.mOpHandle);
+        mError = std::move(rhs.mError);
     }
+    // Construct an object in an error state for error returns
+    KeymasterOperation() : KeymasterOperation(KM_ERROR_UNKNOWN_ERROR) {}
 
   private:
     KeymasterOperation(std::shared_ptr<IKeymasterDevice> d, keymaster_operation_handle_t h)
-        : mDevice{d}, mOpHandle{h} {}
+        : mDevice{d}, mOpHandle{h}, mError {KM_ERROR_OK} {}
+    KeymasterOperation(keymaster_error_t error)
+        : mDevice{nullptr}, mOpHandle{static_cast<keymaster_operation_handle_t>(0)},
+          mError {error} {}
     std::shared_ptr<IKeymasterDevice> mDevice;
     keymaster_operation_handle_t mOpHandle;
+    keymaster_error_t mError;
     DISALLOW_COPY_AND_ASSIGN(KeymasterOperation);
     friend class Keymaster;
 };
@@ -79,12 +85,12 @@
     bool generateKey(const AuthorizationSet& inParams, std::string* key);
     // If the keymaster supports it, permanently delete a key.
     bool deleteKey(const std::string& key);
-    // Begin a new cryptographic operation, collecting output parameters.
+    // Replace stored key blob in response to KM_ERROR_KEY_REQUIRES_UPGRADE.
+    bool upgradeKey(const std::string& oldKey, const AuthorizationSet& inParams,
+                    std::string* newKey);
+    // Begin a new cryptographic operation, collecting output parameters if pointer is non-null
     KeymasterOperation begin(keymaster_purpose_t purpose, const std::string& key,
                              const AuthorizationSet& inParams, AuthorizationSet* outParams);
-    // Begin a new cryptographic operation; don't collect output parameters.
-    KeymasterOperation begin(keymaster_purpose_t purpose, const std::string& key,
-                             const AuthorizationSet& inParams);
 
   private:
     std::shared_ptr<IKeymasterDevice> mDevice;