diff --git a/keystore2/selinux/Android.bp b/keystore2/selinux/Android.bp
index 0810855..254f95e 100644
--- a/keystore2/selinux/Android.bp
+++ b/keystore2/selinux/Android.bp
@@ -70,7 +70,7 @@
         "src/concurrency_test.rs",
     ],
     crate_name: "keystore2_selinux_concurrency_test",
-    test_suites: ["deneral-tests"],
+    test_suites: ["general-tests"],
     auto_gen_config: true,
 
     rustlibs: [
diff --git a/keystore2/src/crypto/certificate_utils.cpp b/keystore2/src/crypto/certificate_utils.cpp
index 31c7fb4..d0508c8 100644
--- a/keystore2/src/crypto/certificate_utils.cpp
+++ b/keystore2/src/crypto/certificate_utils.cpp
@@ -19,6 +19,7 @@
 #include <openssl/err.h>
 #include <openssl/evp.h>
 #include <openssl/mem.h>
+#include <openssl/ossl_typ.h>
 #include <openssl/x509v3.h>
 
 #include <functional>
@@ -512,10 +513,7 @@
     return ASN1_STRING_Ptr(algo_str);
 }
 
-CertUtilsError makeAndSetAlgo(X509_ALGOR* algo_field, Algo algo, Padding padding, Digest digest) {
-    if (algo_field == nullptr) {
-        return CertUtilsError::UnexpectedNullPointer;
-    }
+std::variant<CertUtilsError, X509_ALGOR_Ptr> makeAlgo(Algo algo, Padding padding, Digest digest) {
     ASN1_STRING_Ptr param;
     int param_type = V_ASN1_UNDEF;
     int nid = 0;
@@ -584,23 +582,29 @@
         return CertUtilsError::InvalidArgument;
     }
 
-    if (!X509_ALGOR_set0(algo_field, OBJ_nid2obj(nid), param_type, param.get())) {
+    X509_ALGOR_Ptr result(X509_ALGOR_new());
+    if (!result) {
+        return CertUtilsError::MemoryAllocation;
+    }
+    if (!X509_ALGOR_set0(result.get(), OBJ_nid2obj(nid), param_type, param.get())) {
         return CertUtilsError::Encoding;
     }
     // The X509 struct took ownership.
     param.release();
-    return CertUtilsError::Ok;
+    return result;
 }
 
 // This function allows for signing a
 CertUtilsError signCertWith(X509* certificate,
                             std::function<std::vector<uint8_t>(const uint8_t*, size_t)> sign,
                             Algo algo, Padding padding, Digest digest) {
-    if (auto error = makeAndSetAlgo(certificate->sig_alg, algo, padding, digest)) {
-        return error;
+    auto algo_objV = makeAlgo(algo, padding, digest);
+    if (auto error = std::get_if<CertUtilsError>(&algo_objV)) {
+        return *error;
     }
-    if (auto error = makeAndSetAlgo(certificate->cert_info->signature, algo, padding, digest)) {
-        return error;
+    auto& algo_obj = std::get<X509_ALGOR_Ptr>(algo_objV);
+    if (!X509_set1_signature_algo(certificate, algo_obj.get())) {
+        return CertUtilsError::BoringSsl;
     }
 
     uint8_t* cert_buf = nullptr;
@@ -615,13 +619,10 @@
         return CertUtilsError::SignatureFailed;
     }
 
-    if (!ASN1_STRING_set(certificate->signature, signature.data(), signature.size())) {
+    if (!X509_set1_signature_value(certificate, signature.data(), signature.size())) {
         return CertUtilsError::BoringSsl;
     }
 
-    certificate->signature->flags &= ~(0x07);
-    certificate->signature->flags |= ASN1_STRING_FLAG_BITS_LEFT;
-
     return CertUtilsError::Ok;
 }
 
diff --git a/keystore2/src/crypto/include/certificate_utils.h b/keystore2/src/crypto/include/certificate_utils.h
index 6c25b9a..b43a830 100644
--- a/keystore2/src/crypto/include/certificate_utils.h
+++ b/keystore2/src/crypto/include/certificate_utils.h
@@ -39,6 +39,7 @@
 DEFINE_OPENSSL_OBJECT_POINTER(ASN1_TIME);
 DEFINE_OPENSSL_OBJECT_POINTER(EVP_PKEY);
 DEFINE_OPENSSL_OBJECT_POINTER(X509);
+DEFINE_OPENSSL_OBJECT_POINTER(X509_ALGOR);
 DEFINE_OPENSSL_OBJECT_POINTER(X509_EXTENSION);
 DEFINE_OPENSSL_OBJECT_POINTER(X509_NAME);
 DEFINE_OPENSSL_OBJECT_POINTER(EVP_PKEY_CTX);
diff --git a/ondevice-signing/Android.bp b/ondevice-signing/Android.bp
index 2e5e02e..432e585 100644
--- a/ondevice-signing/Android.bp
+++ b/ondevice-signing/Android.bp
@@ -84,22 +84,19 @@
   srcs: [
     "odsign_main.cpp",
     "CertUtils.cpp",
-    "Keymaster.cpp",
-    "KeymasterSigningKey.cpp",
     "KeystoreKey.cpp",
+    "KeystoreHmacKey.cpp",
     "VerityUtils.cpp",
   ],
 
   header_libs: ["odrefresh_headers"],
 
   static_libs: [
-    "libmini_keyctl_static", // TODO need static?
     "libc++fs",
     "lib_odsign_proto",
   ],
 
   shared_libs: [
-    "android.hardware.keymaster@4.1",
     "android.system.keystore2-V1-cpp",
     "android.hardware.security.keymint-V1-cpp",
     "libbase",
@@ -107,11 +104,7 @@
     "libcrypto",
     "libcrypto_utils",
     "libfsverity",
-    "libhidlbase",
     "liblogwrap",
-    "libkeymaster4support", // For authorization_set
-    "libkeymaster4_1support",
-    "libkeyutils",
     "libprotobuf-cpp-full",
     "libutils",
   ],
diff --git a/ondevice-signing/CertUtils.cpp b/ondevice-signing/CertUtils.cpp
index b0b75a6..14dd6d0 100644
--- a/ondevice-signing/CertUtils.cpp
+++ b/ondevice-signing/CertUtils.cpp
@@ -21,6 +21,7 @@
 #include <openssl/crypto.h>
 #include <openssl/pkcs7.h>
 #include <openssl/rsa.h>
+#include <openssl/x509.h>
 #include <openssl/x509v3.h>
 
 #include <fcntl.h>
@@ -56,12 +57,17 @@
 }
 
 Result<bssl::UniquePtr<RSA>> getRsa(const std::vector<uint8_t>& publicKey) {
+    bssl::UniquePtr<BIGNUM> n(BN_new());
+    bssl::UniquePtr<BIGNUM> e(BN_new());
     bssl::UniquePtr<RSA> rsaPubkey(RSA_new());
-    rsaPubkey->n = BN_new();
-    rsaPubkey->e = BN_new();
-
-    BN_bin2bn(publicKey.data(), publicKey.size(), rsaPubkey->n);
-    BN_set_word(rsaPubkey->e, kRsaKeyExponent);
+    if (!n || !e || !rsaPubkey || !BN_bin2bn(publicKey.data(), publicKey.size(), n.get()) ||
+        !BN_set_word(e.get(), kRsaKeyExponent) ||
+        !RSA_set0_key(rsaPubkey.get(), n.get(), e.get(), /*d=*/nullptr)) {
+        return Error() << "Failed to create RSA key";
+    }
+    // RSA_set0_key takes ownership of |n| and |e| on success.
+    (void)n.release();
+    (void)e.release();
 
     return rsaPubkey;
 }
@@ -69,6 +75,9 @@
 Result<void> verifySignature(const std::string& message, const std::string& signature,
                              const std::vector<uint8_t>& publicKey) {
     auto rsaKey = getRsa(publicKey);
+    if (!rsaKey.ok()) {
+        return rsaKey.error();
+    }
     uint8_t hashBuf[SHA256_DIGEST_LENGTH];
     SHA256(const_cast<uint8_t*>(reinterpret_cast<const uint8_t*>(message.c_str())),
            message.length(), hashBuf);
@@ -99,11 +108,14 @@
     // "publicKey" corresponds to the raw public key bytes - need to create
     // a new RSA key with the correct exponent.
     auto rsaPubkey = getRsa(publicKey);
+    if (!rsaPubkey.ok()) {
+        return rsaPubkey.error();
+    }
 
-    EVP_PKEY* public_key = EVP_PKEY_new();
-    EVP_PKEY_assign_RSA(public_key, rsaPubkey->release());
+    bssl::UniquePtr<EVP_PKEY> public_key(EVP_PKEY_new());
+    EVP_PKEY_assign_RSA(public_key.get(), rsaPubkey->release());
 
-    if (!X509_set_pubkey(x509.get(), public_key)) {
+    if (!X509_set_pubkey(x509.get(), public_key.get())) {
         return Error() << "Unable to set x509 public key";
     }
 
@@ -126,27 +138,30 @@
     add_ext(x509.get(), NID_subject_key_identifier, kSubjectKeyIdentifier);
     add_ext(x509.get(), NID_authority_key_identifier, "keyid:always");
 
-    X509_ALGOR_set0(x509->cert_info->signature, OBJ_nid2obj(NID_sha256WithRSAEncryption),
-                    V_ASN1_NULL, NULL);
-    X509_ALGOR_set0(x509->sig_alg, OBJ_nid2obj(NID_sha256WithRSAEncryption), V_ASN1_NULL, NULL);
+    bssl::UniquePtr<X509_ALGOR> algor(X509_ALGOR_new());
+    if (!algor ||
+        !X509_ALGOR_set0(algor.get(), OBJ_nid2obj(NID_sha256WithRSAEncryption), V_ASN1_NULL,
+                         NULL) ||
+        !X509_set1_signature_algo(x509.get(), algor.get())) {
+        return Error() << "Unable to set x509 signature algorithm";
+    }
 
     // Get the data to be signed
-    char* to_be_signed_buf(nullptr);
-    size_t to_be_signed_length = i2d_re_X509_tbs(x509.get(), (unsigned char**)&to_be_signed_buf);
+    unsigned char* to_be_signed_buf(nullptr);
+    size_t to_be_signed_length = i2d_re_X509_tbs(x509.get(), &to_be_signed_buf);
 
-    auto signed_data = signFunction(std::string(to_be_signed_buf, to_be_signed_length));
+    auto signed_data = signFunction(
+        std::string(reinterpret_cast<const char*>(to_be_signed_buf), to_be_signed_length));
     if (!signed_data.ok()) {
         return signed_data.error();
     }
 
-    // This is the only part that doesn't use boringssl default functions - we manually copy in the
-    // signature that was provided to us.
-    x509->signature->data = (unsigned char*)OPENSSL_malloc(signed_data->size());
-    memcpy(x509->signature->data, signed_data->c_str(), signed_data->size());
-    x509->signature->length = signed_data->size();
+    if (!X509_set1_signature_value(x509.get(),
+                                   reinterpret_cast<const uint8_t*>(signed_data->data()),
+                                   signed_data->size())) {
+        return Error() << "Unable to set x509 signature";
+    }
 
-    x509->signature->flags &= ~(ASN1_STRING_FLAG_BITS_LEFT | 0x07);
-    x509->signature->flags |= ASN1_STRING_FLAG_BITS_LEFT;
     auto f = fopen(path.c_str(), "wbe");
     if (f == nullptr) {
         return Error() << "Failed to open " << path;
@@ -154,7 +169,6 @@
     i2d_X509_fp(f, x509.get());
     fclose(f);
 
-    EVP_PKEY_free(public_key);
     return {};
 }
 
@@ -163,15 +177,14 @@
         return Error() << "Failed to extract public key from x509 cert";
     }
 
-    if (EVP_PKEY_type(pkey->type) != EVP_PKEY_RSA) {
+    if (EVP_PKEY_id(pkey) != EVP_PKEY_RSA) {
         return Error() << "The public key is not an RSA key";
     }
 
-    RSA* rsa = EVP_PKEY_get1_RSA(pkey);
-    auto num_bytes = BN_num_bytes(rsa->n);
+    RSA* rsa = EVP_PKEY_get0_RSA(pkey);
+    auto num_bytes = BN_num_bytes(RSA_get0_n(rsa));
     std::vector<uint8_t> pubKey(num_bytes);
-    int res = BN_bn2bin(rsa->n, pubKey.data());
-    RSA_free(rsa);
+    int res = BN_bn2bin(RSA_get0_n(rsa), pubKey.data());
 
     if (!res) {
         return Error() << "Failed to convert public key to bytes";
diff --git a/ondevice-signing/KeyConstants.h b/ondevice-signing/KeyConstants.h
index 9e1a513..ccc9251 100644
--- a/ondevice-signing/KeyConstants.h
+++ b/ondevice-signing/KeyConstants.h
@@ -16,3 +16,6 @@
 
 static constexpr int kRsaKeySize = 2048;
 static constexpr int kRsaKeyExponent = 65537;
+
+static constexpr int kHmacKeySize = 256;
+static constexpr int kHmacMinMacLength = 256;
diff --git a/ondevice-signing/Keymaster.cpp b/ondevice-signing/Keymaster.cpp
deleted file mode 100644
index f9bf9b2..0000000
--- a/ondevice-signing/Keymaster.cpp
+++ /dev/null
@@ -1,293 +0,0 @@
-/*
- * Copyright (C) 2020 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <string>
-
-#include <android-base/logging.h>
-#include <keymasterV4_1/Keymaster.h>
-#include <keymasterV4_1/authorization_set.h>
-
-#include <fcntl.h>
-#include <sys/stat.h>
-#include <sys/types.h>
-
-#include "Keymaster.h"
-
-using AuthorizationSet = ::android::hardware::keymaster::V4_0::AuthorizationSet;
-using AuthorizationSetBuilder = ::android::hardware::keymaster::V4_0::AuthorizationSetBuilder;
-using Digest = ::android::hardware::keymaster::V4_0::Digest;
-using ErrorCode = ::android::hardware::keymaster::V4_0::ErrorCode;
-using HardwareAuthToken = ::android::hardware::keymaster::V4_0::HardwareAuthToken;
-using HidlBuf = ::android::hardware::hidl_vec<uint8_t>;
-using KeyCharacteristics = ::android::hardware::keymaster::V4_0::KeyCharacteristics;
-using KeyFormat = ::android::hardware::keymaster::V4_0::KeyFormat;
-using KeyParameter = ::android::hardware::keymaster::V4_0::KeyParameter;
-using KeyPurpose = ::android::hardware::keymaster::V4_0::KeyPurpose;
-using KmSupport = ::android::hardware::keymaster::V4_1::support::Keymaster;
-using KmDevice = ::android::hardware::keymaster::V4_1::IKeymasterDevice;
-using OperationHandle = ::android::hardware::keymaster::V4_0::OperationHandle;
-using PaddingMode = ::android::hardware::keymaster::V4_0::PaddingMode;
-using VerificationToken = ::android::hardware::keymaster::V4_0::VerificationToken;
-
-using android::sp;
-using android::base::Error;
-using android::base::Result;
-using android::hardware::hidl_vec;
-
-Keymaster::Keymaster() {}
-
-bool Keymaster::initialize() {
-    // TODO(b/165630556): Stop using Keymaster directly and migrate to keystore2
-    // (once available).
-    auto devices = KmSupport::enumerateAvailableDevices();
-    sp<KmDevice> devToUse = nullptr;
-    for (const auto& dev : devices) {
-        auto version = dev->halVersion();
-        if (version.majorVersion > 4 || (version.majorVersion == 4 && version.minorVersion >= 1)) {
-            // TODO we probably have a preference for the SE, hoping Keystore2 will provide this
-            LOG(INFO) << "Using keymaster " << version.keymasterName << " "
-                      << (int)version.majorVersion << "." << (int)version.minorVersion;
-            devToUse = dev;
-            break;
-        }
-    }
-
-    if (devToUse == nullptr) {
-        LOG(WARNING) << "Didn't find a keymaster to use.";
-    }
-    mDevice = devToUse;
-
-    return mDevice != nullptr;
-}
-
-std::optional<Keymaster> Keymaster::getInstance() {
-    static Keymaster keymaster;
-
-    if (!keymaster.initialize()) {
-        return {};
-    } else {
-        return {keymaster};
-    }
-}
-
-Result<std::vector<uint8_t>> Keymaster::createKey() const {
-    ErrorCode error;
-    HidlBuf keyBlob;
-
-    auto params = AuthorizationSetBuilder()
-                      .Authorization(::android::hardware::keymaster::V4_0::TAG_NO_AUTH_REQUIRED)
-                      // TODO MAKE SURE WE ADD THE EARLY_BOOT_ONLY FLAG here
-                      // currently doesn't work on cuttlefish (b/173618442)
-                      //.Authorization(::android::hardware::keymaster::V4_1::TAG_EARLY_BOOT_ONLY)
-                      .RsaSigningKey(2048, 65537)
-                      .Digest(Digest::SHA_2_256)
-                      .Padding(PaddingMode::RSA_PKCS1_1_5_SIGN);
-
-    mDevice->generateKey(params.hidl_data(), [&](ErrorCode hidl_error, const HidlBuf& hidl_key_blob,
-                                                 const KeyCharacteristics&
-                                                 /* hidl_key_characteristics */) {
-        error = hidl_error;
-        keyBlob = hidl_key_blob;
-    });
-
-    if (error != ErrorCode::OK) {
-        return Error() << "Error creating keymaster signing key: "
-                       << static_cast<std::underlying_type<ErrorCode>::type>(error);
-    }
-
-    return keyBlob;
-}
-
-static ErrorCode Begin(const sp<KmDevice>& keymaster_, KeyPurpose purpose, const HidlBuf& key_blob,
-                       const AuthorizationSet& in_params, AuthorizationSet* out_params,
-                       OperationHandle* op_handle) {
-    ErrorCode error;
-    OperationHandle saved_handle = *op_handle;
-    CHECK(keymaster_
-              ->begin(purpose, key_blob, in_params.hidl_data(), HardwareAuthToken(),
-                      [&](ErrorCode hidl_error, const hidl_vec<KeyParameter>& hidl_out_params,
-                          uint64_t hidl_op_handle) {
-                          error = hidl_error;
-                          *out_params = hidl_out_params;
-                          *op_handle = hidl_op_handle;
-                      })
-              .isOk());
-    if (error != ErrorCode::OK) {
-        // Some implementations may modify *op_handle on error.
-        *op_handle = saved_handle;
-    }
-    return error;
-}
-
-static ErrorCode Update(const sp<KmDevice>& keymaster_, OperationHandle op_handle,
-                        const AuthorizationSet& in_params, const std::string& input,
-                        AuthorizationSet* out_params, std::string* output, size_t* input_consumed) {
-    ErrorCode error;
-    HidlBuf inputData(input.size());
-    memcpy(inputData.data(), input.c_str(), input.size());
-    CHECK(keymaster_
-              ->update(op_handle, in_params.hidl_data(), inputData, HardwareAuthToken(),
-                       VerificationToken(),
-                       [&](ErrorCode hidl_error, uint32_t hidl_input_consumed,
-                           const hidl_vec<KeyParameter>& hidl_out_params,
-                           const HidlBuf& hidl_output) {
-                           error = hidl_error;
-                           out_params->push_back(AuthorizationSet(hidl_out_params));
-                           std::string retdata(reinterpret_cast<const char*>(hidl_output.data()),
-                                               hidl_output.size());
-                           output->append(retdata);
-                           *input_consumed = hidl_input_consumed;
-                       })
-              .isOk());
-    return error;
-}
-
-static ErrorCode Finish(const sp<KmDevice>& keymaster_, OperationHandle op_handle,
-                        const AuthorizationSet& in_params, const std::string& input,
-                        const std::string& signature, AuthorizationSet* out_params,
-                        std::string* output) {
-    ErrorCode error;
-    HidlBuf inputData(input.size());
-    memcpy(inputData.data(), input.c_str(), input.size());
-    HidlBuf signatureData(signature.size());
-    memcpy(signatureData.data(), signature.c_str(), signature.size());
-    // TODO still need to handle error -62 - key requires upgrade
-    CHECK(keymaster_
-              ->finish(op_handle, in_params.hidl_data(), inputData, signatureData,
-                       HardwareAuthToken(), VerificationToken(),
-                       [&](ErrorCode hidl_error, const hidl_vec<KeyParameter>& hidl_out_params,
-                           const HidlBuf& hidl_output) {
-                           error = hidl_error;
-                           *out_params = hidl_out_params;
-                           std::string retdata(reinterpret_cast<const char*>(hidl_output.data()),
-                                               hidl_output.size());
-                           output->append(retdata);
-                       })
-              .isOk());
-    return error;
-}
-
-static std::string ProcessMessage(const sp<KmDevice>& keymaster_, const HidlBuf& key_blob,
-                                  KeyPurpose operation, const std::string& message,
-                                  const AuthorizationSet& in_params, AuthorizationSet* out_params) {
-    AuthorizationSet begin_out_params;
-    OperationHandle op_handle_;
-    ErrorCode ec =
-        Begin(keymaster_, operation, key_blob, in_params, &begin_out_params, &op_handle_);
-
-    std::string output;
-    size_t consumed = 0;
-    AuthorizationSet update_params;
-    AuthorizationSet update_out_params;
-    ec = Update(keymaster_, op_handle_, update_params, message, &update_out_params, &output,
-                &consumed);
-
-    std::string unused;
-    AuthorizationSet finish_params;
-    AuthorizationSet finish_out_params;
-    ec = Finish(keymaster_, op_handle_, finish_params, message.substr(consumed), unused,
-                &finish_out_params, &output);
-
-    out_params->push_back(begin_out_params);
-    out_params->push_back(finish_out_params);
-    return output;
-}
-
-Result<std::vector<uint8_t>>
-Keymaster::extractPublicKey(const std::vector<uint8_t>& keyBlob) const {
-    std::vector<uint8_t> publicKey;
-    ErrorCode error;
-
-    mDevice->exportKey(KeyFormat::X509, keyBlob, {} /* clientId */, {} /* appData */,
-                       [&](ErrorCode hidl_error, const HidlBuf& keyData) {
-                           error = hidl_error;
-                           publicKey = keyData;
-                       });
-
-    if (error != ErrorCode::OK) {
-        return Error() << "Error extracting public key: "
-                       << static_cast<std::underlying_type<ErrorCode>::type>(error);
-    }
-
-    return publicKey;
-}
-
-Result<KeymasterVerifyResult> Keymaster::verifyKey(const std::vector<uint8_t>& keyBlob) const {
-    ErrorCode error;
-    KeyCharacteristics characteristics;
-
-    mDevice->getKeyCharacteristics(
-        keyBlob, {} /* clientId */, {} /* appData */,
-        [&](ErrorCode hidl_error, const KeyCharacteristics& hidl_characteristics) {
-            error = hidl_error;
-            characteristics = hidl_characteristics;
-        });
-
-    if (error == ErrorCode::KEY_REQUIRES_UPGRADE) {
-        return KeymasterVerifyResult::UPGRADE;
-    }
-
-    if (error != ErrorCode::OK) {
-        return Error() << "Error getting key characteristics: "
-                       << static_cast<std::underlying_type<ErrorCode>::type>(error);
-    }
-
-    // TODO(b/165630556)
-    // Verify this is an early boot key and the other key parameters
-    return KeymasterVerifyResult::OK;
-}
-
-Result<std::vector<uint8_t>> Keymaster::upgradeKey(const std::vector<uint8_t>& keyBlob) const {
-    ErrorCode error;
-    HidlBuf newKeyBlob;
-
-    // TODO deduplicate
-    auto params = AuthorizationSetBuilder()
-                      .Authorization(::android::hardware::keymaster::V4_0::TAG_NO_AUTH_REQUIRED)
-                      // TODO MAKE SURE WE ADD THE EARLY_BOOT_ONLY FLAG here
-                      // currently doesn't work on cuttlefish (b/173618442)
-                      //.Authorization(::android::hardware::keymaster::V4_1::TAG_EARLY_BOOT_ONLY)
-                      .RsaSigningKey(2048, 65537)
-                      .Digest(Digest::SHA_2_256)
-                      .Padding(PaddingMode::RSA_PKCS1_1_5_SIGN);
-
-    mDevice->upgradeKey(keyBlob, params.hidl_data(),
-                        [&](ErrorCode hidl_error, const HidlBuf& hidl_key_blob) {
-                            error = hidl_error;
-                            newKeyBlob = hidl_key_blob;
-                        });
-
-    if (error != ErrorCode::OK) {
-        return Error() << "Error upgrading keymaster signing key: "
-                       << static_cast<std::underlying_type<ErrorCode>::type>(error);
-    }
-
-    return newKeyBlob;
-}
-
-Result<std::string> Keymaster::sign(const std::vector<uint8_t>& keyBlob,
-                                    const std::string& message) const {
-    AuthorizationSet out_params;
-    auto params = AuthorizationSetBuilder()
-                      .Digest(Digest::SHA_2_256)
-                      .Padding(PaddingMode::RSA_PKCS1_1_5_SIGN);
-    std::string signature =
-        ProcessMessage(mDevice, keyBlob, KeyPurpose::SIGN, message, params, &out_params);
-    if (!out_params.empty()) {
-        return Error() << "Error signing key: expected empty out params.";
-    }
-    return signature;
-}
diff --git a/ondevice-signing/Keymaster.h b/ondevice-signing/Keymaster.h
deleted file mode 100644
index 455289f..0000000
--- a/ondevice-signing/Keymaster.h
+++ /dev/null
@@ -1,60 +0,0 @@
-/*
- * Copyright (C) 2020 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#pragma once
-
-#include <optional>
-
-#include <android-base/macros.h>
-#include <android-base/result.h>
-#include <android-base/unique_fd.h>
-
-#include <keymasterV4_1/Keymaster.h>
-
-#include <utils/StrongPointer.h>
-
-enum class KeymasterVerifyResult {
-    OK = 0,
-    UPGRADE = -1,
-};
-
-class Keymaster {
-    using KmDevice = ::android::hardware::keymaster::V4_1::IKeymasterDevice;
-
-  public:
-    static std::optional<Keymaster> getInstance();
-
-    android::base::Result<std::vector<uint8_t>> createKey() const;
-
-    android::base::Result<std::vector<uint8_t>>
-    extractPublicKey(const std::vector<uint8_t>& keyBlob) const;
-
-    android::base::Result<KeymasterVerifyResult>
-    verifyKey(const std::vector<uint8_t>& keyBlob) const;
-
-    android::base::Result<std::vector<uint8_t>>
-    upgradeKey(const std::vector<uint8_t>& keyBlob) const;
-
-    /* Sign a message with an initialized signing key */
-    android::base::Result<std::string> sign(const std::vector<uint8_t>& keyBlob,
-                                            const std::string& message) const;
-
-  private:
-    Keymaster();
-    bool initialize();
-
-    android::sp<KmDevice> mDevice;
-};
diff --git a/ondevice-signing/KeymasterSigningKey.cpp b/ondevice-signing/KeymasterSigningKey.cpp
deleted file mode 100644
index dc3ef8a..0000000
--- a/ondevice-signing/KeymasterSigningKey.cpp
+++ /dev/null
@@ -1,168 +0,0 @@
-/*
- * Copyright (C) 2020 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <string>
-
-#include <android-base/file.h>
-#include <android-base/logging.h>
-
-#include <fcntl.h>
-#include <sys/stat.h>
-#include <sys/types.h>
-
-#include "CertUtils.h"
-#include "Keymaster.h"
-#include "KeymasterSigningKey.h"
-
-using android::base::ErrnoError;
-using android::base::Error;
-using android::base::ReadFileToString;
-using android::base::Result;
-using android::base::unique_fd;
-
-const std::string kSigningKeyBlob = "/data/misc/odsign/key.blob";
-
-KeymasterSigningKey::KeymasterSigningKey() {}
-
-Result<std::unique_ptr<KeymasterSigningKey>>
-KeymasterSigningKey::loadFromBlobAndVerify(const std::string& path) {
-    auto signingKey = std::make_unique<KeymasterSigningKey>();
-
-    auto status = signingKey->initializeFromKeyblob(path);
-
-    if (!status.ok()) {
-        return status.error();
-    }
-
-    return signingKey;
-}
-
-Result<void> KeymasterSigningKey::saveKeyblob(const std::string& path) const {
-    int flags = O_WRONLY | O_CREAT | O_TRUNC | O_CLOEXEC;
-
-    unique_fd fd(TEMP_FAILURE_RETRY(open(path.c_str(), flags, 0600)));
-    if (fd == -1) {
-        return ErrnoError() << "Error creating key blob file " << path;
-    }
-
-    if (!android::base::WriteFully(fd, mVerifiedKeyBlob.data(), mVerifiedKeyBlob.size())) {
-        return ErrnoError() << "Error writing key blob file " << path;
-    } else {
-        return {};
-    }
-}
-
-Result<void> KeymasterSigningKey::createSigningKey() {
-    KeymasterSigningKey signingKey;
-    auto keymaster = Keymaster::getInstance();
-    if (!keymaster.has_value()) {
-        return Error() << "Failed to initialize keymaster.";
-    }
-    mKeymaster = keymaster;
-
-    auto keyBlob = mKeymaster->createKey();
-
-    if (!keyBlob.ok()) {
-        return keyBlob.error();
-    }
-
-    mVerifiedKeyBlob.assign(keyBlob->begin(), keyBlob->end());
-
-    return {};
-}
-
-Result<std::unique_ptr<KeymasterSigningKey>> KeymasterSigningKey::createAndPersistNewKey() {
-    auto signingKey = std::make_unique<KeymasterSigningKey>();
-
-    auto status = signingKey->createSigningKey();
-
-    if (!status.ok()) {
-        return status.error();
-    }
-
-    status = signingKey->saveKeyblob(kSigningKeyBlob);
-    if (!status.ok()) {
-        return status.error();
-    }
-
-    return signingKey;
-}
-
-Result<SigningKey*> KeymasterSigningKey::getInstance() {
-    auto key = loadFromBlobAndVerify(kSigningKeyBlob);
-
-    if (!key.ok()) {
-        key = createAndPersistNewKey();
-        if (!key.ok()) {
-            return key.error();
-        }
-    }
-
-    return key->release();
-}
-
-Result<std::vector<uint8_t>> KeymasterSigningKey::getPublicKey() const {
-    auto publicKey = mKeymaster->extractPublicKey(mVerifiedKeyBlob);
-    if (!publicKey.ok()) {
-        return publicKey.error();
-    }
-
-    // Keymaster returns the public key not in a full X509 cert, but just the
-    // "SubjectPublicKeyInfo"
-    return extractPublicKeyFromSubjectPublicKeyInfo(publicKey.value());
-}
-
-Result<void> KeymasterSigningKey::initializeFromKeyblob(const std::string& path) {
-    std::string keyBlobData;
-    auto keymaster = Keymaster::getInstance();
-    if (!keymaster.has_value()) {
-        return Error() << "Failed to initialize keymaster.";
-    }
-    mKeymaster = keymaster;
-
-    bool result = ReadFileToString(path, &keyBlobData);
-    if (!result) {
-        return ErrnoError() << "Failed to read " << path;
-    }
-
-    std::vector<uint8_t> keyBlob = {keyBlobData.begin(), keyBlobData.end()};
-
-    auto verifyResult = mKeymaster->verifyKey(keyBlob);
-    if (!verifyResult.ok()) {
-        return Error() << "Failed to verify key: " << verifyResult.error().message();
-    }
-
-    if (*verifyResult == KeymasterVerifyResult::UPGRADE) {
-        auto upgradeResult = mKeymaster->upgradeKey(keyBlob);
-        if (!upgradeResult.ok()) {
-            return Error() << "Failed to upgrade key: " << upgradeResult.error().message();
-        }
-        mVerifiedKeyBlob = *upgradeResult;
-        // Make sure we persist the new blob
-        auto saveResult = saveKeyblob(path);
-        if (!saveResult.ok()) {
-            return Error() << "Failed to store upgraded key";
-        }
-    } else {
-        mVerifiedKeyBlob = keyBlob;
-    }
-
-    return {};
-}
-
-Result<std::string> KeymasterSigningKey::sign(const std::string& message) const {
-    return mKeymaster->sign(mVerifiedKeyBlob, message);
-}
diff --git a/ondevice-signing/KeymasterSigningKey.h b/ondevice-signing/KeymasterSigningKey.h
deleted file mode 100644
index e66781f..0000000
--- a/ondevice-signing/KeymasterSigningKey.h
+++ /dev/null
@@ -1,61 +0,0 @@
-/*
- * Copyright (C) 2020 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#pragma once
-
-#include <android-base/macros.h>
-#include <android-base/result.h>
-#include <android-base/unique_fd.h>
-
-#include <utils/StrongPointer.h>
-
-#include "Keymaster.h"
-#include "SigningKey.h"
-
-class KeymasterSigningKey : public SigningKey {
-    using KmDevice = ::android::hardware::keymaster::V4_1::IKeymasterDevice;
-
-  public:
-    friend std::unique_ptr<KeymasterSigningKey> std::make_unique<KeymasterSigningKey>();
-    virtual ~KeymasterSigningKey(){};
-
-    // Allow the key to be moved around
-    KeymasterSigningKey& operator=(KeymasterSigningKey&& other) = default;
-    KeymasterSigningKey(KeymasterSigningKey&& other) = default;
-
-    static android::base::Result<SigningKey*> getInstance();
-
-    virtual android::base::Result<std::string> sign(const std::string& message) const;
-    virtual android::base::Result<std::vector<uint8_t>> getPublicKey() const;
-
-  private:
-    KeymasterSigningKey();
-
-    static android::base::Result<std::unique_ptr<KeymasterSigningKey>> createAndPersistNewKey();
-    static android::base::Result<std::unique_ptr<KeymasterSigningKey>>
-    loadFromBlobAndVerify(const std::string& path);
-
-    android::base::Result<void> createSigningKey();
-    android::base::Result<void> initializeFromKeyblob(const std::string& path);
-    android::base::Result<void> saveKeyblob(const std::string& path) const;
-
-    static android::base::Result<KeymasterSigningKey> createNewKey();
-
-    std::optional<Keymaster> mKeymaster;
-    std::vector<uint8_t> mVerifiedKeyBlob;
-
-    DISALLOW_COPY_AND_ASSIGN(KeymasterSigningKey);
-};
diff --git a/ondevice-signing/KeystoreHmacKey.cpp b/ondevice-signing/KeystoreHmacKey.cpp
new file mode 100644
index 0000000..db8d7d9
--- /dev/null
+++ b/ondevice-signing/KeystoreHmacKey.cpp
@@ -0,0 +1,267 @@
+/*
+ * Copyright (C) 2021 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 <string>
+
+#include <android-base/file.h>
+#include <android-base/logging.h>
+#include <binder/IServiceManager.h>
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include "CertUtils.h"
+#include "KeyConstants.h"
+#include "KeystoreHmacKey.h"
+
+using android::sp;
+using android::String16;
+
+using android::hardware::security::keymint::Algorithm;
+using android::hardware::security::keymint::Digest;
+using android::hardware::security::keymint::KeyParameter;
+using android::hardware::security::keymint::KeyParameterValue;
+using android::hardware::security::keymint::KeyPurpose;
+using android::hardware::security::keymint::Tag;
+
+using android::system::keystore2::CreateOperationResponse;
+using android::system::keystore2::Domain;
+using android::system::keystore2::KeyDescriptor;
+using android::system::keystore2::KeyEntryResponse;
+using android::system::keystore2::KeyMetadata;
+
+using android::base::Error;
+using android::base::Result;
+
+using android::base::unique_fd;
+
+// Keystore boot level that the odsign key uses
+static const int kOdsignBootLevel = 30;
+
+static KeyDescriptor getHmacKeyDescriptor() {
+    // AIDL parcelable objects don't have constructor
+    static KeyDescriptor descriptor;
+    static std::once_flag flag;
+    std::call_once(flag, [&]() {
+        descriptor.domain = Domain::SELINUX;
+        descriptor.alias = String16("ondevice-signing-hmac");
+        descriptor.nspace = 101;  // odsign_key
+    });
+
+    return descriptor;
+}
+
+Result<void> KeystoreHmacKey::createKey() {
+    std::vector<KeyParameter> params;
+
+    KeyParameter algo;
+    algo.tag = Tag::ALGORITHM;
+    algo.value = KeyParameterValue::make<KeyParameterValue::algorithm>(Algorithm::HMAC);
+    params.push_back(algo);
+
+    KeyParameter key_size;
+    key_size.tag = Tag::KEY_SIZE;
+    key_size.value = KeyParameterValue::make<KeyParameterValue::integer>(kHmacKeySize);
+    params.push_back(key_size);
+
+    KeyParameter min_mac_length;
+    min_mac_length.tag = Tag::MIN_MAC_LENGTH;
+    min_mac_length.value = KeyParameterValue::make<KeyParameterValue::integer>(256);
+    params.push_back(min_mac_length);
+
+    KeyParameter digest;
+    digest.tag = Tag::DIGEST;
+    digest.value = KeyParameterValue::make<KeyParameterValue::digest>(Digest::SHA_2_256);
+    params.push_back(digest);
+
+    KeyParameter purposeSign;
+    purposeSign.tag = Tag::PURPOSE;
+    purposeSign.value = KeyParameterValue::make<KeyParameterValue::keyPurpose>(KeyPurpose::SIGN);
+    params.push_back(purposeSign);
+
+    KeyParameter purposeVerify;
+    purposeVerify.tag = Tag::PURPOSE;
+    purposeVerify.value =
+        KeyParameterValue::make<KeyParameterValue::keyPurpose>(KeyPurpose::VERIFY);
+    params.push_back(purposeVerify);
+
+    KeyParameter auth;
+    auth.tag = Tag::NO_AUTH_REQUIRED;
+    auth.value = KeyParameterValue::make<KeyParameterValue::boolValue>(true);
+    params.push_back(auth);
+
+    KeyParameter boot_level;
+    boot_level.tag = Tag::MAX_BOOT_LEVEL;
+    boot_level.value = KeyParameterValue::make<KeyParameterValue::integer>(kOdsignBootLevel);
+    params.push_back(boot_level);
+
+    KeyMetadata metadata;
+    auto status = mSecurityLevel->generateKey(mDescriptor, {}, params, 0, {}, &metadata);
+    if (!status.isOk()) {
+        return Error() << "Failed to create new HMAC key";
+    }
+
+    return {};
+}
+
+Result<void> KeystoreHmacKey::initialize(sp<IKeystoreService> service,
+                                         sp<IKeystoreSecurityLevel> securityLevel) {
+    mService = std::move(service);
+    mSecurityLevel = std::move(securityLevel);
+
+    // See if we can fetch an existing key
+    KeyEntryResponse keyEntryResponse;
+    LOG(INFO) << "Trying to retrieve existing HMAC key...";
+    auto status = mService->getKeyEntry(mDescriptor, &keyEntryResponse);
+    bool keyValid = false;
+
+    if (status.isOk()) {
+        // Make sure this is an early boot key
+        for (const auto& auth : keyEntryResponse.metadata.authorizations) {
+            if (auth.keyParameter.tag == Tag::MAX_BOOT_LEVEL) {
+                if (auth.keyParameter.value.get<KeyParameterValue::integer>() == kOdsignBootLevel) {
+                    keyValid = true;
+                    break;
+                }
+            }
+        }
+        if (!keyValid) {
+            LOG(WARNING) << "Found invalid HMAC key without MAX_BOOT_LEVEL tag";
+        }
+    }
+
+    if (!keyValid) {
+        LOG(INFO) << "Existing HMAC key not found or invalid, creating new key";
+        return createKey();
+    } else {
+        return {};
+    }
+}
+
+KeystoreHmacKey::KeystoreHmacKey() {
+    mDescriptor = getHmacKeyDescriptor();
+}
+
+static std::vector<KeyParameter> getVerifyOpParameters() {
+    std::vector<KeyParameter> opParameters;
+
+    KeyParameter algo;
+    algo.tag = Tag::ALGORITHM;
+    algo.value = KeyParameterValue::make<KeyParameterValue::algorithm>(Algorithm::HMAC);
+    opParameters.push_back(algo);
+
+    KeyParameter digest;
+    digest.tag = Tag::DIGEST;
+    digest.value = KeyParameterValue::make<KeyParameterValue::digest>(Digest::SHA_2_256);
+    opParameters.push_back(digest);
+
+    KeyParameter mac_length;
+    mac_length.tag = Tag::MAC_LENGTH;
+    mac_length.value = KeyParameterValue::make<KeyParameterValue::integer>(256);
+    opParameters.push_back(mac_length);
+
+    KeyParameter purpose;
+    purpose.tag = Tag::PURPOSE;
+    purpose.value = KeyParameterValue::make<KeyParameterValue::keyPurpose>(KeyPurpose::VERIFY);
+    opParameters.push_back(purpose);
+
+    return opParameters;
+}
+
+static std::vector<KeyParameter> getSignOpParameters() {
+    std::vector<KeyParameter> opParameters;
+
+    KeyParameter algo;
+    algo.tag = Tag::ALGORITHM;
+    algo.value = KeyParameterValue::make<KeyParameterValue::algorithm>(Algorithm::HMAC);
+    opParameters.push_back(algo);
+
+    KeyParameter mac_length;
+    mac_length.tag = Tag::MAC_LENGTH;
+    mac_length.value = KeyParameterValue::make<KeyParameterValue::integer>(256);
+    opParameters.push_back(mac_length);
+
+    KeyParameter digest;
+    digest.tag = Tag::DIGEST;
+    digest.value = KeyParameterValue::make<KeyParameterValue::digest>(Digest::SHA_2_256);
+    opParameters.push_back(digest);
+
+    KeyParameter purpose;
+    purpose.tag = Tag::PURPOSE;
+    purpose.value = KeyParameterValue::make<KeyParameterValue::keyPurpose>(KeyPurpose::SIGN);
+    opParameters.push_back(purpose);
+
+    return opParameters;
+}
+
+Result<std::string> KeystoreHmacKey::sign(const std::string& message) const {
+    CreateOperationResponse opResponse;
+    static auto params = getSignOpParameters();
+
+    auto status = mSecurityLevel->createOperation(mDescriptor, params, false, &opResponse);
+    if (!status.isOk()) {
+        return Error() << "Failed to create keystore signing operation: "
+                       << status.serviceSpecificErrorCode();
+    }
+    auto operation = opResponse.iOperation;
+
+    std::optional<std::vector<uint8_t>> out;
+    status = operation->update({message.begin(), message.end()}, &out);
+    if (!status.isOk()) {
+        return Error() << "Failed to call keystore update operation.";
+    }
+
+    std::optional<std::vector<uint8_t>> signature;
+    status = operation->finish({}, {}, &signature);
+    if (!status.isOk()) {
+        return Error() << "Failed to call keystore finish operation.";
+    }
+
+    if (!signature.has_value()) {
+        return Error() << "Didn't receive a signature from keystore finish operation.";
+    }
+
+    return std::string{signature.value().begin(), signature.value().end()};
+}
+
+Result<void> KeystoreHmacKey::verify(const std::string& message,
+                                     const std::string& signature) const {
+    CreateOperationResponse opResponse;
+    static auto params = getVerifyOpParameters();
+
+    auto status = mSecurityLevel->createOperation(mDescriptor, params, false, &opResponse);
+    if (!status.isOk()) {
+        return Error() << "Failed to create keystore verification operation: "
+                       << status.serviceSpecificErrorCode();
+    }
+    auto operation = opResponse.iOperation;
+
+    std::optional<std::vector<uint8_t>> out;
+    status = operation->update({message.begin(), message.end()}, &out);
+    if (!status.isOk()) {
+        return Error() << "Failed to call keystore update operation.";
+    }
+
+    std::optional<std::vector<uint8_t>> out_signature;
+    std::vector<uint8_t> in_signature{signature.begin(), signature.end()};
+    status = operation->finish({}, in_signature, &out_signature);
+    if (!status.isOk()) {
+        return Error() << "Failed to call keystore finish operation.";
+    }
+
+    return {};
+}
diff --git a/ondevice-signing/KeystoreHmacKey.h b/ondevice-signing/KeystoreHmacKey.h
new file mode 100644
index 0000000..fbad0fd
--- /dev/null
+++ b/ondevice-signing/KeystoreHmacKey.h
@@ -0,0 +1,46 @@
+/*
+ * Copyright (C) 2021 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.
+ */
+
+#pragma once
+
+#include <optional>
+
+#include <android-base/macros.h>
+#include <android-base/result.h>
+
+#include <utils/StrongPointer.h>
+
+#include <android/system/keystore2/IKeystoreService.h>
+
+class KeystoreHmacKey {
+    using IKeystoreService = ::android::system::keystore2::IKeystoreService;
+    using IKeystoreSecurityLevel = ::android::system::keystore2::IKeystoreSecurityLevel;
+    using KeyDescriptor = ::android::system::keystore2::KeyDescriptor;
+
+  public:
+    KeystoreHmacKey();
+    android::base::Result<void> initialize(android::sp<IKeystoreService> service,
+                                           android::sp<IKeystoreSecurityLevel> securityLevel);
+    android::base::Result<std::string> sign(const std::string& message) const;
+    android::base::Result<void> verify(const std::string& message,
+                                       const std::string& signature) const;
+
+  private:
+    android::base::Result<void> createKey();
+    KeyDescriptor mDescriptor;
+    android::sp<IKeystoreService> mService;
+    android::sp<IKeystoreSecurityLevel> mSecurityLevel;
+};
diff --git a/ondevice-signing/KeystoreKey.cpp b/ondevice-signing/KeystoreKey.cpp
index 4e59c58..0951d92 100644
--- a/ondevice-signing/KeystoreKey.cpp
+++ b/ondevice-signing/KeystoreKey.cpp
@@ -46,7 +46,6 @@
 using android::system::keystore2::Domain;
 using android::system::keystore2::KeyDescriptor;
 using android::system::keystore2::KeyEntryResponse;
-using android::system::keystore2::KeyMetadata;
 
 using android::base::Error;
 using android::base::Result;
@@ -54,6 +53,8 @@
 // Keystore boot level that the odsign key uses
 static const int kOdsignBootLevel = 30;
 
+const std::string kPublicKeySignature = "/data/misc/odsign/publickey.signature";
+
 static KeyDescriptor getKeyDescriptor() {
     // AIDL parcelable objects don't have constructor
     static KeyDescriptor descriptor;
@@ -67,9 +68,11 @@
     return descriptor;
 }
 
-KeystoreKey::KeystoreKey() {}
+KeystoreKey::KeystoreKey() {
+    mDescriptor = getKeyDescriptor();
+}
 
-Result<KeyMetadata> KeystoreKey::createNewKey(const KeyDescriptor& descriptor) {
+Result<std::vector<uint8_t>> KeystoreKey::createKey() {
     std::vector<KeyParameter> params;
 
     KeyParameter algo;
@@ -114,12 +117,31 @@
     params.push_back(boot_level);
 
     KeyMetadata metadata;
-    auto status = mSecurityLevel->generateKey(descriptor, {}, params, 0, {}, &metadata);
+    auto status = mSecurityLevel->generateKey(mDescriptor, {}, params, 0, {}, &metadata);
     if (!status.isOk()) {
         return Error() << "Failed to create new key";
     }
 
-    return metadata;
+    // Extract the public key from the certificate, HMAC it and store the signature
+    auto cert = metadata.certificate;
+    if (!cert) {
+        return Error() << "Key did not have a certificate.";
+    }
+    auto publicKey = extractPublicKeyFromX509(cert.value());
+    if (!publicKey.ok()) {
+        return publicKey.error();
+    }
+    std::string publicKeyString = {publicKey->begin(), publicKey->end()};
+    auto signature = mHmacKey.sign(publicKeyString);
+    if (!signature.ok()) {
+        return Error() << "Failed to sign public key.";
+    }
+
+    if (!android::base::WriteStringToFile(*signature, kPublicKeySignature)) {
+        return Error() << "Can't write public key signature.";
+    }
+
+    return *publicKey;
 }
 
 bool KeystoreKey::initialize() {
@@ -136,50 +158,100 @@
         return false;
     }
 
-    auto status = mService->getSecurityLevel(SecurityLevel::STRONGBOX, &mSecurityLevel);
+    auto status = mService->getSecurityLevel(SecurityLevel::TRUSTED_ENVIRONMENT, &mSecurityLevel);
     if (!status.isOk()) {
-        status = mService->getSecurityLevel(SecurityLevel::TRUSTED_ENVIRONMENT, &mSecurityLevel);
-        if (!status.isOk()) {
-            return false;
-        }
+        return false;
     }
 
-    auto descriptor = getKeyDescriptor();
+    // Initialize the HMAC key we use to sign/verify information about this key
+    auto hmacStatus = mHmacKey.initialize(mService, mSecurityLevel);
+    if (!hmacStatus.ok()) {
+        LOG(ERROR) << hmacStatus.error().message();
+        return false;
+    }
+
+    auto key = getOrCreateKey();
+    if (!key.ok()) {
+        LOG(ERROR) << key.error().message();
+        return false;
+    }
+    mPublicKey = *key;
+    LOG(ERROR) << "Initialized Keystore key.";
+    return true;
+}
+
+Result<std::vector<uint8_t>> KeystoreKey::verifyExistingKey() {
     // See if we can fetch an existing key
     KeyEntryResponse keyEntryResponse;
     LOG(INFO) << "Trying to retrieve existing keystore key...";
-    status = mService->getKeyEntry(descriptor, &keyEntryResponse);
-    bool keyValid = false;
+    auto status = mService->getKeyEntry(mDescriptor, &keyEntryResponse);
 
-    if (status.isOk()) {
-        // Make sure this is an early boot key
-        for (const auto& auth : keyEntryResponse.metadata.authorizations) {
-            if (auth.keyParameter.tag == Tag::MAX_BOOT_LEVEL) {
-                if (auth.keyParameter.value.get<KeyParameterValue::integer>() == kOdsignBootLevel) {
-                    keyValid = true;
-                    break;
-                }
+    if (!status.isOk()) {
+        return Error() << "Failed to find keystore key...";
+    }
+
+    // On some earlier builds, we created this key on the Strongbox security level;
+    // we now use TEE keys instead (mostly for speed). It shouldn't matter since
+    // verified boot is protected by the TEE anyway. If the key happens to be on
+    // the wrong security level, delete it (this should happen just once).
+    if (keyEntryResponse.metadata.keySecurityLevel != SecurityLevel::TRUSTED_ENVIRONMENT) {
+        return Error() << "Found invalid keystore key with security level: "
+                       << android::hardware::security::keymint::toString(
+                              keyEntryResponse.metadata.keySecurityLevel);
+    }
+
+    // Make sure this is an early boot key
+    bool foundBootLevel = false;
+    for (const auto& auth : keyEntryResponse.metadata.authorizations) {
+        if (auth.keyParameter.tag == Tag::MAX_BOOT_LEVEL) {
+            if (auth.keyParameter.value.get<KeyParameterValue::integer>() == kOdsignBootLevel) {
+                foundBootLevel = true;
+                break;
             }
         }
-        if (!keyValid) {
-            LOG(WARNING) << "Found invalid keystore key without MAX_BOOT_LEVEL tag";
-        }
+    }
+    if (!foundBootLevel) {
+        return Error() << "Found invalid keystore key without MAX_BOOT_LEVEL tag";
     }
 
-    if (!keyValid) {
+    // If the key is still considered valid at this point, extract the public
+    // key from the certificate. Note that we cannot trust this public key,
+    // because it is a part of the keystore2 database, which can be modified by
+    // an attacker.  So instead, when creating the key we HMAC the public key
+    // with a key of the same boot level, and verify the signature here.
+    auto cert = keyEntryResponse.metadata.certificate;
+    if (!cert) {
+        return Error() << "Key did not have a certificate.";
+    }
+    auto publicKey = extractPublicKeyFromX509(cert.value());
+    if (!publicKey.ok()) {
+        return publicKey.error();
+    }
+    std::string publicKeyString = {publicKey->begin(), publicKey->end()};
+
+    std::string signature;
+    if (!android::base::ReadFileToString(kPublicKeySignature, &signature)) {
+        return Error() << "Can't find signature for public key.";
+    }
+
+    auto signatureValid = mHmacKey.verify(publicKeyString, signature);
+    if (!signatureValid.ok()) {
+        return Error() << "Signature of public key did not match.";
+    }
+    LOG(INFO) << "Verified public key signature.";
+
+    return *publicKey;
+}
+
+Result<std::vector<uint8_t>> KeystoreKey::getOrCreateKey() {
+    auto existingKey = verifyExistingKey();
+    if (!existingKey.ok()) {
+        LOG(INFO) << existingKey.error().message();
         LOG(INFO) << "Existing keystore key not found or invalid, creating new key";
-        auto newKeyStatus = createNewKey(descriptor);
-        if (!newKeyStatus.ok()) {
-            LOG(ERROR) << "Failed to create new key";
-            return false;
-        }
-        mKeyMetadata = *newKeyStatus;
-    } else {
-        mKeyMetadata = keyEntryResponse.metadata;
+        return createKey();
     }
 
-    LOG(ERROR) << "Initialized Keystore key.";
-    return true;
+    return *existingKey;
 }
 
 Result<SigningKey*> KeystoreKey::getInstance() {
@@ -221,11 +293,9 @@
 
 Result<std::string> KeystoreKey::sign(const std::string& message) const {
     static auto opParameters = getSignOpParameters();
-
     CreateOperationResponse opResponse;
 
-    auto status =
-        mSecurityLevel->createOperation(getKeyDescriptor(), opParameters, false, &opResponse);
+    auto status = mSecurityLevel->createOperation(mDescriptor, opParameters, false, &opResponse);
     if (!status.isOk()) {
         return Error() << "Failed to create keystore signing operation: "
                        << status.serviceSpecificErrorCode();
@@ -248,16 +318,9 @@
         return Error() << "Didn't receive a signature from keystore finish operation.";
     }
 
-    std::string result{signature.value().begin(), signature.value().end()};
-
-    return result;
+    return std::string{signature.value().begin(), signature.value().end()};
 }
 
 Result<std::vector<uint8_t>> KeystoreKey::getPublicKey() const {
-    auto cert = mKeyMetadata.certificate;
-    if (cert) {
-        return extractPublicKeyFromX509(cert.value());
-    } else {
-        return Error() << "Key did not have a certificate";
-    }
+    return mPublicKey;
 }
diff --git a/ondevice-signing/KeystoreKey.h b/ondevice-signing/KeystoreKey.h
index 6b9cb57..1257cbb 100644
--- a/ondevice-signing/KeystoreKey.h
+++ b/ondevice-signing/KeystoreKey.h
@@ -26,6 +26,7 @@
 
 #include <android/system/keystore2/IKeystoreService.h>
 
+#include "KeystoreHmacKey.h"
 #include "SigningKey.h"
 
 class KeystoreKey : public SigningKey {
@@ -44,9 +45,13 @@
   private:
     KeystoreKey();
     bool initialize();
-    android::base::Result<KeyMetadata> createNewKey(const KeyDescriptor& descriptor);
+    android::base::Result<std::vector<uint8_t>> verifyExistingKey();
+    android::base::Result<std::vector<uint8_t>> createKey();
+    android::base::Result<std::vector<uint8_t>> getOrCreateKey();
 
+    KeyDescriptor mDescriptor;
+    KeystoreHmacKey mHmacKey;
     android::sp<IKeystoreService> mService;
     android::sp<IKeystoreSecurityLevel> mSecurityLevel;
-    KeyMetadata mKeyMetadata;
+    std::vector<uint8_t> mPublicKey;
 };
diff --git a/ondevice-signing/odsign_main.cpp b/ondevice-signing/odsign_main.cpp
index 6cab8b6..0991704 100644
--- a/ondevice-signing/odsign_main.cpp
+++ b/ondevice-signing/odsign_main.cpp
@@ -32,7 +32,6 @@
 #include <odrefresh/odrefresh.h>
 
 #include "CertUtils.h"
-#include "KeymasterSigningKey.h"
 #include "KeystoreKey.h"
 #include "VerityUtils.h"
 
@@ -57,7 +56,6 @@
 static const char* kFsVerityProcPath = "/proc/sys/fs/verity";
 
 static const bool kForceCompilation = false;
-static const bool kUseKeystore = true;
 
 static const char* kOdsignVerificationDoneProp = "odsign.verification.done";
 static const char* kOdsignKeyDoneProp = "odsign.key.done";
@@ -95,10 +93,8 @@
         return publicKey.error();
     }
 
-    auto keymasterSignFunction = [&](const std::string& to_be_signed) {
-        return key.sign(to_be_signed);
-    };
-    createSelfSignedCertificate(*publicKey, keymasterSignFunction, outPath);
+    auto keySignFunction = [&](const std::string& to_be_signed) { return key.sign(to_be_signed); };
+    createSelfSignedCertificate(*publicKey, keySignFunction, outPath);
     return {};
 }
 
@@ -302,23 +298,12 @@
         return 0;
     }
 
-    SigningKey* key;
-    if (kUseKeystore) {
-        auto keystoreResult = KeystoreKey::getInstance();
-        if (!keystoreResult.ok()) {
-            LOG(ERROR) << "Could not create keystore key: " << keystoreResult.error().message();
-            return -1;
-        }
-        key = keystoreResult.value();
-    } else {
-        // TODO - keymaster will go away
-        auto keymasterResult = KeymasterSigningKey::getInstance();
-        if (!keymasterResult.ok()) {
-            LOG(ERROR) << "Failed to create keymaster key: " << keymasterResult.error().message();
-            return -1;
-        }
-        key = keymasterResult.value();
+    auto keystoreResult = KeystoreKey::getInstance();
+    if (!keystoreResult.ok()) {
+        LOG(ERROR) << "Could not create keystore key: " << keystoreResult.error().message();
+        return -1;
     }
+    SigningKey* key = keystoreResult.value();
 
     bool supportsFsVerity = access(kFsVerityProcPath, F_OK) == 0;
     if (!supportsFsVerity) {