diff --git a/security/keymint/aidl/vts/functional/KeyMintAidlTestBase.cpp b/security/keymint/aidl/vts/functional/KeyMintAidlTestBase.cpp
index 6555157..eb66aca 100644
--- a/security/keymint/aidl/vts/functional/KeyMintAidlTestBase.cpp
+++ b/security/keymint/aidl/vts/functional/KeyMintAidlTestBase.cpp
@@ -45,7 +45,7 @@
 namespace test {
 
 namespace {
-
+typedef KeyMintAidlTestBase::KeyData KeyData;
 // Predicate for testing basic characteristics validity in generation or import.
 bool KeyCharacteristicsBasicallyValid(SecurityLevel secLevel,
                                       const vector<KeyCharacteristics>& key_characteristics) {
@@ -461,6 +461,34 @@
     }
 }
 
+auto KeyMintAidlTestBase::ProcessMessage(const vector<uint8_t>& key_blob, KeyPurpose operation,
+                                         const string& message, const AuthorizationSet& in_params)
+        -> std::tuple<ErrorCode, string, AuthorizationSet /* out_params */> {
+    AuthorizationSet begin_out_params;
+    ErrorCode result = Begin(operation, key_blob, in_params, &begin_out_params);
+    AuthorizationSet out_params(std::move(begin_out_params));
+    if (result != ErrorCode::OK) {
+        return {result, {}, out_params};
+    }
+
+    string output;
+    int32_t consumed = 0;
+    AuthorizationSet update_params;
+    AuthorizationSet update_out_params;
+    result = Update(update_params, message, &update_out_params, &output, &consumed);
+    out_params.push_back(update_out_params);
+    if (result != ErrorCode::OK) {
+        return {result, output, out_params};
+    }
+
+    string unused;
+    AuthorizationSet finish_params;
+    AuthorizationSet finish_out_params;
+    result = Finish(finish_params, message.substr(consumed), unused, &finish_out_params, &output);
+    out_params.push_back(finish_out_params);
+    return {result, output, out_params};
+}
+
 string KeyMintAidlTestBase::ProcessMessage(const vector<uint8_t>& key_blob, KeyPurpose operation,
                                            const string& message, const AuthorizationSet& in_params,
                                            AuthorizationSet* out_params) {
@@ -859,6 +887,35 @@
     return authList;
 }
 
+ErrorCode KeyMintAidlTestBase::UseAesKey(const vector<uint8_t>& aesKeyBlob) {
+    auto [result, ciphertext, out_params] = ProcessMessage(
+            aesKeyBlob, KeyPurpose::ENCRYPT, "1234567890123456",
+            AuthorizationSetBuilder().BlockMode(BlockMode::ECB).Padding(PaddingMode::NONE));
+    return result;
+}
+
+ErrorCode KeyMintAidlTestBase::UseHmacKey(const vector<uint8_t>& hmacKeyBlob) {
+    auto [result, mac, out_params] = ProcessMessage(
+            hmacKeyBlob, KeyPurpose::SIGN, "1234567890123456",
+            AuthorizationSetBuilder().Authorization(TAG_MAC_LENGTH, 128).Digest(Digest::SHA_2_256));
+    return result;
+}
+
+ErrorCode KeyMintAidlTestBase::UseRsaKey(const vector<uint8_t>& rsaKeyBlob) {
+    std::string message(2048 / 8, 'a');
+    auto [result, signature, out_params] = ProcessMessage(
+            rsaKeyBlob, KeyPurpose::SIGN, message,
+            AuthorizationSetBuilder().Digest(Digest::NONE).Padding(PaddingMode::NONE));
+    return result;
+}
+
+ErrorCode KeyMintAidlTestBase::UseEcdsaKey(const vector<uint8_t>& ecdsaKeyBlob) {
+    auto [result, signature, out_params] =
+            ProcessMessage(ecdsaKeyBlob, KeyPurpose::SIGN, "a",
+                           AuthorizationSetBuilder().Digest(Digest::SHA_2_256));
+    return result;
+}
+
 }  // namespace test
 
 }  // namespace aidl::android::hardware::security::keymint
