diff --git a/identity/Credential.cpp b/identity/Credential.cpp
index 49b412f..59a4d81 100644
--- a/identity/Credential.cpp
+++ b/identity/Credential.cpp
@@ -22,6 +22,7 @@
 
 #include <android/security/identity/ICredentialStore.h>
 
+#include <android/security/keystore/BnCredstoreTokenCallback.h>
 #include <android/security/keystore/IKeystoreService.h>
 #include <binder/IPCThreadState.h>
 #include <binder/IServiceManager.h>
@@ -29,6 +30,8 @@
 
 #include <cppbor.h>
 #include <cppbor_parse.h>
+#include <future>
+#include <tuple>
 
 #include "Credential.h"
 #include "CredentialData.h"
@@ -39,6 +42,8 @@
 namespace identity {
 
 using std::optional;
+using std::promise;
+using std::tuple;
 
 using android::security::keystore::IKeystoreService;
 
@@ -48,7 +53,9 @@
 using ::android::hardware::identity::support::sha256;
 
 using android::hardware::keymaster::V4_0::HardwareAuthToken;
+using android::hardware::keymaster::V4_0::VerificationToken;
 using AidlHardwareAuthToken = android::hardware::keymaster::HardwareAuthToken;
+using AidlVerificationToken = android::hardware::keymaster::VerificationToken;
 
 Credential::Credential(CipherSuite cipherSuite, const std::string& dataPath,
                        const std::string& credentialName)
@@ -116,12 +123,22 @@
     return Status::ok();
 }
 
+class CredstoreTokenCallback : public android::security::keystore::BnCredstoreTokenCallback,
+                               public promise<tuple<bool, vector<uint8_t>, vector<uint8_t>>> {
+  public:
+    CredstoreTokenCallback() {}
+    virtual Status onFinished(bool success, const vector<uint8_t>& authToken,
+                              const vector<uint8_t>& verificationToken) override {
+        this->set_value({success, authToken, verificationToken});
+        return Status::ok();
+    }
+};
+
 // Returns false if an error occurred communicating with keystore.
 //
-// Sets |authToken| to the empty vector if an auth token couldn't be obtained.
-//
-bool getAuthTokenFromKeystore(uint64_t challenge, uint64_t secureUserId,
-                              unsigned int authTokenMaxAgeMillis, vector<uint8_t>& authToken) {
+bool getTokensFromKeystore(uint64_t challenge, uint64_t secureUserId,
+                           unsigned int authTokenMaxAgeMillis, vector<uint8_t>& authToken,
+                           vector<uint8_t>& verificationToken) {
     sp<IServiceManager> sm = defaultServiceManager();
     sp<IBinder> binder = sm->getService(String16("android.security.keystore"));
     sp<IKeystoreService> keystore = interface_cast<IKeystoreService>(binder);
@@ -129,13 +146,27 @@
         return false;
     }
 
-    vector<uint8_t> returnedAuthToken;
-    Status ret = keystore->getAuthTokenForCredstore(challenge, secureUserId, authTokenMaxAgeMillis,
-                                                    &returnedAuthToken);
-    if (!ret.isOk()) {
+    sp<CredstoreTokenCallback> callback = new CredstoreTokenCallback();
+    auto future = callback->get_future();
+
+    Status status =
+        keystore->getTokensForCredstore(challenge, secureUserId, authTokenMaxAgeMillis, callback);
+    if (!status.isOk()) {
+        return false;
+    }
+
+    auto fstatus = future.wait_for(std::chrono::milliseconds(5000));
+    if (fstatus != std::future_status::ready) {
+        LOG(ERROR) << "Waited 5 seconds from tokens for credstore, aborting";
+        return false;
+    }
+    auto [success, returnedAuthToken, returnedVerificationToken] = future.get();
+    if (!success) {
+        LOG(ERROR) << "Error getting tokens from credstore";
         return false;
     }
     authToken = returnedAuthToken;
+    verificationToken = returnedVerificationToken;
     return true;
 }
 
@@ -217,16 +248,37 @@
         authTokenMaxAgeMillis = 10 * 1000;
     }
 
