diff --git a/keystore/.clang-format b/keystore/.clang-format
new file mode 100644
index 0000000..5747e19
--- /dev/null
+++ b/keystore/.clang-format
@@ -0,0 +1,10 @@
+BasedOnStyle: LLVM
+IndentWidth: 4
+UseTab: Never
+BreakBeforeBraces: Attach
+AllowShortFunctionsOnASingleLine: Inline
+AllowShortIfStatementsOnASingleLine: false
+IndentCaseLabels: false
+ColumnLimit: 100
+PointerBindsToType: true
+SpacesBeforeTrailingComments: 2
diff --git a/keystore/Android.mk b/keystore/Android.mk
index 8bf2852..3480123 100644
--- a/keystore/Android.mk
+++ b/keystore/Android.mk
@@ -65,3 +65,18 @@
 LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
 LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
 include $(BUILD_SHARED_LIBRARY)
+
+# Library for unit tests
+include $(CLEAR_VARS)
+ifeq ($(USE_32_BIT_KEYSTORE), true)
+LOCAL_MULTILIB := 32
+endif
+LOCAL_CFLAGS := -Wall -Wextra -Werror
+LOCAL_SRC_FILES := auth_token_table.cpp
+LOCAL_MODULE := libkeystore_test
+LOCAL_C_INCLUDES := $(LOCAL_PATH)/include
+LOCAL_STATIC_LIBRARIES := libgtest_main
+LOCAL_SHARED_LIBRARIES := libkeymaster_messages
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
+include $(BUILD_STATIC_LIBRARY)
diff --git a/keystore/IKeystoreService.cpp b/keystore/IKeystoreService.cpp
index adde6b2..d3cec50 100644
--- a/keystore/IKeystoreService.cpp
+++ b/keystore/IKeystoreService.cpp
@@ -312,6 +312,24 @@
     return true;
 }
 
+/**
+ * Read a byte array from in. The data at *data is still owned by the parcel
+ */
+static void readByteArray(const Parcel& in, const uint8_t** data, size_t* length) {
+    ssize_t slength = in.readInt32();
+    if (slength > 0) {
+        *data = reinterpret_cast<const uint8_t*>(in.readInplace(slength));
+        if (*data) {
+            *length = static_cast<size_t>(slength);
+        } else {
+            *length = 0;
+        }
+    } else {
+        *data = NULL;
+        *length = 0;
+    }
+}
+
 // Read a keymaster_key_param_t* from a Parcel for use in a
 // keymaster_key_characteristics_t. This will be free'd by calling
 // keymaster_free_key_characteristics.
@@ -345,12 +363,18 @@
     return NULL;
 }
 