diff --git a/security/keymint/aidl/vts/functional/KeyMintAidlTestBase.h b/security/keymint/aidl/vts/functional/KeyMintAidlTestBase.h
index 780971d..4e546ed 100644
--- a/security/keymint/aidl/vts/functional/KeyMintAidlTestBase.h
+++ b/security/keymint/aidl/vts/functional/KeyMintAidlTestBase.h
@@ -43,6 +43,11 @@
 
 class KeyMintAidlTestBase : public ::testing::TestWithParam<string> {
   public:
+    struct KeyData {
+        vector<uint8_t> blob;
+        vector<KeyCharacteristics> characteristics;
+    };
+
     void SetUp() override;
     void TearDown() override {
         if (key_blob_.size()) {
@@ -61,7 +66,6 @@
                           vector<KeyCharacteristics>* key_characteristics);
 
     ErrorCode GenerateKey(const AuthorizationSet& key_desc);
-
     ErrorCode ImportKey(const AuthorizationSet& key_desc, KeyFormat format,
                         const string& key_material, vector<uint8_t>* key_blob,
                         vector<KeyCharacteristics>* key_characteristics);
@@ -106,7 +110,9 @@
     string ProcessMessage(const vector<uint8_t>& key_blob, KeyPurpose operation,
                           const string& message, const AuthorizationSet& in_params,
                           AuthorizationSet* out_params);
-
+    std::tuple<ErrorCode, std::string /* processedMessage */, AuthorizationSet /* out_params */>
+    ProcessMessage(const vector<uint8_t>& key_blob, KeyPurpose operation,
+                   const std::string& message, const AuthorizationSet& in_params);
     string SignMessage(const vector<uint8_t>& key_blob, const string& message,
                        const AuthorizationSet& params);
     string SignMessage(const string& message, const AuthorizationSet& params);
@@ -149,6 +155,56 @@
 
     std::pair<ErrorCode, vector<uint8_t>> UpgradeKey(const vector<uint8_t>& key_blob);
 
+    template <typename TagType>
+    std::tuple<KeyData /* aesKey */, KeyData /* hmacKey */, KeyData /* rsaKey */,
+               KeyData /* ecdsaKey */>
+    CreateTestKeys(TagType tagToTest, ErrorCode expectedReturn) {
+        /* AES */
+        KeyData aesKeyData;
+        ErrorCode errorCode = GenerateKey(AuthorizationSetBuilder()
+                                                  .AesEncryptionKey(128)
+                                                  .Authorization(tagToTest)
+                                                  .BlockMode(BlockMode::ECB)
+                                                  .Padding(PaddingMode::NONE)
+                                                  .Authorization(TAG_NO_AUTH_REQUIRED),
+                                          &aesKeyData.blob, &aesKeyData.characteristics);
+        EXPECT_EQ(expectedReturn, errorCode);
+
+        /* HMAC */
+        KeyData hmacKeyData;
+        errorCode = GenerateKey(AuthorizationSetBuilder()
+                                        .HmacKey(128)
+                                        .Authorization(tagToTest)
+                                        .Digest(Digest::SHA_2_256)
+                                        .Authorization(TAG_MIN_MAC_LENGTH, 128)
+                                        .Authorization(TAG_NO_AUTH_REQUIRED),
+                                &hmacKeyData.blob, &hmacKeyData.characteristics);
+        EXPECT_EQ(expectedReturn, errorCode);
+
+        /* RSA */
+        KeyData rsaKeyData;
+        errorCode = GenerateKey(AuthorizationSetBuilder()
+                                        .RsaSigningKey(2048, 65537)
+                                        .Authorization(tagToTest)
+                                        .Digest(Digest::NONE)
+                                        .Padding(PaddingMode::NONE)
+                                        .Authorization(TAG_NO_AUTH_REQUIRED)
+                                        .SetDefaultValidity(),
+                                &rsaKeyData.blob, &rsaKeyData.characteristics);
+        EXPECT_EQ(expectedReturn, errorCode);
+
+        /* ECDSA */
+        KeyData ecdsaKeyData;
+        errorCode = GenerateKey(AuthorizationSetBuilder()
+                                        .EcdsaSigningKey(256)
+                                        .Authorization(tagToTest)
+                                        .Digest(Digest::SHA_2_256)
+                                        .Authorization(TAG_NO_AUTH_REQUIRED)
+                                        .SetDefaultValidity(),
+                                &ecdsaKeyData.blob, &ecdsaKeyData.characteristics);
+        EXPECT_EQ(expectedReturn, errorCode);
+        return {aesKeyData, hmacKeyData, rsaKeyData, ecdsaKeyData};
+    }
     bool IsSecure() const { return securityLevel_ != SecurityLevel::SOFTWARE; }
     SecurityLevel SecLevel() const { return securityLevel_; }
 
@@ -182,6 +238,10 @@
             const vector<KeyCharacteristics>& key_characteristics);
     AuthorizationSet SwEnforcedAuthorizations(
             const vector<KeyCharacteristics>& key_characteristics);
+    ErrorCode UseAesKey(const vector<uint8_t>& aesKeyBlob);
+    ErrorCode UseHmacKey(const vector<uint8_t>& hmacKeyBlob);
+    ErrorCode UseRsaKey(const vector<uint8_t>& rsaKeyBlob);
+    ErrorCode UseEcdsaKey(const vector<uint8_t>& ecdsaKeyBlob);
 
   private:
     std::shared_ptr<IKeyMintDevice> keymint_;
diff --git a/security/keymint/aidl/vts/functional/KeyMintTest.cpp b/security/keymint/aidl/vts/functional/KeyMintTest.cpp
index 88122ce..16c0755 100644
--- a/security/keymint/aidl/vts/functional/KeyMintTest.cpp
+++ b/security/keymint/aidl/vts/functional/KeyMintTest.cpp
@@ -78,7 +78,8 @@
 namespace {
 
 template <TagType tag_type, Tag tag, typename ValueT>
-bool contains(vector<KeyParameter>& set, TypedTag<tag_type, tag> ttag, ValueT expected_value) {
+bool contains(const vector<KeyParameter>& set, TypedTag<tag_type, tag> ttag,
+              ValueT expected_value) {
     auto it = std::find_if(set.begin(), set.end(), [&](const KeyParameter& param) {
         if (auto p = authorizationValue(ttag, param)) {
             return *p == expected_value;
@@ -89,7 +90,7 @@
 }
 
 template <TagType tag_type, Tag tag>
-bool contains(vector<KeyParameter>& set, TypedTag<tag_type, tag>) {
+bool contains(const vector<KeyParameter>& set, TypedTag<tag_type, tag>) {
     auto it = std::find_if(set.begin(), set.end(),
                            [&](const KeyParameter& param) { return param.tag == tag; });
     return (it != set.end());
@@ -4961,6 +4962,99 @@
 
 INSTANTIATE_KEYMINT_AIDL_TEST(KeyAgreementTest);
 
+typedef KeyMintAidlTestBase EarlyBootKeyTest;
+
+TEST_P(EarlyBootKeyTest, CreateEarlyBootKeys) {
+    auto [aesKeyData, hmacKeyData, rsaKeyData, ecdsaKeyData] =
+            CreateTestKeys(TAG_EARLY_BOOT_ONLY, ErrorCode::OK);
+
+    CheckedDeleteKey(&aesKeyData.blob);
+    CheckedDeleteKey(&hmacKeyData.blob);
+    CheckedDeleteKey(&rsaKeyData.blob);
+    CheckedDeleteKey(&ecdsaKeyData.blob);
+}
+
+// This is a more comprenhensive test, but it can only be run on a machine which is still in early
+// boot stage, which no proper Android device is by the time we can run VTS.  To use this,
+// un-disable it and modify vold to remove the call to earlyBootEnded().  Running the test will end
+// early boot, so you'll have to reboot between runs.
+TEST_P(EarlyBootKeyTest, DISABLED_FullTest) {
+    auto [aesKeyData, hmacKeyData, rsaKeyData, ecdsaKeyData] =
+            CreateTestKeys(TAG_EARLY_BOOT_ONLY, ErrorCode::OK);
+    // TAG_EARLY_BOOT_ONLY should be in hw-enforced.
+    EXPECT_TRUE(HwEnforcedAuthorizations(aesKeyData.characteristics).Contains(TAG_EARLY_BOOT_ONLY));
+    EXPECT_TRUE(
+            HwEnforcedAuthorizations(hmacKeyData.characteristics).Contains(TAG_EARLY_BOOT_ONLY));
+    EXPECT_TRUE(HwEnforcedAuthorizations(rsaKeyData.characteristics).Contains(TAG_EARLY_BOOT_ONLY));
+    EXPECT_TRUE(
+            HwEnforcedAuthorizations(ecdsaKeyData.characteristics).Contains(TAG_EARLY_BOOT_ONLY));
+
+    // Should be able to use keys, since early boot has not ended
+    EXPECT_EQ(ErrorCode::OK, UseAesKey(aesKeyData.blob));
+    EXPECT_EQ(ErrorCode::OK, UseHmacKey(hmacKeyData.blob));
+    EXPECT_EQ(ErrorCode::OK, UseRsaKey(rsaKeyData.blob));
+    EXPECT_EQ(ErrorCode::OK, UseEcdsaKey(ecdsaKeyData.blob));
+
+    // End early boot
+    ErrorCode earlyBootResult = GetReturnErrorCode(keyMint().earlyBootEnded());
+    EXPECT_EQ(earlyBootResult, ErrorCode::OK);
+
+    // Should not be able to use already-created keys.
+    EXPECT_EQ(ErrorCode::EARLY_BOOT_ENDED, UseAesKey(aesKeyData.blob));
+    EXPECT_EQ(ErrorCode::EARLY_BOOT_ENDED, UseHmacKey(hmacKeyData.blob));
+    EXPECT_EQ(ErrorCode::EARLY_BOOT_ENDED, UseRsaKey(rsaKeyData.blob));
+    EXPECT_EQ(ErrorCode::EARLY_BOOT_ENDED, UseEcdsaKey(ecdsaKeyData.blob));
+
+    CheckedDeleteKey(&aesKeyData.blob);
+    CheckedDeleteKey(&hmacKeyData.blob);
+    CheckedDeleteKey(&rsaKeyData.blob);
+    CheckedDeleteKey(&ecdsaKeyData.blob);
+
+    // Should not be able to create new keys
+    std::tie(aesKeyData, hmacKeyData, rsaKeyData, ecdsaKeyData) =
+            CreateTestKeys(TAG_EARLY_BOOT_ONLY, ErrorCode::EARLY_BOOT_ENDED);
+
+    CheckedDeleteKey(&aesKeyData.blob);
+    CheckedDeleteKey(&hmacKeyData.blob);
+    CheckedDeleteKey(&rsaKeyData.blob);
+    CheckedDeleteKey(&ecdsaKeyData.blob);
+}
+INSTANTIATE_KEYMINT_AIDL_TEST(EarlyBootKeyTest);
+
+typedef KeyMintAidlTestBase UnlockedDeviceRequiredTest;
+
+// This may be a problematic test.  It can't be run repeatedly without unlocking the device in
+// between runs... and on most test devices there are no enrolled credentials so it can't be
+// unlocked at all, meaning the only way to get the test to pass again on a properly-functioning
+// device is to reboot it.  For that reason, this is disabled by default.  It can be used as part of
+// a manual test process, which includes unlocking between runs, which is why it's included here.
+// Well, that and the fact that it's the only test we can do without also making calls into the
+// Gatekeeper HAL.  We haven't written any cross-HAL tests, and don't know what all of the
+// implications might be, so that may or may not be a solution.
+TEST_P(UnlockedDeviceRequiredTest, DISABLED_KeysBecomeUnusable) {
+    auto [aesKeyData, hmacKeyData, rsaKeyData, ecdsaKeyData] =
+            CreateTestKeys(TAG_UNLOCKED_DEVICE_REQUIRED, ErrorCode::OK);
+
+    EXPECT_EQ(ErrorCode::OK, UseAesKey(aesKeyData.blob));
+    EXPECT_EQ(ErrorCode::OK, UseHmacKey(hmacKeyData.blob));
+    EXPECT_EQ(ErrorCode::OK, UseRsaKey(rsaKeyData.blob));
+    EXPECT_EQ(ErrorCode::OK, UseEcdsaKey(ecdsaKeyData.blob));
+
+    ErrorCode rc = GetReturnErrorCode(
+            keyMint().deviceLocked(false /* passwordOnly */, {} /* verificationToken */));
+    ASSERT_EQ(ErrorCode::OK, rc);
+    EXPECT_EQ(ErrorCode::DEVICE_LOCKED, UseAesKey(aesKeyData.blob));
+    EXPECT_EQ(ErrorCode::DEVICE_LOCKED, UseHmacKey(hmacKeyData.blob));
+    EXPECT_EQ(ErrorCode::DEVICE_LOCKED, UseRsaKey(rsaKeyData.blob));
+    EXPECT_EQ(ErrorCode::DEVICE_LOCKED, UseEcdsaKey(ecdsaKeyData.blob));
+
+    CheckedDeleteKey(&aesKeyData.blob);
+    CheckedDeleteKey(&hmacKeyData.blob);
+    CheckedDeleteKey(&rsaKeyData.blob);
+    CheckedDeleteKey(&ecdsaKeyData.blob);
+}
+INSTANTIATE_KEYMINT_AIDL_TEST(UnlockedDeviceRequiredTest);
+
 }  // namespace aidl::android::hardware::security::keymint::test
 
 int main(int argc, char** argv) {