diff --git a/identity/Credential.cpp b/identity/Credential.cpp
index 4a2bae1..a3c72ed 100644
--- a/identity/Credential.cpp
+++ b/identity/Credential.cpp
@@ -117,26 +117,42 @@
                                                 "Error loading data for credential");
     }
 
-    selectedAuthKey_ = data->selectAuthKey(allowUsingExhaustedKeys, allowUsingExpiredKeys);
-    if (selectedAuthKey_ == nullptr) {
+    // We just check if a key is available, we actually don't store it since we
+    // don't keep CredentialData around between binder calls.
+    const AuthKeyData* authKey =
+        data->selectAuthKey(allowUsingExhaustedKeys, allowUsingExpiredKeys);
+    if (authKey == nullptr) {
         return Status::fromServiceSpecificError(
             ICredentialStore::ERROR_NO_AUTHENTICATION_KEY_AVAILABLE,
             "No suitable authentication key available");
     }
 
+    if (!ensureChallenge()) {
+        return Status::fromServiceSpecificError(ICredentialStore::ERROR_GENERIC,
+                                                "Error getting challenge (bug in HAL or TA)");
+    }
+    *_aidl_return = selectedChallenge_;
+    return Status::ok();
+}
+
+bool Credential::ensureChallenge() {
+    if (selectedChallenge_ != 0) {
+        return true;
+    }
+
     int64_t challenge;
     Status status = halBinder_->createAuthChallenge(&challenge);
     if (!status.isOk()) {
-        return halStatusToGenericError(status);
+        LOG(ERROR) << "Error getting challenge: " << status.exceptionMessage();
+        return false;
     }
     if (challenge == 0) {
-        return Status::fromServiceSpecificError(ICredentialStore::ERROR_GENERIC,
-                                                "Returned challenge is 0 (bug in HAL or TA)");
+        LOG(ERROR) << "Returned challenge is 0 (bug in HAL or TA)";
+        return false;
     }
 
     selectedChallenge_ = challenge;
-    *_aidl_return = challenge;
-    return Status::ok();
+    return true;
 }
 
 class CredstoreTokenCallback : public android::security::keystore::BnCredstoreTokenCallback,
@@ -279,13 +295,6 @@
         }
     }
 
-    // If requesting a challenge-based authToken the idea is that authentication
-    // happens as part of the transaction. As such, authTokenMaxAgeMillis should
-    // be nearly zero. We'll use 10 seconds for this.
-    if (userAuthNeeded && selectedChallenge_ != 0) {
-        authTokenMaxAgeMillis = 10 * 1000;
-    }
-
     // 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.
     //
