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 fc85616..583f5b6 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