-    // Only get an authToken if it's actually needed.
+    // Reset tokens and only get them if they're actually needed, e.g. if user authentication
+    // is needed in any of the access control profiles for data items being requested.
+    //
     AidlHardwareAuthToken aidlAuthToken;
+    AidlVerificationToken aidlVerificationToken;
+    aidlAuthToken.challenge = 0;
+    aidlAuthToken.userId = 0;
+    aidlAuthToken.authenticatorId = 0;
+    aidlAuthToken.authenticatorType =
+        ::android::hardware::keymaster::HardwareAuthenticatorType::NONE;
+    aidlAuthToken.timestamp.milliSeconds = 0;
+    aidlAuthToken.mac.clear();
+    aidlVerificationToken.challenge = 0;
+    aidlVerificationToken.timestamp.milliSeconds = 0;
+    aidlVerificationToken.securityLevel = ::android::hardware::keymaster::SecurityLevel::SOFTWARE;
+    aidlVerificationToken.mac.clear();
     if (userAuthNeeded) {
         vector<uint8_t> authTokenBytes;
-        if (!getAuthTokenFromKeystore(selectedChallenge_, data_->getSecureUserId(),
-                                      authTokenMaxAgeMillis, authTokenBytes)) {
-            LOG(ERROR) << "Error getting auth token from keystore";
+        vector<uint8_t> verificationTokenBytes;
+        if (!getTokensFromKeystore(selectedChallenge_, data_->getSecureUserId(),
+                                   authTokenMaxAgeMillis, authTokenBytes, verificationTokenBytes)) {
+            LOG(ERROR) << "Error getting tokens from keystore";
             return Status::fromServiceSpecificError(ICredentialStore::ERROR_GENERIC,
-                                                    "Error getting auth token from keystore");
+                                                    "Error getting tokens from keystore");
         }
+
+        // It's entirely possible getTokensFromKeystore() succeeded but didn't
+        // return any tokens (in which case the returned byte-vectors are
+        // empty). For example, this can happen if no auth token is available
+        // which satifies e.g. |authTokenMaxAgeMillis|.
+        //
         if (authTokenBytes.size() > 0) {
             HardwareAuthToken authToken =
                 android::hardware::keymaster::V4_0::support::hidlVec2AuthToken(authTokenBytes);
@@ -240,6 +292,22 @@
             aidlAuthToken.timestamp.milliSeconds = int64_t(authToken.timestamp);
             aidlAuthToken.mac = authToken.mac;
         }
+
+        if (verificationTokenBytes.size() > 0) {
+            optional<VerificationToken> token =
+                android::hardware::keymaster::V4_0::support::deserializeVerificationToken(
+                    verificationTokenBytes);
+            if (!token) {
+                LOG(ERROR) << "Error deserializing verification token";
+                return Status::fromServiceSpecificError(ICredentialStore::ERROR_GENERIC,
+                                                        "Error deserializing verification token");
+            }
+            aidlVerificationToken.challenge = token->challenge;
+            aidlVerificationToken.timestamp.milliSeconds = token->timestamp;
+            aidlVerificationToken.securityLevel =
+                ::android::hardware::keymaster::SecurityLevel(token->securityLevel);
+            aidlVerificationToken.mac = token->mac;
+        }
     }
 
     // Note that the selectAuthKey() method is only called if a CryptoObject is involved at
@@ -285,7 +353,14 @@
     // doesn't have this method.
     Status status = halBinder_->setRequestedNamespaces(halRequestNamespaces);
     if (!status.isOk()) {
-        LOG(INFO) << "Failed setting expected requested namespaces assuming V1 HAL "
+        LOG(INFO) << "Failed setting expected requested namespaces, assuming V1 HAL "
+                  << "and continuing";
+    }
+
+    // Pass the verification token. Failure is OK, this method isn't in the V1 HAL.
+    status = halBinder_->setVerificationToken(aidlVerificationToken);
+    if (!status.isOk()) {
+        LOG(INFO) << "Failed setting verification token, assuming V1 HAL "
                   << "and continuing";
     }
 
