diff --git a/keystore2/src/km_compat/Android.bp b/keystore2/src/km_compat/Android.bp
index fa214a7..4127aa0 100644
--- a/keystore2/src/km_compat/Android.bp
+++ b/keystore2/src/km_compat/Android.bp
@@ -67,6 +67,7 @@
         "libcrypto",
         "libhidlbase",
         "libkeymaster4_1support",
+        "libkeymint",
         "libkeymint_support",
         "libkeystore2_crypto",
         "libutils",
diff --git a/keystore2/src/km_compat/km_compat.cpp b/keystore2/src/km_compat/km_compat.cpp
index 812f513..f376e97 100644
--- a/keystore2/src/km_compat/km_compat.cpp
+++ b/keystore2/src/km_compat/km_compat.cpp
@@ -17,9 +17,11 @@
 #include "km_compat.h"
 
 #include "km_compat_type_conversion.h"
+#include <AndroidKeyMintDevice.h>
 #include <aidl/android/hardware/security/keymint/Algorithm.h>
 #include <aidl/android/hardware/security/keymint/Digest.h>
 #include <aidl/android/hardware/security/keymint/ErrorCode.h>
+#include <aidl/android/hardware/security/keymint/KeyParameterValue.h>
 #include <aidl/android/hardware/security/keymint/PaddingMode.h>
 #include <aidl/android/system/keystore2/ResponseCode.h>
 #include <android-base/logging.h>
@@ -35,7 +37,9 @@
 #include "certificate_utils.h"
 
 using ::aidl::android::hardware::security::keymint::Algorithm;
+using ::aidl::android::hardware::security::keymint::CreateKeyMintDevice;
 using ::aidl::android::hardware::security::keymint::Digest;
+using ::aidl::android::hardware::security::keymint::KeyParameterValue;
 using ::aidl::android::hardware::security::keymint::PaddingMode;
 using ::aidl::android::hardware::security::keymint::Tag;
 using ::aidl::android::system::keystore2::ResponseCode;
@@ -134,6 +138,77 @@
     }
 }
 
