diff --git a/CryptCommandListener.cpp b/CryptCommandListener.cpp
index 75c840f..4221fcf 100644
--- a/CryptCommandListener.cpp
+++ b/CryptCommandListener.cpp
@@ -380,10 +380,16 @@
         if (!check_argc(cli, subcommand, argc, 3, "<user>")) return 0;
         return sendGenericOkFail(cli, e4crypt_destroy_user_key(atoi(argv[2])));
 
+    } else if (subcommand == "change_user_key") {
+        if (!check_argc(cli, subcommand, argc, 7,
+            "<user> <serial> <token> <old_secret> <new_secret>")) return 0;
+        return sendGenericOkFail(cli, e4crypt_change_user_key(
+            atoi(argv[2]), atoi(argv[3]), argv[4], argv[5], argv[6]));
+
     } else if (subcommand == "unlock_user_key") {
-        if (!check_argc(cli, subcommand, argc, 5, "<user> <serial> <token>")) return 0;
+        if (!check_argc(cli, subcommand, argc, 6, "<user> <serial> <token> <secret>")) return 0;
         return sendGenericOkFail(cli, e4crypt_unlock_user_key(
-            atoi(argv[2]), atoi(argv[3]), parseNull(argv[4])));
+            atoi(argv[2]), atoi(argv[3]), argv[4], argv[5]));
 
     } else if (subcommand == "lock_user_key") {
         if (!check_argc(cli, subcommand, argc, 3, "<user>")) return 0;
diff --git a/Ext4Crypt.cpp b/Ext4Crypt.cpp
index d66fdc6..cae39fb 100644
--- a/Ext4Crypt.cpp
+++ b/Ext4Crypt.cpp
@@ -55,6 +55,7 @@
 #include <android-base/stringprintf.h>
 
 using android::base::StringPrintf;
+using android::vold::kEmptyAuthentication;
 
 // NOTE: keep in sync with StorageManager
 static constexpr int FLAG_STORAGE_DE = 1 << 0;
@@ -94,6 +95,9 @@
     // Map user ids to key references
     std::map<userid_t, std::string> s_de_key_raw_refs;
     std::map<userid_t, std::string> s_ce_key_raw_refs;
+    // TODO abolish this map. Keys should not be long-lived in user memory, only kernel memory.
+    // See b/26948053
+    std::map<userid_t, std::string> s_ce_keys;
 
     // ext4enc:TODO get this const from somewhere good
     const int EXT4_KEY_DESCRIPTOR_SIZE = 8;
@@ -196,21 +200,16 @@
     return StringPrintf("%s/ce/%d/current", user_key_dir.c_str(), user_id);
 }
 
