diff --git a/keystore2/src/fuzzers/Android.bp b/keystore2/src/fuzzers/Android.bp
new file mode 100644
index 0000000..384ab77
--- /dev/null
+++ b/keystore2/src/fuzzers/Android.bp
@@ -0,0 +1,29 @@
+// Copyright 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.
+
+package {
+    default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+rust_fuzz {
+    name: "legacy_blob_fuzzer",
+    srcs: ["legacy_blob_fuzzer.rs"],
+    rustlibs: [
+        "libkeystore2",
+    ],
+    fuzz_config: {
+        fuzz_on_haiku_device: true,
+        fuzz_on_haiku_host: false,
+    },
+}
diff --git a/keystore2/src/fuzzers/legacy_blob_fuzzer.rs b/keystore2/src/fuzzers/legacy_blob_fuzzer.rs
new file mode 100644
index 0000000..5c89ca4
--- /dev/null
+++ b/keystore2/src/fuzzers/legacy_blob_fuzzer.rs
@@ -0,0 +1,24 @@
+// Copyright 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.
+
+#![allow(missing_docs)]
+#![no_main]
+#[macro_use]
+extern crate libfuzzer_sys;
+use keystore2::legacy_blob::LegacyBlobLoader;
+
+fuzz_target!(|data: &[u8]| {
+    let string = data.iter().filter_map(|c| std::char::from_u32(*c as u32)).collect::<String>();
+    let _res = LegacyBlobLoader::decode_alias(&string);
+});
diff --git a/ondevice-signing/Android.bp b/ondevice-signing/Android.bp
index c8ce373..5219240 100644
--- a/ondevice-signing/Android.bp
+++ b/ondevice-signing/Android.bp
@@ -107,7 +107,7 @@
     "libcrypto_utils",
     "libfsverity",
     "liblogwrap",
-    "libprotobuf-cpp-full",
+    "libprotobuf-cpp-lite",
     "libutils",
   ],
 }
diff --git a/ondevice-signing/CertUtils.cpp b/ondevice-signing/CertUtils.cpp
index d2f19ce..8d4f273 100644
--- a/ondevice-signing/CertUtils.cpp
+++ b/ondevice-signing/CertUtils.cpp
@@ -77,7 +77,7 @@
                                reinterpret_cast<const unsigned char*>(value), -1, -1, 0);
 }
 
