Rethink the EVP_PKEY cache of provider side keys

The role of this cache was two-fold:

1.  It was a cache of key copies exported to providers with which an
    operation was initiated.
2.  If the EVP_PKEY didn't have a legacy key, item 0 of the cache was
    the corresponding provider side origin, while the rest was the
    actual cache.

This dual role for item 0 made the code a bit confusing, so we now
make a separate keymgmt / keydata pair outside of that cache, which is
the provider side "origin" key.

A hard rule is that an EVP_PKEY cannot hold a legacy "origin" and a
provider side "origin" at the same time.

Reviewed-by: Shane Lontis <shane.lontis@oracle.com>
(Merged from https://github.com/openssl/openssl/pull/11148)

12 files changed, 238 insertions, 205 deletions

diff --git a/crypto/asn1/i2d_pr.c b/crypto/asn1/i2d_pr.c
index dd2a82da74..73b4461306 100644
--- a/crypto/asn1/i2d_pr.c
+++ b/crypto/asn1/i2d_pr.c
@@ -30,7 +30,7 @@ int i2d_PrivateKey(const EVP_PKEY *a, unsigned char **pp)
         }
         return ret;
     }
-    if (a->pkeys[0].keymgmt != NULL) {
+    if (a->keymgmt != NULL) {
         const char *serprop = OSSL_SERIALIZER_PrivateKey_TO_DER_PQ;
         OSSL_SERIALIZER_CTX *ctx =
             OSSL_SERIALIZER_CTX_new_by_EVP_PKEY(a, serprop);
diff --git a/crypto/evp/exchange.c b/crypto/evp/exchange.c
index 142a820651..ec5ba03f09 100644
--- a/crypto/evp/exchange.c
+++ b/crypto/evp/exchange.c
@@ -200,10 +200,13 @@ int EVP_PKEY_derive_init(EVP_PKEY_CTX *ctx)
     if (ctx->engine != NULL || ctx->keytype == NULL)
         goto legacy;
 
-    /* Ensure that the key is provided.  If not, go legacy */
+    /*
+     * Ensure that the key is provided, either natively, or as a cached export.
+     *  If not, go legacy
+     */
     tmp_keymgmt = ctx->keymgmt;
-    provkey = evp_pkey_make_provided(ctx->pkey, ctx->libctx,
-                                     &tmp_keymgmt, ctx->propquery);
+    provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
+                                          &tmp_keymgmt, ctx->propquery);
     if (provkey == NULL)
         goto legacy;
     if (!EVP_KEYMGMT_up_ref(tmp_keymgmt)) {
@@ -309,8 +312,8 @@ int EVP_PKEY_derive_set_peer(EVP_PKEY_CTX *ctx, EVP_PKEY *peer)
         return -2;
     }
 
-    provkey = evp_pkey_make_provided(peer, ctx->libctx, &ctx->keymgmt,
-                                     ctx->propquery);
+    provkey = evp_pkey_export_to_provider(peer, ctx->libctx, &ctx->keymgmt,
+                                          ctx->propquery);
     /*
      * If making the key provided wasn't possible, legacy may be able to pick
      * it up
diff --git a/crypto/evp/keymgmt_lib.c b/crypto/evp/keymgmt_lib.c
index cb30405166..a88d65dc5e 100644
--- a/crypto/evp/keymgmt_lib.c
+++ b/crypto/evp/keymgmt_lib.c
@@ -47,31 +47,48 @@ void *evp_keymgmt_util_export_to_provider(EVP_PKEY *pk, EVP_KEYMGMT *keymgmt)
 {
     void *keydata = NULL;
     struct import_data_st import_data;
-    size_t i, j;
+    size_t i = 0;
 
     /* Export to where? */
     if (keymgmt == NULL)
         return NULL;
 
     /* If we have an unassigned key, give up */
-    if (pk->pkeys[0].keymgmt == NULL)
+    if (pk->keymgmt == NULL)
         return NULL;
 
+    /* If |keymgmt| matches the "origin" |keymgmt|, no more to do */
+    if (pk->keymgmt == keymgmt)
+        return pk->keydata;
+
+    /* If this key is already exported to |keymgmt|, no more to do */
+    i = evp_keymgmt_util_find_operation_cache_index(pk, keymgmt);
+    if (i < OSSL_NELEM(pk->operation_cache)
+        && pk->operation_cache[i].keymgmt != NULL)
+        return pk->operation_cache[i].keydata;
+
+    /* If the "origin" |keymgmt| doesn't support exporting, give up */
     /*
-     * See if we have exported to this provider already.
-     * If we have, return immediately.
+     * TODO(3.0) consider an evp_keymgmt_export() return value that indicates
+     * that the method is unsupported.
      */
-    i = evp_keymgmt_util_find_pkey_cache_index(pk, keymgmt);
+    if (pk->keymgmt->export == NULL)
+        return NULL;
 
-    /* If we're already exported to the given keymgmt, no more to do */
-    if (keymgmt == pk->pkeys[i].keymgmt)
-        return pk->pkeys[i].keydata;
+    /* Check that we have found an empty slot in the export cache */
+    /*
+     * TODO(3.0) Right now, we assume we have ample space.  We will have to
+     * think about a cache aging scheme, though, if |i| indexes outside the
+     * array.
+     */
+    if (!ossl_assert(i < OSSL_NELEM(pk->operation_cache)))
+        return NULL;
 
     /*
      * Make sure that the type of the keymgmt to export to matches the type
-     * of already cached keymgmt
+     * of the "origin"
      */
-    if (!ossl_assert(match_type(pk->pkeys[0].keymgmt, keymgmt)))
+    if (!ossl_assert(match_type(pk->keymgmt, keymgmt)))
         return NULL;
 
     /* Create space to import data into */
@@ -89,109 +106,90 @@ void *evp_keymgmt_util_export_to_provider(EVP_PKEY *pk, EVP_KEYMGMT *keymgmt)
     import_data.keymgmt = keymgmt;
     import_data.selection = OSSL_KEYMGMT_SELECT_ALL;
 
-    for (j = 0; j < i && pk->pkeys[j].keymgmt != NULL; j++) {
-        EVP_KEYMGMT *exp_keymgmt = pk->pkeys[j].keymgmt;
-        void *exp_keydata = pk->pkeys[j].keydata;
-
-        /*
-         * TODO(3.0) consider an evp_keymgmt_export() return value that
-         * indicates that the method is unsupported.
-         */
-        if (exp_keymgmt->export == NULL)
-            continue;
-
-        /*
-         * The export function calls the callback (try_import), which does
-         * the import for us.  If successful, we're done.
-         */
-        if (evp_keymgmt_export(exp_keymgmt, exp_keydata,
-                               OSSL_KEYMGMT_SELECT_ALL,
-                               &try_import, &import_data))
-            break;
-
+    /*
+     * The export function calls the callback (try_import), which does the
+     * import for us.  If successful, we're done.
+     */
+    if (!evp_keymgmt_export(pk->keymgmt, pk->keydata, OSSL_KEYMGMT_SELECT_ALL,
+                            &try_import, &import_data)) {
         /* If there was an error, bail out */
         evp_keymgmt_freedata(keymgmt, keydata);
         return NULL;
     }
 
-    /*
-     * TODO(3.0) Right now, we assume we have ample space.  We will
-     * have to think about a cache aging scheme, though, if |i| indexes
-     * outside the array.
-     */
-    if (!ossl_assert(i < OSSL_NELEM(pk->pkeys)))
+    /* Add the new export to the operation cache */
+    if (!evp_keymgmt_util_cache_keydata(pk, i, keymgmt, keydata)) {
+        evp_keymgmt_freedata(keymgmt, keydata);
         return NULL;
-
-    evp_keymgmt_util_cache_pkey(pk, i, keymgmt, keydata);
+    }
 
     return keydata;
 }
 
-void evp_keymgmt_util_clear_pkey_cache(EVP_PKEY *pk)
+void evp_keymgmt_util_clear_operation_cache(EVP_PKEY *pk)
 {
-    size_t i, end = OSSL_NELEM(pk->pkeys);
+    size_t i, end = OSSL_NELEM(pk->operation_cache);
 
     if (pk != NULL) {
-        for (i = 0; i < end && pk->pkeys[i].keymgmt != NULL; i++) {
-            EVP_KEYMGMT *keymgmt = pk->pkeys[i].keymgmt;
-            void *keydata = pk->pkeys[i].keydata;
+        for (i = 0; i < end && pk->operation_cache[i].keymgmt != NULL; i++) {
+            EVP_KEYMGMT *keymgmt = pk->operation_cache[i].keymgmt;
+            void *keydata = pk->operation_cache[i].keydata;
 
-            pk->pkeys[i].keymgmt = NULL;
-            pk->pkeys[i].keydata = NULL;
+            pk->operation_cache[i].keymgmt = NULL;
+            pk->operation_cache[i].keydata = NULL;
             evp_keymgmt_freedata(keymgmt, keydata);
             EVP_KEYMGMT_free(keymgmt);
         }
-
-        pk->cache.size = 0;
-        pk->cache.bits = 0;
-        pk->cache.security_bits = 0;
     }
 }
 
-size_t evp_keymgmt_util_find_pkey_cache_index(EVP_PKEY *pk,
-                                              EVP_KEYMGMT *keymgmt)
+size_t evp_keymgmt_util_find_operation_cache_index(EVP_PKEY *pk,
+                                                   EVP_KEYMGMT *keymgmt)
 {
-    size_t i, end = OSSL_NELEM(pk->pkeys);
+    size_t i, end = OSSL_NELEM(pk->operation_cache);
 
-    for (i = 0; i < end && pk->pkeys[i].keymgmt != NULL; i++) {
-        if (keymgmt == pk->pkeys[i].keymgmt)
+    for (i = 0; i < end && pk->operation_cache[i].keymgmt != NULL; i++) {
+        if (keymgmt == pk->operation_cache[i].keymgmt)
             break;
     }
 
     return i;
 }
 
-void evp_keymgmt_util_cache_pkey(EVP_PKEY *pk, size_t index,
-                                 EVP_KEYMGMT *keymgmt, void *keydata)
+int evp_keymgmt_util_cache_keydata(EVP_PKEY *pk, size_t index,
+                                   EVP_KEYMGMT *keymgmt, void *keydata)
 {
     if (keydata != NULL) {
-        EVP_KEYMGMT_up_ref(keymgmt);
-        pk->pkeys[index].keydata = keydata;
-        pk->pkeys[index].keymgmt = keymgmt;
-
-        /*
-         * Cache information about the key object.  Only needed for the
-         * "original" provider side key.
-         *
-         * This services functions like EVP_PKEY_size, EVP_PKEY_bits, etc
-         */
-        if (index == 0) {
-            int bits = 0;
-            int security_bits = 0;
-            int size = 0;
-            OSSL_PARAM params[4];
-
-            params[0] = OSSL_PARAM_construct_int(OSSL_PKEY_PARAM_BITS, &bits);
-            params[1] = OSSL_PARAM_construct_int(OSSL_PKEY_PARAM_SECURITY_BITS,
-                                                 &security_bits);
-            params[2] = OSSL_PARAM_construct_int(OSSL_PKEY_PARAM_MAX_SIZE,
-                                                 &size);
-            params[3] = OSSL_PARAM_construct_end();
-            if (evp_keymgmt_get_params(keymgmt, keydata, params)) {
-                pk->cache.size = size;
-                pk->cache.bits = bits;
-                pk->cache.security_bits = security_bits;
-            }
+        if (!EVP_KEYMGMT_up_ref(keymgmt))
+            return 0;
+        pk->operation_cache[index].keydata = keydata;
+        pk->operation_cache[index].keymgmt = keymgmt;
+    }
+    return 1;
+}
+
+void evp_keymgmt_util_cache_keyinfo(EVP_PKEY *pk)
+{
+    /*
+     * Cache information about the provider "origin" key.
+     *
+     * This services functions like EVP_PKEY_size, EVP_PKEY_bits, etc
+     */
+    if (pk->keymgmt != NULL) {
+        int bits = 0;
+        int security_bits = 0;
+        int size = 0;
+        OSSL_PARAM params[4];
+
+        params[0] = OSSL_PARAM_construct_int(OSSL_PKEY_PARAM_BITS, &bits);
+        params[1] = OSSL_PARAM_construct_int(OSSL_PKEY_PARAM_SECURITY_BITS,
+                                             &security_bits);
+        params[2] = OSSL_PARAM_construct_int(OSSL_PKEY_PARAM_MAX_SIZE, &size);
+        params[3] = OSSL_PARAM_construct_end();
+        if (evp_keymgmt_get_params(pk->keymgmt, pk->keydata, params)) {
+            pk->cache.size = size;
+            pk->cache.bits = bits;
+            pk->cache.security_bits = security_bits;
         }
     }
 }
@@ -202,14 +200,16 @@ void *evp_keymgmt_util_fromdata(EVP_PKEY *target, EVP_KEYMGMT *keymgmt,
     void *keydata = evp_keymgmt_newdata(keymgmt);
 
     if (keydata != NULL) {
-        if (!evp_keymgmt_import(keymgmt, keydata, selection, params)) {
+        if (!evp_keymgmt_import(keymgmt, keydata, selection, params)
+            || !EVP_KEYMGMT_up_ref(keymgmt)) {
             evp_keymgmt_freedata(keymgmt, keydata);
             return NULL;
         }
 
-
-        evp_keymgmt_util_clear_pkey_cache(target);
-        evp_keymgmt_util_cache_pkey(target, 0, keymgmt, keydata);
+        evp_keymgmt_util_clear_operation_cache(target);
+        target->keymgmt = keymgmt;
+        target->keydata = keydata;
+        evp_keymgmt_util_cache_keyinfo(target);
     }
 
     return keydata;
diff --git a/crypto/evp/m_sigver.c b/crypto/evp/m_sigver.c
index 1ea5669c02..b6c66722ec 100644
--- a/crypto/evp/m_sigver.c
+++ b/crypto/evp/m_sigver.c
@@ -64,10 +64,13 @@ static int do_sigver_init(EVP_MD_CTX *ctx, EVP_PKEY_CTX **pctx,
     if (locpctx->keytype == NULL)
         goto legacy;
 
-    /* Ensure that the key is provided.  If not, go legacy */
+    /*
+     * Ensure that the key is provided, either natively, or as a cached export.
+     *  If not, go legacy
+     */
     tmp_keymgmt = locpctx->keymgmt;
-    provkey = evp_pkey_make_provided(locpctx->pkey, locpctx->libctx,
-                                     &tmp_keymgmt, locpctx->propquery);
+    provkey = evp_pkey_export_to_provider(locpctx->pkey, locpctx->libctx,
+                                          &tmp_keymgmt, locpctx->propquery);
     if (provkey == NULL)
         goto legacy;
     if (!EVP_KEYMGMT_up_ref(tmp_keymgmt)) {
diff --git a/crypto/evp/p_lib.c b/crypto/evp/p_lib.c
index 2ffddf5d0a..574527aa5c 100644
--- a/crypto/evp/p_lib.c
+++ b/crypto/evp/p_lib.c
@@ -713,7 +713,7 @@ int EVP_PKEY_print_params(BIO *out, const EVP_PKEY *pkey,
 static int legacy_asn1_ctrl_to_param(EVP_PKEY *pkey, int op,
                                      int arg1, void *arg2)
 {
-    if (pkey->pkeys[0].keymgmt == NULL)
+    if (pkey->keymgmt == NULL)
         return 0;
     switch (op) {
     case ASN1_PKEY_CTRL_DEFAULT_MD_NID:
@@ -768,9 +768,7 @@ int EVP_PKEY_get_default_digest_name(EVP_PKEY *pkey,
                                              mdmandatory,
                                              sizeof(mdmandatory));
         params[2] = OSSL_PARAM_construct_end();
-        if (!evp_keymgmt_get_params(pkey->pkeys[0].keymgmt,
-                                    pkey->pkeys[0].keydata,
-                                    params))
+        if (!evp_keymgmt_get_params(pkey->keymgmt, pkey->keydata, params))
             return 0;
         if (mdmandatory[0] != '\0') {
             OPENSSL_strlcpy(mdname, mdmandatory, mdname_sz);
@@ -872,12 +870,18 @@ static void evp_pkey_free_it(EVP_PKEY *x)
 {
     /* internal function; x is never NULL */
 
-    evp_keymgmt_util_clear_pkey_cache(x);
+    evp_keymgmt_util_clear_operation_cache(x);
 
     if (x->ameth && x->ameth->pkey_free) {
         x->ameth->pkey_free(x);
         x->pkey.ptr = NULL;
     }
+    if (x->keymgmt != NULL) {
+        evp_keymgmt_freedata(x->keymgmt, x->keydata);
+        EVP_KEYMGMT_free(x->keymgmt);
+        x->keymgmt = NULL;
+        x->keydata = NULL;
+    }
 #if !defined(OPENSSL_NO_ENGINE) && !defined(FIPS_MODE)
     ENGINE_finish(x->engine);
     x->engine = NULL;
@@ -917,8 +921,9 @@ int EVP_PKEY_size(const EVP_PKEY *pkey)
     return 0;
 }
 
-void *evp_pkey_make_provided(EVP_PKEY *pk, OPENSSL_CTX *libctx,
-                             EVP_KEYMGMT **keymgmt, const char *propquery)
+void *evp_pkey_export_to_provider(EVP_PKEY *pk, OPENSSL_CTX *libctx,
+                                  EVP_KEYMGMT **keymgmt,
+                                  const char *propquery)
 {
     EVP_KEYMGMT *allocated_keymgmt = NULL;
     EVP_KEYMGMT *tmp_keymgmt = NULL;
@@ -927,59 +932,22 @@ void *evp_pkey_make_provided(EVP_PKEY *pk, OPENSSL_CTX *libctx,
     if (pk == NULL)
         return NULL;
 
-    if (keymgmt != NULL) {
-        tmp_keymgmt = *keymgmt;
-        *keymgmt = NULL;
-    }
-
 #ifndef FIPS_MODE
-    /*
-     * If there is an underlying legacy key and it has changed, invalidate
-     * the cache of provider keys.
-     */
     if (pk->pkey.ptr != NULL) {
-        EVP_KEYMGMT *legacy_keymgmt = NULL;
-
-        /*
-         * If there is no dirty counter, this key can't be used with
-         * providers.
-         */
-        if (pk->ameth->dirty_cnt == NULL)
-            goto end;
-
-        /*
-         * If no keymgmt was given by the caller, we set it to the first
-         * that's cached, to become the keymgmt to re-export to if needed,
-         * or to have a token keymgmt to return on success.  Further checks
-         * are done further down.
-         *
-         * We need to carefully save the pointer somewhere other than in
-         * tmp_keymgmt, so the EVP_KEYMGMT_up_ref() below doesn't mistakenly
-         * increment the reference counter of a keymgmt given by the caller.
-         */
-        if (tmp_keymgmt == NULL)
-            legacy_keymgmt = pk->pkeys[0].keymgmt;
-
-        /*
-         * If the dirty counter changed since last time, we make sure to
-         * hold on to the keymgmt we just got (if we got one), then clear
-         * the cache.
-         */
-        if (pk->ameth->dirty_cnt(pk) != pk->dirty_cnt_copy) {
-            if (legacy_keymgmt != NULL && !EVP_KEYMGMT_up_ref(legacy_keymgmt))
-                goto end;
-            evp_keymgmt_util_clear_pkey_cache(pk);
-        }
-
         /*
-         * |legacy_keymgmt| was only given a value if |tmp_keymgmt| is
-         * NULL.
+         * If the legacy key doesn't have an dirty counter or export function,
+         * give up
          */
-        if (legacy_keymgmt != NULL)
-            tmp_keymgmt = legacy_keymgmt;
+        if (pk->ameth->dirty_cnt == NULL || pk->ameth->export_to == NULL)
+            return NULL;
     }
 #endif
 
+    if (keymgmt != NULL) {
+        tmp_keymgmt = *keymgmt;
+        *keymgmt = NULL;
+    }
+
     /* If no keymgmt was given or found, get a default keymgmt */
     if (tmp_keymgmt == NULL) {
         EVP_PKEY_CTX *ctx = EVP_PKEY_CTX_new_from_pkey(libctx, pk, propquery);
@@ -990,35 +958,41 @@ void *evp_pkey_make_provided(EVP_PKEY *pk, OPENSSL_CTX *libctx,
         EVP_PKEY_CTX_free(ctx);
     }
 
+    /* If there's still no keymgmt to be had, give up */
     if (tmp_keymgmt == NULL)
         goto end;
 
 #ifndef FIPS_MODE
     if (pk->pkey.ptr != NULL) {
-        size_t i;
+        size_t i = 0;
 
         /*
-         * Find our keymgmt in the cache.  If it's present, it means that
-         * export has already been done.  We take token copies of the
-         * cached pointers, to have token success values to return.
-         *
-         * TODO(3.0) Right now, we assume we have ample space.  We will
-         * have to think about a cache aging scheme, though, if |i| indexes
-         * outside the array.
+         * If the legacy "origin" hasn't changed since last time, we try
+         * to find our keymgmt in the operation cache.  If it has changed,
+         * |i| remains zero, and we will clear the cache further down.
          */
-        i = evp_keymgmt_util_find_pkey_cache_index(pk, tmp_keymgmt);
-        if (!ossl_assert(i < OSSL_NELEM(pk->pkeys)))
-            goto end;
-        if (pk->pkeys[i].keymgmt != NULL) {
-            keydata = pk->pkeys[i].keydata;
-            goto end;
+        if (pk->ameth->dirty_cnt(pk) == pk->dirty_cnt_copy) {
+            i = evp_keymgmt_util_find_operation_cache_index(pk, tmp_keymgmt);
+
+            /*
+             * If |tmp_keymgmt| is present in the operation cache, it means
+             * that export doesn't need to be redone.  In that case, we take
+             * token copies of the cached pointers, to have token success
+             * values to return.
+             */
+            if (i < OSSL_NELEM(pk->operation_cache)
+                && pk->operation_cache[i].keymgmt != NULL) {
+                keydata = pk->operation_cache[i].keydata;
+                goto end;
+            }
         }
 
         /*
-         * If we still don't have a keymgmt at this point, or the legacy
-         * key doesn't have an export function, just bail out.
+         * TODO(3.0) Right now, we assume we have ample space.  We will have
+         * to think about a cache aging scheme, though, if |i| indexes outside
+         * the array.
          */
-        if (pk->ameth->export_to == NULL)
+        if (!ossl_assert(i < OSSL_NELEM(pk->operation_cache)))
             goto end;
 
         /* Make sure that the keymgmt key type matches the legacy NID */
@@ -1034,7 +1008,27 @@ void *evp_pkey_make_provided(EVP_PKEY *pk, OPENSSL_CTX *libctx,
             goto end;
         }
 
-        evp_keymgmt_util_cache_pkey(pk, i, tmp_keymgmt, keydata);
+        /*
+         * If the dirty counter changed since last time, then clear the
+         * operation cache.  In that case, we know that |i| is zero.  Just
+         * in case this is a re-export, we increment then decrement the
+         * keymgmt reference counter.
+         */
+        if (!EVP_KEYMGMT_up_ref(tmp_keymgmt)) { /* refcnt++ */
+            evp_keymgmt_freedata(tmp_keymgmt, keydata);
+            keydata = NULL;
+            goto end;
+        }
+        if (pk->ameth->dirty_cnt(pk) != pk->dirty_cnt_copy)
+            evp_keymgmt_util_clear_operation_cache(pk);
+        EVP_KEYMGMT_free(tmp_keymgmt); /* refcnt-- */
+
+        /* Add the new export to the operation cache */
+        if (!evp_keymgmt_util_cache_keydata(pk, i, tmp_keymgmt, keydata)) {
+            evp_keymgmt_freedata(tmp_keymgmt, keydata);
+            keydata = NULL;
+            goto end;
+        }
 
         /* Synchronize the dirty count */
         pk->dirty_cnt_copy = pk->ameth->dirty_cnt(pk);
diff --git a/crypto/evp/pmeth_check.c b/crypto/evp/pmeth_check.c
index 1186ad2b12..c02353d5ea 100644
--- a/crypto/evp/pmeth_check.c
+++ b/crypto/evp/pmeth_check.c
@@ -28,8 +28,8 @@ int EVP_PKEY_public_check(EVP_PKEY_CTX *ctx)
         return 0;
     }
 
-    keymgmt = pkey->pkeys[0].keymgmt;
-    key = pkey->pkeys[0].keydata;
+    keymgmt = pkey->keymgmt;
+    key = pkey->keydata;
 
     if (key != NULL && keymgmt != NULL)
         return evp_keymgmt_validate(keymgmt, key,
@@ -61,8 +61,8 @@ int EVP_PKEY_param_check(EVP_PKEY_CTX *ctx)
         return 0;
     }
 
-    keymgmt = pkey->pkeys[0].keymgmt;
-    key = pkey->pkeys[0].keydata;
+    keymgmt = pkey->keymgmt;
+    key = pkey->keydata;
 
     if (key != NULL && keymgmt != NULL)
         return evp_keymgmt_validate(keymgmt, key,
@@ -94,8 +94,8 @@ int EVP_PKEY_private_check(EVP_PKEY_CTX *ctx)
         return 0;
     }
 
-    keymgmt = pkey->pkeys[0].keymgmt;
-    key = pkey->pkeys[0].keydata;
+    keymgmt = pkey->keymgmt;
+    key = pkey->keydata;
 
     if (key != NULL && keymgmt != NULL)
         return evp_keymgmt_validate(keymgmt, key,
@@ -115,8 +115,8 @@ int EVP_PKEY_pairwise_check(EVP_PKEY_CTX *ctx)
         return 0;
     }
 
-    keymgmt = pkey->pkeys[0].keymgmt;
-    key = pkey->pkeys[0].keydata;
+    keymgmt = pkey->keymgmt;
+    key = pkey->keydata;
 
     if (key != NULL && keymgmt != NULL)
         return evp_keymgmt_validate(keymgmt, key, OSSL_KEYMGMT_SELECT_KEYPAIR);
@@ -135,8 +135,8 @@ int EVP_PKEY_check(EVP_PKEY_CTX *ctx)
         return 0;
     }
 
-    keymgmt = pkey->pkeys[0].keymgmt;
-    key = pkey->pkeys[0].keydata;
+    keymgmt = pkey->keymgmt;
+    key = pkey->keydata;
 
     if (key != NULL && keymgmt != NULL)
         return evp_keymgmt_validate(keymgmt, key, OSSL_KEYMGMT_SELECT_ALL);
diff --git a/crypto/evp/pmeth_fn.c b/crypto/evp/pmeth_fn.c
index 0b5af8e136..ca0790fcd6 100644
--- a/crypto/evp/pmeth_fn.c
+++ b/crypto/evp/pmeth_fn.c
@@ -41,10 +41,13 @@ static int evp_pkey_asym_cipher_init(EVP_PKEY_CTX *ctx, int operation)
     if (ctx->keytype == NULL || ctx->engine != NULL)
         goto legacy;
 
-    /* Ensure that the key is provided.  If not, go legacy */
+    /*
+     * Ensure that the key is provided, either natively, or as a cached export.
+     *  If not, go legacy
+     */
     tmp_keymgmt = ctx->keymgmt;
-    provkey = evp_pkey_make_provided(ctx->pkey, ctx->libctx,
-                                     &tmp_keymgmt, ctx->propquery);
+    provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
+                                          &tmp_keymgmt, ctx->propquery);
     if (provkey == NULL)
         goto legacy;
     if (!EVP_KEYMGMT_up_ref(tmp_keymgmt)) {
diff --git a/crypto/evp/pmeth_lib.c b/crypto/evp/pmeth_lib.c
index cb64b95bf6..c82a543857 100644
--- a/crypto/evp/pmeth_lib.c
+++ b/crypto/evp/pmeth_lib.c
@@ -160,8 +160,7 @@ static EVP_PKEY_CTX *int_ctx_new(OPENSSL_CTX *libctx,
         /* If we have an engine, something went wrong somewhere... */
         if (!ossl_assert(e == NULL))
             return NULL;
-        name = evp_first_name(pkey->pkeys[0].keymgmt->prov,
-                              pkey->pkeys[0].keymgmt->name_id);
+        name = evp_first_name(pkey->keymgmt->prov, pkey->keymgmt->name_id);
         /*
          * TODO: I wonder if the EVP_PKEY should have the name and propquery
          * that were used when building it....  /RL
diff --git a/crypto/evp/signature.c b/crypto/evp/signature.c
index ca9d91efc5..3dfd4041e7 100644
--- a/crypto/evp/signature.c
+++ b/crypto/evp/signature.c
@@ -342,10 +342,13 @@ static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation)
     if (ctx->keytype == NULL)
         goto legacy;
 
-    /* Ensure that the key is provided.  If not, go legacy */
+    /*
+     * Ensure that the key is provided, either natively, or as a cached export.
+     *  If not, go legacy
+     */
     tmp_keymgmt = ctx->keymgmt;
-    provkey = evp_pkey_make_provided(ctx->pkey, ctx->libctx,
-                                     &tmp_keymgmt, ctx->propquery);
+    provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
+                                          &tmp_keymgmt, ctx->propquery);
     if (provkey == NULL)
         goto legacy;
     if (!EVP_KEYMGMT_up_ref(tmp_keymgmt)) {
diff --git a/crypto/serializer/serializer_pkey.c b/crypto/serializer/serializer_pkey.c
index 3b0cc3ac86..1b6df1da53 100644
--- a/crypto/serializer/serializer_pkey.c
+++ b/crypto/serializer/serializer_pkey.c
@@ -267,8 +267,8 @@ static int serializer_write_cb(const OSSL_PARAM params[], void *arg)
 static int serializer_EVP_PKEY_to_bio(OSSL_SERIALIZER_CTX *ctx, BIO *out)
 {
     const EVP_PKEY *pkey = ctx->object;
-    void *keydata = pkey->pkeys[0].keydata;
-    EVP_KEYMGMT *keymgmt = pkey->pkeys[0].keymgmt;
+    void *keydata = pkey->keydata;
+    EVP_KEYMGMT *keymgmt = pkey->keymgmt;
 
     /*
      * OSSL_SERIALIZER_CTX_new() creates a context, even when the
@@ -306,7 +306,7 @@ OSSL_SERIALIZER_CTX *OSSL_SERIALIZER_CTX_new_by_EVP_PKEY(const EVP_PKEY *pkey,
 {
     OSSL_SERIALIZER_CTX *ctx = NULL;
     OSSL_SERIALIZER *ser = NULL;
-    EVP_KEYMGMT *keymgmt = pkey->pkeys[0].keymgmt;
+    EVP_KEYMGMT *keymgmt = pkey->keymgmt;
     int selection = OSSL_KEYMGMT_SELECT_ALL;
 
     if (!ossl_assert(pkey != NULL && propquery != NULL)) {
diff --git a/crypto/x509/x_pubkey.c b/crypto/x509/x_pubkey.c
index f79a57cb7d..f643170b45 100644
--- a/crypto/x509/x_pubkey.c
+++ b/crypto/x509/x_pubkey.c
@@ -91,7 +91,7 @@ int X509_PUBKEY_set(X509_PUBKEY **x, EVP_PKEY *pkey)
             X509err(X509_F_X509_PUBKEY_SET, X509_R_METHOD_NOT_SUPPORTED);
             goto error;
         }
-    } else if (pkey->pkeys[0].keymgmt != NULL) {
+    } else if (pkey->keymgmt != NULL) {
         BIO *bmem = BIO_new(BIO_s_mem());
         const char *serprop = OSSL_SERIALIZER_PUBKEY_TO_DER_PQ;
         OSSL_SERIALIZER_CTX *sctx =
@@ -270,7 +270,7 @@ int i2d_PUBKEY(const EVP_PKEY *a, unsigned char **pp)
             xpk->pkey = NULL;
         }
         X509_PUBKEY_free(xpk);
-    } else if (a->pkeys[0].keymgmt != NULL) {
+    } else if (a->keymgmt != NULL) {
         const char *serprop = OSSL_SERIALIZER_PUBKEY_TO_DER_PQ;
         OSSL_SERIALIZER_CTX *ctx =
             OSSL_SERIALIZER_CTX_new_by_EVP_PKEY(a, serprop);
diff --git a/include/crypto/evp.h b/include/crypto/evp.h
index 1724a12c7c..aed2ccf31d 100644
--- a/include/crypto/evp.h
+++ b/include/crypto/evp.h
@@ -504,6 +504,11 @@ struct evp_pkey_st {
     /* == Legacy attributes == */
     int type;
     int save_type;
+
+    /*
+     * Legacy key "origin" is composed of a pointer to an EVP_PKEY_ASN1_METHOD,
+     * a pointer to a low level key and possibly a pointer to an engine.
+     */
     const EVP_PKEY_ASN1_METHOD *ameth;
     ENGINE *engine;
     ENGINE *pmeth_engine; /* If not NULL public key ENGINE to use */
@@ -531,20 +536,41 @@ struct evp_pkey_st {
     int save_parameters;
 
     /* == Provider attributes == */
+
+    /*
+     * Provider keydata "origin" is composed of a pointer to an EVP_KEYMGMT
+     * and a pointer to the provider side key data.  This is never used at
+     * the same time as the legacy key data above.
+     */
+    EVP_KEYMGMT *keymgmt;
+    void *keydata;
+    /*
+     * If any libcrypto code does anything that may modify the keydata
+     * contents, this dirty counter must be incremented.
+     */
+    size_t dirty_cnt;
+
     /*
-     * To support transparent export/import between providers that support
-     * the methods for it, and still not having to do the export/import
-     * every time a key object is changed, we maintain a cache of imported
-     * key objects, indexed by keymgmt address.  pkeys[0] is *always* the
-     * "original" data unless we have a legacy key attached.
+     * To support transparent execution of operation in backends other
+     * than the "origin" key, we support transparent export/import to
+     * those providers, and maintain a cache of the imported keydata,
+     * so we don't need to redo the export/import every time we perform
+     * the same operation in that same provider.
+     * This requires that the "origin" backend (whether it's a legacy or a
+     * provider "origin") implements exports, and that the target provider
+     * has an EVP_KEYMGMT that implements import.
+     *
+     * The cache limit is set at 10 different providers using the same
+     * "origin".  It's probably over the top, but is preferable to too
+     * few.
      */
     struct {
         EVP_KEYMGMT *keymgmt;
         void *keydata;
-    } pkeys[10];
+    } operation_cache[10];
     /*
-     * If there is a legacy key assigned to this structure, we keep
-     * a copy of that key's dirty count.
+     * We keep a copy of that "origin"'s dirty count, so we know if the
+     * operation cache needs flushing.
      */
     size_t dirty_cnt_copy;
 
@@ -574,18 +600,20 @@ void openssl_add_all_ciphers_int(void);
 void openssl_add_all_digests_int(void);
 void evp_cleanup_int(void);
 void evp_app_cleanup_int(void);
-void *evp_pkey_make_provided(EVP_PKEY *pk, OPENSSL_CTX *libctx,
-                             EVP_KEYMGMT **keymgmt, const char *propquery);
+void *evp_pkey_export_to_provider(EVP_PKEY *pk, OPENSSL_CTX *libctx,
+                                  EVP_KEYMGMT **keymgmt,
+                                  const char *propquery);
 
 /*
  * KEYMGMT utility functions
  */
 void *evp_keymgmt_util_export_to_provider(EVP_PKEY *pk, EVP_KEYMGMT *keymgmt);
-size_t evp_keymgmt_util_find_pkey_cache_index(EVP_PKEY *pk,
-                                              EVP_KEYMGMT *keymgmt);
-void evp_keymgmt_util_clear_pkey_cache(EVP_PKEY *pk);
-void evp_keymgmt_util_cache_pkey(EVP_PKEY *pk, size_t index,
-                                 EVP_KEYMGMT *keymgmt, void *keydata);
+size_t evp_keymgmt_util_find_operation_cache_index(EVP_PKEY *pk,
+                                                   EVP_KEYMGMT *keymgmt);
+void evp_keymgmt_util_clear_operation_cache(EVP_PKEY *pk);
+int evp_keymgmt_util_cache_keydata(EVP_PKEY *pk, size_t index,
+                                   EVP_KEYMGMT *keymgmt, void *keydata);
+void evp_keymgmt_util_cache_keyinfo(EVP_PKEY *pk);
 void *evp_keymgmt_util_fromdata(EVP_PKEY *target, EVP_KEYMGMT *keymgmt,
                                 int selection, const OSSL_PARAM params[]);