@@ -303,6 +312,28 @@
     aidlVerificationToken.securityLevel = ::android::hardware::keymaster::SecurityLevel::SOFTWARE;
     aidlVerificationToken.mac.clear();
     if (userAuthNeeded) {
+        // If user authentication is needed, always get a challenge from the
+        // HAL/TA since it'll need it to check the returned VerificationToken
+        // for freshness.
+        if (!ensureChallenge()) {
+            return Status::fromServiceSpecificError(ICredentialStore::ERROR_GENERIC,
+                                                    "Error getting challenge (bug in HAL or TA)");
+        }
+
+        // Note: if all selected profiles require auth-on-every-presentation
+        // then authTokenMaxAgeMillis will be 0 (because timeoutMillis for each
+        // profile is 0). Which means that keystore will only return an
+        // AuthToken if its challenge matches what we pass, regardless of its
+        // age. This is intended b/c the HAL/TA will check not care about
+        // the age in this case, it only cares that the challenge matches.
+        //
+        // Otherwise, if one or more of the profiles is auth-with-a-timeout then
+        // authTokenMaxAgeMillis will be set to the largest of those
+        // timeouts. We'll get an AuthToken which satisfies this deadline if it
+        // exists. This authToken _may_ have the requested challenge but it's
+        // not a guarantee and it's also not required.
+        //
+
         vector<uint8_t> authTokenBytes;
         vector<uint8_t> verificationTokenBytes;
         if (!getTokensFromKeystore(selectedChallenge_, data->getSecureUserId(),
@@ -320,6 +351,7 @@
         if (authTokenBytes.size() > 0) {
             HardwareAuthToken authToken =
                 android::hardware::keymaster::V4_0::support::hidlVec2AuthToken(authTokenBytes);
+
             // Convert from HIDL to AIDL...
             aidlAuthToken.challenge = int64_t(authToken.challenge);
             aidlAuthToken.userId = int64_t(authToken.userId);
@@ -351,15 +383,25 @@
     // Note that the selectAuthKey() method is only called if a CryptoObject is involved at
     // the Java layer. So we could end up with no previously selected auth key and we may
     // need one.
-    const AuthKeyData* authKey = selectedAuthKey_;
-    if (sessionTranscript.size() > 0) {
-        if (authKey == nullptr) {
-            authKey = data->selectAuthKey(allowUsingExhaustedKeys, allowUsingExpiredKeys);
-            if (authKey == nullptr) {
-                return Status::fromServiceSpecificError(
-                    ICredentialStore::ERROR_NO_AUTHENTICATION_KEY_AVAILABLE,
-                    "No suitable authentication key available");
-            }
+    //
+    const AuthKeyData* authKey =
+        data->selectAuthKey(allowUsingExhaustedKeys, allowUsingExpiredKeys);
+    if (authKey == nullptr) {
+        // If no authKey is available, consider it an error only when a
+        // SessionTranscript was provided.
+        //
+        // We allow no SessionTranscript to be provided because it makes
+        // the API simpler to deal with insofar it can be used without having
+        // to generate any authentication keys.
+        //
+        // In this "no SessionTranscript is provided" mode we don't return
+        // DeviceNameSpaces nor a MAC over DeviceAuthentication so we don't
+        // need a device key.
+        //
+        if (sessionTranscript.size() > 0) {
+            return Status::fromServiceSpecificError(
+                ICredentialStore::ERROR_NO_AUTHENTICATION_KEY_AVAILABLE,
+                "No suitable authentication key available and one is needed");
         }
     }
     vector<uint8_t> signingKeyBlob;
@@ -750,31 +792,36 @@
     //
     // It is because of this we need to set the CredentialKey certificate chain,
     // keyCount, and maxUsesPerKey below.
-    sp<WritableCredential> writableCredential =
-        new WritableCredential(dataPath_, credentialName_, docType.value(), true, hwInfo_,
-                               halWritableCredential, halApiVersion_);
+    sp<WritableCredential> writableCredential = new WritableCredential(
+        dataPath_, credentialName_, docType.value(), true, hwInfo_, halWritableCredential);
 
     writableCredential->setAttestationCertificate(data->getAttestationCertificate());
     auto [keyCount, maxUsesPerKey] = data->getAvailableAuthenticationKeys();
     writableCredential->setAvailableAuthenticationKeys(keyCount, maxUsesPerKey);
 
-    // Because its data has changed, we need to reconnect to the HAL when the
-    // credential has been updated... otherwise the remote object will have
-    // stale data for future calls (e.g. getAuthKeysNeedingCertification().
+    // Because its data has changed, we need to replace the binder for the
+    // IIdentityCredential when the credential has been updated... otherwise the
+    // remote object will have stale data for future calls, for example
+    // getAuthKeysNeedingCertification().
     //
-    // The joys and pitfalls of mutable objects...
+    // The way this is implemented is that setCredentialToReloadWhenUpdated()
+    // instructs the WritableCredential to call writableCredentialPersonalized()
+    // on |this|.
     //
-    writableCredential->setCredentialUpdatedCallback([this] {
-        Status status = this->ensureOrReplaceHalBinder();
-        if (!status.isOk()) {
-            LOG(ERROR) << "Error loading credential";
-        }
-    });
+    //
+    writableCredential->setCredentialToReloadWhenUpdated(this);
 
     *_aidl_return = writableCredential;
     return Status::ok();
 }
 
+void Credential::writableCredentialPersonalized() {
+    Status status = ensureOrReplaceHalBinder();
+    if (!status.isOk()) {
+        LOG(ERROR) << "Error reloading credential";
+    }
+}
+
 }  // namespace identity
 }  // namespace security
 }  // namespace android
diff --git a/identity/Credential.h b/identity/Credential.h
index 7f08515..a76f3cc 100644
--- a/identity/Credential.h
+++ b/identity/Credential.h
@@ -50,6 +50,7 @@
     ~Credential();
 
     Status ensureOrReplaceHalBinder();
+    void writableCredentialPersonalized();
 
     // ICredential overrides
     Status createEphemeralKeyPair(vector<uint8_t>* _aidl_return) override;
@@ -94,12 +95,13 @@
     HardwareInformation hwInfo_;
     sp<IIdentityCredentialStore> halStoreBinder_;
 
-    const AuthKeyData* selectedAuthKey_ = nullptr;
     uint64_t selectedChallenge_ = 0;
 
     sp<IIdentityCredential> halBinder_;
     int halApiVersion_;
 
+    bool ensureChallenge();
+
     ssize_t
     calcExpectedDeviceNameSpacesSize(const vector<uint8_t>& requestMessage,
                                      const vector<RequestNamespaceParcel>& requestNamespaces,
diff --git a/identity/CredentialData.h b/identity/CredentialData.h
index b037997..24b55d3 100644
--- a/identity/CredentialData.h
+++ b/identity/CredentialData.h
@@ -55,7 +55,7 @@
 
     vector<uint8_t> certificate;
     vector<uint8_t> keyBlob;
-    int64_t expirationDateMillisSinceEpoch;
+    int64_t expirationDateMillisSinceEpoch = 0;
     vector<uint8_t> staticAuthenticationData;
     vector<uint8_t> pendingCertificate;
     vector<uint8_t> pendingKeyBlob;
diff --git a/identity/CredentialStore.cpp b/identity/CredentialStore.cpp
index f77294e..509e022 100644
--- a/identity/CredentialStore.cpp
+++ b/identity/CredentialStore.cpp
@@ -90,7 +90,7 @@
     }
 
     sp<IWritableCredential> writableCredential = new WritableCredential(
-        dataPath_, credentialName, docType, false, hwInfo_, halWritableCredential, halApiVersion_);
+        dataPath_, credentialName, docType, false, hwInfo_, halWritableCredential);
     *_aidl_return = writableCredential;
     return Status::ok();
 }