diff --git a/identity/main.cpp b/identity/main.cpp
index af03a30..8f4968d 100644
--- a/identity/main.cpp
+++ b/identity/main.cpp
@@ -53,6 +53,9 @@
     CHECK(ret == ::android::OK) << "Couldn't register binder service";
     LOG(ERROR) << "Registered binder service";
 
+    // This is needed for binder callbacks from keystore on a ICredstoreTokenCallback binder.
+    android::ProcessState::self()->startThreadPool();
+
     IPCThreadState::self()->joinThreadPool();
 
     return 0;
diff --git a/keystore/Android.bp b/keystore/Android.bp
index 6145047..b881757 100644
--- a/keystore/Android.bp
+++ b/keystore/Android.bp
@@ -294,6 +294,7 @@
     name: "keystore_aidl",
     srcs: [
         "binder/android/security/IConfirmationPromptCallback.aidl",
+        "binder/android/security/keystore/ICredstoreTokenCallback.aidl",
         "binder/android/security/keystore/IKeystoreCertificateChainCallback.aidl",
         "binder/android/security/keystore/IKeystoreExportKeyCallback.aidl",
         "binder/android/security/keystore/IKeystoreKeyCharacteristicsCallback.aidl",
diff --git a/keystore/binder/android/security/keystore/ICredstoreTokenCallback.aidl b/keystore/binder/android/security/keystore/ICredstoreTokenCallback.aidl
new file mode 100644
index 0000000..b42e3d4
--- /dev/null
+++ b/keystore/binder/android/security/keystore/ICredstoreTokenCallback.aidl
@@ -0,0 +1,25 @@
+/**
+ * Copyright (c) 2020, 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.
+ */
+
+package android.security.keystore;
+
+
+/**
+ * @hide
+ */
+oneway interface ICredstoreTokenCallback {
+	void onFinished(boolean success, in byte[] authToken, in byte[] verificationToken);
+}
diff --git a/keystore/binder/android/security/keystore/IKeystoreService.aidl b/keystore/binder/android/security/keystore/IKeystoreService.aidl
index fcea115..6edca56 100644
--- a/keystore/binder/android/security/keystore/IKeystoreService.aidl
+++ b/keystore/binder/android/security/keystore/IKeystoreService.aidl
@@ -19,6 +19,7 @@
 import android.security.keymaster.KeymasterArguments;
 import android.security.keymaster.KeymasterBlob;
 import android.security.keymaster.OperationResult;
+import android.security.keystore.ICredstoreTokenCallback;
 import android.security.keystore.IKeystoreResponseCallback;
 import android.security.keystore.IKeystoreKeyCharacteristicsCallback;
 import android.security.keystore.IKeystoreExportKeyCallback;
@@ -86,5 +87,6 @@
     int listUidsOfAuthBoundKeys(out @utf8InCpp List<String> uids);
 
     // Called by credstore (and only credstore).
-    byte[] getAuthTokenForCredstore(in long challenge, in long secureUserId, in int authTokenMaxAgeMillis);
+    void getTokensForCredstore(in long challenge, in long secureUserId, in int authTokenMaxAgeMillis,
+                               in ICredstoreTokenCallback cb);
 }
diff --git a/keystore/key_store_service.cpp b/keystore/key_store_service.cpp
index 75fcbde..cdc0d64 100644
--- a/keystore/key_store_service.cpp
+++ b/keystore/key_store_service.cpp
@@ -57,6 +57,8 @@
 namespace {
 
 using ::android::binder::Status;
+using android::hardware::keymaster::V4_0::support::authToken2HidlVec;
+using android::hardware::keymaster::V4_0::support::serializeVerificationToken;
 using android::security::keymaster::ExportResult;
 using android::security::keymaster::KeymasterArguments;
 using android::security::keymaster::KeymasterBlob;
@@ -64,6 +66,7 @@
 using android::security::keymaster::operationFailed;
 using android::security::keymaster::OperationResult;
 using ConfirmationResponseCode = android::hardware::confirmationui::V1_0::ResponseCode;
+using ::android::security::keystore::ICredstoreTokenCallback;
 using ::android::security::keystore::IKeystoreOperationResultCallback;
 using ::android::security::keystore::IKeystoreResponseCallback;
 using ::android::security::keystore::KeystoreResponse;
@@ -943,9 +946,9 @@
     return Status::ok();
 }
 