+// Size of prefix for blobs, see keyBlobPrefix().
+//
+const size_t kKeyBlobPrefixSize = 8;
+
+// Magic used in blob prefix, see keyBlobPrefix().
+//
+const uint8_t kKeyBlobMagic[7] = {'p', 'K', 'M', 'b', 'l', 'o', 'b'};
+
+// Prefixes a keyblob returned by e.g. generateKey() with information on whether it
+// originated from the real underlying KeyMaster HAL or from soft-KeyMint.
+//
+// When dealing with a keyblob, use prefixedKeyBlobRemovePrefix() to remove the
+// prefix and prefixedKeyBlobIsSoftKeyMint() to determine its origin.
+//
+// Note how the prefix itself has a magic marker ("pKMblob") which can be used
+// to identify if a blob has a prefix at all (it's assumed that any valid blob
+// from KeyMint or KeyMaster HALs never starts with the magic). This is needed
+// because blobs persisted to disk prior to using this code will not have the
+// prefix and in that case we want prefixedKeyBlobRemovePrefix() to still work.
+//
+std::vector<uint8_t> keyBlobPrefix(const std::vector<uint8_t>& blob, bool isSoftKeyMint) {
+    std::vector<uint8_t> result;
+    result.reserve(blob.size() + kKeyBlobPrefixSize);
+    result.insert(result.begin(), kKeyBlobMagic, kKeyBlobMagic + sizeof kKeyBlobMagic);
+    result.push_back(isSoftKeyMint ? 1 : 0);
+    std::copy(blob.begin(), blob.end(), std::back_inserter(result));
+    return result;
+}
+
+// Helper for prefixedKeyBlobRemovePrefix() and prefixedKeyBlobIsSoftKeyMint().
+//
+// First bool is whether there's a valid prefix. If there is, the second bool is
+// the |isSoftKeyMint| value of the prefix
+//
+std::pair<bool, bool> prefixedKeyBlobParsePrefix(const std::vector<uint8_t>& prefixedBlob) {
+    // Having a unprefixed blob is not that uncommon, for example all devices
+    // upgrading to keystore2 (so e.g. upgrading to Android 12) will have
+    // unprefixed blobs. So don't spew warnings/errors in this case...
+    if (prefixedBlob.size() < kKeyBlobPrefixSize) {
+        return std::make_pair(false, false);
+    }
+    if (std::memcmp(prefixedBlob.data(), kKeyBlobMagic, sizeof kKeyBlobMagic) != 0) {
+        return std::make_pair(false, false);
+    }
+    if (prefixedBlob[kKeyBlobPrefixSize - 1] != 0 && prefixedBlob[kKeyBlobPrefixSize - 1] != 1) {
+        return std::make_pair(false, false);
+    }
+    bool isSoftKeyMint = (prefixedBlob[kKeyBlobPrefixSize - 1] == 1);
+    return std::make_pair(true, isSoftKeyMint);
+}
+
+// Returns the prefix from a blob. If there's no prefix, returns the passed-in blob.
+//
+std::vector<uint8_t> prefixedKeyBlobRemovePrefix(const std::vector<uint8_t>& prefixedBlob) {
+    auto parsed = prefixedKeyBlobParsePrefix(prefixedBlob);
+    if (!parsed.first) {
+        // Not actually prefixed, blob was probably persisted to disk prior to the
+        // prefixing code being introduced.
+        return prefixedBlob;
+    }
+    return std::vector<uint8_t>(prefixedBlob.begin() + kKeyBlobPrefixSize, prefixedBlob.end());
+}
+
+// Returns true if the blob's origin is soft-KeyMint, false otherwise or if there
+// is no prefix on the passed-in blob.
+//
+bool prefixedKeyBlobIsSoftKeyMint(const std::vector<uint8_t>& prefixedBlob) {
+    auto parsed = prefixedKeyBlobParsePrefix(prefixedBlob);
+    return parsed.second;
+}
+
 /*
  * Returns true if the parameter is not understood by KM 4.1 and older but can be enforced by
  * Keystore. These parameters need to be included in the returned KeyCharacteristics, but will not
@@ -333,17 +408,39 @@
     return convertErrorCode(result);
 }
 
-ScopedAStatus
-KeyMintDevice::generateKey(const std::vector<KeyParameter>& inKeyParams,
-                           const std::optional<AttestationKey>& /* in_attestationKey */,
-                           KeyCreationResult* out_creationResult) {
+ScopedAStatus KeyMintDevice::generateKey(const std::vector<KeyParameter>& inKeyParams,
+                                         const std::optional<AttestationKey>& in_attestationKey,
+                                         KeyCreationResult* out_creationResult) {
+
+    // Since KeyMaster doesn't support ECDH, route all key creation requests to
+    // soft-KeyMint if and only an ECDH key is requested.
+    //
+    // For this to work we'll need to also route begin() and deleteKey() calls to
+    // soft-KM. In order to do that, we'll prefix all keyblobs with whether it was
+    // created by the real underlying KeyMaster HAL or whether it was created by
+    // soft-KeyMint.
+    //
+    // See keyBlobPrefix() for more discussion.
+    //
+    for (const auto& keyParam : inKeyParams) {
+        if (keyParam.tag == Tag::PURPOSE &&
+            keyParam.value.get<KeyParameterValue::Tag::keyPurpose>() == KeyPurpose::AGREE_KEY) {
+            auto ret =
+                softKeyMintDevice_->generateKey(inKeyParams, in_attestationKey, out_creationResult);
+            if (ret.isOk()) {
+                out_creationResult->keyBlob = keyBlobPrefix(out_creationResult->keyBlob, true);
+            }
+            return ret;
+        }
+    }
+
     auto legacyKeyGenParams = convertKeyParametersToLegacy(extractGenerationParams(inKeyParams));
     KMV1::ErrorCode errorCode;
     auto result = mDevice->generateKey(
         legacyKeyGenParams, [&](V4_0_ErrorCode error, const hidl_vec<uint8_t>& keyBlob,
                                 const V4_0_KeyCharacteristics& keyCharacteristics) {
             errorCode = convert(error);
-            out_creationResult->keyBlob = keyBlob;
+            out_creationResult->keyBlob = keyBlobPrefix(keyBlob, false);
             out_creationResult->keyCharacteristics =
                 processLegacyCharacteristics(securityLevel_, inKeyParams, keyCharacteristics);
         });
@@ -379,7 +476,8 @@
                                      [&](V4_0_ErrorCode error, const hidl_vec<uint8_t>& keyBlob,
                                          const V4_0_KeyCharacteristics& keyCharacteristics) {
                                          errorCode = convert(error);
-                                         out_creationResult->keyBlob = keyBlob;
+                                         out_creationResult->keyBlob =
+                                             keyBlobPrefix(keyBlob, false);
                                          out_creationResult->keyCharacteristics =
                                              processLegacyCharacteristics(
                                                  securityLevel_, inKeyParams, keyCharacteristics);
@@ -419,7 +517,7 @@
         [&](V4_0_ErrorCode error, const hidl_vec<uint8_t>& keyBlob,
             const V4_0_KeyCharacteristics& keyCharacteristics) {
             errorCode = convert(error);
-            out_creationResult->keyBlob = keyBlob;
+            out_creationResult->keyBlob = keyBlobPrefix(keyBlob, false);
             out_creationResult->keyCharacteristics =
                 processLegacyCharacteristics(securityLevel_, {}, keyCharacteristics);
         });
@@ -448,8 +546,13 @@
     return convertErrorCode(errorCode);
 }
 
-ScopedAStatus KeyMintDevice::deleteKey(const std::vector<uint8_t>& in_inKeyBlob) {
-    auto result = mDevice->deleteKey(in_inKeyBlob);
+ScopedAStatus KeyMintDevice::deleteKey(const std::vector<uint8_t>& prefixedKeyBlob) {
+    const std::vector<uint8_t>& keyBlob = prefixedKeyBlobRemovePrefix(prefixedKeyBlob);
+    if (prefixedKeyBlobIsSoftKeyMint(prefixedKeyBlob)) {
+        return softKeyMintDevice_->deleteKey(prefixedKeyBlob);
+    }
+
+    auto result = mDevice->deleteKey(keyBlob);
     if (!result.isOk()) {
         LOG(ERROR) << __func__ << " transaction failed. " << result.description();
         return convertErrorCode(KMV1::ErrorCode::UNKNOWN_ERROR);
@@ -473,13 +576,20 @@
 }
 
 ScopedAStatus KeyMintDevice::begin(KeyPurpose in_inPurpose,
-                                   const std::vector<uint8_t>& in_inKeyBlob,
+                                   const std::vector<uint8_t>& prefixedKeyBlob,
                                    const std::vector<KeyParameter>& in_inParams,
                                    const HardwareAuthToken& in_inAuthToken,
                                    BeginResult* _aidl_return) {
     if (!mOperationSlots.claimSlot()) {
         return convertErrorCode(V4_0_ErrorCode::TOO_MANY_OPERATIONS);
     }
+
+    const std::vector<uint8_t>& in_inKeyBlob = prefixedKeyBlobRemovePrefix(prefixedKeyBlob);
+    if (prefixedKeyBlobIsSoftKeyMint(prefixedKeyBlob)) {
+        return softKeyMintDevice_->begin(in_inPurpose, in_inKeyBlob, in_inParams, in_inAuthToken,
+                                         _aidl_return);
+    }
+
     auto legacyPurpose =
         static_cast<::android::hardware::keymaster::V4_0::KeyPurpose>(in_inPurpose);
     auto legacyParams = convertKeyParametersToLegacy(in_inParams);
@@ -839,7 +949,8 @@
 
 std::optional<KMV1::ErrorCode>
 KeyMintDevice::signCertificate(const std::vector<KeyParameter>& keyParams,
-                               const std::vector<uint8_t>& keyBlob, X509* cert) {
+                               const std::vector<uint8_t>& prefixedKeyBlob, X509* cert) {
+
     auto algorithm = getParam(keyParams, KMV1::TAG_ALGORITHM);
     auto algoOrError = getKeystoreAlgorithm(*algorithm);
     if (std::holds_alternative<KMV1::ErrorCode>(algoOrError)) {
@@ -874,7 +985,8 @@
                 kps.push_back(KMV1::makeKeyParameter(KMV1::TAG_PADDING, origPadding));
             }
             BeginResult beginResult;
-            auto error = begin(KeyPurpose::SIGN, keyBlob, kps, HardwareAuthToken(), &beginResult);
+            auto error =
+                begin(KeyPurpose::SIGN, prefixedKeyBlob, kps, HardwareAuthToken(), &beginResult);
             if (!error.isOk()) {
                 errorCode = toErrorCode(error);
                 return std::vector<uint8_t>();
@@ -911,7 +1023,9 @@
 
 std::variant<std::vector<Certificate>, KMV1::ErrorCode>
 KeyMintDevice::getCertificate(const std::vector<KeyParameter>& keyParams,
-                              const std::vector<uint8_t>& keyBlob) {
+                              const std::vector<uint8_t>& prefixedKeyBlob) {
+    const std::vector<uint8_t>& keyBlob = prefixedKeyBlobRemovePrefix(prefixedKeyBlob);
+
     // There are no certificates for symmetric keys.
     auto algorithm = getParam(keyParams, KMV1::TAG_ALGORITHM);
     if (!algorithm) {
@@ -1009,14 +1123,14 @@
 // 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;
+namespace keymasterNs = ::android::hardware::keymaster::V4_1;
 
-using keymaster::SecurityLevel;
+using keymasterNs::SecurityLevel;
 
 // Copied from system/security/keystore/KeyStore.h.
 
 using ::android::sp;
-using keymaster::support::Keymaster;
+using keymasterNs::support::Keymaster;
 
 template <typename T, size_t count> class Devices : public std::array<T, count> {
   public:
@@ -1041,8 +1155,8 @@
 // Copied from system/security/keystore/keystore_main.cpp.
 
 using ::android::hardware::hidl_string;
-using keymaster::support::Keymaster3;
-using keymaster::support::Keymaster4;
+using keymasterNs::support::Keymaster3;
+using keymasterNs::support::Keymaster4;
 
 template <typename Wrapper>
 KeymasterDevices enumerateKeymasterDevices(IServiceManager* serviceManager) {
@@ -1124,6 +1238,8 @@
     } else {
         mOperationSlots.setNumFreeSlots(15);
     }
+
+    softKeyMintDevice_.reset(CreateKeyMintDevice(KeyMintSecurityLevel::SOFTWARE));
 }
 
 sp<Keymaster> getDevice(KeyMintSecurityLevel securityLevel) {
diff --git a/keystore2/src/km_compat/km_compat.h b/keystore2/src/km_compat/km_compat.h
index 57a7bbd..6edb8af 100644
--- a/keystore2/src/km_compat/km_compat.h
+++ b/keystore2/src/km_compat/km_compat.h
@@ -128,6 +128,9 @@
     std::optional<KMV1_ErrorCode> signCertificate(const std::vector<KeyParameter>& keyParams,
                                                   const std::vector<uint8_t>& keyBlob, X509* cert);
     KeyMintSecurityLevel securityLevel_;
+
+    // Software-based KeyMint device used to implement ECDH.
+    std::shared_ptr<IKeyMintDevice> softKeyMintDevice_;
 };
 
 class KeyMintOperation : public aidl::android::hardware::security::keymint::BnKeyMintOperation {