-static bool read_and_install_key(const std::string &key_path, std::string &raw_ref)
-{
-    std::string key;
-    if (!android::vold::retrieveKey(key_path, key)) return false;
-    if (!install_key(key, raw_ref)) return false;
-    return true;
-}
-
-static bool read_and_install_user_ce_key(userid_t user_id)
-{
+static bool read_and_install_user_ce_key(
+        userid_t user_id, const android::vold::KeyAuthentication &auth) {
     if (s_ce_key_raw_refs.count(user_id) != 0) return true;
-    const auto key_path = get_ce_key_path(user_id);
-    std::string raw_ref;
-    if (!read_and_install_key(key_path, raw_ref)) return false;
-    s_ce_key_raw_refs[user_id] = raw_ref;
+    const auto ce_key_path = get_ce_key_path(user_id);
+    std::string ce_key;
+    if (!android::vold::retrieveKey(ce_key_path, auth, ce_key)) return false;
+    std::string ce_raw_ref;
+    if (!install_key(ce_key, ce_raw_ref)) return false;
+    s_ce_keys[user_id] = ce_key;
+    s_ce_key_raw_refs[user_id] = ce_raw_ref;
     LOG(DEBUG) << "Installed ce key for user " << user_id;
     return true;
 }
@@ -239,7 +238,8 @@
 
 // NB this assumes that there is only one thread listening for crypt commands, because
 // it creates keys in a fixed location.
-static bool store_key(const std::string &key_path, const std::string &key) {
+static bool store_key(const std::string &key_path,
+        const android::vold::KeyAuthentication &auth, const std::string &key) {
     if (path_exists(key_path)) {
         LOG(ERROR) << "Already exists, cannot create key at: " << key_path;
         return false;
@@ -247,7 +247,7 @@
     if (path_exists(user_key_temp)) {
         android::vold::destroyKey(user_key_temp);
     }
-    if (!android::vold::storeKey(user_key_temp, key)) return false;
+    if (!android::vold::storeKey(user_key_temp, auth, key)) return false;
     if (rename(user_key_temp.c_str(), key_path.c_str()) != 0) {
         PLOG(ERROR) << "Unable to move new key to location: " << key_path;
         return false;
@@ -264,16 +264,17 @@
         // If the key should be created as ephemeral, don't store it.
         s_ephemeral_users.insert(user_id);
     } else {
-        if (!store_key(get_de_key_path(user_id), de_key)) return false;
+        if (!store_key(get_de_key_path(user_id), kEmptyAuthentication, de_key)) return false;
         if (!prepare_dir(user_key_dir + "/ce/" + std::to_string(user_id),
             0700, AID_ROOT, AID_ROOT)) return false;
-        if (!store_key(get_ce_key_path(user_id), ce_key)) return false;
+        if (!store_key(get_ce_key_path(user_id), kEmptyAuthentication, ce_key)) return false;
     }
     std::string de_raw_ref;
     if (!install_key(de_key, de_raw_ref)) return false;
     s_de_key_raw_refs[user_id] = de_raw_ref;
     std::string ce_raw_ref;
     if (!install_key(ce_key, ce_raw_ref)) return false;
+    s_ce_keys[user_id] = ce_key;
     s_ce_key_raw_refs[user_id] = ce_raw_ref;
     LOG(DEBUG) << "Created keys for user " << user_id;
     return true;
@@ -329,8 +330,11 @@
         }
         userid_t user_id = atoi(entry->d_name);
         if (s_de_key_raw_refs.count(user_id) == 0) {
+            auto key_path = de_dir + "/" + entry->d_name;
+            std::string key;
+            if (!android::vold::retrieveKey(key_path, kEmptyAuthentication, key)) return false;
             std::string raw_ref;
-            if (!read_and_install_key(de_dir + "/" + entry->d_name, raw_ref)) return false;
+            if (!install_key(key, raw_ref)) return false;
             s_de_key_raw_refs[user_id] = raw_ref;
             LOG(DEBUG) << "Installed de key for user " << user_id;
         }
@@ -351,7 +355,7 @@
 
     std::string device_key;
     std::string device_key_path = std::string(path) + device_key_leaf;
-    if (!android::vold::retrieveKey(device_key_path, device_key)) {
+    if (!android::vold::retrieveKey(device_key_path, kEmptyAuthentication, device_key)) {
         LOG(INFO) << "Creating new key";
         if (!random_key(device_key)) {
             return -1;
@@ -362,7 +366,7 @@
             android::vold::destroyKey(key_temp);
         }
 
-        if (!android::vold::storeKey(key_temp, device_key)) return false;
+        if (!android::vold::storeKey(key_temp, kEmptyAuthentication, device_key)) return false;
         if (rename(key_temp.c_str(), device_key_path.c_str()) != 0) {
             PLOG(ERROR) << "Unable to move new key to location: "
                         << device_key_path;
@@ -453,9 +457,12 @@
         return 0;
     }
     bool success = true;
+    s_ce_keys.erase(user_id);
     std::string raw_ref;
     success &= lookup_key_ref(s_ce_key_raw_refs, user_id, raw_ref) && evict_key(raw_ref);
+    s_ce_key_raw_refs.erase(user_id);
     success &= lookup_key_ref(s_de_key_raw_refs, user_id, raw_ref) && evict_key(raw_ref);
+    s_de_key_raw_refs.erase(user_id);
     auto it = s_ephemeral_users.find(user_id);
     if (it != s_ephemeral_users.end()) {
         s_ephemeral_users.erase(it);
@@ -496,11 +503,58 @@
     return 0;
 }
 
+static bool parse_hex(const char *hex, std::string &result) {
+    if (strcmp("!", hex) == 0) {
+        result = "";
+        return true;
+    }
+    if (android::vold::HexToStr(hex, result) != 0) {
+        LOG(ERROR) << "Invalid FBE hex string"; // Don't log the string for security reasons
+        return false;
+    }
+    return true;
+}
+
+int e4crypt_change_user_key(userid_t user_id, int serial,
+        const char* token_hex, const char* old_secret_hex, const char* new_secret_hex) {
+    LOG(DEBUG) << "e4crypt_change_user_key " << user_id << " serial=" << serial <<
+        " token_present=" << (strcmp(token_hex, "!") != 0);
+    if (!e4crypt_is_native()) return 0;
+    if (s_ephemeral_users.count(user_id) != 0) return 0;
+    std::string token, old_secret, new_secret;
+    if (!parse_hex(token_hex, token)) return -1;
+    if (!parse_hex(old_secret_hex, old_secret)) return -1;
+    if (!parse_hex(new_secret_hex, new_secret)) return -1;
+    auto auth = new_secret.empty()
+        ? kEmptyAuthentication
+        : android::vold::KeyAuthentication(token, new_secret);
+    auto it = s_ce_keys.find(user_id);
+    if (it == s_ce_keys.end()) {
+        LOG(ERROR) << "Key not loaded into memory, can't change for user " << user_id;
+        return -1;
+    }
+    auto ce_key = it->second;
+    auto ce_key_path = get_ce_key_path(user_id);
+    android::vold::destroyKey(ce_key_path);
+    if (!store_key(ce_key_path, auth, ce_key)) return -1;
+    return 0;
+}
+
 // TODO: rename to 'install' for consistency, and take flags to know which keys to install
-int e4crypt_unlock_user_key(userid_t user_id, int serial, const char* token) {
-    LOG(DEBUG) << "e4crypt_unlock_user_key " << user_id << " " << (token != nullptr);
+int e4crypt_unlock_user_key(userid_t user_id, int serial,
+        const char* token_hex, const char* secret_hex) {
+    LOG(DEBUG) << "e4crypt_unlock_user_key " << user_id << " serial=" << serial <<
+        " token_present=" << (strcmp(token_hex, "!") != 0);
     if (e4crypt_is_native()) {
-        if (!read_and_install_user_ce_key(user_id)) {
+        if (s_ce_key_raw_refs.count(user_id) != 0) {
+            LOG(WARNING) << "Tried to unlock already-unlocked key for user " << user_id;
+            return 0;
+        }
+        std::string token, secret;
+        if (!parse_hex(token_hex, token)) return false;
+        if (!parse_hex(secret_hex, secret)) return false;
+        android::vold::KeyAuthentication auth(token, secret);
+        if (!read_and_install_user_ce_key(user_id, auth)) {
             LOG(ERROR) << "Couldn't read key for " << user_id;
             return -1;
         }
diff --git a/Ext4Crypt.h b/Ext4Crypt.h
index d732e86..80838c8 100644
--- a/Ext4Crypt.h
+++ b/Ext4Crypt.h
@@ -28,8 +28,11 @@
 int e4crypt_init_user0();
 int e4crypt_vold_create_user_key(userid_t user_id, int serial, bool ephemeral);
 int e4crypt_destroy_user_key(userid_t user_id);
+int e4crypt_change_user_key(userid_t user_id, int serial,
+    const char* token, const char* old_secret, const char* new_secret);
 
-int e4crypt_unlock_user_key(userid_t user_id, int serial, const char* token);
+int e4crypt_unlock_user_key(userid_t user_id, int serial,
+    const char* token, const char* secret);
 int e4crypt_lock_user_key(userid_t user_id);
 
 int e4crypt_prepare_user_storage(const char* volume_uuid, userid_t user_id,
diff --git a/KeyStorage.cpp b/KeyStorage.cpp
index 070b79d..def1a32 100644
--- a/KeyStorage.cpp
+++ b/KeyStorage.cpp
@@ -37,17 +37,22 @@
 namespace android {
 namespace vold {
 
+const KeyAuthentication kEmptyAuthentication { "", "" };
+
 static constexpr size_t AES_KEY_BYTES = 32;
 static constexpr size_t GCM_NONCE_BYTES = 12;
 static constexpr size_t GCM_MAC_BYTES = 16;
 // FIXME: better name than "secdiscardable" sought!
 static constexpr size_t SECDISCARDABLE_BYTES = 1<<14;
 
+static const char* kCurrentVersion = "1";
 static const char* kRmPath = "/system/bin/rm";
 static const char* kSecdiscardPath = "/system/bin/secdiscard";
-static const char* kFn_keymaster_key_blob = "keymaster_key_blob";
 static const char* kFn_encrypted_key = "encrypted_key";
+static const char* kFn_keymaster_key_blob = "keymaster_key_blob";
 static const char* kFn_secdiscardable = "secdiscardable";
+static const char* kFn_stretching = "stretching";
+static const char* kFn_version = "version";
 
 static bool checkSize(const std::string& kind, size_t actual, size_t expected) {
     if (actual != expected) {
@@ -160,11 +165,23 @@
     return true;
 }
 
-bool storeKey(const std::string &dir, const std::string &key) {
+static keymaster::AuthorizationSet buildParams(
+        const KeyAuthentication &auth, const std::string &secdiscardable) {
+    keymaster::AuthorizationSetBuilder paramBuilder;
+    auto appId = hashSecdiscardable(secdiscardable) + auth.secret;
+    addStringParam(paramBuilder, keymaster::TAG_APPLICATION_ID, appId);
+    if (!auth.token.empty()) {
+        addStringParam(paramBuilder, keymaster::TAG_AUTH_TOKEN, auth.token);
+    }
+    return paramBuilder.build();
+}
+
+bool storeKey(const std::string &dir, const KeyAuthentication &auth, const std::string &key) {
     if (TEMP_FAILURE_RETRY(mkdir(dir.c_str(), 0700)) == -1) {
         PLOG(ERROR) << "key mkdir " << dir;
         return false;
     }
+    if (!writeStringToFile(kCurrentVersion, dir + "/" +  kFn_version)) return false;
     std::string secdiscardable;
     if (ReadRandomBytes(SECDISCARDABLE_BYTES, secdiscardable) != OK) {
         // TODO status_t plays badly with PLOG, fix it.
@@ -172,8 +189,10 @@
         return false;
     }
     if (!writeStringToFile(secdiscardable, dir + "/" + kFn_secdiscardable)) return false;
-    auto extraParams = addStringParam(keymaster::AuthorizationSetBuilder(),
-            keymaster::TAG_APPLICATION_ID, hashSecdiscardable(secdiscardable)).build();
+    // Future proofing for when we add key stretching per b/27056334
+    auto stretching = auth.secret.empty() ? "nopassword" : "none";
+    if (!writeStringToFile(stretching, dir + "/" +  kFn_stretching)) return false;
+    auto extraParams = buildParams(auth, secdiscardable);
     Keymaster keymaster;
     if (!keymaster) return false;
     std::string kmKey;
@@ -186,11 +205,16 @@
     return true;
 }
 
-bool retrieveKey(const std::string &dir, std::string &key) {
+bool retrieveKey(const std::string &dir, const KeyAuthentication &auth, std::string &key) {
+    std::string version;
+    if (!readFileToString(dir + "/" + kFn_version, version)) return false;
+    if (version != kCurrentVersion) {
+        LOG(ERROR) << "Version mismatch, expected " << kCurrentVersion << " got " << version;
+        return false;
+    }
     std::string secdiscardable;
     if (!readFileToString(dir + "/" + kFn_secdiscardable, secdiscardable)) return false;
-    auto extraParams = addStringParam(keymaster::AuthorizationSetBuilder(),
-            keymaster::TAG_APPLICATION_ID, hashSecdiscardable(secdiscardable)).build();
+    auto extraParams = buildParams(auth, secdiscardable);
     std::string kmKey;
     if (!readFileToString(dir + "/" + kFn_keymaster_key_blob, kmKey)) return false;
     std::string encryptedMessage;
diff --git a/KeyStorage.h b/KeyStorage.h
index a35349c..54c3b2c 100644
--- a/KeyStorage.h
+++ b/KeyStorage.h
@@ -22,14 +22,27 @@
 namespace android {
 namespace vold {
 
+// Represents the information needed to decrypt a disk encryption key.
+// If "token" is nonempty, it is passed in as a required Gatekeeper auth token.
+// If "secret" is nonempty, it is appended to the application-specific
+// binary needed to unlock.
+class KeyAuthentication {
+public:
+    KeyAuthentication(std::string t, std::string s): token {t}, secret {s} {};
+    const std::string token;
+    const std::string secret;
+};
+
+extern const KeyAuthentication kEmptyAuthentication;
+
 // Create a directory at the named path, and store "key" in it,
 // in such a way that it can only be retrieved via Keymaster and
 // can be securely deleted.
 // It's safe to move/rename the directory after creation.
-bool storeKey(const std::string &dir, const std::string &key);
+bool storeKey(const std::string &dir, const KeyAuthentication &auth, const std::string &key);
 
 // Retrieve the key from the named directory.
-bool retrieveKey(const std::string &dir, std::string &key);
+bool retrieveKey(const std::string &dir, const KeyAuthentication &auth, std::string &key);
 
 // Securely destroy the key stored in the named directory and delete the directory.
 bool destroyKey(const std::string &dir);
diff --git a/Keymaster.h b/Keymaster.h
index 003baa6..a4deddf 100644
--- a/Keymaster.h
+++ b/Keymaster.h
@@ -33,7 +33,6 @@
 // This is tailored to the needs of KeyStorage, but could be extended to be
 // a more general interface.
 
-
 // Wrapper for a keymaster_operation_handle_t representing an
 // ongoing Keymaster operation.  Aborts the operation
 // in the destructor if it is unfinished. Methods log failures
@@ -100,6 +99,12 @@
     return params.Authorization(tag, val.data(), val.size());
 }
 
+template <keymaster_tag_t Tag>
+inline void addStringParam(AuthorizationSetBuilder &params,
+        TypedTag<KM_BYTES, Tag> tag, const std::string& val) {
+    params.Authorization(tag, val.data(), val.size());
+}
+
 }  // namespace vold
 }  // namespace android