diff --git a/identity/WritableCredential.cpp b/identity/WritableCredential.cpp
index d0688b8..a300e51 100644
--- a/identity/WritableCredential.cpp
+++ b/identity/WritableCredential.cpp
@@ -41,15 +41,14 @@
 WritableCredential::WritableCredential(const string& dataPath, const string& credentialName,
                                        const string& docType, bool isUpdate,
                                        HardwareInformation hwInfo,
-                                       sp<IWritableIdentityCredential> halBinder, int halApiVersion)
+                                       sp<IWritableIdentityCredential> halBinder)
     : dataPath_(dataPath), credentialName_(credentialName), docType_(docType), isUpdate_(isUpdate),
-      hwInfo_(std::move(hwInfo)), halBinder_(halBinder), halApiVersion_(halApiVersion) {}
+      hwInfo_(std::move(hwInfo)), halBinder_(halBinder) {}
 
 WritableCredential::~WritableCredential() {}
 
-void WritableCredential::setCredentialUpdatedCallback(
-    std::function<void()>&& onCredentialUpdatedCallback) {
-    onCredentialUpdatedCallback_ = onCredentialUpdatedCallback;
+void WritableCredential::setCredentialToReloadWhenUpdated(sp<Credential> credential) {
+    credentialToReloadWhenUpdated_ = credential;
 }
 
 Status WritableCredential::ensureAttestationCertificateExists(const vector<uint8_t>& challenge) {
@@ -268,7 +267,10 @@
                                                 "Error saving credential data to disk");
     }
 
-    onCredentialUpdatedCallback_();
+    if (credentialToReloadWhenUpdated_) {
+        credentialToReloadWhenUpdated_->writableCredentialPersonalized();
+        credentialToReloadWhenUpdated_.clear();
+    }
 
     *_aidl_return = proofOfProvisioningSignature;
     return Status::ok();
diff --git a/identity/WritableCredential.h b/identity/WritableCredential.h
index 6ff31ae..838b956 100644
--- a/identity/WritableCredential.h
+++ b/identity/WritableCredential.h
@@ -24,6 +24,8 @@
 
 #include <android/hardware/identity/IIdentityCredentialStore.h>
 