-Result<bssl::UniquePtr<RSA>> getRsa(const std::vector<uint8_t>& publicKey) {
+static Result<bssl::UniquePtr<RSA>> getRsaFromModulus(const std::vector<uint8_t>& publicKey) {
     bssl::UniquePtr<BIGNUM> n(BN_new());
     bssl::UniquePtr<BIGNUM> e(BN_new());
     bssl::UniquePtr<RSA> rsaPubkey(RSA_new());
@@ -93,9 +93,53 @@
     return rsaPubkey;
 }
 
+static Result<bssl::UniquePtr<RSA>>
+getRsaFromRsaPublicKey(const std::vector<uint8_t>& rsaPublicKey) {
+    auto derBytes = rsaPublicKey.data();
+    bssl::UniquePtr<RSA> rsaKey(d2i_RSAPublicKey(nullptr, &derBytes, rsaPublicKey.size()));
+    if (rsaKey.get() == nullptr) {
+        return Error() << "Failed to parse RsaPublicKey";
+    }
+    if (derBytes != rsaPublicKey.data() + rsaPublicKey.size()) {
+        return Error() << "Key has unexpected trailing data";
+    }
+
+    return rsaKey;
+}
+
+static Result<bssl::UniquePtr<EVP_PKEY>> modulusToRsaPkey(const std::vector<uint8_t>& publicKey) {
+    // "publicKey" corresponds to the raw public key bytes - need to create
+    // a new RSA key with the correct exponent.
+    auto rsaPubkey = getRsaFromModulus(publicKey);
+    if (!rsaPubkey.ok()) {
+        return rsaPubkey.error();
+    }
+
+    bssl::UniquePtr<EVP_PKEY> public_key(EVP_PKEY_new());
+    if (!EVP_PKEY_assign_RSA(public_key.get(), rsaPubkey->release())) {
+        return Error() << "Failed to assign key";
+    }
+    return public_key;
+}
+
+static Result<bssl::UniquePtr<EVP_PKEY>>
+rsaPublicKeyToRsaPkey(const std::vector<uint8_t>& rsaPublicKey) {
+    // rsaPublicKey contains both modulus and exponent, DER-encoded.
+    auto rsaKey = getRsaFromRsaPublicKey(rsaPublicKey);
+    if (!rsaKey.ok()) {
+        return rsaKey.error();
+    }
+
+    bssl::UniquePtr<EVP_PKEY> public_key(EVP_PKEY_new());
+    if (!EVP_PKEY_assign_RSA(public_key.get(), rsaKey->release())) {
+        return Error() << "Failed to assign key";
+    }
+    return public_key;
+}
+
 Result<void> verifySignature(const std::string& message, const std::string& signature,
                              const std::vector<uint8_t>& publicKey) {
-    auto rsaKey = getRsa(publicKey);
+    auto rsaKey = getRsaFromModulus(publicKey);
     if (!rsaKey.ok()) {
         return rsaKey.error();
     }
@@ -112,23 +156,27 @@
     return {};
 }
 
-static Result<bssl::UniquePtr<EVP_PKEY>> toRsaPkey(const std::vector<uint8_t>& publicKey) {
-    // "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();
+Result<void> verifyRsaPublicKeySignature(const std::string& message, const std::string& signature,
+                                         const std::vector<uint8_t>& rsaPublicKey) {
+    auto rsaKey = getRsaFromRsaPublicKey(rsaPublicKey);
+    if (!rsaKey.ok()) {
+        return rsaKey.error();
     }
 
-    bssl::UniquePtr<EVP_PKEY> public_key(EVP_PKEY_new());
-    if (!EVP_PKEY_assign_RSA(public_key.get(), rsaPubkey->release())) {
-        return Error() << "Failed to assign key";
+    uint8_t hashBuf[SHA256_DIGEST_LENGTH];
+    SHA256(reinterpret_cast<const uint8_t*>(message.data()), message.size(), hashBuf);
+
+    bool success = RSA_verify(NID_sha256, hashBuf, sizeof(hashBuf),
+                              reinterpret_cast<const uint8_t*>(signature.data()), signature.size(),
+                              rsaKey->get());
+    if (!success) {
+        return Error() << "Failed to verify signature";
     }
-    return public_key;
+    return {};
 }
 
 static Result<void> createCertificate(
-    const CertSubject& subject, const std::vector<uint8_t>& publicKey,
+    const CertSubject& subject, EVP_PKEY* publicKey,
     const std::function<android::base::Result<std::string>(const std::string&)>& signFunction,
     const std::optional<std::string>& issuerCertPath, const std::string& path) {
 
@@ -153,12 +201,7 @@
         return Error() << "Unable to set x509 signature algorithm";
     }
 
-    auto public_key = toRsaPkey(publicKey);
-    if (!public_key.ok()) {
-        return public_key.error();
-    }
-
-    if (!X509_set_pubkey(x509.get(), public_key.value().get())) {
+    if (!X509_set_pubkey(x509.get(), publicKey)) {
         return Error() << "Unable to set x509 public key";
     }
 
@@ -241,14 +284,24 @@
     const std::vector<uint8_t>& publicKey,
     const std::function<Result<std::string>(const std::string&)>& signFunction,
     const std::string& path) {
-    return createCertificate(kRootSubject, publicKey, signFunction, {}, path);
+    auto rsa_pkey = modulusToRsaPkey(publicKey);
+    if (!rsa_pkey.ok()) {
+        return rsa_pkey.error();
+    }
+
+    return createCertificate(kRootSubject, rsa_pkey.value().get(), signFunction, {}, path);
 }
 
 android::base::Result<void> createLeafCertificate(
-    const CertSubject& subject, const std::vector<uint8_t>& publicKey,
+    const CertSubject& subject, const std::vector<uint8_t>& rsaPublicKey,
     const std::function<android::base::Result<std::string>(const std::string&)>& signFunction,
     const std::string& issuerCertPath, const std::string& path) {
-    return createCertificate(subject, publicKey, signFunction, issuerCertPath, path);
+    auto rsa_pkey = rsaPublicKeyToRsaPkey(rsaPublicKey);
+    if (!rsa_pkey.ok()) {
+        return rsa_pkey.error();
+    }
+
+    return createCertificate(subject, rsa_pkey.value().get(), signFunction, issuerCertPath, path);
 }
 
 Result<std::vector<uint8_t>> extractPublicKey(EVP_PKEY* pkey) {
@@ -332,7 +385,7 @@
 
 Result<CertInfo> verifyAndExtractCertInfoFromX509(const std::string& path,
                                                   const std::vector<uint8_t>& publicKey) {
-    auto public_key = toRsaPkey(publicKey);
+    auto public_key = modulusToRsaPkey(publicKey);
     if (!public_key.ok()) {
         return public_key.error();
     }
@@ -349,7 +402,7 @@
     }
 
     bssl::UniquePtr<EVP_PKEY> pkey(X509_get_pubkey(x509));
-    auto subject_key = extractPublicKey(pkey.get());
+    auto subject_key = extractRsaPublicKey(pkey.get());
     if (!subject_key.ok()) {
         return subject_key.error();
     }
@@ -382,20 +435,20 @@
     BIGNUM* serial = BN_new();
     int sig_nid = NID_rsaEncryption;
 
-    X509_NAME* name = X509_NAME_new();
-    if (!name) {
-        return Error() << "Unable to get x509 subject name";
+    X509_NAME* issuer_name = X509_NAME_new();
+    if (!issuer_name) {
+        return Error() << "Unable to create x509 subject name";
     }
-    X509_NAME_add_entry_by_txt(name, "C", MBSTRING_ASC,
+    X509_NAME_add_entry_by_txt(issuer_name, "C", MBSTRING_ASC,
                                reinterpret_cast<const unsigned char*>(kIssuerCountry), -1, -1, 0);
-    X509_NAME_add_entry_by_txt(name, "O", MBSTRING_ASC,
+    X509_NAME_add_entry_by_txt(issuer_name, "O", MBSTRING_ASC,
                                reinterpret_cast<const unsigned char*>(kIssuerOrg), -1, -1, 0);
-    X509_NAME_add_entry_by_txt(name, "CN", MBSTRING_ASC,
-                               reinterpret_cast<const unsigned char*>(signer.commonName), -1, -1,
-                               0);
+    X509_NAME_add_entry_by_txt(issuer_name, "CN", MBSTRING_ASC,
+                               reinterpret_cast<const unsigned char*>(kRootSubject.commonName), -1,
+                               -1, 0);
 
     BN_set_word(serial, signer.serialNumber);
-    name_der_len = i2d_X509_NAME(name, &name_der);
+    name_der_len = i2d_X509_NAME(issuer_name, &name_der);
     CBB_init(&out, 1024);
 
     if (!CBB_add_asn1(&out, &outer_seq, CBS_ASN1_SEQUENCE) ||
diff --git a/ondevice-signing/CertUtils.h b/ondevice-signing/CertUtils.h
index fd6080d..1ed4c06 100644
--- a/ondevice-signing/CertUtils.h
+++ b/ondevice-signing/CertUtils.h
@@ -25,7 +25,7 @@
 // Information extracted from a certificate.
 struct CertInfo {
     std::string subjectCn;
-    std::vector<uint8_t> subjectKey;
+    std::vector<uint8_t> subjectRsaPublicKey;
 };
 
 // Subjects of certificates we issue.
@@ -69,3 +69,7 @@
 android::base::Result<void> verifySignature(const std::string& message,
                                             const std::string& signature,
                                             const std::vector<uint8_t>& publicKey);
+
+android::base::Result<void> verifyRsaPublicKeySignature(const std::string& message,
+                                                        const std::string& signature,
+                                                        const std::vector<uint8_t>& rsaPublicKey);
diff --git a/ondevice-signing/FakeCompOs.cpp b/ondevice-signing/FakeCompOs.cpp
index 637fe5c..e2273a3 100644
--- a/ondevice-signing/FakeCompOs.cpp
+++ b/ondevice-signing/FakeCompOs.cpp
@@ -16,6 +16,7 @@
 
 #include "FakeCompOs.h"
 
+#include "CertUtils.h"
 #include "KeyConstants.h"
 
 #include <android-base/file.h>
@@ -212,28 +213,6 @@
     return signature.value();
 }
 
-Result<void> FakeCompOs::verifySignature(const ByteVector& message, const ByteVector& signature,
-                                         const ByteVector& rsaPublicKey) const {
-    auto derBytes = rsaPublicKey.data();
-    bssl::UniquePtr<RSA> rsaKey(d2i_RSAPublicKey(nullptr, &derBytes, rsaPublicKey.size()));
-    if (rsaKey.get() == nullptr) {
-        return Error() << "Failed to parse RsaPublicKey";
-    }
-    if (derBytes != rsaPublicKey.data() + rsaPublicKey.size()) {
-        return Error() << "Key has unexpected trailing data";
-    }
-
-    uint8_t hashBuf[SHA256_DIGEST_LENGTH];
-    SHA256(message.data(), message.size(), hashBuf);
-
-    bool success = RSA_verify(NID_sha256, hashBuf, sizeof(hashBuf), signature.data(),
-                              signature.size(), rsaKey.get());
-    if (!success) {
-        return Error() << "Failed to verify signature";
-    }
-    return {};
-}
-
 Result<void> FakeCompOs::loadAndVerifyKey(const ByteVector& keyBlob,
                                           const ByteVector& publicKey) const {
     // To verify the key is valid, we use it to sign some data, and then verify the signature using
@@ -249,5 +228,8 @@
         return signature.error();
     }
 
-    return verifySignature(data, signature.value(), publicKey);
+    std::string signatureString(reinterpret_cast<char*>(signature.value().data()),
+                                signature.value().size());
+    std::string dataString(reinterpret_cast<char*>(data.data()), data.size());
+    return verifySignature(dataString, signatureString, publicKey);
 }
diff --git a/ondevice-signing/FakeCompOs.h b/ondevice-signing/FakeCompOs.h
index 6c12c60..7d76938 100644
--- a/ondevice-signing/FakeCompOs.h
+++ b/ondevice-signing/FakeCompOs.h
@@ -53,9 +53,6 @@
 
     android::base::Result<ByteVector> signData(const ByteVector& keyBlob,
                                                const ByteVector& data) const;
-    android::base::Result<void> verifySignature(const ByteVector& message,
-                                                const ByteVector& signature,
-                                                const ByteVector& rsaPublicKey) const;
 
     KeyDescriptor mDescriptor;
     android::sp<IKeystoreService> mService;
diff --git a/ondevice-signing/VerityUtils.cpp b/ondevice-signing/VerityUtils.cpp
index 543e5a4..e58de68 100644
--- a/ondevice-signing/VerityUtils.cpp
+++ b/ondevice-signing/VerityUtils.cpp
@@ -27,6 +27,7 @@
 
 #include <android-base/logging.h>
 #include <android-base/unique_fd.h>
+#include <asm/byteorder.h>
 #include <libfsverity.h>
 #include <linux/fsverity.h>
 
@@ -46,14 +47,6 @@
 static const char* kFsVerityInitPath = "/system/bin/fsverity_init";
 static const char* kSignatureExtension = ".signature";
 
-#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
-#define cpu_to_le16(v) ((__force __le16)(uint16_t)(v))
-#define le16_to_cpu(v) ((__force uint16_t)(__le16)(v))
-#else
-#define cpu_to_le16(v) ((__force __le16)__builtin_bswap16(v))
-#define le16_to_cpu(v) (__builtin_bswap16((__force uint16_t)(v)))
-#endif
-
 static bool isSignatureFile(const std::filesystem::path& path) {
     return path.extension().native() == kSignatureExtension;
 }
@@ -128,8 +121,8 @@
     auto d = makeUniqueWithTrailingData<fsverity_formatted_digest>(digest.size());
 
     memcpy(d->magic, "FSVerity", 8);
-    d->digest_algorithm = cpu_to_le16(FS_VERITY_HASH_ALG_SHA256);
-    d->digest_size = cpu_to_le16(digest.size());
+    d->digest_algorithm = __cpu_to_le16(FS_VERITY_HASH_ALG_SHA256);
+    d->digest_size = __cpu_to_le16(digest.size());
     memcpy(d->digest, digest.data(), digest.size());
 
     auto signed_digest = key.sign(std::string((char*)d.get(), sizeof(*d) + digest.size()));
@@ -314,9 +307,20 @@
             auto& raw_digest = signature->digest();
             auto& raw_signature = signature->signature();
 
+            // Re-construct the fsverity_formatted_digest that was signed, so we
+            // can verify the signature.
+            std::vector<uint8_t> buffer(sizeof(fsverity_formatted_digest) + raw_digest.size());
+            auto signed_data = new (buffer.data()) fsverity_formatted_digest;
+            memcpy(signed_data->magic, "FSVerity", sizeof signed_data->magic);
+            signed_data->digest_algorithm = __cpu_to_le16(FS_VERITY_HASH_ALG_SHA256);
+            signed_data->digest_size = __cpu_to_le16(raw_digest.size());
+            memcpy(signed_data->digest, raw_digest.data(), raw_digest.size());
+
             // Make sure the signature matches the CompOs public key, and not some other
             // fs-verity trusted key.
-            auto verified = verifySignature(raw_digest, raw_signature, compos_key);
+            std::string to_verify(reinterpret_cast<char*>(buffer.data()), buffer.size());
+
+            auto verified = verifyRsaPublicKeySignature(to_verify, raw_signature, compos_key);
             if (!verified.ok()) {
                 return Error() << verified.error() << ": " << path;
             }
diff --git a/ondevice-signing/odsign_main.cpp b/ondevice-signing/odsign_main.cpp
index b14a91e..d11107f 100644
--- a/ondevice-signing/odsign_main.cpp
+++ b/ondevice-signing/odsign_main.cpp
@@ -162,9 +162,9 @@
     return createSelfSignedCertificate(*publicKey, keySignFunction, outPath);
 }
 
-Result<std::vector<uint8_t>> extractPublicKeyFromLeafCert(const SigningKey& key,
-                                                          const std::string& certPath,
-                                                          const std::string& expectedCn) {
+Result<std::vector<uint8_t>> extractRsaPublicKeyFromLeafCert(const SigningKey& key,
+                                                             const std::string& certPath,
+                                                             const std::string& expectedCn) {
     if (access(certPath.c_str(), F_OK) < 0) {
         return ErrnoError() << "Certificate not found: " << certPath;
     }
@@ -185,7 +185,7 @@
                        << ", should be " << expectedCn;
     }
 
-    return existingCertInfo.value().subjectKey;
+    return existingCertInfo.value().subjectRsaPublicKey;
 }
 
 Result<std::vector<uint8_t>> verifyOrGenerateCompOsKey(const SigningKey& signingKey) {
@@ -403,7 +403,7 @@
 Result<std::vector<uint8_t>> addCompOsCertToFsVerityKeyring(const SigningKey& signingKey) {
     std::vector<uint8_t> compos_key;
     auto existing_key =
-        extractPublicKeyFromLeafCert(signingKey, kCompOsCert, kCompOsSubject.commonName);
+        extractRsaPublicKeyFromLeafCert(signingKey, kCompOsCert, kCompOsSubject.commonName);
     if (existing_key.ok()) {
         LOG(INFO) << "Found and verified existing CompOs public key certificate: " << kCompOsCert;
         compos_key = std::move(existing_key.value());
diff --git a/ondevice-signing/proto/Android.bp b/ondevice-signing/proto/Android.bp
index fc08677..c042b8e 100644
--- a/ondevice-signing/proto/Android.bp
+++ b/ondevice-signing/proto/Android.bp
@@ -23,7 +23,7 @@
     host_supported: true,
     proto: {
         export_proto_headers: true,
-        type: "full",
+        type: "lite",
     },
     srcs: ["odsign_info.proto"],
 }
@@ -33,7 +33,11 @@
     host_supported: true,
     proto: {
         export_proto_headers: true,
-        type: "full",
+        type: "lite",
     },
     srcs: ["compos_signature.proto"],
+    apex_available: [
+        "//apex_available:platform",
+        "com.android.compos",
+    ],
 }
diff --git a/ondevice-signing/proto/compos_signature.proto b/ondevice-signing/proto/compos_signature.proto
index 0659ade..2f7d09f 100644
--- a/ondevice-signing/proto/compos_signature.proto
+++ b/ondevice-signing/proto/compos_signature.proto
@@ -20,10 +20,11 @@
 
 // Data provided by CompOS to allow validation of a file it generated.
 message Signature {
-    // The fs-verity digest (root hash of the Merkle tree) of the file
-    // contents.
+    // The fs-verity digest (which is derived from the root hash of
+    // the Merkle tree) of the file contents.
     bytes digest = 1;
 
-    // Signature of the digest, signed using CompOS's private key.
+    // Signature of a fsverity_formatted_digest structure containing
+    // the digest, signed using CompOS's private key.
     bytes signature = 2;
 }