diff --git a/ondevice-signing/Android.bp b/ondevice-signing/Android.bp
index 2e5e02e..ff9d10b 100644
--- a/ondevice-signing/Android.bp
+++ b/ondevice-signing/Android.bp
@@ -87,6 +87,7 @@
     "Keymaster.cpp",
     "KeymasterSigningKey.cpp",
     "KeystoreKey.cpp",
+    "KeystoreHmacKey.cpp",
     "VerityUtils.cpp",
   ],
 
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/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 453f256..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() {
@@ -141,52 +163,95 @@
         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;
-    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;
-                }
+    auto status = mService->getKeyEntry(mDescriptor, &keyEntryResponse);
+
+    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";
-        }
-
-        // 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) {
-            LOG(WARNING) << "Discarding key with security level: "
-                         << android::hardware::security::keymint::toString(
-                                keyEntryResponse.metadata.keySecurityLevel);
-            keyValid = false;
-        }
+    }
+    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() {
@@ -228,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();
@@ -255,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;
 };