+#include "Credential.h"
+
 namespace android {
 namespace security {
 namespace identity {
@@ -38,13 +40,15 @@
   public:
     WritableCredential(const string& dataPath, const string& credentialName, const string& docType,
                        bool isUpdate, HardwareInformation hwInfo,
-                       sp<IWritableIdentityCredential> halBinder, int halApiVersion);
+                       sp<IWritableIdentityCredential> halBinder);
     ~WritableCredential();
 
     // Used when updating a credential
     void setAttestationCertificate(const vector<uint8_t>& attestationCertificate);
     void setAvailableAuthenticationKeys(int keyCount, int maxUsesPerKey);
-    void setCredentialUpdatedCallback(std::function<void()>&& onCredentialUpdatedCallback);
+
+    // Used by Credential::update()
+    void setCredentialToReloadWhenUpdated(sp<Credential> credential);
 
     // IWritableCredential overrides
     Status getCredentialKeyCertificateChain(const vector<uint8_t>& challenge,
@@ -61,13 +65,12 @@
     bool isUpdate_;
     HardwareInformation hwInfo_;
     sp<IWritableIdentityCredential> halBinder_;
-    int halApiVersion_;
 
     vector<uint8_t> attestationCertificate_;
     int keyCount_ = 0;
     int maxUsesPerKey_ = 1;
 
-    std::function<void()> onCredentialUpdatedCallback_ = []() {};
+    sp<Credential> credentialToReloadWhenUpdated_;
 
     ssize_t calcExpectedProofOfProvisioningSize(
         const vector<AccessControlProfileParcel>& accessControlProfiles,
diff --git a/keystore/auth_token_table.cpp b/keystore/auth_token_table.cpp
index 5e6d572..971f9ef 100644
--- a/keystore/auth_token_table.cpp
+++ b/keystore/auth_token_table.cpp
@@ -178,33 +178,39 @@
                                               int64_t authTokenMaxAgeMillis) {
     std::vector<uint64_t> sids = {secureUserId};
     HardwareAuthenticatorType auth_type = HardwareAuthenticatorType::ANY;
-
     time_t now = clock_function_();
+    int64_t nowMillis = now * 1000;
 
-    // challenge-based - the authToken has to contain the given challenge.
-    if (challenge != 0) {
-        auto matching_op = find_if(
-            entries_, [&](Entry& e) { return e.token().challenge == challenge && !e.completed(); });
-        if (matching_op == entries_.end()) {
-            return {AUTH_TOKEN_NOT_FOUND, {}};
-        }
-
-        if (!matching_op->SatisfiesAuth(sids, auth_type)) {
-            return {AUTH_TOKEN_WRONG_SID, {}};
-        }
-
-        if (authTokenMaxAgeMillis > 0) {
-            if (static_cast<int64_t>(matching_op->time_received()) + authTokenMaxAgeMillis <
-                static_cast<int64_t>(now)) {
-                return {AUTH_TOKEN_EXPIRED, {}};
-            }
-        }
-
-        return {OK, matching_op->token()};
+    // It's an error to call this without a non-zero challenge.
+    if (challenge == 0) {
+        return {OP_HANDLE_REQUIRED, {}};
     }
 
-    // Otherwise, no challenge - any authToken younger than the specified maximum
-    // age will do.
+    // First see if we can find a token which matches the given challenge. If we
+    // can, return the newest one. We specifically don't care about its age.
+    //
+    Entry* newest_match_for_challenge = nullptr;
+    for (auto& entry : entries_) {
+        if (entry.token().challenge == challenge && !entry.completed() &&
+            entry.SatisfiesAuth(sids, auth_type)) {
+            if (newest_match_for_challenge == nullptr ||
+                entry.is_newer_than(newest_match_for_challenge)) {
+                newest_match_for_challenge = &entry;
+            }
+        }
+    }
+    if (newest_match_for_challenge != nullptr) {
+        newest_match_for_challenge->UpdateLastUse(now);
+        return {OK, newest_match_for_challenge->token()};
+    }
+
+    // If that didn't work, we'll take the most recent token within the specified
+    // deadline, if any. Of course if the deadline is zero it doesn't make sense
+    // to look at all.
+    if (authTokenMaxAgeMillis == 0) {
+        return {AUTH_TOKEN_NOT_FOUND, {}};
+    }
+
     Entry* newest_match = nullptr;
     for (auto& entry : entries_) {
         if (entry.SatisfiesAuth(sids, auth_type) && entry.is_newer_than(newest_match)) {
@@ -216,11 +222,9 @@
         return {AUTH_TOKEN_NOT_FOUND, {}};
     }
 
-    if (authTokenMaxAgeMillis > 0) {
-        if (static_cast<int64_t>(newest_match->time_received()) + authTokenMaxAgeMillis <
-            static_cast<int64_t>(now)) {
-            return {AUTH_TOKEN_EXPIRED, {}};
-        }
+    int64_t tokenAgeMillis = nowMillis - newest_match->time_received() * 1000;
+    if (tokenAgeMillis >= authTokenMaxAgeMillis) {
+        return {AUTH_TOKEN_EXPIRED, {}};
     }
 
     newest_match->UpdateLastUse(now);
diff --git a/keystore/binder/android/security/keystore/IKeystoreService.aidl b/keystore/binder/android/security/keystore/IKeystoreService.aidl
index e0879dd..3b9a1b4 100644
--- a/keystore/binder/android/security/keystore/IKeystoreService.aidl
+++ b/keystore/binder/android/security/keystore/IKeystoreService.aidl
@@ -87,7 +87,20 @@
     int onKeyguardVisibilityChanged(in boolean isShowing, in int userId);
     int listUidsOfAuthBoundKeys(out @utf8InCpp List<String> uids);
 
-    // Called by credstore (and only credstore).
+    // This method looks through auth-tokens cached by keystore which match
+    // the passed-in |secureUserId|.
+    //
+    // If one or more of these tokens has a |challenge| field which matches
+    // the passed-in |challenge| parameter, the most recent is returned. In
+    // this case the |authTokenMaxAgeMillis| parameter is not used.
+    //
+    // Otherwise, the most recent auth-token of these tokens which is younger
+    // than |authTokenMaxAgeMillis| is returned.
+    //
+    // The passed in |challenge| parameter must always be non-zero.
+    //
+    // This method is called by credstore (and only credstore).
+    //
     void getTokensForCredstore(in long challenge, in long secureUserId, in int authTokenMaxAgeMillis,
                                in ICredstoreTokenCallback cb);
 }