-Status KeyStoreService::getAuthTokenForCredstore(int64_t challenge, int64_t secureUserId,
-                                                 int32_t authTokenMaxAgeMillis,
-                                                 std::vector<uint8_t>* _aidl_return) {
+Status KeyStoreService::getTokensForCredstore(int64_t challenge, int64_t secureUserId,
+                                              int32_t authTokenMaxAgeMillis,
+                                              const ::android::sp<ICredstoreTokenCallback>& cb) {
     uid_t callingUid = IPCThreadState::self()->getCallingUid();
     if (callingUid != AID_CREDSTORE) {
         return Status::fromServiceSpecificError(static_cast<int32_t>(0));
@@ -953,11 +956,48 @@
 
     auto [err, authToken] = mKeyStore->getAuthTokenTable().FindAuthorizationForCredstore(
         challenge, secureUserId, authTokenMaxAgeMillis);
-    std::vector<uint8_t> ret;
-    if (err == AuthTokenTable::OK) {
-        ret = android::hardware::keymaster::V4_0::support::authToken2HidlVec(authToken);
+    // It's entirely possible we couldn't find an authToken (e.g. no user auth
+    // happened within the requested deadline) and in that case, we just
+    // callback immediately signaling success but just not returning any tokens.
+    if (err != AuthTokenTable::OK) {
+        cb->onFinished(true, {} /* serializedAuthToken */, {} /* serializedVerificationToken */);
+        return Status::ok();
     }
-    *_aidl_return = ret;
+
+    // If we did find an authToken, get a verificationToken as well...
+    //
+    std::vector<uint8_t> serializedAuthToken = authToken2HidlVec(authToken);
+    std::vector<uint8_t> serializedVerificationToken;
+    std::shared_ptr<KeymasterWorker> dev = mKeyStore->getDevice(SecurityLevel::TRUSTED_ENVIRONMENT);
+    if (!dev) {
+        LOG(ERROR) << "Unable to get KM device for SecurityLevel::TRUSTED_ENVIRONMENT";
+        dev = mKeyStore->getDevice(SecurityLevel::SOFTWARE);
+        if (!dev) {
+            LOG(ERROR) << "Unable to get KM device for SecurityLevel::SOFTWARE";
+            cb->onFinished(false, {}, {});
+            return Status::fromServiceSpecificError(static_cast<int32_t>(0));
+        }
+    }
+
+    dev->verifyAuthorization(
+        challenge, {} /* params */, authToken,
+        [serializedAuthToken, cb](KeyStoreServiceReturnCode rc, HardwareAuthToken,
+                                  VerificationToken verificationToken) {
+            if (rc != ErrorCode::OK) {
+                LOG(ERROR) << "verifyAuthorization failed, rc=" << rc;
+                cb->onFinished(false, {}, {});
+                return;
+            }
+            std::optional<std::vector<uint8_t>> serializedVerificationToken =
+                serializeVerificationToken(verificationToken);
+            if (!serializedVerificationToken) {
+                LOG(ERROR) << "Error serializing verificationToken";
+                cb->onFinished(false, {}, {});
+                return;
+            }
+            cb->onFinished(true, serializedAuthToken, serializedVerificationToken.value());
+        });
+
     return Status::ok();
 }
 
diff --git a/keystore/key_store_service.h b/keystore/key_store_service.h
index 8c1d508..5fdddb9 100644
--- a/keystore/key_store_service.h
+++ b/keystore/key_store_service.h
@@ -132,9 +132,9 @@
           const ::android::sp<::android::IBinder>& token, int32_t* _aidl_return) override;
     ::android::binder::Status addAuthToken(const ::std::vector<uint8_t>& authToken,
                                            int32_t* _aidl_return) override;
-    ::android::binder::Status
-    getAuthTokenForCredstore(int64_t challenge, int64_t secureUserId, int32_t authTokenMaxAge,
-                             ::std::vector<uint8_t>* _aidl_return) override;
+    ::android::binder::Status getTokensForCredstore(
+        int64_t challenge, int64_t secureUserId, int32_t authTokenMaxAge,
+        const ::android::sp<::android::security::keystore::ICredstoreTokenCallback>& cb) override;
     ::android::binder::Status onUserAdded(int32_t userId, int32_t parentId,
                                           int32_t* _aidl_return) override;
     ::android::binder::Status onUserRemoved(int32_t userId, int32_t* _aidl_return) override;
diff --git a/keystore/tests/Android.bp b/keystore/tests/Android.bp
index eac6fe6..883e020 100644
--- a/keystore/tests/Android.bp
+++ b/keystore/tests/Android.bp
@@ -13,6 +13,7 @@
         "auth_token_formatting_test.cpp",
         "blob_test.cpp",
         "confirmationui_rate_limiting_test.cpp",
+        "verification_token_seralization_test.cpp",
         "gtest_main.cpp",
     ],
     name: "keystore_unit_tests",
diff --git a/keystore/tests/verification_token_seralization_test.cpp b/keystore/tests/verification_token_seralization_test.cpp
new file mode 100644
index 0000000..276541a
--- /dev/null
+++ b/keystore/tests/verification_token_seralization_test.cpp
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2015 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 <keymasterV4_0/keymaster_utils.h>
+
+namespace keystore {
+namespace test {
+
+using android::hardware::keymaster::V4_0::SecurityLevel;
+using android::hardware::keymaster::V4_0::VerificationToken;
+using android::hardware::keymaster::V4_0::support::deserializeVerificationToken;
+using android::hardware::keymaster::V4_0::support::serializeVerificationToken;
+using std::optional;
+using std::vector;
+
+TEST(VerificationTokenSeralizationTest, SerializationTest) {
+    VerificationToken token;
+    token.challenge = 12345;
+    token.timestamp = 67890;
+    token.securityLevel = SecurityLevel::TRUSTED_ENVIRONMENT;
+    token.mac.resize(32);
+    for (size_t n = 0; n < 32; n++) {
+        token.mac[n] = n;
+    }
+    optional<vector<uint8_t>> serialized = serializeVerificationToken(token);
+    ASSERT_TRUE(serialized.has_value());
+    optional<VerificationToken> deserialized = deserializeVerificationToken(serialized.value());
+    ASSERT_TRUE(deserialized.has_value());
+    ASSERT_EQ(token.challenge, deserialized.value().challenge);
+    ASSERT_EQ(token.timestamp, deserialized.value().timestamp);
+    ASSERT_EQ(token.securityLevel, deserialized.value().securityLevel);
+    ASSERT_EQ(0u, deserialized.value().parametersVerified.size());
+    ASSERT_EQ(token.mac, deserialized.value().mac);
+}
+
+TEST(VerificationTokenSeralizationTest, SerializationTestNoMac) {
+    VerificationToken token;
+    token.challenge = 12345;
+    token.timestamp = 67890;
+    token.securityLevel = SecurityLevel::TRUSTED_ENVIRONMENT;
+    token.mac.resize(0);
+    optional<vector<uint8_t>> serialized = serializeVerificationToken(token);
+    ASSERT_TRUE(serialized.has_value());
+    optional<VerificationToken> deserialized = deserializeVerificationToken(serialized.value());
+    ASSERT_TRUE(deserialized.has_value());
+    ASSERT_EQ(token.challenge, deserialized.value().challenge);
+    ASSERT_EQ(token.timestamp, deserialized.value().timestamp);
+    ASSERT_EQ(token.securityLevel, deserialized.value().securityLevel);
+    ASSERT_EQ(0u, deserialized.value().parametersVerified.size());
+    ASSERT_EQ(token.mac, deserialized.value().mac);
+}
+
+}  // namespace test
+}  // namespace keystore