-static void readKeymasterBlob(const Parcel& in, keymaster_blob_t* blob) {
+static std::unique_ptr<keymaster_blob_t> readKeymasterBlob(const Parcel& in) {
+    std::unique_ptr<keymaster_blob_t> blob;
+    if (in.readInt32() != 1) {
+        blob.reset(NULL);
+        return blob;
+    }
     ssize_t length = in.readInt32();
+    blob.reset(new keymaster_blob_t);
     if (length > 0) {
-        blob->data = (uint8_t*) in.readInplace(length);
+        blob->data = reinterpret_cast<const uint8_t*>(in.readInplace(length));
         if (blob->data) {
-            blob->data_length = (size_t) length;
+            blob->data_length = static_cast<size_t>(length);
         } else {
             blob->data_length = 0;
         }
@@ -358,6 +382,7 @@
         blob->data = NULL;
         blob->data_length = 0;
     }
+    return blob;
 }
 
 class BpKeystoreService: public BpInterface<IKeystoreService>
@@ -959,7 +984,6 @@
     {
         Parcel data, reply;
         data.writeInterfaceToken(IKeystoreService::getInterfaceDescriptor());
-        data.writeInt32(bufLength);
         data.writeByteArray(bufLength, buf);
         status_t status = remote()->transact(BnKeystoreService::ADD_RNG_ENTROPY, data, &reply);
         if (status != NO_ERROR) {
@@ -976,13 +1000,15 @@
     };
 
     virtual int32_t generateKey(const String16& name, const KeymasterArguments& params,
-                                int uid, int flags, KeyCharacteristics* outCharacteristics)
+                                const uint8_t* entropy, size_t entropyLength, int uid, int flags,
+                                KeyCharacteristics* outCharacteristics)
     {
         Parcel data, reply;
         data.writeInterfaceToken(IKeystoreService::getInterfaceDescriptor());
         data.writeString16(name);
         data.writeInt32(1);
         params.writeToParcel(&data);
+        data.writeByteArray(entropyLength, entropy);
         data.writeInt32(uid);
         data.writeInt32(flags);
         status_t status = remote()->transact(BnKeystoreService::GENERATE_KEY, data, &reply);
@@ -1002,15 +1028,23 @@
         return ret;
     }
     virtual int32_t getKeyCharacteristics(const String16& name,
-                                          const keymaster_blob_t& clientId,
-                                          const keymaster_blob_t& appData,
+                                          const keymaster_blob_t* clientId,
+                                          const keymaster_blob_t* appData,
                                           KeyCharacteristics* outCharacteristics)
     {
         Parcel data, reply;
         data.writeInterfaceToken(IKeystoreService::getInterfaceDescriptor());
         data.writeString16(name);
-        data.writeByteArray(clientId.data_length, clientId.data);
-        data.writeByteArray(appData.data_length, appData.data);
+        if (clientId) {
+            data.writeByteArray(clientId->data_length, clientId->data);
+        } else {
+            data.writeInt32(-1);
+        }
+        if (appData) {
+            data.writeByteArray(appData->data_length, appData->data);
+        } else {
+            data.writeInt32(-1);
+        }
         status_t status = remote()->transact(BnKeystoreService::GET_KEY_CHARACTERISTICS,
                                              data, &reply);
         if (status != NO_ERROR) {
@@ -1060,8 +1094,8 @@
     }
 
     virtual void exportKey(const String16& name, keymaster_key_format_t format,
-                           const keymaster_blob_t& clientId,
-                           const keymaster_blob_t& appData, ExportResult* result)
+                           const keymaster_blob_t* clientId,
+                           const keymaster_blob_t* appData, ExportResult* result)
     {
         if (!result) {
             return;
@@ -1071,8 +1105,16 @@
         data.writeInterfaceToken(IKeystoreService::getInterfaceDescriptor());
         data.writeString16(name);
         data.writeInt32(format);
-        data.writeByteArray(clientId.data_length, clientId.data);
-        data.writeByteArray(appData.data_length, appData.data);
+        if (clientId) {
+            data.writeByteArray(clientId->data_length, clientId->data);
+        } else {
+            data.writeInt32(-1);
+        }
+        if (appData) {
+            data.writeByteArray(appData->data_length, appData->data);
+        } else {
+            data.writeInt32(-1);
+        }
         status_t status = remote()->transact(BnKeystoreService::EXPORT_KEY, data, &reply);
         if (status != NO_ERROR) {
             ALOGD("exportKey() could not contact remote: %d\n", status);
@@ -1092,7 +1134,8 @@
 
     virtual void begin(const sp<IBinder>& appToken, const String16& name,
                        keymaster_purpose_t purpose, bool pruneable,
-                       const KeymasterArguments& params, KeymasterArguments* outParams,
+                       const KeymasterArguments& params, const uint8_t* entropy,
+                       size_t entropyLength, KeymasterArguments* outParams,
                        OperationResult* result)
     {
         if (!result || !outParams) {
@@ -1106,6 +1149,7 @@
         data.writeInt32(pruneable ? 1 : 0);
         data.writeInt32(1);
         params.writeToParcel(&data);
+        data.writeByteArray(entropyLength, entropy);
         status_t status = remote()->transact(BnKeystoreService::BEGIN, data, &reply);
         if (status != NO_ERROR) {
             ALOGD("begin() could not contact remote: %d\n", status);
@@ -1189,7 +1233,7 @@
         Parcel data, reply;
         data.writeInterfaceToken(IKeystoreService::getInterfaceDescriptor());
         data.writeStrongBinder(token);
-        status_t status = remote()->transact(BnKeystoreService::FINISH, data, &reply);
+        status_t status = remote()->transact(BnKeystoreService::ABORT, data, &reply);
         if (status != NO_ERROR) {
             ALOGD("abort() could not contact remote: %d\n", status);
             return KM_ERROR_UNKNOWN_ERROR;
@@ -1202,6 +1246,45 @@
         }
         return ret;
     }
+
+    virtual bool isOperationAuthorized(const sp<IBinder>& token)
+    {
+        Parcel data, reply;
+        data.writeInterfaceToken(IKeystoreService::getInterfaceDescriptor());
+        data.writeStrongBinder(token);
+        status_t status = remote()->transact(BnKeystoreService::IS_OPERATION_AUTHORIZED, data,
+                                             &reply);
+        if (status != NO_ERROR) {
+            ALOGD("isOperationAuthorized() could not contact remote: %d\n", status);
+            return false;
+        }
+        int32_t err = reply.readExceptionCode();
+        int32_t ret = reply.readInt32();
+        if (err < 0) {
+            ALOGD("isOperationAuthorized() caught exception %d\n", err);
+            return false;
+        }
+        return ret == 1;
+    }
+
+    virtual int32_t addAuthToken(const uint8_t* token, size_t length)
+    {
+        Parcel data, reply;
+        data.writeInterfaceToken(IKeystoreService::getInterfaceDescriptor());
+        data.writeByteArray(length, token);
+        status_t status = remote()->transact(BnKeystoreService::ADD_AUTH_TOKEN, data, &reply);
+        if (status != NO_ERROR) {
+            ALOGD("addAuthToken() could not contact remote: %d\n", status);
+            return -1;
+        }
+        int32_t err = reply.readExceptionCode();
+        int32_t ret = reply.readInt32();
+        if (err < 0) {
+            ALOGD("addAuthToken() caught exception %d\n", err);
+            return -1;
+        }
+        return ret;
+    };
 };
 
 IMPLEMENT_META_INTERFACE(KeystoreService, "android.security.IKeystoreService");
@@ -1530,13 +1613,9 @@
         }
         case ADD_RNG_ENTROPY: {
             CHECK_INTERFACE(IKeystoreService, data, reply);
-            size_t size = data.readInt32();
-            uint8_t* bytes;
-            if (size > 0) {
-                bytes = (uint8_t*) data.readInplace(size);
-            } else {
-                bytes = NULL;
-            }
+            const uint8_t* bytes = NULL;
+            size_t size = 0;
+            readByteArray(data, &bytes, &size);
             int32_t ret = addRngEntropy(bytes, size);
             reply->writeNoException();
             reply->writeInt32(ret);
@@ -1549,10 +1628,14 @@
             if (data.readInt32() != 0) {
                 args.readFromParcel(data);
             }
+            const uint8_t* entropy = NULL;
+            size_t entropyLength = 0;
+            readByteArray(data, &entropy, &entropyLength);
             int32_t uid = data.readInt32();
             int32_t flags = data.readInt32();
             KeyCharacteristics outCharacteristics;
-            int32_t ret = generateKey(name, args, uid, flags, &outCharacteristics);
+            int32_t ret = generateKey(name, args, entropy, entropyLength, uid, flags,
+                                      &outCharacteristics);
             reply->writeNoException();
             reply->writeInt32(ret);
             reply->writeInt32(1);
@@ -1562,11 +1645,11 @@
         case GET_KEY_CHARACTERISTICS: {
             CHECK_INTERFACE(IKeystoreService, data, reply);
             String16 name = data.readString16();
-            keymaster_blob_t clientId, appData;
-            readKeymasterBlob(data, &clientId);
-            readKeymasterBlob(data, &appData);
+            std::unique_ptr<keymaster_blob_t> clientId = readKeymasterBlob(data);
+            std::unique_ptr<keymaster_blob_t> appData = readKeymasterBlob(data);
             KeyCharacteristics outCharacteristics;
-            int ret = getKeyCharacteristics(name, clientId, appData, &outCharacteristics);
+            int ret = getKeyCharacteristics(name, clientId.get(), appData.get(),
+                                            &outCharacteristics);
             reply->writeNoException();
             reply->writeInt32(ret);
             reply->writeInt32(1);
@@ -1581,18 +1664,13 @@
                 args.readFromParcel(data);
             }
             keymaster_key_format_t format = static_cast<keymaster_key_format_t>(data.readInt32());
-            uint8_t* keyData = NULL;
-            ssize_t keyLength = data.readInt32();
-            size_t ukeyLength = (size_t) keyLength;
-            if (keyLength >= 0) {
-                keyData = (uint8_t*) data.readInplace(keyLength);
-            } else {
-                ukeyLength = 0;
-            }
+            const uint8_t* keyData = NULL;
+            size_t keyLength = 0;
+            readByteArray(data, &keyData, &keyLength);
             int32_t uid = data.readInt32();
             int32_t flags = data.readInt32();
             KeyCharacteristics outCharacteristics;
-            int32_t ret = importKey(name, args, format, keyData, ukeyLength, uid, flags,
+            int32_t ret = importKey(name, args, format, keyData, keyLength, uid, flags,
                                     &outCharacteristics);
             reply->writeNoException();
             reply->writeInt32(ret);
@@ -1605,11 +1683,10 @@
             CHECK_INTERFACE(IKeystoreService, data, reply);
             String16 name = data.readString16();
             keymaster_key_format_t format = static_cast<keymaster_key_format_t>(data.readInt32());
-            keymaster_blob_t clientId, appData;
-            readKeymasterBlob(data, &clientId);
-            readKeymasterBlob(data, &appData);
+            std::unique_ptr<keymaster_blob_t> clientId = readKeymasterBlob(data);
+            std::unique_ptr<keymaster_blob_t> appData = readKeymasterBlob(data);
             ExportResult result;
-            exportKey(name, format, clientId, appData, &result);
+            exportKey(name, format, clientId.get(), appData.get(), &result);
             reply->writeNoException();
             reply->writeInt32(1);
             result.writeToParcel(reply);
@@ -1626,9 +1703,13 @@
             if (data.readInt32() != 0) {
                 args.readFromParcel(data);
             }
+            const uint8_t* entropy = NULL;
+            size_t entropyLength = 0;
+            readByteArray(data, &entropy, &entropyLength);
             KeymasterArguments outArgs;
             OperationResult result;
-            begin(token, name, purpose, pruneable, args, &outArgs, &result);
+            begin(token, name, purpose, pruneable, args, entropy, entropyLength, &outArgs,
+                  &result);
             reply->writeNoException();
             reply->writeInt32(1);
             result.writeToParcel(reply);
@@ -1644,16 +1725,11 @@
             if (data.readInt32() != 0) {
                 args.readFromParcel(data);
             }
-            uint8_t* buf = NULL;
-            ssize_t bufLength = data.readInt32();
-            size_t ubufLength = (size_t) bufLength;
-            if (bufLength > 0) {
-                buf = (uint8_t*) data.readInplace(ubufLength);
-            } else {
-                ubufLength = 0;
-            }
+            const uint8_t* buf = NULL;
+            size_t bufLength = 0;
+            readByteArray(data, &buf, &bufLength);
             OperationResult result;
-            update(token, args, buf, ubufLength, &result);
+            update(token, args, buf, bufLength, &result);
             reply->writeNoException();
             reply->writeInt32(1);
             result.writeToParcel(reply);
@@ -1667,16 +1743,11 @@
             if (data.readInt32() != 0) {
                 args.readFromParcel(data);
             }
-            uint8_t* buf = NULL;
-            ssize_t bufLength = data.readInt32();
-            size_t ubufLength = (size_t) bufLength;
-            if (bufLength > 0) {
-                buf = (uint8_t*) data.readInplace(ubufLength);
-            } else {
-                ubufLength = 0;
-            }
+            const uint8_t* buf = NULL;
+            size_t bufLength = 0;
+            readByteArray(data, &buf, &bufLength);
             OperationResult result;
-            finish(token, args, buf, ubufLength, &result);
+            finish(token, args, buf, bufLength, &result);
             reply->writeNoException();
             reply->writeInt32(1);
             result.writeToParcel(reply);
@@ -1692,6 +1763,27 @@
 
             return NO_ERROR;
         }
+        case IS_OPERATION_AUTHORIZED: {
+            CHECK_INTERFACE(IKeystoreService, data, reply);
+            sp<IBinder> token = data.readStrongBinder();
+            bool result = isOperationAuthorized(token);
+            reply->writeNoException();
+            reply->writeInt32(result ? 1 : 0);
+
+            return NO_ERROR;
+        }
+        case ADD_AUTH_TOKEN: {
+            CHECK_INTERFACE(IKeystoreService, data, reply);
+            sp<IBinder> token = data.readStrongBinder();
+            const uint8_t* token_bytes = NULL;
+            size_t size = 0;
+            readByteArray(data, &token_bytes, &size);
+            int32_t result = addAuthToken(token_bytes, size);
+            reply->writeNoException();
+            reply->writeInt32(result);
+
+            return NO_ERROR;
+        }
         default:
             return BBinder::onTransact(code, data, reply, flags);
     }
diff --git a/keystore/auth_token_table.cpp b/keystore/auth_token_table.cpp
new file mode 100644
index 0000000..2ae10a0
--- /dev/null
+++ b/keystore/auth_token_table.cpp
@@ -0,0 +1,198 @@
+/*
+ * 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 "auth_token_table.h"
+
+#include <assert.h>
+#include <time.h>
+
+#include <algorithm>
+
+#include <keymaster/google_keymaster_utils.h>
+#include <keymaster/logger.h>
+
+namespace keymaster {
+
+//
+// Some trivial template wrappers around std algorithms, so they take containers not ranges.
+//
+template <typename Container, typename Predicate>
+typename Container::iterator find_if(Container& container, Predicate pred) {
+    return std::find_if(container.begin(), container.end(), pred);
+}
+
+template <typename Container, typename Predicate>
+typename Container::iterator remove_if(Container& container, Predicate pred) {
+    return std::remove_if(container.begin(), container.end(), pred);
+}
+
+template <typename Container> typename Container::iterator min_element(Container& container) {
+    return std::min_element(container.begin(), container.end());
+}
+
+time_t clock_gettime_raw() {
+    struct timespec time;
+    clock_gettime(CLOCK_MONOTONIC_RAW, &time);
+    return time.tv_sec;
+}
+
+void AuthTokenTable::AddAuthenticationToken(const hw_auth_token_t* auth_token) {
+    Entry new_entry(auth_token, clock_function_());
+    RemoveEntriesSupersededBy(new_entry);
+    if (entries_.size() >= max_entries_) {
+        LOG_W("Auth token table filled up; replacing oldest entry", 0);
+        *min_element(entries_) = std::move(new_entry);
+    } else {
+        entries_.push_back(std::move(new_entry));
+    }
+}
+
+inline bool KeyRequiresAuthentication(const AuthorizationSet& key_info) {
+    return key_info.find(TAG_NO_AUTH_REQUIRED) == -1;
+}
+
+inline bool KeyRequiresAuthPerOperation(const AuthorizationSet& key_info) {
+    return key_info.find(TAG_AUTH_TIMEOUT) == -1;
+}
+
+AuthTokenTable::Error AuthTokenTable::FindAuthorization(const AuthorizationSet& key_info,
+                                                        keymaster_operation_handle_t op_handle,
+                                                        const hw_auth_token_t** found) {
+    if (!KeyRequiresAuthentication(key_info))
+        return AUTH_NOT_REQUIRED;
+
+    hw_authenticator_type_t auth_type = HW_AUTH_NONE;
+    key_info.GetTagValue(TAG_USER_AUTH_TYPE, &auth_type);
+
+    std::vector<uint64_t> key_sids;
+    ExtractSids(key_info, &key_sids);
+
+    if (KeyRequiresAuthPerOperation(key_info))
+        return FindAuthPerOpAuthorization(key_sids, auth_type, op_handle, found);
+    else
+        return FindTimedAuthorization(key_sids, auth_type, key_info, found);
+}
+
+AuthTokenTable::Error AuthTokenTable::FindAuthPerOpAuthorization(
+    const std::vector<uint64_t>& sids, hw_authenticator_type_t auth_type,
+    keymaster_operation_handle_t op_handle, const hw_auth_token_t** found) {
+    if (op_handle == 0)
+        return OP_HANDLE_REQUIRED;
+
+    auto matching_op = find_if(
+        entries_, [&](Entry& e) { return e.token()->challenge == op_handle && !e.completed(); });
+
+    if (matching_op == entries_.end())
+        return AUTH_TOKEN_NOT_FOUND;
+
+    if (!matching_op->SatisfiesAuth(sids, auth_type))
+        return AUTH_TOKEN_WRONG_SID;
+
+    *found = matching_op->token();
+    return OK;
+}
+
+AuthTokenTable::Error AuthTokenTable::FindTimedAuthorization(const std::vector<uint64_t>& sids,
+                                                             hw_authenticator_type_t auth_type,
+                                                             const AuthorizationSet& key_info,
+                                                             const hw_auth_token_t** found) {
+    Entry* newest_match = NULL;
+    for (auto& entry : entries_)
+        if (entry.SatisfiesAuth(sids, auth_type) && entry.is_newer_than(newest_match))
+            newest_match = &entry;
+
+    if (!newest_match)
+        return AUTH_TOKEN_NOT_FOUND;
+
+    uint32_t timeout;
+    key_info.GetTagValue(TAG_AUTH_TIMEOUT, &timeout);
+    time_t now = clock_function_();
+    if (static_cast<int64_t>(newest_match->time_received()) + timeout < static_cast<int64_t>(now))
+        return AUTH_TOKEN_EXPIRED;
+
+    newest_match->UpdateLastUse(now);
+    *found = newest_match->token();
+    return OK;
+}
+
+void AuthTokenTable::ExtractSids(const AuthorizationSet& key_info, std::vector<uint64_t>* sids) {
+    assert(sids);
+    for (auto& param : key_info)
+        if (param.tag == TAG_USER_SECURE_ID)
+            sids->push_back(param.long_integer);
+}
+
+void AuthTokenTable::RemoveEntriesSupersededBy(const Entry& entry) {
+    entries_.erase(remove_if(entries_, [&](Entry& e) { return entry.Supersedes(e); }),
+                   entries_.end());
+}
+
+bool AuthTokenTable::IsSupersededBySomeEntry(const Entry& entry) {
+    return std::any_of(entries_.begin(), entries_.end(),
+                       [&](Entry& e) { return e.Supersedes(entry); });
+}
+
+void AuthTokenTable::MarkCompleted(const keymaster_operation_handle_t op_handle) {
+    auto found = find_if(entries_, [&](Entry& e) { return e.token()->challenge == op_handle; });
+    if (found == entries_.end())
+        return;
+
+    assert(!IsSupersededBySomeEntry(*found));
+    found->mark_completed();
+
+    if (IsSupersededBySomeEntry(*found))
+        entries_.erase(found);
+}
+
+AuthTokenTable::Entry::Entry(const hw_auth_token_t* token, time_t current_time)
+    : token_(token), time_received_(current_time), last_use_(current_time),
+      operation_completed_(token_->challenge == 0) {
+}
+
+uint32_t AuthTokenTable::Entry::timestamp_host_order() const {
+    return ntoh(token_->timestamp);
+}
+
+hw_authenticator_type_t AuthTokenTable::Entry::authenticator_type() const {
+    hw_authenticator_type_t result = static_cast<hw_authenticator_type_t>(
+        ntoh(static_cast<uint32_t>(token_->authenticator_type)));
+    return result;
+}
+
+bool AuthTokenTable::Entry::SatisfiesAuth(const std::vector<uint64_t>& sids,
+                                          hw_authenticator_type_t auth_type) {
+    for (auto sid : sids)
+        if ((sid == token_->authenticator_id) ||
+            (sid == token_->user_id && (auth_type & authenticator_type()) != 0))
+            return true;
+    return false;
+}
+
+void AuthTokenTable::Entry::UpdateLastUse(time_t time) {
+    this->last_use_ = time;
+}
+
+bool AuthTokenTable::Entry::Supersedes(const Entry& entry) const {
+    if (!entry.completed())
+        return false;
+
+    return (token_->user_id == entry.token_->user_id &&
+            token_->authenticator_type == entry.token_->authenticator_type &&
+            token_->authenticator_type == entry.token_->authenticator_type &&
+            timestamp_host_order() > entry.timestamp_host_order());
+}
+
+}  // namespace keymaster
diff --git a/keystore/auth_token_table.h b/keystore/auth_token_table.h
new file mode 100644
index 0000000..d1184e9
--- /dev/null
+++ b/keystore/auth_token_table.h
@@ -0,0 +1,160 @@
+/*
+ * 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 <memory>
+#include <vector>
+
+#include <hardware/hw_auth_token.h>
+#include <keymaster/authorization_set.h>
+
+#ifndef SYSTEM_KEYMASTER_AUTH_TOKEN_TABLE_H
+#define SYSTEM_KEYMASTER_AUTH_TOKEN_TABLE_H
+
+namespace keymaster {
+
+namespace test {
+class AuthTokenTableTest;
+}  // namespace test
+
+time_t clock_gettime_raw();
+
+/**
+ * AuthTokenTable manages a set of received authorization tokens and can provide the appropriate
+ * token for authorizing a key operation.
+ *
+ * To keep the table from growing without bound, superseded entries are removed when possible, and
+ * least recently used entries are automatically pruned when when the table exceeds a size limit,
+ * which is expected to be relatively small, since the implementation uses a linear search.
+ */
+class AuthTokenTable {
+  public:
+    AuthTokenTable(size_t max_entries = 32, time_t (*clock_function)() = clock_gettime_raw)
+        : max_entries_(max_entries), clock_function_(clock_function) {}
+
+    enum Error {
+        OK,
+        AUTH_NOT_REQUIRED = -1,
+        AUTH_TOKEN_EXPIRED = -2,    // Found a matching token, but it's too old.
+        AUTH_TOKEN_WRONG_SID = -3,  // Found a token with the right challenge, but wrong SID.  This
+                                    // most likely indicates that the authenticator was updated
+                                    // (e.g. new fingerprint enrolled).
+        OP_HANDLE_REQUIRED = -4,    // The key requires auth per use but op_handle was zero.
+        AUTH_TOKEN_NOT_FOUND = -5,
+    };
+
+    /**
+     * Add an authorization token to the table.  The table takes ownership of the argument.
+     */
+    void AddAuthenticationToken(const hw_auth_token_t* token);
+
+    /**
+     * Find an authorization token that authorizes the operation specified by \p operation_handle on
+     * a key with the characteristics specified in \p key_info.
+     *
+     * This method is O(n * m), where n is the number of KM_TAG_USER_SECURE_ID entries in key_info
+     * and m is the number of entries in the table.  It could be made better, but n and m should
+     * always be small.
+     *
+     * The table retains ownership of the returned object.
+     */
+    Error FindAuthorization(const AuthorizationSet& key_info,
+                            keymaster_operation_handle_t op_handle, const hw_auth_token_t** found);
+
+    /**
+     * Find an authorization token that authorizes the operation specified by \p operation_handle on
+     * a key with the characteristics specified in \p key_info.
+     *
+     * This method is O(n * m), where n is the number of KM_TAG_USER_SECURE_ID entries in key_info
+     * and m is the number of entries in the table.  It could be made better, but n and m should
+     * always be small.
+     *
+     * The table retains ownership of the returned object.
+     */
+    Error FindAuthorization(const keymaster_key_param_t* params, size_t params_count,
+                            keymaster_operation_handle_t op_handle, const hw_auth_token_t** found) {
+        return FindAuthorization(AuthorizationSet(params, params_count), op_handle, found);
+    }
+
+    /**
+     * Mark operation completed.  This allows tokens associated with the specified operation to be
+     * superseded by new tokens.
+     */
+    void MarkCompleted(const keymaster_operation_handle_t op_handle);
+
+    size_t size() { return entries_.size(); }
+
+  private:
+    friend class AuthTokenTableTest;
+
+    class Entry {
+      public:
+        Entry(const hw_auth_token_t* token, time_t current_time);
+        Entry(Entry&& entry) { *this = std::move(entry); }
+
+        void operator=(Entry&& rhs) {
+            token_ = std::move(rhs.token_);
+            time_received_ = rhs.time_received_;
+            last_use_ = rhs.last_use_;
+            operation_completed_ = rhs.operation_completed_;
+        }
+
+        bool operator<(const Entry& rhs) const { return last_use_ < rhs.last_use_; }
+
+        void UpdateLastUse(time_t time);
+
+        bool Supersedes(const Entry& entry) const;
+        bool SatisfiesAuth(const std::vector<uint64_t>& sids, hw_authenticator_type_t auth_type);
+
+        bool is_newer_than(const Entry* entry) {
+            if (!entry)
+                return true;
+            return timestamp_host_order() > entry->timestamp_host_order();
+        }
+
+        void mark_completed() { operation_completed_ = true; }
+
+        const hw_auth_token_t* token() { return token_.get(); }
+        time_t time_received() const { return time_received_; }
+        bool completed() const { return operation_completed_; }
+        uint32_t timestamp_host_order() const;
+        hw_authenticator_type_t authenticator_type() const;
+
+      private:
+        std::unique_ptr<const hw_auth_token_t> token_;
+        time_t time_received_;
+        time_t last_use_;
+        bool operation_completed_;
+    };
+
+    Error FindAuthPerOpAuthorization(const std::vector<uint64_t>& sids,
+                                     hw_authenticator_type_t auth_type,
+                                     keymaster_operation_handle_t op_handle,
+                                     const hw_auth_token_t** found);
+    Error FindTimedAuthorization(const std::vector<uint64_t>& sids,
+                                 hw_authenticator_type_t auth_type,
+                                 const AuthorizationSet& key_info, const hw_auth_token_t** found);
+    void ExtractSids(const AuthorizationSet& key_info, std::vector<uint64_t>* sids);
+    void RemoveEntriesSupersededBy(const Entry& entry);
+    bool IsSupersededBySomeEntry(const Entry& entry);
+
+    std::vector<Entry> entries_;
+    size_t max_entries_;
+    time_t (*clock_function_)();
+};
+
+}  // namespace keymaster
+
+#endif  // SYSTEM_KEYMASTER_AUTH_TOKEN_TABLE_H
diff --git a/keystore/include/keystore/IKeystoreService.h b/keystore/include/keystore/IKeystoreService.h
index cbdab83..8b5b5d3 100644
--- a/keystore/include/keystore/IKeystoreService.h
+++ b/keystore/include/keystore/IKeystoreService.h
@@ -133,6 +133,8 @@
         UPDATE = IBinder::FIRST_CALL_TRANSACTION + 32,
         FINISH = IBinder::FIRST_CALL_TRANSACTION + 33,
         ABORT = IBinder::FIRST_CALL_TRANSACTION + 34,
+        IS_OPERATION_AUTHORIZED = IBinder::FIRST_CALL_TRANSACTION + 35,
+        ADD_AUTH_TOKEN = IBinder::FIRST_CALL_TRANSACTION + 36,
     };
 
     DECLARE_META_INTERFACE(KeystoreService);
@@ -198,23 +200,27 @@
     virtual int32_t addRngEntropy(const uint8_t* data, size_t dataLength) = 0;
 
     virtual int32_t generateKey(const String16& name, const KeymasterArguments& params,
-                                int uid, int flags, KeyCharacteristics* outCharacteristics) = 0;
+                                const uint8_t* entropy, size_t entropyLength, int uid, int flags,
+                                KeyCharacteristics* outCharacteristics) = 0;
+
     virtual int32_t getKeyCharacteristics(const String16& name,
-                                          const keymaster_blob_t& clientId,
-                                          const keymaster_blob_t& appData,
+                                          const keymaster_blob_t* clientId,
+                                          const keymaster_blob_t* appData,
                                           KeyCharacteristics* outCharacteristics) = 0;
+
     virtual int32_t importKey(const String16& name, const KeymasterArguments&  params,
                               keymaster_key_format_t format, const uint8_t *keyData,
                               size_t keyLength, int uid, int flags,
                               KeyCharacteristics* outCharacteristics) = 0;
 
     virtual void exportKey(const String16& name, keymaster_key_format_t format,
-                           const keymaster_blob_t& clientId,
-                           const keymaster_blob_t& appData, ExportResult* result) = 0;
+                           const keymaster_blob_t* clientId,
+                           const keymaster_blob_t* appData, ExportResult* result) = 0;
 
     virtual void begin(const sp<IBinder>& apptoken, const String16& name,
                        keymaster_purpose_t purpose, bool pruneable,
-                       const KeymasterArguments& params, KeymasterArguments* outParams,
+                       const KeymasterArguments& params, const uint8_t* entropy,
+                       size_t entropyLength, KeymasterArguments* outParams,
                        OperationResult* result) = 0;
 
     virtual void update(const sp<IBinder>& token, const KeymasterArguments& params,
@@ -226,6 +232,10 @@
 
     virtual int32_t abort(const sp<IBinder>& handle) = 0;
 
+    virtual bool isOperationAuthorized(const sp<IBinder>& handle) = 0;
+
+    virtual int32_t addAuthToken(const uint8_t* token, size_t length) = 0;
+
 };
 
 // ----------------------------------------------------------------------------
