diff --git a/keystore2/src/km_compat/Android.bp b/keystore2/src/km_compat/Android.bp
new file mode 100644
index 0000000..01cf2cc
--- /dev/null
+++ b/keystore2/src/km_compat/Android.bp
@@ -0,0 +1,105 @@
+// Copyright 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.
+
+rust_library {
+    name: "libkeystore2_km_compat",
+    crate_name: "keystore2_km_compat",
+    srcs: ["lib.rs"],
+
+    rustlibs: [
+        "android.hardware.security.keymint-rust",
+        "android.security.compat-rust",
+    ],
+    shared_libs: [
+        "libkm_compat_service",
+    ]
+}
+
+rust_test {
+    name: "keystore2_km_compat_test",
+    crate_name: "keystore2",
+    srcs: ["lib.rs"],
+    test_suites: ["general-tests"],
+    auto_gen_config: true,
+    rustlibs: [
+        "android.hardware.security.keymint-rust",
+        "android.security.compat-rust",
+    ],
+    shared_libs: [
+        "libkm_compat_service",
+    ],
+}
+
+cc_library {
+    name: "libkm_compat",
+    srcs: ["km_compat.cpp"],
+    shared_libs: [
+        "android.hardware.keymaster@3.0",
+        "android.hardware.keymaster@4.0",
+        "android.hardware.keymaster@4.1",
+        "android.hardware.security.keymint-unstable-ndk_platform",
+        "android.security.compat-ndk_platform",
+        "android.system.keystore2-ndk_platform",
+        "libbase",
+        "libbinder_ndk",
+        "libcrypto",
+        "libhidlbase",
+        "libkeymaster4_1support",
+        "libkeystore2_crypto",
+        "libutils",
+    ],
+}
+
+cc_library {
+    name: "libkm_compat_service",
+    srcs: ["km_compat_service.cpp"],
+    shared_libs: [
+        "android.security.compat-ndk_platform",
+        "libbinder_ndk",
+        "libcrypto",
+        "libkm_compat",
+        "libkeymaster4_1support",
+        "libkeystore2_crypto",
+    ],
+}
+
+cc_test {
+    cflags: [
+        "-Wall",
+        "-Werror",
+        "-Wextra",
+    ],
+    srcs: [
+        "certificate_test.cpp",
+        "gtest_main.cpp",
+        "slot_test.cpp",
+    ],
+    shared_libs: [
+        "android.hardware.keymaster@3.0",
+        "android.hardware.keymaster@4.0",
+        "android.hardware.keymaster@4.1",
+        "android.hardware.security.keymint-unstable-ndk_platform",
+        "android.security.compat-ndk_platform",
+        "android.system.keystore2-ndk_platform",
+        "libbase",
+        "libbinder_ndk",
+        "libcrypto",
+        "libhidlbase",
+        "libkeymaster4_1support",
+        "libkeystore2_crypto",
+        "libkm_compat",
+        "libutils",
+    ],
+    name: "keystore2_certificate_test",
+}
diff --git a/keystore2/src/km_compat/certificate_test.cpp b/keystore2/src/km_compat/certificate_test.cpp
new file mode 100644
index 0000000..d8c8c0a
--- /dev/null
+++ b/keystore2/src/km_compat/certificate_test.cpp
@@ -0,0 +1,135 @@
+/*
+ * Copyright 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 <gtest/gtest.h>
+
+#include "km_compat.h"
+
+#include <aidl/android/hardware/security/keymint/Algorithm.h>
+#include <aidl/android/hardware/security/keymint/BlockMode.h>
+#include <aidl/android/hardware/security/keymint/Digest.h>
+#include <aidl/android/hardware/security/keymint/PaddingMode.h>
+
+#include <openssl/evp.h>
+#include <openssl/x509.h>
+
+#define DEFINE_OPENSSL_OBJECT_POINTER(name) using name##_Ptr = bssl::UniquePtr<name>
+
+DEFINE_OPENSSL_OBJECT_POINTER(EVP_PKEY);
+DEFINE_OPENSSL_OBJECT_POINTER(X509);
+
+using ::aidl::android::hardware::security::keymint::Algorithm;
+using ::aidl::android::hardware::security::keymint::BlockMode;
+using ::aidl::android::hardware::security::keymint::Certificate;
+using ::aidl::android::hardware::security::keymint::Digest;
+using ::aidl::android::hardware::security::keymint::PaddingMode;
+using ::aidl::android::hardware::security::keymint::SecurityLevel;
+using ::aidl::android::hardware::security::keymint::Tag;
+
+static std::variant<std::vector<Certificate>, ScopedAStatus>
+getCertificate(const std::vector<KeyParameter>& keyParams) {
+    static std::shared_ptr<KeyMintDevice> device =
+        KeyMintDevice::createKeyMintDevice(SecurityLevel::TRUSTED_ENVIRONMENT);
+    ByteArray blob;
+    KeyCharacteristics characteristics;
+    std::vector<Certificate> certChain;
+    auto status = device->generateKey(keyParams, &blob, &characteristics, &certChain);
+    if (!status.isOk()) {
+        return status;
+    }
+    return certChain;
+}
+
+static void ensureCertChainSize(const std::variant<std::vector<Certificate>, ScopedAStatus>& result,
+                                uint32_t size) {
+    ASSERT_TRUE(std::holds_alternative<std::vector<Certificate>>(result));
+    auto certChain = std::get<std::vector<Certificate>>(result);
+    ASSERT_EQ(certChain.size(), size);
+}
+
+static void verify(const Certificate& certificate) {
+    const uint8_t* p = certificate.encodedCertificate.data();
+    X509_Ptr decoded_cert(d2i_X509(nullptr, &p, (long)certificate.encodedCertificate.size()));
+    EVP_PKEY_Ptr decoded_pkey(X509_get_pubkey(decoded_cert.get()));
+    ASSERT_TRUE(X509_verify(decoded_cert.get(), decoded_pkey.get()));
+}
+
+static std::vector<KeyParameter> getRSAKeyParams(const std::vector<KeyParameter>& extraParams) {
+    auto keyParams = std::vector<KeyParameter>({
+        KeyParameter{.tag = Tag::ALGORITHM, .integer = static_cast<int32_t>(Algorithm::RSA)},
+        KeyParameter{.tag = Tag::KEY_SIZE, .integer = 2048},
+        KeyParameter{.tag = Tag::RSA_PUBLIC_EXPONENT, .longInteger = 65537},
+    });
+    keyParams.insert(keyParams.end(), extraParams.begin(), extraParams.end());
+    return keyParams;
+}
+
+TEST(CertificateTest, TestRSAKeygen) {
+    auto keyParams = getRSAKeyParams({
+        KeyParameter{.tag = Tag::DIGEST, .integer = static_cast<int32_t>(Digest::SHA_2_256)},
+        KeyParameter{.tag = Tag::PADDING, .integer = static_cast<int32_t>(PaddingMode::RSA_PSS)},
+        KeyParameter{.tag = Tag::NO_AUTH_REQUIRED, .boolValue = true},
+        KeyParameter{.tag = Tag::PURPOSE, .integer = static_cast<int32_t>(KeyPurpose::SIGN)},
+        KeyParameter{.tag = Tag::PURPOSE, .integer = static_cast<int32_t>(KeyPurpose::ENCRYPT)},
+    });
+    auto result = getCertificate(keyParams);
+    ensureCertChainSize(result, 1);
+}
+
+TEST(CertificateTest, TestAES) {
+    auto keyParams = {
+        KeyParameter{.tag = Tag::ALGORITHM, .integer = static_cast<int32_t>(Algorithm::AES)},
+        KeyParameter{.tag = Tag::KEY_SIZE, .integer = 128},
+        KeyParameter{.tag = Tag::BLOCK_MODE, .integer = static_cast<int32_t>(BlockMode::CBC)},
+        KeyParameter{.tag = Tag::PADDING, .integer = static_cast<int32_t>(PaddingMode::NONE)},
+        KeyParameter{.tag = Tag::PURPOSE, .integer = static_cast<int32_t>(KeyPurpose::ENCRYPT)},
+    };
+    auto result = getCertificate(keyParams);
+    ensureCertChainSize(result, 0);
+}
+
+TEST(CertificateTest, TestAttestion) {
+    auto keyParams = getRSAKeyParams({
+        KeyParameter{.tag = Tag::PURPOSE, .integer = static_cast<int32_t>(KeyPurpose::SIGN)},
+        KeyParameter{.tag = Tag::ATTESTATION_CHALLENGE, .blob = {42}},
+        KeyParameter{.tag = Tag::ATTESTATION_APPLICATION_ID, .blob = {42}},
+    });
+    auto result = getCertificate(keyParams);
+    ensureCertChainSize(result, 3);
+    verify(std::get<std::vector<Certificate>>(result).back());
+}
+
+TEST(CertificateTest, TestRSAKeygenNoEncryptNoAuthRequired) {
+    auto keyParams = getRSAKeyParams({
+        KeyParameter{.tag = Tag::DIGEST, .integer = static_cast<int32_t>(Digest::SHA_2_256)},
+        KeyParameter{.tag = Tag::PADDING, .integer = static_cast<int32_t>(PaddingMode::RSA_PSS)},
+        KeyParameter{.tag = Tag::NO_AUTH_REQUIRED, .boolValue = true},
+        KeyParameter{.tag = Tag::PURPOSE, .integer = static_cast<int32_t>(KeyPurpose::SIGN)},
+    });
+    auto result = getCertificate(keyParams);
+    ensureCertChainSize(result, 1);
+    verify(std::get<std::vector<Certificate>>(result)[0]);
+}
+
+TEST(CertificateTest, TestRSAKeygenNoEncryptAuthRequired) {
+    auto keyParams = getRSAKeyParams({
+        KeyParameter{.tag = Tag::DIGEST, .integer = static_cast<int32_t>(Digest::SHA_2_256)},
+        KeyParameter{.tag = Tag::PADDING, .integer = static_cast<int32_t>(PaddingMode::RSA_PSS)},
+        KeyParameter{.tag = Tag::PURPOSE, .integer = static_cast<int32_t>(KeyPurpose::SIGN)},
+    });
+    auto result = getCertificate(keyParams);
+    ensureCertChainSize(result, 1);
+}
diff --git a/keystore2/src/km_compat/gtest_main.cpp b/keystore2/src/km_compat/gtest_main.cpp
new file mode 100644
index 0000000..149cbbc
--- /dev/null
+++ b/keystore2/src/km_compat/gtest_main.cpp
@@ -0,0 +1,21 @@
+/*
+ * 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 <gtest/gtest.h>
+int main(int argc, char** argv) {
+    ::testing::InitGoogleTest(&argc, argv);
+    return RUN_ALL_TESTS();
+}
diff --git a/keystore2/src/km_compat/km_compat.cpp b/keystore2/src/km_compat/km_compat.cpp
new file mode 100644
index 0000000..7900576
--- /dev/null
+++ b/keystore2/src/km_compat/km_compat.cpp
@@ -0,0 +1,924 @@
+/*
+ * 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 "km_compat.h"
+
+#include <aidl/android/hardware/security/keymint/Algorithm.h>
+#include <aidl/android/hardware/security/keymint/Digest.h>
+#include <aidl/android/hardware/security/keymint/PaddingMode.h>
+#include <aidl/android/system/keystore2/ResponseCode.h>
+#include <android-base/logging.h>
+#include <android/hidl/manager/1.2/IServiceManager.h>
+#include <binder/IServiceManager.h>
+#include <keymasterV4_1/Keymaster.h>
+#include <keymasterV4_1/Keymaster3.h>
+#include <keymasterV4_1/Keymaster4.h>
+#include <keymasterV4_1/keymaster_tags.h>
+
+using ::aidl::android::hardware::security::keymint::Algorithm;
+using ::aidl::android::hardware::security::keymint::Digest;
+using ::aidl::android::hardware::security::keymint::PaddingMode;
+using ::aidl::android::hardware::security::keymint::Tag;
+using ::aidl::android::hardware::security::keymint::VerificationToken;
+using ::aidl::android::system::keystore2::ResponseCode;
+using ::android::hardware::hidl_vec;
+using ::android::hardware::keymaster::V4_0::TagType;
+using ::android::hidl::manager::V1_2::IServiceManager;
+using V4_0_HardwareAuthToken = ::android::hardware::keymaster::V4_0::HardwareAuthToken;
+using V4_0_KeyCharacteristics = ::android::hardware::keymaster::V4_0::KeyCharacteristics;
+using V4_0_KeyFormat = ::android::hardware::keymaster::V4_0::KeyFormat;
+using V4_0_KeyParameter = ::android::hardware::keymaster::V4_0::KeyParameter;
+using V4_0_VerificationToken = ::android::hardware::keymaster::V4_0::VerificationToken;
+
+// Utility functions
+
+// Converts a V4 error code into a ScopedAStatus
+ScopedAStatus convertErrorCode(V4_0_ErrorCode result) {
+    if (result == V4_0_ErrorCode::OK) {
+        return ScopedAStatus::ok();
+    }
+    return ScopedAStatus::fromServiceSpecificError(static_cast<int32_t>(result));
+}
+
+// TODO: The enum representation will need to be updated when we get unions.
+static V4_0_KeyParameter convertKeyParameterToLegacy(const KeyParameter& kp) {
+    V4_0_KeyParameter lkp;
+    lkp.tag = static_cast<::android::hardware::keymaster::V4_0::Tag>(kp.tag);
+    switch (::android::hardware::keymaster::V4_0::typeFromTag(lkp.tag)) {
+    case TagType::ENUM:
+    case TagType::ENUM_REP:
+    case TagType::UINT:
+    case TagType::UINT_REP:
+        lkp.f.integer = kp.integer;
+        break;
+    case TagType::ULONG:
+    case TagType::ULONG_REP:
+        lkp.f.longInteger = kp.longInteger;
+        break;
+    case TagType::DATE:
+        lkp.f.dateTime = kp.longInteger;
+        break;
+    case TagType::BOOL:
+        lkp.f.boolValue = kp.boolValue;
+        break;
+    case TagType::BIGNUM:
+    case TagType::BYTES:
+        lkp.blob = kp.blob;
+        break;
+    case TagType::INVALID:
+        break;
+    }
+    return lkp;
+}
+
+static std::vector<V4_0_KeyParameter>
+convertKeyParametersToLegacy(const std::vector<KeyParameter>& kps) {
+    std::vector<V4_0_KeyParameter> legacyKps(kps.size());
+    std::transform(kps.begin(), kps.end(), legacyKps.begin(), convertKeyParameterToLegacy);
+    return legacyKps;
+}
+
+// TODO: The enum representation will need to be updated when we get unions.
+static KeyParameter convertKeyParameterFromLegacy(const V4_0_KeyParameter& lkp) {
+    KeyParameter kp;
+    kp.tag = static_cast<Tag>(lkp.tag);
+    switch (::android::hardware::keymaster::V4_0::typeFromTag(lkp.tag)) {
+    case TagType::ENUM:
+    case TagType::ENUM_REP:
+    case TagType::UINT:
+    case TagType::UINT_REP:
+        kp.integer = lkp.f.integer;
+        break;
+    case TagType::ULONG:
+    case TagType::ULONG_REP:
+        kp.longInteger = lkp.f.longInteger;
+        break;
+    case TagType::DATE:
+        kp.longInteger = lkp.f.dateTime;
+        break;
+    case TagType::BOOL:
+        kp.boolValue = lkp.f.boolValue;
+        break;
+    case TagType::BIGNUM:
+    case TagType::BYTES:
+        kp.blob = lkp.blob;
+        break;
+    case TagType::INVALID:
+        break;
+    }
+    return kp;
+}
+
+static std::vector<KeyParameter>
+convertKeyParametersFromLegacy(const std::vector<V4_0_KeyParameter>& legacyKps) {
+    std::vector<KeyParameter> kps(legacyKps.size());
+    std::transform(legacyKps.begin(), legacyKps.end(), kps.begin(), convertKeyParameterFromLegacy);
+    return kps;
+}
+
+static KeyCharacteristics
+convertKeyCharacteristicsFromLegacy(const V4_0_KeyCharacteristics& legacyKc) {
+    KeyCharacteristics kc;
+    kc.softwareEnforced = convertKeyParametersFromLegacy(legacyKc.softwareEnforced);
+    kc.hardwareEnforced = convertKeyParametersFromLegacy(legacyKc.hardwareEnforced);
+    return kc;
+}
+
+static V4_0_KeyFormat convertKeyFormatToLegacy(const KeyFormat& kf) {
+    return static_cast<V4_0_KeyFormat>(kf);
+}
+
+static V4_0_HardwareAuthToken convertAuthTokenToLegacy(const HardwareAuthToken& at) {
+    V4_0_HardwareAuthToken legacyAt;
+    legacyAt.challenge = at.challenge;
+    legacyAt.userId = at.userId;
+    legacyAt.authenticatorId = at.authenticatorId;
+    legacyAt.authenticatorType =
+        static_cast<::android::hardware::keymaster::V4_0::HardwareAuthenticatorType>(
+            at.authenticatorType);
+    legacyAt.timestamp = at.timestamp.milliSeconds;
+    legacyAt.mac = at.mac;
+    return legacyAt;
+}
+
+static V4_0_VerificationToken convertVerificationTokenToLegacy(const VerificationToken& vt) {
+    V4_0_VerificationToken legacyVt;
+    legacyVt.challenge = vt.challenge;
+    legacyVt.timestamp = vt.timestamp.milliSeconds;
+    legacyVt.securityLevel =
+        static_cast<::android::hardware::keymaster::V4_0::SecurityLevel>(vt.securityLevel);
+    legacyVt.mac = vt.mac;
+    return legacyVt;
+}
+
+void OperationSlots::setNumFreeSlots(uint8_t numFreeSlots) {
+    std::lock_guard<std::mutex> lock(mNumFreeSlotsMutex);
+    mNumFreeSlots = numFreeSlots;
+}
+
+bool OperationSlots::claimSlot() {
+    std::lock_guard<std::mutex> lock(mNumFreeSlotsMutex);
+    if (mNumFreeSlots > 0) {
+        mNumFreeSlots--;
+        return true;
+    }
+    return false;
+}
+
+void OperationSlots::freeSlot() {
+    std::lock_guard<std::mutex> lock(mNumFreeSlotsMutex);
+    mNumFreeSlots++;
+}
+
+void OperationSlot::freeSlot() {
+    if (mIsActive) {
+        mOperationSlots->freeSlot();
+        mIsActive = false;
+    }
+}
+
+// KeyMintDevice implementation
+
+ScopedAStatus KeyMintDevice::getHardwareInfo(KeyMintHardwareInfo* _aidl_return) {
+    // TODO: What do I do about the version number?  Is it the version of the device I get?
+    auto result = mDevice->getHardwareInfo([&](auto securityLevel, const auto& keymasterName,
+                                               const auto& keymasterAuthorName) {
+        _aidl_return->securityLevel =
+            static_cast<::aidl::android::hardware::security::keymint::SecurityLevel>(securityLevel);
+        _aidl_return->keyMintName = keymasterName;
+        _aidl_return->keyMintAuthorName = keymasterAuthorName;
+    });
+    if (!result.isOk()) {
+        return ScopedAStatus::fromServiceSpecificError(
+            static_cast<int32_t>(ResponseCode::SYSTEM_ERROR));
+    }
+    return ScopedAStatus::ok();
+}
+
+// We're not implementing this.
+ScopedAStatus KeyMintDevice::verifyAuthorization(int64_t in_challenge ATTRIBUTE_UNUSED,
+                                                 const HardwareAuthToken& in_token ATTRIBUTE_UNUSED,
+                                                 VerificationToken* _aidl_return ATTRIBUTE_UNUSED) {
+    return ScopedAStatus::fromServiceSpecificError(
+        static_cast<int32_t>(V4_0_ErrorCode::UNIMPLEMENTED));
+}
+
+ScopedAStatus KeyMintDevice::addRngEntropy(const std::vector<uint8_t>& in_data) {
+    V4_0_ErrorCode errorCode = mDevice->addRngEntropy(in_data);
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus KeyMintDevice::generateKey(const std::vector<KeyParameter>& in_keyParams,
+                                         ByteArray* out_generatedKeyBlob,
+                                         KeyCharacteristics* out_generatedKeyCharacteristics,
+                                         std::vector<Certificate>* out_outCertChain) {
+    auto legacyKeyParams = convertKeyParametersToLegacy(in_keyParams);
+    V4_0_ErrorCode errorCode;
+    auto result = mDevice->generateKey(
+        legacyKeyParams, [&](V4_0_ErrorCode error, const hidl_vec<uint8_t>& keyBlob,
+                             const V4_0_KeyCharacteristics& keyCharacteristics) {
+            errorCode = error;
+            out_generatedKeyBlob->data = keyBlob;
+            *out_generatedKeyCharacteristics =
+                convertKeyCharacteristicsFromLegacy(keyCharacteristics);
+        });
+    if (!result.isOk()) {
+        return ScopedAStatus::fromServiceSpecificError(
+            static_cast<int32_t>(ResponseCode::SYSTEM_ERROR));
+    }
+    if (errorCode == V4_0_ErrorCode::OK) {
+        auto cert = getCertificate(in_keyParams, out_generatedKeyBlob->data);
+        if (std::holds_alternative<V4_0_ErrorCode>(cert)) {
+            auto code = std::get<V4_0_ErrorCode>(cert);
+            // We return OK in successful cases that do not generate a certificate.
+            if (code != V4_0_ErrorCode::OK) {
+                errorCode = code;
+                deleteKey(out_generatedKeyBlob->data);
+            }
+        } else {
+            *out_outCertChain = std::get<std::vector<Certificate>>(cert);
+        }
+    }
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus KeyMintDevice::importKey(const std::vector<KeyParameter>& in_inKeyParams,
+                                       KeyFormat in_inKeyFormat,
+                                       const std::vector<uint8_t>& in_inKeyData,
+                                       ByteArray* out_outImportedKeyBlob,
+                                       KeyCharacteristics* out_outImportedKeyCharacteristics,
+                                       std::vector<Certificate>* out_outCertChain) {
+    auto legacyKeyParams = convertKeyParametersToLegacy(in_inKeyParams);
+    auto legacyKeyFormat = convertKeyFormatToLegacy(in_inKeyFormat);
+    V4_0_ErrorCode errorCode;
+    auto result =
+        mDevice->importKey(legacyKeyParams, legacyKeyFormat, in_inKeyData,
+                           [&](V4_0_ErrorCode error, const hidl_vec<uint8_t>& keyBlob,
+                               const V4_0_KeyCharacteristics& keyCharacteristics) {
+                               errorCode = error;
+                               out_outImportedKeyBlob->data = keyBlob;
+                               *out_outImportedKeyCharacteristics =
+                                   convertKeyCharacteristicsFromLegacy(keyCharacteristics);
+                           });
+    if (!result.isOk()) {
+        return ScopedAStatus::fromServiceSpecificError(
+            static_cast<int32_t>(ResponseCode::SYSTEM_ERROR));
+    }
+    if (errorCode == V4_0_ErrorCode::OK) {
+        auto cert = getCertificate(in_inKeyParams, out_outImportedKeyBlob->data);
+        if (std::holds_alternative<V4_0_ErrorCode>(cert)) {
+            auto code = std::get<V4_0_ErrorCode>(cert);
+            // We return OK in successful cases that do not generate a certificate.
+            if (code != V4_0_ErrorCode::OK) {
+                errorCode = code;
+                deleteKey(out_outImportedKeyBlob->data);
+            }
+        } else {
+            *out_outCertChain = std::get<std::vector<Certificate>>(cert);
+        }
+    }
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus KeyMintDevice::importWrappedKey(
+    const std::vector<uint8_t>& in_inWrappedKeyData,
+    const std::vector<uint8_t>& in_inWrappingKeyBlob, const std::vector<uint8_t>& in_inMaskingKey,
+    const std::vector<KeyParameter>& in_inUnwrappingParams, int64_t in_inPasswordSid,
+    int64_t in_inBiometricSid, ByteArray* out_outImportedKeyBlob,
+    KeyCharacteristics* out_outImportedKeyCharacteristics) {
+    auto legacyUnwrappingParams = convertKeyParametersToLegacy(in_inUnwrappingParams);
+    V4_0_ErrorCode errorCode;
+    auto result =
+        mDevice->importWrappedKey(in_inWrappedKeyData, in_inWrappingKeyBlob, in_inMaskingKey,
+                                  legacyUnwrappingParams, in_inPasswordSid, in_inBiometricSid,
+                                  [&](V4_0_ErrorCode error, const hidl_vec<uint8_t>& keyBlob,
+                                      const V4_0_KeyCharacteristics& keyCharacteristics) {
+                                      errorCode = error;
+                                      out_outImportedKeyBlob->data = keyBlob;
+                                      *out_outImportedKeyCharacteristics =
+                                          convertKeyCharacteristicsFromLegacy(keyCharacteristics);
+                                  });
+    if (!result.isOk()) {
+        return ScopedAStatus::fromServiceSpecificError(
+            static_cast<int32_t>(ResponseCode::SYSTEM_ERROR));
+    }
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus KeyMintDevice::upgradeKey(const std::vector<uint8_t>& in_inKeyBlobToUpgrade,
+                                        const std::vector<KeyParameter>& in_inUpgradeParams,
+                                        std::vector<uint8_t>* _aidl_return) {
+    auto legacyUpgradeParams = convertKeyParametersToLegacy(in_inUpgradeParams);
+    V4_0_ErrorCode errorCode;
+    auto result =
+        mDevice->upgradeKey(in_inKeyBlobToUpgrade, legacyUpgradeParams,
+                            [&](V4_0_ErrorCode error, const hidl_vec<uint8_t>& upgradedKeyBlob) {
+                                errorCode = error;
+                                *_aidl_return = upgradedKeyBlob;
+                            });
+    if (!result.isOk()) {
+        return ScopedAStatus::fromServiceSpecificError(
+            static_cast<int32_t>(ResponseCode::SYSTEM_ERROR));
+    }
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus KeyMintDevice::deleteKey(const std::vector<uint8_t>& in_inKeyBlob) {
+    V4_0_ErrorCode errorCode = mDevice->deleteKey(in_inKeyBlob);
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus KeyMintDevice::deleteAllKeys() {
+    V4_0_ErrorCode errorCode = mDevice->deleteAllKeys();
+    return convertErrorCode(errorCode);
+}
+
+// We're not implementing this.
+ScopedAStatus KeyMintDevice::destroyAttestationIds() {
+    return ScopedAStatus::fromServiceSpecificError(
+        static_cast<int32_t>(V4_0_ErrorCode::UNIMPLEMENTED));
+}
+
+ScopedAStatus KeyMintDevice::begin(KeyPurpose in_inPurpose,
+                                   const std::vector<uint8_t>& in_inKeyBlob,
+                                   const std::vector<KeyParameter>& in_inParams,
+                                   const HardwareAuthToken& in_inAuthToken,
+                                   BeginResult* _aidl_return) {
+    if (!mOperationSlots.claimSlot()) {
+        return convertErrorCode(V4_0_ErrorCode::TOO_MANY_OPERATIONS);
+    }
+    auto legacyPurpose =
+        static_cast<::android::hardware::keymaster::V4_0::KeyPurpose>(in_inPurpose);
+    auto legacyParams = convertKeyParametersToLegacy(in_inParams);
+    auto legacyAuthToken = convertAuthTokenToLegacy(in_inAuthToken);
+    V4_0_ErrorCode errorCode;
+    auto result = mDevice->begin(
+        legacyPurpose, in_inKeyBlob, legacyParams, legacyAuthToken,
+        [&](V4_0_ErrorCode error, const hidl_vec<V4_0_KeyParameter>& outParams,
+            uint64_t operationHandle) {
+            errorCode = error;
+            _aidl_return->challenge = operationHandle;  // TODO: Is this right?
+            _aidl_return->params = convertKeyParametersFromLegacy(outParams);
+            _aidl_return->operation = ndk::SharedRefBase::make<KeyMintOperation>(
+                mDevice, operationHandle, &mOperationSlots, error == V4_0_ErrorCode::OK);
+        });
+    if (!result.isOk()) {
+        // TODO: In this case we're guaranteed that _aidl_return was not initialized, right?
+        mOperationSlots.freeSlot();
+        return ScopedAStatus::fromServiceSpecificError(
+            static_cast<int32_t>(ResponseCode::SYSTEM_ERROR));
+    }
+    if (errorCode != V4_0_ErrorCode::OK) {
+        mOperationSlots.freeSlot();
+    }
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus
+KeyMintOperation::update(const std::optional<KeyParameterArray>& in_inParams,
+                         const std::optional<std::vector<uint8_t>>& in_input,
+                         const std::optional<HardwareAuthToken>& in_inAuthToken,
+                         const std::optional<VerificationToken>& in_inVerificationToken,
+                         std::optional<KeyParameterArray>* out_outParams,
+                         std::optional<ByteArray>* out_output, int32_t* _aidl_return) {
+    std::vector<V4_0_KeyParameter> legacyParams;
+    if (in_inParams.has_value()) {
+        legacyParams = convertKeyParametersToLegacy(in_inParams.value().params);
+    }
+    auto input = in_input.value_or(std::vector<uint8_t>());
+    V4_0_HardwareAuthToken authToken;
+    if (in_inAuthToken.has_value()) {
+        authToken = convertAuthTokenToLegacy(in_inAuthToken.value());
+    }
+    V4_0_VerificationToken verificationToken;
+    if (in_inVerificationToken.has_value()) {
+        verificationToken = convertVerificationTokenToLegacy(in_inVerificationToken.value());
+    }
+    V4_0_ErrorCode errorCode;
+    auto result = mDevice->update(
+        mOperationHandle, legacyParams, input, authToken, verificationToken,
+        [&](V4_0_ErrorCode error, uint32_t inputConsumed,
+            const hidl_vec<V4_0_KeyParameter>& outParams, const hidl_vec<uint8_t>& output) {
+            errorCode = error;
+            out_outParams->emplace();
+            out_outParams->value().params = convertKeyParametersFromLegacy(outParams);
+            out_output->emplace();
+            out_output->value().data = output;
+            *_aidl_return = inputConsumed;
+        });
+    if (!result.isOk()) {
+        mOperationSlot.freeSlot();
+        return ScopedAStatus::fromServiceSpecificError(
+            static_cast<int32_t>(ResponseCode::SYSTEM_ERROR));
+    }
+    if (errorCode != V4_0_ErrorCode::OK) {
+        mOperationSlot.freeSlot();
+    }
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus
+KeyMintOperation::finish(const std::optional<KeyParameterArray>& in_inParams,
+                         const std::optional<std::vector<uint8_t>>& in_input,
+                         const std::optional<std::vector<uint8_t>>& in_inSignature,
+                         const std::optional<HardwareAuthToken>& in_authToken,
+                         const std::optional<VerificationToken>& in_inVerificationToken,
+                         std::optional<KeyParameterArray>* out_outParams,
+                         std::vector<uint8_t>* _aidl_return) {
+    V4_0_ErrorCode errorCode;
+    std::vector<V4_0_KeyParameter> legacyParams;
+    if (in_inParams.has_value()) {
+        legacyParams = convertKeyParametersToLegacy(in_inParams.value().params);
+    }
+    auto input = in_input.value_or(std::vector<uint8_t>());
+    auto signature = in_inSignature.value_or(std::vector<uint8_t>());
+    V4_0_HardwareAuthToken authToken;
+    if (in_authToken.has_value()) {
+        authToken = convertAuthTokenToLegacy(in_authToken.value());
+    }
+    V4_0_VerificationToken verificationToken;
+    if (in_inVerificationToken.has_value()) {
+        verificationToken = convertVerificationTokenToLegacy(in_inVerificationToken.value());
+    }
+    auto result = mDevice->finish(
+        mOperationHandle, legacyParams, input, signature, authToken, verificationToken,
+        [&](V4_0_ErrorCode error, const hidl_vec<V4_0_KeyParameter>& outParams,
+            const hidl_vec<uint8_t>& output) {
+            errorCode = error;
+            out_outParams->emplace();
+            out_outParams->value().params = convertKeyParametersFromLegacy(outParams);
+            *_aidl_return = output;
+        });
+    mOperationSlot.freeSlot();
+    if (!result.isOk()) {
+        return ScopedAStatus::fromServiceSpecificError(
+            static_cast<int32_t>(ResponseCode::SYSTEM_ERROR));
+    }
+    return convertErrorCode(errorCode);
+}
+
+ScopedAStatus KeyMintOperation::abort() {
+    V4_0_ErrorCode errorCode = mDevice->abort(mOperationHandle);
+    mOperationSlot.freeSlot();
+    return convertErrorCode(errorCode);
+}
+
+KeyMintOperation::~KeyMintOperation() {
+    if (mOperationSlot.hasSlot()) {
+        auto error = abort();
+        if (!error.isOk()) {
+            LOG(WARNING) << "Error calling abort in ~KeyMintOperation: " << error.getMessage();
+        }
+    }
+}
+
+// Certificate implementation
+
+static std::optional<KeyParameter> getParam(const std::vector<KeyParameter>& keyParams, Tag tag) {
+    auto it = find_if(keyParams.begin(), keyParams.end(),
+                      [&](const KeyParameter& kp) { return kp.tag == tag; });
+    if (it == keyParams.end()) {
+        return std::nullopt;
+    }
+    return std::optional(*it);
+}
+
+static bool containsParam(const std::vector<KeyParameter>& keyParams, Tag tag) {
+    return getParam(keyParams, tag).has_value();
+}
+
+// Prefer the smallest.
+// If no options are found, return the first.
+template <typename T>
+static T getMaximum(const std::vector<KeyParameter>& keyParams, Tag tag,
+                    std::vector<T> sortedOptions) {
+    auto bestSoFar = sortedOptions.end();
+    for (const KeyParameter& kp : keyParams) {
+        if (kp.tag == tag) {
+            auto it =
+                std::find(sortedOptions.begin(), sortedOptions.end(), static_cast<T>(kp.integer));
+            if (std::distance(it, bestSoFar) < 0) {
+                bestSoFar = it;
+            }
+        }
+    }
+    if (bestSoFar == sortedOptions.end()) {
+        return sortedOptions[0];
+    }
+    return *bestSoFar;
+}
+
+// TODO: What should I do if these tags don't exist?  An empty blob might be okay, but what about
+// the integers and longs?
+// TODO: Migrate to using accessTagValue when possible.
+static std::vector<uint8_t> getBlob(const std::optional<KeyParameter> kp) {
+    if (!kp.has_value()) {
+        return {};
+    }
+    return kp->blob;
+}
+
+static int32_t getLong(std::optional<KeyParameter> kp) {
+    if (!kp.has_value()) {
+        return -1;
+    }
+    return kp->longInteger;
+}
+
+static int64_t getInteger(std::optional<KeyParameter> kp) {
+    if (!kp.has_value()) {
+        return -1;
+    }
+    return kp->integer;
+}
+
+static std::variant<keystore::X509_Ptr, V4_0_ErrorCode>
+makeCert(::android::sp<Keymaster> mDevice, const std::vector<KeyParameter>& keyParams,
+         const std::vector<uint8_t>& keyBlob) {
+    // Start generating the certificate.
+    // Get public key for makeCert.
+    V4_0_ErrorCode errorCode = V4_0_ErrorCode::OK;
+    std::vector<uint8_t> key;
+    auto result = mDevice->exportKey(
+        V4_0_KeyFormat::X509, keyBlob, getBlob(getParam(keyParams, Tag::APPLICATION_ID)),
+        getBlob(getParam(keyParams, Tag::APPLICATION_DATA)),
+        [&](V4_0_ErrorCode error, const hidl_vec<uint8_t>& keyMaterial) {
+            errorCode = error;
+            key = keyMaterial;
+        });
+    if (!result.isOk()) {
+        return V4_0_ErrorCode::UNKNOWN_ERROR;
+    }
+    if (errorCode != V4_0_ErrorCode::OK) {
+        return errorCode;
+    }
+    // Get pkey for makeCert.
+    CBS cbs;
+    CBS_init(&cbs, key.data(), key.size());
+    auto pkey = EVP_parse_public_key(&cbs);
+    // makeCert
+    // TODO: Get the serial and subject from key params once the tags are added.  Also use new tags
+    // for the two datetime parameters once we get those.
+    auto certOrError = keystore::makeCert(
+        pkey, 42, "TODO", getLong(getParam(keyParams, Tag::ACTIVE_DATETIME)),
+        getLong(getParam(keyParams, Tag::USAGE_EXPIRE_DATETIME)),
+        false /* intentionally left blank */, std::nullopt /* intentionally left blank */,
+        std::nullopt /* intentionally left blank */);
+    if (std::holds_alternative<keystore::CertUtilsError>(certOrError)) {
+        // TODO: What error should I actually return?  And the same everywhere below.
+        return V4_0_ErrorCode::UNKNOWN_ERROR;
+    }
+    return std::move(std::get<keystore::X509_Ptr>(certOrError));
+}
+
+static std::variant<keystore::Algo, V4_0_ErrorCode> getKeystoreAlgorithm(Algorithm algorithm) {
+    switch (algorithm) {
+    case Algorithm::RSA:
+        return keystore::Algo::RSA;
+    case Algorithm::EC:
+        return keystore::Algo::ECDSA;
+    default:
+        return V4_0_ErrorCode::UNKNOWN_ERROR;
+    }
+}
+
+static std::variant<keystore::Padding, V4_0_ErrorCode> getKeystorePadding(PaddingMode padding) {
+    switch (padding) {
+    case PaddingMode::RSA_PKCS1_1_5_SIGN:
+        return keystore::Padding::PKCS1_5;
+    case PaddingMode::RSA_PSS:
+        return keystore::Padding::PSS;
+    default:
+        return keystore::Padding::Ignored;
+    }
+}
+
+static std::variant<keystore::Digest, V4_0_ErrorCode> getKeystoreDigest(Digest digest) {
+    switch (digest) {
+    case Digest::SHA1:
+        return keystore::Digest::SHA1;
+    case Digest::SHA_2_224:
+        return keystore::Digest::SHA224;
+    case Digest::SHA_2_256:
+    case Digest::NONE:
+        return keystore::Digest::SHA256;
+    case Digest::SHA_2_384:
+        return keystore::Digest::SHA384;
+    case Digest::SHA_2_512:
+        return keystore::Digest::SHA512;
+    default:
+        return V4_0_ErrorCode::UNKNOWN_ERROR;
+    }
+}
+
+std::optional<V4_0_ErrorCode>
+KeyMintDevice::signCertificate(const std::vector<KeyParameter>& keyParams,
+                               const std::vector<uint8_t>& keyBlob, X509* cert) {
+    auto algorithm = static_cast<Algorithm>(getInteger(getParam(keyParams, Tag::ALGORITHM)));
+    auto algoOrError = getKeystoreAlgorithm(algorithm);
+    if (std::holds_alternative<V4_0_ErrorCode>(algoOrError)) {
+        return std::get<V4_0_ErrorCode>(algoOrError);
+    }
+    auto algo = std::get<keystore::Algo>(algoOrError);
+    auto origPadding = getMaximum<PaddingMode>(
+        keyParams, Tag::PADDING, {PaddingMode::RSA_PSS, PaddingMode::RSA_PKCS1_1_5_SIGN});
+    auto paddingOrError = getKeystorePadding(origPadding);
+    if (std::holds_alternative<V4_0_ErrorCode>(paddingOrError)) {
+        return std::get<V4_0_ErrorCode>(paddingOrError);
+    }
+    auto padding = std::get<keystore::Padding>(paddingOrError);
+    auto origDigest = getMaximum<Digest>(
+        keyParams, Tag::DIGEST,
+        {Digest::SHA_2_256, Digest::SHA_2_512, Digest::SHA_2_384, Digest::SHA_2_224, Digest::SHA1});
+    auto digestOrError = getKeystoreDigest(origDigest);
+    if (std::holds_alternative<V4_0_ErrorCode>(digestOrError)) {
+        return std::get<V4_0_ErrorCode>(digestOrError);
+    }
+    auto digest = std::get<keystore::Digest>(digestOrError);
+
+    V4_0_ErrorCode errorCode = V4_0_ErrorCode::OK;
+    auto error = keystore::signCertWith(
+        &*cert,
+        [&](const uint8_t* data, size_t len) {
+            std::vector<uint8_t> dataVec(data, data + len);
+            std::vector<KeyParameter> kps = {
+                KeyParameter{.tag = Tag::PADDING, .integer = static_cast<int32_t>(origPadding)},
+                KeyParameter{.tag = Tag::DIGEST, .integer = static_cast<int32_t>(origDigest)},
+            };
+            BeginResult beginResult;
+            auto error = begin(KeyPurpose::SIGN, keyBlob, kps, HardwareAuthToken(), &beginResult);
+            if (!error.isOk()) {
+                errorCode = static_cast<V4_0_ErrorCode>(error.getServiceSpecificError());
+                return std::vector<uint8_t>();
+            }
+            std::optional<KeyParameterArray> outParams;
+            std::optional<ByteArray> outByte;
+            int32_t status;
+            beginResult.operation->update(std::nullopt, dataVec, HardwareAuthToken(),
+                                          VerificationToken(), &outParams, &outByte, &status);
+            if (!status) {
+                return std::vector<uint8_t>();
+            }
+            std::vector<uint8_t> result;
+            error = beginResult.operation->finish(std::nullopt, std::nullopt, std::nullopt,
+                                                  std::nullopt, std::nullopt, &outParams, &result);
+            if (!error.isOk()) {
+                errorCode = static_cast<V4_0_ErrorCode>(error.getServiceSpecificError());
+                return std::vector<uint8_t>();
+            }
+            return result;
+        },
+        algo, padding, digest);
+    if (error) {
+        return V4_0_ErrorCode::UNKNOWN_ERROR;
+    }
+    if (errorCode != V4_0_ErrorCode::OK) {
+        return errorCode;
+    }
+    return std::nullopt;
+}
+
+std::variant<std::vector<Certificate>, V4_0_ErrorCode>
+KeyMintDevice::getCertificate(const std::vector<KeyParameter>& keyParams,
+                              const std::vector<uint8_t>& keyBlob) {
+    // There are no certificates for symmetric keys.
+    auto algorithm = static_cast<Algorithm>(getInteger(getParam(keyParams, Tag::ALGORITHM)));
+    switch (algorithm) {
+    case Algorithm::RSA:
+    case Algorithm::EC:
+        break;
+    default:
+        return V4_0_ErrorCode::OK;
+    }
+    // If attestation was requested, call and use attestKey.
+    if (containsParam(keyParams, Tag::ATTESTATION_CHALLENGE)) {
+        auto legacyParams = convertKeyParametersToLegacy(keyParams);
+        std::vector<Certificate> certs;
+        V4_0_ErrorCode errorCode = V4_0_ErrorCode::OK;
+        auto result = mDevice->attestKey(
+            keyBlob, legacyParams,
+            [&](V4_0_ErrorCode error, const hidl_vec<hidl_vec<uint8_t>>& certChain) {
+                errorCode = error;
+                for (const auto& cert : certChain) {
+                    Certificate certificate;
+                    certificate.encodedCertificate = cert;
+                    certs.push_back(certificate);
+                }
+            });
+        if (!result.isOk()) {
+            return V4_0_ErrorCode::UNKNOWN_ERROR;
+        }
+        if (errorCode != V4_0_ErrorCode::OK) {
+            return errorCode;
+        }
+        return certs;
+    }
+
+    // makeCert
+    auto certOrError = makeCert(mDevice, keyParams, keyBlob);
+    if (std::holds_alternative<V4_0_ErrorCode>(certOrError)) {
+        return std::get<V4_0_ErrorCode>(certOrError);
+    }
+    auto cert = std::move(std::get<keystore::X509_Ptr>(certOrError));
+
+    // setIssuer
+    auto error = keystore::setIssuer(&*cert, &*cert, false);
+    if (error) {
+        return V4_0_ErrorCode::UNKNOWN_ERROR;
+    }
+
+    // Signing
+    auto canSelfSign =
+        std::find_if(keyParams.begin(), keyParams.end(), [&](const KeyParameter& kp) {
+            return kp.tag == Tag::PURPOSE &&
+                   static_cast<KeyPurpose>(kp.integer) == KeyPurpose::SIGN;
+        }) != keyParams.end();
+    auto noAuthRequired = containsParam(keyParams, Tag::NO_AUTH_REQUIRED);
+    if (canSelfSign && noAuthRequired) {
+        auto errorCode = signCertificate(keyParams, keyBlob, &*cert);
+        if (errorCode.has_value()) {
+            return errorCode.value();
+        }
+    } else {
+        keystore::EVP_PKEY_CTX_Ptr pkey_ctx(EVP_PKEY_CTX_new_id(EVP_PKEY_EC, NULL));
+        EVP_PKEY_keygen_init(pkey_ctx.get());
+        EVP_PKEY_CTX_set_ec_paramgen_curve_nid(pkey_ctx.get(), NID_X9_62_prime256v1);
+        EVP_PKEY* pkey_ptr = nullptr;
+        EVP_PKEY_keygen(pkey_ctx.get(), &pkey_ptr);
+        error = keystore::signCert(&*cert, pkey_ptr);
+    }
+    if (error) {
+        return V4_0_ErrorCode::UNKNOWN_ERROR;
+    }
+
+    // encodeCert
+    auto encodedCertOrError = keystore::encodeCert(&*cert);
+    if (std::holds_alternative<keystore::CertUtilsError>(encodedCertOrError)) {
+        return V4_0_ErrorCode::UNKNOWN_ERROR;
+    }
+
+    Certificate certificate{.encodedCertificate =
+                                std::get<std::vector<uint8_t>>(encodedCertOrError)};
+    std::vector certificates = {certificate};
+    return certificates;
+}
+
+// Code to find the Keymaster devices (copied from existing code).
+
+// Copied from system/security/keystore/include/keystore/keymaster_types.h.
+
+// Changing this namespace alias will change the keymaster version.
+namespace keymaster = ::android::hardware::keymaster::V4_1;
+
+using keymaster::SecurityLevel;
+
+// Copied from system/security/keystore/KeyStore.h.
+
+using ::android::sp;
+using keymaster::support::Keymaster;
+
+template <typename T, size_t count> class Devices : public std::array<T, count> {
+  public:
+    T& operator[](SecurityLevel secLevel) {
+        static_assert(uint32_t(SecurityLevel::SOFTWARE) == 0 &&
+                          uint32_t(SecurityLevel::TRUSTED_ENVIRONMENT) == 1 &&
+                          uint32_t(SecurityLevel::STRONGBOX) == 2,
+                      "Numeric values of security levels have changed");
+        return std::array<T, count>::at(static_cast<uint32_t>(secLevel));
+    }
+    T operator[](SecurityLevel secLevel) const {
+        if (static_cast<uint32_t>(secLevel) > static_cast<uint32_t>(SecurityLevel::STRONGBOX)) {
+            LOG(ERROR) << "Invalid security level requested";
+            return {};
+        }
+        return (*const_cast<Devices*>(this))[secLevel];
+    }
+};
+
+using KeymasterDevices = Devices<sp<Keymaster>, 3>;
+
+// Copied from system/security/keystore/keystore_main.cpp.
+
+using ::android::hardware::hidl_string;
+using keymaster::support::Keymaster3;
+using keymaster::support::Keymaster4;
+
+template <typename Wrapper>
+KeymasterDevices enumerateKeymasterDevices(IServiceManager* serviceManager) {
+    KeymasterDevices result;
+    serviceManager->listManifestByInterface(
+        Wrapper::WrappedIKeymasterDevice::descriptor, [&](const hidl_vec<hidl_string>& names) {
+            auto try_get_device = [&](const auto& name, bool fail_silent) {
+                auto device = Wrapper::WrappedIKeymasterDevice::getService(name);
+                if (fail_silent && !device) return;
+                CHECK(device) << "Failed to get service for \""
+                              << Wrapper::WrappedIKeymasterDevice::descriptor
+                              << "\" with interface name \"" << name << "\"";
+
+                sp<Keymaster> kmDevice(new Wrapper(device, name));
+                auto halVersion = kmDevice->halVersion();
+                SecurityLevel securityLevel = halVersion.securityLevel;
+                LOG(INFO) << "found " << Wrapper::WrappedIKeymasterDevice::descriptor
+                          << " with interface name " << name << " and seclevel "
+                          << toString(securityLevel);
+                CHECK(static_cast<uint32_t>(securityLevel) < result.size())
+                    << "Security level of \"" << Wrapper::WrappedIKeymasterDevice::descriptor
+                    << "\" with interface name \"" << name << "\" out of range";
+                auto& deviceSlot = result[securityLevel];
+                if (deviceSlot) {
+                    if (!fail_silent) {
+                        LOG(WARNING) << "Implementation of \""
+                                     << Wrapper::WrappedIKeymasterDevice::descriptor
+                                     << "\" with interface name \"" << name
+                                     << "\" and security level: " << toString(securityLevel)
+                                     << " Masked by other implementation of Keymaster";
+                    }
+                } else {
+                    deviceSlot = kmDevice;
+                }
+            };
+            bool has_default = false;
+            for (auto& n : names) {
+                try_get_device(n, false);
+                if (n == "default") has_default = true;
+            }
+            // Make sure that we always check the default device. If we enumerate only what is
+            // known to hwservicemanager, we miss a possible passthrough HAL.
+            if (!has_default) {
+                try_get_device("default", true /* fail_silent */);
+            }
+        });
+    return result;
+}
+
+KeymasterDevices initializeKeymasters() {
+    auto serviceManager = IServiceManager::getService();
+    CHECK(serviceManager.get()) << "Failed to get ServiceManager";
+    auto result = enumerateKeymasterDevices<Keymaster4>(serviceManager.get());
+    auto softKeymaster = result[SecurityLevel::SOFTWARE];
+    if (!result[SecurityLevel::TRUSTED_ENVIRONMENT]) {
+        result = enumerateKeymasterDevices<Keymaster3>(serviceManager.get());
+    }
+    if (softKeymaster) result[SecurityLevel::SOFTWARE] = softKeymaster;
+    if (result[SecurityLevel::SOFTWARE] && !result[SecurityLevel::TRUSTED_ENVIRONMENT]) {
+        LOG(WARNING) << "No secure Keymaster implementation found, but device offers insecure"
+                        " Keymaster HAL. Using as default.";
+        result[SecurityLevel::TRUSTED_ENVIRONMENT] = result[SecurityLevel::SOFTWARE];
+        result[SecurityLevel::SOFTWARE] = nullptr;
+    }
+    // The software bit was removed since we do not need it.
+    return result;
+}
+
+// KeyMintDevice implementation
+
+KeyMintDevice::KeyMintDevice(sp<Keymaster> device, KeyMintSecurityLevel securityLevel)
+    : mDevice(device) {
+    if (securityLevel == KeyMintSecurityLevel::STRONGBOX) {
+        mOperationSlots.setNumFreeSlots(3);
+    } else {
+        mOperationSlots.setNumFreeSlots(15);
+    }
+}
+
+void KeyMintDevice::setNumFreeSlots(uint8_t numFreeSlots) {
+    mOperationSlots.setNumFreeSlots(numFreeSlots);
+}
+
+std::shared_ptr<KeyMintDevice>
+KeyMintDevice::createKeyMintDevice(KeyMintSecurityLevel securityLevel) {
+    auto secLevel = static_cast<SecurityLevel>(securityLevel);
+    auto devices = initializeKeymasters();
+    auto device = devices[secLevel];
+    if (!device) {
+        return {};
+    }
+    return ndk::SharedRefBase::make<KeyMintDevice>(std::move(device), securityLevel);
+}
+
+ScopedAStatus
+KeystoreCompatService::getKeyMintDevice(KeyMintSecurityLevel in_securityLevel,
+                                        std::shared_ptr<IKeyMintDevice>* _aidl_return) {
+    if (mDeviceCache.find(in_securityLevel) == mDeviceCache.end()) {
+        auto device = KeyMintDevice::createKeyMintDevice(in_securityLevel);
+        if (!device) {
+            return ScopedAStatus::fromStatus(STATUS_NAME_NOT_FOUND);
+        }
+        mDeviceCache[in_securityLevel] = std::move(device);
+    }
+    *_aidl_return = mDeviceCache[in_securityLevel];
+    return ScopedAStatus::ok();
+}
diff --git a/keystore2/src/km_compat/km_compat.h b/keystore2/src/km_compat/km_compat.h
new file mode 100644
index 0000000..904d391
--- /dev/null
+++ b/keystore2/src/km_compat/km_compat.h
@@ -0,0 +1,162 @@
+/*
+ * 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 <aidl/android/hardware/security/keymint/BnKeyMintDevice.h>
+#include <aidl/android/hardware/security/keymint/BnKeyMintOperation.h>
+#include <aidl/android/security/compat/BnKeystoreCompatService.h>
+#include <keymasterV4_1/Keymaster4.h>
+#include <unordered_map>
+#include <variant>
+
+#include "certificate_utils.h"
+
+using ::aidl::android::hardware::security::keymint::BeginResult;
+using ::aidl::android::hardware::security::keymint::ByteArray;
+using ::aidl::android::hardware::security::keymint::Certificate;
+using ::aidl::android::hardware::security::keymint::HardwareAuthToken;
+using ::aidl::android::hardware::security::keymint::KeyCharacteristics;
+using ::aidl::android::hardware::security::keymint::KeyFormat;
+using ::aidl::android::hardware::security::keymint::KeyMintHardwareInfo;
+using ::aidl::android::hardware::security::keymint::KeyParameter;
+using ::aidl::android::hardware::security::keymint::KeyParameterArray;
+using ::aidl::android::hardware::security::keymint::KeyPurpose;
+using ::aidl::android::hardware::security::keymint::VerificationToken;
+using KeyMintSecurityLevel = ::aidl::android::hardware::security::keymint::SecurityLevel;
+using V4_0_ErrorCode = ::android::hardware::keymaster::V4_0::ErrorCode;
+using ::aidl::android::hardware::security::keymint::IKeyMintDevice;
+using ::aidl::android::security::compat::BnKeystoreCompatService;
+using ::android::hardware::keymaster::V4_1::support::Keymaster;
+using ::ndk::ScopedAStatus;
+
+class OperationSlots {
+  private:
+    uint8_t mNumFreeSlots;
+    std::mutex mNumFreeSlotsMutex;
+
+  public:
+    void setNumFreeSlots(uint8_t numFreeSlots);
+    bool claimSlot();
+    void freeSlot();
+};
+
+// An abstraction for a single operation slot.
+// This contains logic to ensure that we do not free the slot multiple times,
+// e.g., if we call abort twice on the same operation.
+class OperationSlot {
+  private:
+    OperationSlots* mOperationSlots;
+    bool mIsActive;
+
+  public:
+    OperationSlot(OperationSlots* slots, bool isActive)
+        : mOperationSlots(slots), mIsActive(isActive) {}
+
+    void freeSlot();
+    bool hasSlot() { return mIsActive; }
+};
+
+class KeyMintDevice : public aidl::android::hardware::security::keymint::BnKeyMintDevice {
+  private:
+    ::android::sp<Keymaster> mDevice;
+    OperationSlots mOperationSlots;
+
+  public:
+    explicit KeyMintDevice(::android::sp<Keymaster>, KeyMintSecurityLevel);
+    static std::shared_ptr<KeyMintDevice> createKeyMintDevice(KeyMintSecurityLevel securityLevel);
+
+    ScopedAStatus getHardwareInfo(KeyMintHardwareInfo* _aidl_return) override;
+    ScopedAStatus verifyAuthorization(int64_t in_challenge, const HardwareAuthToken& in_token,
+                                      VerificationToken* _aidl_return) override;
+    ScopedAStatus addRngEntropy(const std::vector<uint8_t>& in_data) override;
+    ScopedAStatus generateKey(const std::vector<KeyParameter>& in_keyParams,
+                              ByteArray* out_generatedKeyBlob,
+                              KeyCharacteristics* out_generatedKeyCharacteristics,
+                              std::vector<Certificate>* out_outCertChain) override;
+    ScopedAStatus importKey(const std::vector<KeyParameter>& in_inKeyParams,
+                            KeyFormat in_inKeyFormat, const std::vector<uint8_t>& in_inKeyData,
+                            ByteArray* out_outImportedKeyBlob,
+                            KeyCharacteristics* out_outImportedKeyCharacteristics,
+                            std::vector<Certificate>* out_outCertChain) override;
+    ScopedAStatus importWrappedKey(const std::vector<uint8_t>& in_inWrappedKeyData,
+                                   const std::vector<uint8_t>& in_inWrappingKeyBlob,
+                                   const std::vector<uint8_t>& in_inMaskingKey,
+                                   const std::vector<KeyParameter>& in_inUnwrappingParams,
+                                   int64_t in_inPasswordSid, int64_t in_inBiometricSid,
+                                   ByteArray* out_outImportedKeyBlob,
+                                   KeyCharacteristics* out_outImportedKeyCharacteristics) override;
+    ScopedAStatus upgradeKey(const std::vector<uint8_t>& in_inKeyBlobToUpgrade,
+                             const std::vector<KeyParameter>& in_inUpgradeParams,
+                             std::vector<uint8_t>* _aidl_return) override;
+    ScopedAStatus deleteKey(const std::vector<uint8_t>& in_inKeyBlob) override;
+    ScopedAStatus deleteAllKeys() override;
+    ScopedAStatus destroyAttestationIds() override;
+    ScopedAStatus begin(KeyPurpose in_inPurpose, const std::vector<uint8_t>& in_inKeyBlob,
+                        const std::vector<KeyParameter>& in_inParams,
+                        const HardwareAuthToken& in_inAuthToken,
+                        BeginResult* _aidl_return) override;
+
+    // These are public to allow testing code to use them directly.
+    // This class should not be used publicly anyway.
+
+    std::variant<std::vector<Certificate>, V4_0_ErrorCode>
+    getCertificate(const std::vector<KeyParameter>& keyParams, const std::vector<uint8_t>& keyBlob);
+
+    void setNumFreeSlots(uint8_t numFreeSlots);
+
+  private:
+    std::optional<V4_0_ErrorCode> signCertificate(const std::vector<KeyParameter>& keyParams,
+                                                  const std::vector<uint8_t>& keyBlob, X509* cert);
+};
+
+class KeyMintOperation : public aidl::android::hardware::security::keymint::BnKeyMintOperation {
+  private:
+    ::android::sp<Keymaster> mDevice;
+    uint64_t mOperationHandle;
+    OperationSlot mOperationSlot;
+
+  public:
+    KeyMintOperation(::android::sp<Keymaster> device, uint64_t operationHandle,
+                     OperationSlots* slots, bool isActive)
+        : mDevice(device), mOperationHandle(operationHandle), mOperationSlot(slots, isActive) {}
+    ~KeyMintOperation();
+
+    ScopedAStatus update(const std::optional<KeyParameterArray>& in_inParams,
+                         const std::optional<std::vector<uint8_t>>& in_input,
+                         const std::optional<HardwareAuthToken>& in_inAuthToken,
+                         const std::optional<VerificationToken>& in_inVerificationToken,
+                         std::optional<KeyParameterArray>* out_outParams,
+                         std::optional<ByteArray>* out_output, int32_t* _aidl_return);
+    ScopedAStatus finish(const std::optional<KeyParameterArray>& in_inParams,
+                         const std::optional<std::vector<uint8_t>>& in_input,
+                         const std::optional<std::vector<uint8_t>>& in_inSignature,
+                         const std::optional<HardwareAuthToken>& in_authToken,
+                         const std::optional<VerificationToken>& in_inVerificationToken,
+                         std::optional<KeyParameterArray>* out_outParams,
+                         std::vector<uint8_t>* _aidl_return);
+    ScopedAStatus abort();
+};
+
+class KeystoreCompatService : public BnKeystoreCompatService {
+  private:
+    std::unordered_map<KeyMintSecurityLevel, std::shared_ptr<IKeyMintDevice>> mDeviceCache;
+
+  public:
+    KeystoreCompatService() {}
+    ScopedAStatus getKeyMintDevice(KeyMintSecurityLevel in_securityLevel,
+                                   std::shared_ptr<IKeyMintDevice>* _aidl_return) override;
+};
diff --git a/keystore2/src/km_compat/km_compat_service.cpp b/keystore2/src/km_compat/km_compat_service.cpp
new file mode 100644
index 0000000..56d7909
--- /dev/null
+++ b/keystore2/src/km_compat/km_compat_service.cpp
@@ -0,0 +1,29 @@
+/*
+ * 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 "km_compat.h"
+#include <android/binder_manager.h>
+
+extern "C" {
+
+// Create a KeyMintDevice and add it as a service.
+int32_t addKeyMintDeviceService() {
+    std::shared_ptr<KeystoreCompatService> ti = ndk::SharedRefBase::make<KeystoreCompatService>();
+    const auto instanceName = "android.security.compat";
+    binder_status_t status = AServiceManager_addService(ti->asBinder().get(), instanceName);
+    return status;
+}
+}
diff --git a/keystore2/src/km_compat/lib.rs b/keystore2/src/km_compat/lib.rs
new file mode 100644
index 0000000..b6a6baf
--- /dev/null
+++ b/keystore2/src/km_compat/lib.rs
@@ -0,0 +1,310 @@
+// Copyright 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.
+
+// TODO: Once this is stable, remove this and document everything public.
+#![allow(missing_docs)]
+
+extern "C" {
+    fn addKeyMintDeviceService() -> i32;
+}
+
+pub fn add_keymint_device_service() -> i32 {
+    unsafe { addKeyMintDeviceService() }
+}
+
+#[cfg(test)]
+mod tests {
+
+    use super::*;
+    use android_hardware_security_keymint::aidl::android::hardware::security::keymint::{
+        Algorithm::Algorithm, BeginResult::BeginResult, BlockMode::BlockMode, ByteArray::ByteArray,
+        Certificate::Certificate, Digest::Digest, ErrorCode::ErrorCode,
+        HardwareAuthToken::HardwareAuthToken, IKeyMintDevice::IKeyMintDevice,
+        KeyCharacteristics::KeyCharacteristics, KeyFormat::KeyFormat, KeyParameter::KeyParameter,
+        KeyParameterArray::KeyParameterArray, KeyPurpose::KeyPurpose, PaddingMode::PaddingMode,
+        SecurityLevel::SecurityLevel, Tag::Tag,
+    };
+    use android_hardware_security_keymint::binder;
+    use android_security_compat::aidl::android::security::compat::IKeystoreCompatService::IKeystoreCompatService;
+
+    fn get_device() -> Box<dyn IKeyMintDevice> {
+        add_keymint_device_service();
+        let compat_service: Box<dyn IKeystoreCompatService> =
+            binder::get_interface("android.security.compat").unwrap();
+        compat_service.getKeyMintDevice(SecurityLevel::TRUSTED_ENVIRONMENT).unwrap()
+    }
+
+    #[test]
+    fn test_get_hardware_info() {
+        let legacy = get_device();
+        let hinfo = legacy.getHardwareInfo().unwrap();
+        assert_eq!(hinfo.versionNumber, 0);
+        assert_ne!(hinfo.securityLevel, SecurityLevel::SOFTWARE);
+        assert_eq!(hinfo.keyMintName, "RemoteKeymaster");
+        assert_eq!(hinfo.keyMintAuthorName, "Google");
+    }
+
+    #[test]
+    fn test_verify_authorization() {
+        use android_hardware_security_keymint::aidl::android::hardware::security::keymint::HardwareAuthToken::HardwareAuthToken;
+        let legacy = get_device();
+        let result = legacy.verifyAuthorization(0, &HardwareAuthToken::default());
+        assert!(result.is_err());
+        assert_eq!(result.unwrap_err().service_specific_error(), ErrorCode::UNIMPLEMENTED.0,);
+    }
+
+    #[test]
+    fn test_add_rng_entropy() {
+        let legacy = get_device();
+        let result = legacy.addRngEntropy(&[42; 16]);
+        assert!(result.is_ok(), "{:?}", result);
+    }
+
+    // TODO: If I only need the key itself, don't return the other things.
+    fn generate_key(
+        legacy: &dyn IKeyMintDevice,
+        kps: Vec<KeyParameter>,
+    ) -> (ByteArray, KeyCharacteristics, Vec<Certificate>) {
+        let mut blob = ByteArray { data: vec![] };
+        let mut characteristics = KeyCharacteristics::default();
+        let mut cert_chain = vec![];
+        let result = legacy.generateKey(&kps, &mut blob, &mut characteristics, &mut cert_chain);
+        assert!(result.is_ok(), "{:?}", result);
+        assert_ne!(blob.data.len(), 0);
+        (blob, characteristics, cert_chain)
+    }
+
+    fn generate_rsa_key(legacy: &dyn IKeyMintDevice, encrypt: bool, attest: bool) -> Vec<u8> {
+        let mut kps = vec![
+            KeyParameter { tag: Tag::ALGORITHM, integer: Algorithm::RSA.0, ..Default::default() },
+            KeyParameter { tag: Tag::KEY_SIZE, integer: 2048, ..Default::default() },
+            KeyParameter {
+                tag: Tag::RSA_PUBLIC_EXPONENT,
+                longInteger: 65537,
+                ..Default::default()
+            },
+            KeyParameter { tag: Tag::DIGEST, integer: Digest::SHA_2_256.0, ..Default::default() },
+            KeyParameter {
+                tag: Tag::PADDING,
+                integer: PaddingMode::RSA_PSS.0,
+                ..Default::default()
+            },
+            KeyParameter { tag: Tag::NO_AUTH_REQUIRED, boolValue: true, ..Default::default() },
+            KeyParameter { tag: Tag::PURPOSE, integer: KeyPurpose::SIGN.0, ..Default::default() },
+        ];
+        if encrypt {
+            kps.push(KeyParameter {
+                tag: Tag::PURPOSE,
+                integer: KeyPurpose::ENCRYPT.0,
+                ..Default::default()
+            });
+        }
+        if attest {
+            kps.push(KeyParameter {
+                tag: Tag::ATTESTATION_CHALLENGE,
+                blob: vec![42; 8],
+                ..Default::default()
+            });
+            kps.push(KeyParameter {
+                tag: Tag::ATTESTATION_APPLICATION_ID,
+                blob: vec![42; 8],
+                ..Default::default()
+            });
+        }
+        let (blob, _, cert_chain) = generate_key(legacy, kps);
+        if attest {
+            // TODO: Will this always be greater than 1?
+            assert!(cert_chain.len() > 1);
+        } else {
+            assert_eq!(cert_chain.len(), 1);
+        }
+        blob.data
+    }
+
+    #[test]
+    fn test_generate_key_no_encrypt() {
+        let legacy = get_device();
+        generate_rsa_key(legacy.as_ref(), false, false);
+    }
+
+    #[test]
+    fn test_generate_key_encrypt() {
+        let legacy = get_device();
+        generate_rsa_key(legacy.as_ref(), true, false);
+    }
+
+    #[test]
+    fn test_generate_key_attested() {
+        let legacy = get_device();
+        generate_rsa_key(legacy.as_ref(), false, true);
+    }
+
+    #[test]
+    fn test_import_key() {
+        let legacy = get_device();
+        let kps =
+            [KeyParameter { tag: Tag::ALGORITHM, integer: Algorithm::AES.0, ..Default::default() }];
+        let kf = KeyFormat::RAW;
+        let kd = [0; 16];
+        let mut blob = ByteArray { data: vec![] };
+        let mut characteristics = KeyCharacteristics::default();
+        let mut cert_chain = vec![];
+        let result =
+            legacy.importKey(&kps, kf, &kd, &mut blob, &mut characteristics, &mut cert_chain);
+        assert!(result.is_ok(), "{:?}", result);
+        assert_ne!(blob.data.len(), 0);
+        assert_eq!(cert_chain.len(), 0);
+    }
+
+    #[test]
+    fn test_import_wrapped_key() {
+        let legacy = get_device();
+        let mut blob = ByteArray { data: vec![] };
+        let mut characteristics = KeyCharacteristics::default();
+        let result =
+            legacy.importWrappedKey(&[], &[], &[], &[], 0, 0, &mut blob, &mut characteristics);
+        // TODO: This test seems to fail on cuttlefish.  How should I test it?
+        assert!(result.is_err());
+    }
+
+    #[test]
+    fn test_upgrade_key() {
+        let legacy = get_device();
+        let blob = generate_rsa_key(legacy.as_ref(), false, false);
+        let result = legacy.upgradeKey(&blob, &[]);
+        // TODO: This test seems to fail on cuttlefish.  How should I test it?
+        assert!(result.is_err());
+    }
+
+    #[test]
+    fn test_delete_key() {
+        let legacy = get_device();
+        let blob = generate_rsa_key(legacy.as_ref(), false, false);
+        let result = legacy.deleteKey(&blob);
+        assert!(result.is_ok(), "{:?}", result);
+    }
+
+    #[test]
+    fn test_delete_all_keys() {
+        let legacy = get_device();
+        let result = legacy.deleteAllKeys();
+        assert!(result.is_ok(), "{:?}", result);
+    }
+
+    #[test]
+    fn test_destroy_attestation_ids() {
+        let legacy = get_device();
+        let result = legacy.destroyAttestationIds();
+        assert!(result.is_err());
+        assert_eq!(result.unwrap_err().service_specific_error(), ErrorCode::UNIMPLEMENTED.0,);
+    }
+
+    fn generate_aes_key(legacy: &dyn IKeyMintDevice) -> Vec<u8> {
+        let kps = vec![
+            KeyParameter { tag: Tag::ALGORITHM, integer: Algorithm::AES.0, ..Default::default() },
+            KeyParameter { tag: Tag::KEY_SIZE, integer: 128, ..Default::default() },
+            KeyParameter { tag: Tag::BLOCK_MODE, integer: BlockMode::CBC.0, ..Default::default() },
+            KeyParameter { tag: Tag::PADDING, integer: PaddingMode::NONE.0, ..Default::default() },
+            KeyParameter { tag: Tag::NO_AUTH_REQUIRED, boolValue: true, ..Default::default() },
+            KeyParameter {
+                tag: Tag::PURPOSE,
+                integer: KeyPurpose::ENCRYPT.0,
+                ..Default::default()
+            },
+            KeyParameter {
+                tag: Tag::PURPOSE,
+                integer: KeyPurpose::DECRYPT.0,
+                ..Default::default()
+            },
+        ];
+        let (blob, _, cert_chain) = generate_key(legacy, kps);
+        assert_eq!(cert_chain.len(), 0);
+        blob.data
+    }
+
+    fn begin(
+        legacy: &dyn IKeyMintDevice,
+        blob: &[u8],
+        purpose: KeyPurpose,
+        extra_params: Option<Vec<KeyParameter>>,
+    ) -> BeginResult {
+        let mut kps = vec![
+            KeyParameter { tag: Tag::BLOCK_MODE, integer: BlockMode::CBC.0, ..Default::default() },
+            KeyParameter { tag: Tag::PADDING, integer: PaddingMode::NONE.0, ..Default::default() },
+        ];
+        if let Some(mut extras) = extra_params {
+            kps.append(&mut extras);
+        }
+        let result = legacy.begin(purpose, &blob, &kps, &HardwareAuthToken::default());
+        assert!(result.is_ok(), "{:?}", result);
+        result.unwrap()
+    }
+
+    #[test]
+    fn test_begin_abort() {
+        let legacy = get_device();
+        let blob = generate_aes_key(legacy.as_ref());
+        let begin_result = begin(legacy.as_ref(), &blob, KeyPurpose::ENCRYPT, None);
+        let operation = begin_result.operation.unwrap();
+        let result = operation.abort();
+        assert!(result.is_ok(), "{:?}", result);
+        let result = operation.abort();
+        assert!(result.is_err());
+    }
+
+    #[test]
+    fn test_begin_update_finish() {
+        let legacy = get_device();
+        let blob = generate_aes_key(legacy.as_ref());
+
+        let begin_result = begin(legacy.as_ref(), &blob, KeyPurpose::ENCRYPT, None);
+        let operation = begin_result.operation.unwrap();
+        let params = KeyParameterArray {
+            params: vec![KeyParameter {
+                tag: Tag::ASSOCIATED_DATA,
+                blob: b"foobar".to_vec(),
+                ..Default::default()
+            }],
+        };
+        let message = [42; 128];
+        let mut out_params = None;
+        let result =
+            operation.finish(Some(&params), Some(&message), None, None, None, &mut out_params);
+        assert!(result.is_ok(), "{:?}", result);
+        let ciphertext = result.unwrap();
+        assert!(!ciphertext.is_empty());
+        assert!(out_params.is_some());
+
+        let begin_result =
+            begin(legacy.as_ref(), &blob, KeyPurpose::DECRYPT, Some(begin_result.params));
+        let operation = begin_result.operation.unwrap();
+        let mut out_params = None;
+        let mut output = None;
+        let result = operation.update(
+            Some(&params),
+            Some(&ciphertext),
+            None,
+            None,
+            &mut out_params,
+            &mut output,
+        );
+        assert!(result.is_ok(), "{:?}", result);
+        assert_eq!(result.unwrap(), message.len() as i32);
+        assert!(output.is_some());
+        assert_eq!(output.unwrap().data, message.to_vec());
+        let result = operation.finish(Some(&params), None, None, None, None, &mut out_params);
+        assert!(result.is_ok(), "{:?}", result);
+        assert!(out_params.is_some());
+    }
+}
diff --git a/keystore2/src/km_compat/slot_test.cpp b/keystore2/src/km_compat/slot_test.cpp
new file mode 100644
index 0000000..e56fb37
--- /dev/null
+++ b/keystore2/src/km_compat/slot_test.cpp
@@ -0,0 +1,170 @@
+/*
+ * Copyright 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 <gtest/gtest.h>
+
+#include "km_compat.h"
+#include <keymint_support/keymint_tags.h>
+
+#include <aidl/android/hardware/security/keymint/ErrorCode.h>
+#include <aidl/android/hardware/security/keymint/IKeyMintOperation.h>
+
+using ::aidl::android::hardware::security::keymint::Algorithm;
+using ::aidl::android::hardware::security::keymint::BlockMode;
+using ::aidl::android::hardware::security::keymint::ByteArray;
+using ::aidl::android::hardware::security::keymint::Certificate;
+using ::aidl::android::hardware::security::keymint::Digest;
+using ::aidl::android::hardware::security::keymint::ErrorCode;
+using ::aidl::android::hardware::security::keymint::IKeyMintOperation;
+using ::aidl::android::hardware::security::keymint::KeyCharacteristics;
+using ::aidl::android::hardware::security::keymint::KeyPurpose;
+using ::aidl::android::hardware::security::keymint::PaddingMode;
+using ::aidl::android::hardware::security::keymint::SecurityLevel;
+
+namespace KMV1 = ::aidl::android::hardware::security::keymint;
+
+static std::vector<uint8_t> generateAESKey(std::shared_ptr<KeyMintDevice> device) {
+    auto keyParams = std::vector<KeyParameter>({
+        KMV1::makeKeyParameter(KMV1::TAG_ALGORITHM, Algorithm::AES),
+        KMV1::makeKeyParameter(KMV1::TAG_KEY_SIZE, 128),
+        KMV1::makeKeyParameter(KMV1::TAG_BLOCK_MODE, BlockMode::CBC),
+        KMV1::makeKeyParameter(KMV1::TAG_PADDING, PaddingMode::NONE),
+        KMV1::makeKeyParameter(KMV1::TAG_NO_AUTH_REQUIRED, true),
+        KMV1::makeKeyParameter(KMV1::TAG_PURPOSE, KeyPurpose::ENCRYPT),
+        KMV1::makeKeyParameter(KMV1::TAG_PURPOSE, KeyPurpose::DECRYPT),
+    });
+    ByteArray blob;
+    KeyCharacteristics characteristics;
+    std::vector<Certificate> cert;
+    auto status = device->generateKey(keyParams, &blob, &characteristics, &cert);
+    if (!status.isOk()) {
+        return {};
+    }
+    return blob.data;
+}
+
+static std::variant<BeginResult, ScopedAStatus> begin(std::shared_ptr<KeyMintDevice> device,
+                                                      bool valid) {
+    auto blob = generateAESKey(device);
+    std::vector<KeyParameter> kps;
+    if (valid) {
+        kps.push_back(KMV1::makeKeyParameter(KMV1::TAG_BLOCK_MODE, BlockMode::CBC));
+        kps.push_back(KMV1::makeKeyParameter(KMV1::TAG_PADDING, PaddingMode::NONE));
+    }
+    BeginResult beginResult;
+    auto status = device->begin(KeyPurpose::ENCRYPT, blob, kps, HardwareAuthToken(), &beginResult);
+    if (!status.isOk()) {
+        return status;
+    }
+    return beginResult;
+}
+
+static const int NUM_SLOTS = 2;
+
+TEST(SlotTest, TestSlots) {
+    static std::shared_ptr<KeyMintDevice> device =
+        KeyMintDevice::createKeyMintDevice(SecurityLevel::TRUSTED_ENVIRONMENT);
+    device->setNumFreeSlots(NUM_SLOTS);
+
+    // A begin() that returns a failure should not use a slot.
+    auto result = begin(device, false);
+    ASSERT_TRUE(std::holds_alternative<ScopedAStatus>(result));
+
+    // Fill up all the slots.
+    std::vector<std::shared_ptr<IKeyMintOperation>> operations;
+    for (int i = 0; i < NUM_SLOTS; i++) {
+        auto result = begin(device, true);
+        ASSERT_TRUE(std::holds_alternative<BeginResult>(result));
+        operations.push_back(std::get<BeginResult>(result).operation);
+    }
+
+    // We should not be able to create a new operation.
+    result = begin(device, true);
+    ASSERT_TRUE(std::holds_alternative<ScopedAStatus>(result));
+    ASSERT_EQ(std::get<ScopedAStatus>(result).getServiceSpecificError(),
+              static_cast<int32_t>(ErrorCode::TOO_MANY_OPERATIONS));
+
+    // TODO: I'm not sure how to generate a failing update call to test that.
+
+    // Calling finish should free up a slot.
+    auto last = operations.back();
+    operations.pop_back();
+    std::optional<KeyParameterArray> kpa;
+    std::vector<uint8_t> byteVec;
+    auto status = last->finish(std::nullopt, std::nullopt, std::nullopt, std::nullopt, std::nullopt,
+                               &kpa, &byteVec);
+    ASSERT_TRUE(status.isOk());
+    result = begin(device, true);
+    ASSERT_TRUE(std::holds_alternative<BeginResult>(result));
+    operations.push_back(std::get<BeginResult>(result).operation);
+
+    // Calling finish and abort on an already-finished operation should not free up another slot.
+    status = last->finish(std::nullopt, std::nullopt, std::nullopt, std::nullopt, std::nullopt,
+                          &kpa, &byteVec);
+    ASSERT_TRUE(!status.isOk());
+    status = last->abort();
+    ASSERT_TRUE(!status.isOk());
+    result = begin(device, true);
+    ASSERT_TRUE(std::holds_alternative<ScopedAStatus>(result));
+    ASSERT_EQ(std::get<ScopedAStatus>(result).getServiceSpecificError(),
+              static_cast<int32_t>(ErrorCode::TOO_MANY_OPERATIONS));
+
+    // Calling abort should free up a slot.
+    last = operations.back();
+    operations.pop_back();
+    status = last->abort();
+    ASSERT_TRUE(status.isOk());
+    result = begin(device, true);
+    ASSERT_TRUE(std::holds_alternative<BeginResult>(result));
+    operations.push_back(std::get<BeginResult>(result).operation);
+
+    // Calling finish and abort on an already-aborted operation should not free up another slot.
+    status = last->finish(std::nullopt, std::nullopt, std::nullopt, std::nullopt, std::nullopt,
+                          &kpa, &byteVec);
+    ASSERT_TRUE(!status.isOk());
+    status = last->abort();
+    ASSERT_TRUE(!status.isOk());
+    result = begin(device, true);
+    ASSERT_TRUE(std::holds_alternative<ScopedAStatus>(result));
+    ASSERT_EQ(std::get<ScopedAStatus>(result).getServiceSpecificError(),
+              static_cast<int32_t>(ErrorCode::TOO_MANY_OPERATIONS));
+
+    // Generating a certificate with signWith also uses a slot.
+    auto kps = std::vector<KeyParameter>({
+        KMV1::makeKeyParameter(KMV1::TAG_ALGORITHM, Algorithm::RSA),
+        KMV1::makeKeyParameter(KMV1::TAG_KEY_SIZE, 2048),
+        KMV1::makeKeyParameter(KMV1::TAG_RSA_PUBLIC_EXPONENT, 65537),
+        KMV1::makeKeyParameter(KMV1::TAG_DIGEST, Digest::SHA_2_256),
+        KMV1::makeKeyParameter(KMV1::TAG_PURPOSE, KeyPurpose::SIGN),
+        KMV1::makeKeyParameter(KMV1::TAG_NO_AUTH_REQUIRED, true),
+    });
+    ByteArray blob;
+    KeyCharacteristics characteristics;
+    std::vector<Certificate> cert;
+    status = device->generateKey(kps, &blob, &characteristics, &cert);
+    ASSERT_TRUE(!status.isOk());
+    ASSERT_EQ(status.getServiceSpecificError(),
+              static_cast<int32_t>(ErrorCode::TOO_MANY_OPERATIONS));
+    // But generating a certificate with signCert does not use a slot.
+    kps.pop_back();
+    status = device->generateKey(kps, &blob, &characteristics, &cert);
+    ASSERT_TRUE(status.isOk());
+
+    // Destructing operations should free up their slots.
+    operations.clear();
+    result = begin(device, true);
+    ASSERT_TRUE(std::holds_alternative<BeginResult>(result));
+}