diff --git a/keystore/keystore.cpp b/keystore/keystore.cpp
index 560b261..5997cd5 100644
--- a/keystore/keystore.cpp
+++ b/keystore/keystore.cpp
@@ -2469,7 +2469,8 @@
     }
 
     int32_t generateKey(const String16& name, const KeymasterArguments& params,
-                        int uid, int flags, KeyCharacteristics* outCharacteristics) {
+                        const uint8_t* entropy, size_t entropyLength, int uid, int flags,
+                        KeyCharacteristics* outCharacteristics) {
         uid_t callingUid = IPCThreadState::self()->getCallingUid();
         pid_t callingPid = IPCThreadState::self()->getCallingPid();
         if (!has_permission(callingUid, P_INSERT, callingPid)) {
@@ -2499,19 +2500,37 @@
         if (device == NULL) {
             return ::SYSTEM_ERROR;
         }
-        // TODO: Seed from Linux RNG either before this or periodically
+        // TODO: Seed from Linux RNG before this.
         if (device->common.module->module_api_version >= KEYMASTER_MODULE_API_VERSION_1_0 &&
                 device->generate_key != NULL) {
-            rc = device->generate_key(device, params.params.data(), params.params.size(), &blob,
-                                      &out);
+            if (!entropy) {
+                rc = KM_ERROR_OK;
+            } else if (device->add_rng_entropy) {
+                rc = device->add_rng_entropy(device, entropy, entropyLength);
+            } else {
+                rc = KM_ERROR_UNIMPLEMENTED;
+            }
+            if (rc == KM_ERROR_OK) {
+                rc = device->generate_key(device, params.params.data(), params.params.size(),
+                                          &blob, &out);
+            }
         }
         // If the HW device didn't support generate_key or generate_key failed
         // fall back to the software implementation.
         if (rc && fallback->generate_key != NULL) {
             isFallback = true;
-            rc = fallback->generate_key(fallback, params.params.data(), params.params.size(),
-                                      &blob,
-                                      &out);
+            if (!entropy) {
+                rc = KM_ERROR_OK;
+            } else if (fallback->add_rng_entropy) {
+                rc = fallback->add_rng_entropy(fallback, entropy, entropyLength);
+            } else {
+                rc = KM_ERROR_UNIMPLEMENTED;
+            }
+            if (rc == KM_ERROR_OK) {
+                rc = fallback->generate_key(fallback, params.params.data(), params.params.size(),
+                                            &blob,
+                                            &out);
+            }
         }
 
         if (out) {
@@ -2540,8 +2559,8 @@
     }
 
     int32_t getKeyCharacteristics(const String16& name,
-                                  const keymaster_blob_t& clientId,
-                                  const keymaster_blob_t& appData,
+                                  const keymaster_blob_t* clientId,
+                                  const keymaster_blob_t* appData,
                                   KeyCharacteristics* outCharacteristics) {
 
         if (!outCharacteristics) {
@@ -2568,7 +2587,7 @@
             ALOGW("device does not implement get_key_characteristics");
             return KM_ERROR_UNIMPLEMENTED;
         }
-        rc = dev->get_key_characteristics(dev, &key, &clientId, &appData, &out);
+        rc = dev->get_key_characteristics(dev, &key, clientId, appData, &out);
         if (out) {
             outCharacteristics->characteristics = *out;
             free(out);
@@ -2645,8 +2664,8 @@
     }
 
     void exportKey(const String16& name, keymaster_key_format_t format,
-                           const keymaster_blob_t& clientId,
-                           const keymaster_blob_t& appData, ExportResult* result) {
+                           const keymaster_blob_t* clientId,
+                           const keymaster_blob_t* appData, ExportResult* result) {
 
         uid_t callingUid = IPCThreadState::self()->getCallingUid();
 
@@ -2669,15 +2688,15 @@
             return;
         }
         uint8_t* ptr = NULL;
-        rc = dev->export_key(dev, format, &key, &clientId, &appData,
+        rc = dev->export_key(dev, format, &key, clientId, appData,
                                              &ptr, &result->dataLength);
         result->exportData.reset(ptr);
         result->resultCode = rc ? rc : ::NO_ERROR;
     }
 
     void begin(const sp<IBinder>& appToken, const String16& name, keymaster_purpose_t purpose,
-               bool pruneable, const KeymasterArguments& params,
-               KeymasterArguments* outParams, OperationResult* result) {
+               bool pruneable, const KeymasterArguments& params, const uint8_t* entropy,
+               size_t entropyLength, KeymasterArguments* outParams, OperationResult* result) {
         if (!result || !outParams) {
             ALOGE("Unexpected null arguments to begin()");
             return;
@@ -2703,10 +2722,22 @@
         size_t outSize;
         keymaster_operation_handle_t handle;
         keymaster1_device_t* dev = mKeyStore->getDeviceForBlob(keyBlob);
+        keymaster_error_t err = KM_ERROR_UNIMPLEMENTED;
+        // Add entropy to the device first.
+        if (entropy) {
+            if (dev->add_rng_entropy) {
+                err = dev->add_rng_entropy(dev, entropy, entropyLength);
+            } else {
+                err = KM_ERROR_UNIMPLEMENTED;
+            }
+            if (err) {
+                result->resultCode = err;
+                return;
+            }
+        }
         // TODO: Check authorization.
-        keymaster_error_t err = dev->begin(dev, purpose, &key, params.params.data(),
-                                           params.params.size(), &out, &outSize,
-                                           &handle);
+        err = dev->begin(dev, purpose, &key, params.params.data(), params.params.size(), &out,
+                         &outSize, &handle);
 
         // If there are too many operations abort the oldest operation that was
         // started as pruneable and try again.
@@ -2794,6 +2825,20 @@
         return ::NO_ERROR;
     }
 
+    bool isOperationAuthorized(const sp<IBinder>& token) {
+        const keymaster1_device_t* dev;
+        keymaster_operation_handle_t handle;
+        if(!mOperationMap.getOperation(token, &handle, &dev)) {
+            return false;
+        }
+        // TODO: Check authorization.
+        return true;
+    }
+
+    int32_t addAuthToken(const uint8_t* /*token*/, size_t /*length*/) {
+        return KM_ERROR_UNIMPLEMENTED;
+    }
+
 private:
     inline bool isKeystoreUnlocked(State state) {
         switch (state) {
diff --git a/keystore/tests/Android.mk b/keystore/tests/Android.mk
new file mode 100644
index 0000000..be8c426
--- /dev/null
+++ b/keystore/tests/Android.mk
@@ -0,0 +1,31 @@
+#
+# 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.
+#
+
+LOCAL_PATH := $(call my-dir)
+
+# Unit test for AuthTokenTable
+include $(CLEAR_VARS)
+ifeq ($(USE_32_BIT_KEYSTORE), true)
+LOCAL_MULTILIB := 32
+endif
+LOCAL_CFLAGS := -Wall -Wextra -Werror
+LOCAL_SRC_FILES := auth_token_table_test.cpp
+LOCAL_MODULE := auth_token_table_test
+LOCAL_C_INCLUDES := $(LOCAL_PATH)/include
+LOCAL_STATIC_LIBRARIES := libgtest_main libkeystore_test
+LOCAL_SHARED_LIBRARIES := libkeymaster_messages
+LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
+include $(BUILD_NATIVE_TEST)
diff --git a/keystore/tests/Makefile b/keystore/tests/Makefile
new file mode 100644
index 0000000..5c1117f
--- /dev/null
+++ b/keystore/tests/Makefile
@@ -0,0 +1,116 @@
+##########
+# This makefile builds local unit tests that run locally on the development machine.  Note
+# that it may be necessary to install some libraries on the dev maching to make the tests
+# build.
+#
+# The same unit tests are also built by Android.mk to run on the target device.  The tests
+# should always build and pass in both places.  The on-device test is what really matters,
+# of course, but debugging is often somewhat easier on the dev platform.
+##########
+
+BASE=../../../..
+SUBS=system/core \
+	system/keymaster\
+	hardware/libhardware \
+	external/gtest
+GTEST=$(BASE)/external/gtest
+KEYMASTER=$(BASE)/system/keymaster
+
+INCLUDES=$(foreach dir,$(SUBS),-I $(BASE)/$(dir)/include) \
+	-I $(BASE)/libnativehelper/include/nativehelper \
+	-I $(GTEST) -Iinclude
+
+# Add USE_CLANG=1 to the make command line to build with clang, which has better error
+# reporting and diagnoses some conditions that GCC doesn't.
+ifdef USE_CLANG
+CC=/usr/bin/clang
+CXX=/usr/bin/clang
+CLANG_TEST_DEFINE=-DKEYMASTER_CLANG_TEST_BUILD
+COMPILER_SPECIFIC_ARGS=-std=c++11 $(CLANG_TEST_DEFINE)
+else
+COMPILER_SPECIFIC_ARGS=-std=c++0x -fprofile-arcs
+endif
+
+CPPFLAGS=$(INCLUDES) -g -O0 -MD
+CXXFLAGS=-Wall -Werror -Wno-unused -Winit-self -Wpointer-arith	-Wunused-parameter \
+        -Werror=sign-compare -Wmissing-declarations -ftest-coverage -fno-permissive \
+	-Wno-deprecated-declarations -fno-exceptions -DKEYMASTER_NAME_TAGS \
+	$(COMPILER_SPECIFIC_ARGS)
+
+# Uncomment to enable debug logging.
+# CXXFLAGS += -DDEBUG
+
+LDLIBS=-lpthread -lstdc++ -lgcov
+
+# This list of sources is used for dependency generation and cleanup.  Add each new source
+# file here (not headers).
+CPPSRCS=\
+	../auth_token_table.cpp \
+	auth_token_table_test.cpp
+
+# This list of binaries determes what gets built and run.  Add each new test binary here.
+BINARIES=\
+	auth_token_table_test
+
+.PHONY: coverage memcheck massif clean run
+
+%.run: %
+	./$<
+	touch $@
+
+run: $(BINARIES:=.run)
+
+auth_token_table_test: auth_token_table_test.o \
+	../auth_token_table.o \
+	$(GTEST)/src/gtest-all.o \
+	$(KEYMASTER)/authorization_set.o \
+	$(KEYMASTER)/logger.o \
+	$(KEYMASTER)/serializable.o
+
+coverage: coverage.info
+	genhtml coverage.info --output-directory coverage
+
+coverage.info: run
+	lcov --capture --directory=. --directory=.. -b . --output-file coverage.info
+
+%.coverage : %
+	$(MAKE) clean && $(MAKE) $<
+	./$<
+	lcov --capture --directory=. --output-file coverage.info
+	genhtml coverage.info --output-directory coverage
+#UNINIT_OPTS=--track-origins=yes
+UNINIT_OPTS=--undef-value-errors=no
+
+MEMCHECK_OPTS=--leak-check=full \
+	--show-reachable=yes \
+	--vgdb=full \
+	$(UNINIT_OPTS) \
+	--error-exitcode=1
+
+MASSIF_OPTS=--tool=massif \
+	--stacks=yes
+
+%.memcheck : %
+	valgrind $(MEMCHECK_OPTS) ./$< && \
+	touch $@
+
+%.massif : %
+	valgrind $(MASSIF_OPTS) --massif-out-file=$@ ./$<
+
+memcheck: $(BINARIES:=.memcheck)
+
+massif: $(BINARIES:=.massif)
+
+OBJS=$(CPPSRCS:.cpp=.o)
+DEPS=$(CPPSRCS:.cpp=.d)
+GCOV=$(CPPSRCS:.cpp=.gcov) $(CPPSRCS:.cpp=.gcda) $(CPPSRCS:.cpp=.gcno)
+
+clean:
+	rm -f $(OBJS) $(DEPS) $(BINARIES) $(GCOV) \
+		$(BINARIES:=.run) $(BINARIES:=.memcheck) $(BINARIES:=.massif) \
+		*gcov *gcno *gcda coverage.info
+	rm -rf coverage
+
+-include $(CPPSRCS:.cpp=.d)
+-include $(CCSRCS:.cc=.d)
+
diff --git a/keystore/tests/auth_token_table_test.cpp b/keystore/tests/auth_token_table_test.cpp
new file mode 100644
index 0000000..0f74e77
--- /dev/null
+++ b/keystore/tests/auth_token_table_test.cpp
@@ -0,0 +1,391 @@
+/*
+ * 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 <keymaster/google_keymaster_utils.h>
+#include <keymaster/logger.h>
+
+#include "../auth_token_table.h"
+
+using std::vector;
+
+int main(int argc, char** argv) {
+    ::testing::InitGoogleTest(&argc, argv);
+    int result = RUN_ALL_TESTS();
+}
+
+inline bool operator==(const hw_auth_token_t& a, const hw_auth_token_t& b) {
+    return (memcmp(&a, &b, sizeof(a)) == 0);
+}
+
+namespace keymaster {
+namespace test {
+
+class StdoutLogger : public Logger {
+  public:
+    StdoutLogger() { set_instance(this); }
+
+    int log_msg(LogLevel level, const char* fmt, va_list args) const {
+        int output_len = 0;
+        switch (level) {
+        case DEBUG_LVL:
+            output_len = printf("DEBUG: ");
+            break;
+        case INFO_LVL:
+            output_len = printf("INFO: ");
+            break;
+        case WARNING_LVL:
+            output_len = printf("WARNING: ");
+            break;
+        case ERROR_LVL:
+            output_len = printf("ERROR: ");
+            break;
+        case SEVERE_LVL:
+            output_len = printf("SEVERE: ");
+            break;
+        }
+
+        output_len += vprintf(fmt, args);
+        output_len += printf("\n");
+        return output_len;
+    }
+};
+
+StdoutLogger logger;
+
+TEST(AuthTokenTableTest, Create) {
+    AuthTokenTable table;
+}
+
+static hw_auth_token_t* make_token(uint64_t rsid, uint64_t ssid = 0, uint64_t challenge = 0,
+                                   uint32_t timestamp = 0) {
+    hw_auth_token_t* token = new hw_auth_token_t;
+    token->user_id = rsid;
+    token->authenticator_id = ssid;
+    token->authenticator_type = hton(static_cast<uint32_t>(HW_AUTH_PASSWORD));
+    token->challenge = challenge;
+    token->timestamp = hton(timestamp);
+    return token;
+}
+
+static AuthorizationSet make_set(uint64_t rsid, uint32_t timeout = 10000) {
+    AuthorizationSetBuilder builder;
+    builder.Authorization(TAG_USER_ID, 10)
+        .Authorization(TAG_USER_AUTH_TYPE, HW_AUTH_PASSWORD)
+        .Authorization(TAG_USER_SECURE_ID, rsid);
+    // Use timeout == 0 to indicate tags that require auth per operation.
+    if (timeout != 0)
+        builder.Authorization(TAG_AUTH_TIMEOUT, timeout);
+    return builder.build();
+}
+
+// Tests obviously run so fast that a real-time clock with a one-second granularity rarely changes
+// output during a test run.  This test clock "ticks" one second every time it's called.
+static time_t monotonic_clock() {
+    static time_t time = 0;
+    return time++;
+}
+
+TEST(AuthTokenTableTest, SimpleAddAndFindTokens) {
+    AuthTokenTable table;
+
+    table.AddAuthenticationToken(make_token(1, 2));
+    table.AddAuthenticationToken(make_token(3, 4));
+    EXPECT_EQ(2U, table.size());
+
+    const hw_auth_token_t* found;
+
+    ASSERT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(1U, found->user_id);
+    EXPECT_EQ(2U, found->authenticator_id);
+
+    ASSERT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(1U, found->user_id);
+    EXPECT_EQ(2U, found->authenticator_id);
+
+    ASSERT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+    EXPECT_EQ(3U, found->user_id);
+    EXPECT_EQ(4U, found->authenticator_id);
+
+    ASSERT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(4), 0, &found));
+    EXPECT_EQ(3U, found->user_id);
+    EXPECT_EQ(4U, found->authenticator_id);
+
+    ASSERT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(5), 0, &found));
+}
+
+TEST(AuthTokenTableTest, TableOverflow) {
+    AuthTokenTable table(3, monotonic_clock);
+
+    table.AddAuthenticationToken(make_token(1));
+    table.AddAuthenticationToken(make_token(2));
+    table.AddAuthenticationToken(make_token(3));
+
+    const hw_auth_token_t* found;
+
+    // All three should be in the table.
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+
+    table.AddAuthenticationToken(make_token(4));
+
+    // Oldest should be gone.
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1), 0, &found));
+
+    // Others should be there, including the new one (4).  Search for it first, then the others, so
+    // 4 becomes the least recently used.
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(4), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+
+    table.AddAuthenticationToken(make_token(5));
+
+    // 5 should have replaced 4.
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(4), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(5), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+
+    table.AddAuthenticationToken(make_token(6));
+    table.AddAuthenticationToken(make_token(7));
+
+    // 2 and 5 should be gone
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(5), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(6), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(7), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(3), 0, &found));
+
+    table.AddAuthenticationToken(make_token(8));
+    table.AddAuthenticationToken(make_token(9));
+    table.AddAuthenticationToken(make_token(10));
+
+    // Only the three most recent should be there.
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(3), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(4), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(5), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(6), 0, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(7), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(8), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(9), 0, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(10), 0, &found));
+}
+
+TEST(AuthTokenTableTest, AuthenticationNotRequired) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    EXPECT_EQ(AuthTokenTable::AUTH_NOT_REQUIRED,
+              table.FindAuthorization(AuthorizationSetBuilder().Authorization(TAG_NO_AUTH_REQUIRED),
+                                      0 /* no challenge */, &found));
+}
+
+TEST(AuthTokenTableTest, OperationHandleNotFound) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    table.AddAuthenticationToken(make_token(1, 0, 1, 5));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */),
+                                      2 /* non-matching challenge */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1, 0 /* no timeout */),
+                                                          1 /* matching challenge */, &found));
+    table.MarkCompleted(1);
+    EXPECT_EQ(
+        AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+        table.FindAuthorization(make_set(1, 0 /* no timeout */), 1 /* used challenge */, &found));
+}
+
+TEST(AuthTokenTableTest, OperationHandleRequired) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    table.AddAuthenticationToken(make_token(1));
+    EXPECT_EQ(
+        AuthTokenTable::OP_HANDLE_REQUIRED,
+        table.FindAuthorization(make_set(1, 0 /* no timeout */), 0 /* no op handle */, &found));
+}
+
+TEST(AuthTokenTableTest, AuthSidChanged) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    table.AddAuthenticationToken(make_token(1, 3, /* op handle */ 1));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_WRONG_SID,
+              table.FindAuthorization(make_set(2, 0 /* no timeout */), 1 /* op handle */, &found));
+}
+
+TEST(AuthTokenTableTest, TokenExpired) {
+    AuthTokenTable table(5, monotonic_clock);
+    const hw_auth_token_t* found;
+
+    auto key_info = make_set(1, 5 /* five second timeout */);
+
+    // monotonic_clock "ticks" one second each time it's called, which is once per request, so the
+    // sixth request should fail, since key_info says the key is good for five seconds.
+    //
+    // Note that this tests the decision of the AuthTokenTable to reject a request it knows is
+    // expired.  An additional check of the secure timestamp (in the token) will be made by
+    // keymaster when the found token is passed to it.
+    table.AddAuthenticationToken(make_token(1, 0));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_EXPIRED,
+              table.FindAuthorization(key_info, 0 /* no op handle */, &found));
+}
+
+TEST(AuthTokenTableTest, MarkNonexistentEntryCompleted) {
+    AuthTokenTable table;
+    // Marking a nonexistent entry completed is ignored.  This test is mainly for code coverage.
+    table.MarkCompleted(1);
+}
+
+TEST(AuthTokenTableTest, SupersededEntries) {
+    AuthTokenTable table;
+    const hw_auth_token_t* found;
+
+    // Add two identical tokens, without challenges.  The second should supersede the first, based
+    // on timestamp (fourth arg to make_token).
+    table.AddAuthenticationToken(make_token(1, 0, 0, 0));
+    table.AddAuthenticationToken(make_token(1, 0, 0, 1));
+    EXPECT_EQ(1U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(1U, ntoh(found->timestamp));
+
+    // Add a third token, this with a different RSID.  It should not be superseded.
+    table.AddAuthenticationToken(make_token(2, 0, 0, 2));
+    EXPECT_EQ(2U, table.size());
+
+    // Add two more, superseding each of the two in the table.
+    table.AddAuthenticationToken(make_token(1, 0, 0, 3));
+    table.AddAuthenticationToken(make_token(2, 0, 0, 4));
+    EXPECT_EQ(2U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0, &found));
+    EXPECT_EQ(3U, ntoh(found->timestamp));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0, &found));
+    EXPECT_EQ(4U, ntoh(found->timestamp));
+
+    // Add another, this one with a challenge value.  It should supersede the old one since it is
+    // newer, and matches other than the challenge.
+    table.AddAuthenticationToken(make_token(1, 0, 1, 5));
+    EXPECT_EQ(2U, table.size());
+
+    // And another, also with a challenge.  Because of the challenge values, the one just added
+    // cannot be superseded.
+    table.AddAuthenticationToken(make_token(1, 0, 2, 6));
+    EXPECT_EQ(3U, table.size());
+
+    // Should be able to find each of them, by specifying their challenge, with a key that is not
+    // timed (timed keys don't care about challenges).
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout*/), 1 /* challenge */, &found));
+    EXPECT_EQ(5U, ntoh(found->timestamp));
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 2 /* challenge */, &found));
+    EXPECT_EQ(6U, ntoh(found->timestamp));
+
+    // Add another, without a challenge, and the same timestamp as the last one.  This new one
+    // actually could be considered already-superseded, but the table doesn't handle that case,
+    // since it seems unlikely to occur in practice.
+    table.AddAuthenticationToken(make_token(1, 0, 0, 6));
+    EXPECT_EQ(4U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(6U, ntoh(found->timestamp));
+
+    // Add another without a challenge but an increased timestamp. This should supersede the
+    // previous challenge-free entry.
+    table.AddAuthenticationToken(make_token(1, 0, 0, 7));
+    EXPECT_EQ(4U, table.size());
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 2 /* challenge */, &found));
+    EXPECT_EQ(6U, ntoh(found->timestamp));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(7U, ntoh(found->timestamp));
+
+    // Mark the entry with challenge 2 as complete.  Since there's a newer challenge-free entry, the
+    // challenge entry will be superseded.
+    table.MarkCompleted(2);
+    EXPECT_EQ(3U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 2 /* challenge */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(7U, ntoh(found->timestamp));
+
+    // Add another SID 1 entry with a challenge.  It supersedes the previous SID 1 entry with
+    // no challenge (timestamp 7), but not the one with challenge 1 (timestamp 5).
+    table.AddAuthenticationToken(make_token(1, 0, 3, 8));
+    EXPECT_EQ(3U, table.size());
+
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 1 /* challenge */, &found));
+    EXPECT_EQ(5U, ntoh(found->timestamp));
+
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 3 /* challenge */, &found));
+    EXPECT_EQ(8U, ntoh(found->timestamp));
+
+    // SID 2 entry is still there.
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(2), 0 /* challenge */, &found));
+    EXPECT_EQ(4U, ntoh(found->timestamp));
+
+    // Mark the entry with challenge 3 as complete.  Since the older challenge 1 entry is
+    // incomplete, nothing is superseded.
+    table.MarkCompleted(3);
+    EXPECT_EQ(3U, table.size());
+
+    EXPECT_EQ(AuthTokenTable::OK,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 1 /* challenge */, &found));
+    EXPECT_EQ(5U, ntoh(found->timestamp));
+
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(8U, ntoh(found->timestamp));
+
+    // Mark the entry with challenge 1 as complete.  Since there's a newer one (with challenge 3,
+    // completed), the challenge 1 entry is superseded and removed.
+    table.MarkCompleted(1);
+    EXPECT_EQ(2U, table.size());
+    EXPECT_EQ(AuthTokenTable::AUTH_TOKEN_NOT_FOUND,
+              table.FindAuthorization(make_set(1, 0 /* no timeout */), 1 /* challenge */, &found));
+    EXPECT_EQ(AuthTokenTable::OK, table.FindAuthorization(make_set(1), 0 /* challenge */, &found));
+    EXPECT_EQ(8U, ntoh(found->timestamp));
+}
+
+}  // namespace keymaster
+}  // namespace test