EVP: Allow a fallback for operations that work with an EVP_PKEY

Functions like EVP_PKEY_sign_init() do an implicit fetch of the
operation implementation (EVP_SIGNATURE in this case), then get the
KEYMGMT from the same provider, and tries to export the key there if
necessary.

If an export of the key isn't possible (because the provider that
holds the key is an HSM and therefore can't export), we would simply
fail without looking any further.

This change modifies the behaviour a bit by trying a second fetch of
the operation implementation, but specifically from the provider of
the EVP_PKEY that's being used.  This is done with the same properties
that were used with the initial operation implementation fetch, and
should therefore be safe, allowing only what those properties allow.

Fixes #16614

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/16725)

9 files changed, 386 insertions, 124 deletions

diff --git a/crypto/evp/asymcipher.c b/crypto/evp/asymcipher.c
index e2912829e2..f158b815cf 100644
--- a/crypto/evp/asymcipher.c
+++ b/crypto/evp/asymcipher.c
@@ -24,7 +24,9 @@ static int evp_pkey_asym_cipher_init(EVP_PKEY_CTX *ctx, int operation,
     void *provkey = NULL;
     EVP_ASYM_CIPHER *cipher = NULL;
     EVP_KEYMGMT *tmp_keymgmt = NULL;
+    const OSSL_PROVIDER *tmp_prov = NULL;
     const char *supported_ciph = NULL;
+    int iter;
 
     if (ctx == NULL) {
         ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
@@ -58,34 +60,76 @@ static int evp_pkey_asym_cipher_init(EVP_PKEY_CTX *ctx, int operation,
     }
 
     /*
-     * Because we cleared out old ops, we shouldn't need to worry about
-     * checking if cipher is already there.
+     * We perform two iterations:
+     *
+     * 1.  Do the normal asym cipher fetch, using the fetching data given by
+     *     the EVP_PKEY_CTX.
+     * 2.  Do the provider specific asym cipher fetch, from the same provider
+     *     as |ctx->keymgmt|
+     *
+     * We then try to fetch the keymgmt from the same provider as the
+     * asym cipher, and try to export |ctx->pkey| to that keymgmt (when
+     * this keymgmt happens to be the same as |ctx->keymgmt|, the export
+     * is a no-op, but we call it anyway to not complicate the code even
+     * more).
+     * If the export call succeeds (returns a non-NULL provider key pointer),
+     * we're done and can perform the operation itself.  If not, we perform
+     * the second iteration, or jump to legacy.
      */
-    cipher = EVP_ASYM_CIPHER_fetch(ctx->libctx, supported_ciph,
-                                   ctx->propquery);
+    for (iter = 1, provkey = NULL; iter < 3 && provkey == NULL; iter++) {
+        EVP_KEYMGMT *tmp_keymgmt_tofree;
 
-    if (cipher == NULL)
-        goto legacy;
+        /*
+         * If we're on the second iteration, free the results from the first.
+         * They are NULL on the first iteration, so no need to check what
+         * iteration we're on.
+         */
+        EVP_ASYM_CIPHER_free(cipher);
+        EVP_KEYMGMT_free(tmp_keymgmt);
+
+        switch (iter) {
+        case 1:
+            cipher = EVP_ASYM_CIPHER_fetch(ctx->libctx, supported_ciph,
+                                           ctx->propquery);
+            if (cipher != NULL)
+                tmp_prov = EVP_ASYM_CIPHER_get0_provider(cipher);
+            break;
+        case 2:
+            tmp_prov = EVP_KEYMGMT_get0_provider(ctx->keymgmt);
+            cipher =
+                evp_asym_cipher_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                                supported_ciph, ctx->propquery);
+            if (cipher == NULL)
+                goto legacy;
+            break;
+        }
+        if (cipher == NULL)
+            continue;
 
-    /*
-     * Ensure that the key is provided, either natively, or as a cached export.
-     * We start by fetching the keymgmt with the same name as |ctx->pkey|,
-     * but from the provider of the asym cipher method, using the same property
-     * query as when fetching the asym cipher method.
-     * With the keymgmt we found (if we did), we try to export |ctx->pkey|
-     * to it (evp_pkey_export_to_provider() is smart enough to only actually
-
-     * export it if |tmp_keymgmt| is different from |ctx->pkey|'s keymgmt)
-     */
-    tmp_keymgmt
-        = evp_keymgmt_fetch_from_prov(EVP_ASYM_CIPHER_get0_provider(cipher),
-                                      EVP_KEYMGMT_get0_name(ctx->keymgmt),
-                                      ctx->propquery);
-    if (tmp_keymgmt != NULL)
-        provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
-                                              &tmp_keymgmt, ctx->propquery);
-    if (provkey == NULL)
+        /*
+         * Ensure that the key is provided, either natively, or as a cached
+         * export.  We start by fetching the keymgmt with the same name as
+         * |ctx->pkey|, but from the provider of the asym cipher method, using
+         * the same property query as when fetching the asym cipher method.
+         * With the keymgmt we found (if we did), we try to export |ctx->pkey|
+         * to it (evp_pkey_export_to_provider() is smart enough to only actually
+         * export it if |tmp_keymgmt| is different from |ctx->pkey|'s keymgmt)
+         */
+        tmp_keymgmt_tofree = tmp_keymgmt
+            = evp_keymgmt_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                          EVP_KEYMGMT_get0_name(ctx->keymgmt),
+                                          ctx->propquery);
+        if (tmp_keymgmt != NULL)
+            provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
+                                                  &tmp_keymgmt, ctx->propquery);
+        if (tmp_keymgmt == NULL)
+            EVP_KEYMGMT_free(tmp_keymgmt_tofree);
+    }
+
+    if (provkey == NULL) {
+        EVP_ASYM_CIPHER_free(cipher);
         goto legacy;
+    }
 
     ERR_pop_to_mark();
 
diff --git a/crypto/evp/exchange.c b/crypto/evp/exchange.c
index 35da4743a4..d12dcee947 100644
--- a/crypto/evp/exchange.c
+++ b/crypto/evp/exchange.c
@@ -203,7 +203,9 @@ int EVP_PKEY_derive_init_ex(EVP_PKEY_CTX *ctx, const OSSL_PARAM params[])
     void *provkey = NULL;
     EVP_KEYEXCH *exchange = NULL;
     EVP_KEYMGMT *tmp_keymgmt = NULL;
+    const OSSL_PROVIDER *tmp_prov = NULL;
     const char *supported_exch = NULL;
+    int iter;
 
     if (ctx == NULL) {
         ERR_raise(ERR_LIB_EVP, ERR_R_PASSED_NULL_PARAMETER);
@@ -255,32 +257,76 @@ int EVP_PKEY_derive_init_ex(EVP_PKEY_CTX *ctx, const OSSL_PARAM params[])
 
 
     /*
-     * Because we cleared out old ops, we shouldn't need to worry about
-     * checking if exchange is already there.
+     * We perform two iterations:
+     *
+     * 1.  Do the normal exchange fetch, using the fetching data given by
+     *     the EVP_PKEY_CTX.
+     * 2.  Do the provider specific exchange fetch, from the same provider
+     *     as |ctx->keymgmt|
+     *
+     * We then try to fetch the keymgmt from the same provider as the
+     * exchange, and try to export |ctx->pkey| to that keymgmt (when
+     * this keymgmt happens to be the same as |ctx->keymgmt|, the export
+     * is a no-op, but we call it anyway to not complicate the code even
+     * more).
+     * If the export call succeeds (returns a non-NULL provider key pointer),
+     * we're done and can perform the operation itself.  If not, we perform
+     * the second iteration, or jump to legacy.
      */
-    exchange = EVP_KEYEXCH_fetch(ctx->libctx, supported_exch, ctx->propquery);
-    if (exchange == NULL)
-        goto legacy;
+    for (iter = 1, provkey = NULL; iter < 3 && provkey == NULL; iter++) {
+        EVP_KEYMGMT *tmp_keymgmt_tofree;
 
-    /*
-     * Ensure that the key is provided, either natively, or as a cached export.
-     * We start by fetching the keymgmt with the same name as |ctx->pkey|,
-     * but from the provider of the exch method, using the same property
-     * query as when fetching the exch method.
-     * With the keymgmt we found (if we did), we try to export |ctx->pkey|
-     * to it (evp_pkey_export_to_provider() is smart enough to only actually
-
-     * export it if |tmp_keymgmt| is different from |ctx->pkey|'s keymgmt)
-     */
-    tmp_keymgmt
-        = evp_keymgmt_fetch_from_prov(EVP_KEYEXCH_get0_provider(exchange),
-                                      EVP_KEYMGMT_get0_name(ctx->keymgmt),
-                                      ctx->propquery);
-    if (tmp_keymgmt != NULL)
-        provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
-                                              &tmp_keymgmt, ctx->propquery);
-    if (provkey == NULL)
+        /*
+         * If we're on the second iteration, free the results from the first.
+         * They are NULL on the first iteration, so no need to check what
+         * iteration we're on.
+         */
+        EVP_KEYEXCH_free(exchange);
+        EVP_KEYMGMT_free(tmp_keymgmt);
+
+        switch (iter) {
+        case 1:
+            exchange =
+                EVP_KEYEXCH_fetch(ctx->libctx, supported_exch, ctx->propquery);
+            if (exchange != NULL)
+                tmp_prov = EVP_KEYEXCH_get0_provider(exchange);
+            break;
+        case 2:
+            tmp_prov = EVP_KEYMGMT_get0_provider(ctx->keymgmt);
+            exchange =
+                evp_keyexch_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                              supported_exch, ctx->propquery);
+            if (exchange == NULL)
+                goto legacy;
+            break;
+        }
+        if (exchange == NULL)
+            continue;
+
+        /*
+         * Ensure that the key is provided, either natively, or as a cached
+         * export.  We start by fetching the keymgmt with the same name as
+         * |ctx->pkey|, but from the provider of the exchange method, using
+         * the same property query as when fetching the exchange method.
+         * With the keymgmt we found (if we did), we try to export |ctx->pkey|
+         * to it (evp_pkey_export_to_provider() is smart enough to only actually
+         * export it if |tmp_keymgmt| is different from |ctx->pkey|'s keymgmt)
+         */
+        tmp_keymgmt_tofree = tmp_keymgmt =
+            evp_keymgmt_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                        EVP_KEYMGMT_get0_name(ctx->keymgmt),
+                                        ctx->propquery);
+        if (tmp_keymgmt != NULL)
+            provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
+                                                  &tmp_keymgmt, ctx->propquery);
+        if (tmp_keymgmt == NULL)
+            EVP_KEYMGMT_free(tmp_keymgmt_tofree);
+    }
+
+    if (provkey == NULL) {
+        EVP_KEYEXCH_free(exchange);
         goto legacy;
+    }
 
     ERR_pop_to_mark();
 
diff --git a/crypto/evp/kem.c b/crypto/evp/kem.c
index a3537cc452..d5bdc6290a 100644
--- a/crypto/evp/kem.c
+++ b/crypto/evp/kem.c
@@ -23,8 +23,10 @@ static int evp_kem_init(EVP_PKEY_CTX *ctx, int operation,
     int ret = 0;
     EVP_KEM *kem = NULL;
     EVP_KEYMGMT *tmp_keymgmt = NULL;
+    const OSSL_PROVIDER *tmp_prov = NULL;
     void *provkey = NULL;
     const char *supported_kem = NULL;
+    int iter;
 
     if (ctx == NULL || ctx->keytype == NULL) {
         ERR_raise(ERR_LIB_EVP, EVP_R_INITIALIZATION_ERROR);
@@ -49,31 +51,80 @@ static int evp_kem_init(EVP_PKEY_CTX *ctx, int operation,
         goto err;
     }
 
-    kem = EVP_KEM_fetch(ctx->libctx, supported_kem, ctx->propquery);
-    if (kem == NULL) {
-        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
-        ret = -2;
-        goto err;
-    }
-
     /*
-     * Ensure that the key is provided, either natively, or as a cached export.
-     * We start by fetching the keymgmt with the same name as |ctx->pkey|,
-     * but from the provider of the kem method, using the same property
-     * query as when fetching the kem method.
-     * With the keymgmt we found (if we did), we try to export |ctx->pkey|
-     * to it (evp_pkey_export_to_provider() is smart enough to only actually
-
-     * export it if |tmp_keymgmt| is different from |ctx->pkey|'s keymgmt)
+     * Because we cleared out old ops, we shouldn't need to worry about
+     * checking if kem is already there.
+     * We perform two iterations:
+     *
+     * 1.  Do the normal kem fetch, using the fetching data given by
+     *     the EVP_PKEY_CTX.
+     * 2.  Do the provider specific kem fetch, from the same provider
+     *     as |ctx->keymgmt|
+     *
+     * We then try to fetch the keymgmt from the same provider as the
+     * kem, and try to export |ctx->pkey| to that keymgmt (when this
+     * keymgmt happens to be the same as |ctx->keymgmt|, the export is
+     * a no-op, but we call it anyway to not complicate the code even
+     * more).
+     * If the export call succeeds (returns a non-NULL provider key pointer),
+     * we're done and can perform the operation itself.  If not, we perform
+     * the second iteration, or jump to legacy.
      */
-    tmp_keymgmt
-        = evp_keymgmt_fetch_from_prov(EVP_KEM_get0_provider(kem),
-                                      EVP_KEYMGMT_get0_name(ctx->keymgmt),
-                                      ctx->propquery);
-    if (tmp_keymgmt != NULL)
-        provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
-                                              &tmp_keymgmt, ctx->propquery);
+    for (iter = 1, provkey = NULL; iter < 3 && provkey == NULL; iter++) {
+        EVP_KEYMGMT *tmp_keymgmt_tofree;
+
+        /*
+         * If we're on the second iteration, free the results from the first.
+         * They are NULL on the first iteration, so no need to check what
+         * iteration we're on.
+         */
+        EVP_KEM_free(kem);
+        EVP_KEYMGMT_free(tmp_keymgmt);
+
+        switch (iter) {
+        case 1:
+            kem = EVP_KEM_fetch(ctx->libctx, supported_kem, ctx->propquery);
+            if (kem != NULL)
+                tmp_prov = EVP_KEM_get0_provider(kem);
+            break;
+        case 2:
+            tmp_prov = EVP_KEYMGMT_get0_provider(ctx->keymgmt);
+            kem = evp_kem_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                          supported_kem, ctx->propquery);
+
+            if (kem == NULL) {
+                ERR_raise(ERR_LIB_EVP,
+                          EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
+                ret = -2;
+                goto err;
+            }
+        }
+        if (kem == NULL)
+            continue;
+
+        /*
+         * Ensure that the key is provided, either natively, or as a cached
+         * export.  We start by fetching the keymgmt with the same name as
+         * |ctx->pkey|, but from the provider of the kem method, using the
+         * same property query as when fetching the kem method.
+         * With the keymgmt we found (if we did), we try to export |ctx->pkey|
+         * to it (evp_pkey_export_to_provider() is smart enough to only actually
+
+         * export it if |tmp_keymgmt| is different from |ctx->pkey|'s keymgmt)
+         */
+        tmp_keymgmt_tofree = tmp_keymgmt =
+            evp_keymgmt_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                        EVP_KEYMGMT_get0_name(ctx->keymgmt),
+                                        ctx->propquery);
+        if (tmp_keymgmt != NULL)
+            provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
+                                                  &tmp_keymgmt, ctx->propquery);
+        if (tmp_keymgmt == NULL)
+            EVP_KEYMGMT_free(tmp_keymgmt_tofree);
+    }
+
     if (provkey == NULL) {
+        EVP_KEM_free(kem);
         ERR_raise(ERR_LIB_EVP, EVP_R_INITIALIZATION_ERROR);
         goto err;
     }
diff --git a/crypto/evp/m_sigver.c b/crypto/evp/m_sigver.c
index 55675c36e1..eeb1a9adfa 100644
--- a/crypto/evp/m_sigver.c
+++ b/crypto/evp/m_sigver.c
@@ -45,10 +45,11 @@ static int do_sigver_init(EVP_MD_CTX *ctx, EVP_PKEY_CTX **pctx,
     EVP_PKEY_CTX *locpctx = NULL;
     EVP_SIGNATURE *signature = NULL;
     EVP_KEYMGMT *tmp_keymgmt = NULL;
+    const OSSL_PROVIDER *tmp_prov = NULL;
     const char *supported_sig = NULL;
     char locmdname[80] = "";     /* 80 chars should be enough */
     void *provkey = NULL;
-    int ret;
+    int ret, iter;
 
     if (ctx->algctx != NULL) {
         if (!ossl_assert(ctx->digest != NULL)) {
@@ -98,33 +99,75 @@ static int do_sigver_init(EVP_MD_CTX *ctx, EVP_PKEY_CTX **pctx,
     }
 
     /*
-     * Because we cleared out old ops, we shouldn't need to worry about
-     * checking if signature is already there.
+     * We perform two iterations:
+     *
+     * 1.  Do the normal signature fetch, using the fetching data given by
+     *     the EVP_PKEY_CTX.
+     * 2.  Do the provider specific signature fetch, from the same provider
+     *     as |ctx->keymgmt|
+     *
+     * We then try to fetch the keymgmt from the same provider as the
+     * signature, and try to export |ctx->pkey| to that keymgmt (when
+     * this keymgmt happens to be the same as |ctx->keymgmt|, the export
+     * is a no-op, but we call it anyway to not complicate the code even
+     * more).
+     * If the export call succeeds (returns a non-NULL provider key pointer),
+     * we're done and can perform the operation itself.  If not, we perform
+     * the second iteration, or jump to legacy.
      */
-    signature = EVP_SIGNATURE_fetch(locpctx->libctx, supported_sig,
-                                    locpctx->propquery);
-
-    if (signature == NULL)
-        goto legacy;
+    for (iter = 1, provkey = NULL; iter < 3 && provkey == NULL; iter++) {
+        EVP_KEYMGMT *tmp_keymgmt_tofree = NULL;
+
+        /*
+         * If we're on the second iteration, free the results from the first.
+         * They are NULL on the first iteration, so no need to check what
+         * iteration we're on.
+         */
+        EVP_SIGNATURE_free(signature);
+        EVP_KEYMGMT_free(tmp_keymgmt);
+
+        switch (iter) {
+        case 1:
+            signature = EVP_SIGNATURE_fetch(locpctx->libctx, supported_sig,
+                                            locpctx->propquery);
+            if (signature != NULL)
+                tmp_prov = EVP_SIGNATURE_get0_provider(signature);
+            break;
+        case 2:
+            tmp_prov = EVP_KEYMGMT_get0_provider(locpctx->keymgmt);
+            signature =
+                evp_signature_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                              supported_sig, locpctx->propquery);
+            if (signature == NULL)
+                goto legacy;
+            break;
+        }
+        if (signature == NULL)
+            continue;
+
+        /*
+         * Ensure that the key is provided, either natively, or as a cached
+         * export.  We start by fetching the keymgmt with the same name as
+         * |locpctx->pkey|, but from the provider of the signature method, using
+         * the same property query as when fetching the signature method.
+         * With the keymgmt we found (if we did), we try to export |locpctx->pkey|
+         * to it (evp_pkey_export_to_provider() is smart enough to only actually
+
+         * export it if |tmp_keymgmt| is different from |locpctx->pkey|'s keymgmt)
+         */
+        tmp_keymgmt_tofree = tmp_keymgmt =
+            evp_keymgmt_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                        EVP_KEYMGMT_get0_name(locpctx->keymgmt),
+                                        locpctx->propquery);
+        if (tmp_keymgmt != NULL)
+            provkey = evp_pkey_export_to_provider(locpctx->pkey, locpctx->libctx,
+                                                  &tmp_keymgmt, locpctx->propquery);
+        if (tmp_keymgmt == NULL)
+            EVP_KEYMGMT_free(tmp_keymgmt_tofree);
+    }
 
-    /*
-     * Ensure that the key is provided, either natively, or as a cached export.
-     * We start by fetching the keymgmt with the same name as |locpctx->pkey|,
-     * but from the provider of the signature method, using the same property
-     * query as when fetching the signature method.
-     * With the keymgmt we found (if we did), we try to export |locpctx->pkey|
-     * to it (evp_pkey_export_to_provider() is smart enough to only actually
-
-     * export it if |tmp_keymgmt| is different from |locpctx->pkey|'s keymgmt)
-     */
-    tmp_keymgmt
-        = evp_keymgmt_fetch_from_prov(EVP_SIGNATURE_get0_provider(signature),
-                                      EVP_KEYMGMT_get0_name(locpctx->keymgmt),
-                                      locpctx->propquery);
-    if (tmp_keymgmt != NULL)
-        provkey = evp_pkey_export_to_provider(locpctx->pkey, locpctx->libctx,
-                                              &tmp_keymgmt, locpctx->propquery);
     if (provkey == NULL) {
+        EVP_SIGNATURE_free(signature);
         ERR_clear_last_mark();
         ERR_raise(ERR_LIB_EVP, EVP_R_INITIALIZATION_ERROR);
         goto err;
diff --git a/crypto/evp/signature.c b/crypto/evp/signature.c
index f5c3bbcb1e..b33fe0d952 100644
--- a/crypto/evp/signature.c
+++ b/crypto/evp/signature.c
@@ -397,7 +397,9 @@ static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation,
     void *provkey = NULL;
     EVP_SIGNATURE *signature = NULL;
     EVP_KEYMGMT *tmp_keymgmt = NULL;
+    const OSSL_PROVIDER *tmp_prov = NULL;
     const char *supported_sig = NULL;
+    int iter;
 
     if (ctx == NULL) {
         ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
@@ -430,34 +432,77 @@ static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation,
     }
 
     /*
-     * Because we cleared out old ops, we shouldn't need to worry about
-     * checking if signature is already there.
+     * We perform two iterations:
+     *
+     * 1.  Do the normal signature fetch, using the fetching data given by
+     *     the EVP_PKEY_CTX.
+     * 2.  Do the provider specific signature fetch, from the same provider
+     *     as |ctx->keymgmt|
+     *
+     * We then try to fetch the keymgmt from the same provider as the
+     * signature, and try to export |ctx->pkey| to that keymgmt (when
+     * this keymgmt happens to be the same as |ctx->keymgmt|, the export
+     * is a no-op, but we call it anyway to not complicate the code even
+     * more).
+     * If the export call succeeds (returns a non-NULL provider key pointer),
+     * we're done and can perform the operation itself.  If not, we perform
+     * the second iteration, or jump to legacy.
      */
-    signature =
-        EVP_SIGNATURE_fetch(ctx->libctx, supported_sig, ctx->propquery);
+    for (iter = 1; iter < 3 && provkey == NULL; iter++) {
+        EVP_KEYMGMT *tmp_keymgmt_tofree;
 
-    if (signature == NULL)
-        goto legacy;
+        /*
+         * If we're on the second iteration, free the results from the first.
+         * They are NULL on the first iteration, so no need to check what
+         * iteration we're on.
+         */
+        EVP_SIGNATURE_free(signature);
+        EVP_KEYMGMT_free(tmp_keymgmt);
+
+        switch (iter) {
+        case 1:
+            signature =
+                EVP_SIGNATURE_fetch(ctx->libctx, supported_sig, ctx->propquery);
+            if (signature != NULL)
+                tmp_prov = EVP_SIGNATURE_get0_provider(signature);
+            break;
+        case 2:
+            tmp_prov = EVP_KEYMGMT_get0_provider(ctx->keymgmt);
+            signature =
+                evp_signature_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                              supported_sig, ctx->propquery);
+            if (signature == NULL)
+                goto legacy;
+            break;
+        }
+        if (signature == NULL)
+            continue;
 
-    /*
-     * Ensure that the key is provided, either natively, or as a cached export.
-     * We start by fetching the keymgmt with the same name as |ctx->pkey|,
-     * but from the provider of the signature method, using the same property
-     * query as when fetching the signature method.
-     * With the keymgmt we found (if we did), we try to export |ctx->pkey|
-     * to it (evp_pkey_export_to_provider() is smart enough to only actually
-
-     * export it if |tmp_keymgmt| is different from |ctx->pkey|'s keymgmt)
-     */
-    tmp_keymgmt
-        = evp_keymgmt_fetch_from_prov(EVP_SIGNATURE_get0_provider(signature),
-                                      EVP_KEYMGMT_get0_name(ctx->keymgmt),
-                                      ctx->propquery);
-    if (tmp_keymgmt != NULL)
-        provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
-                                              &tmp_keymgmt, ctx->propquery);
-    if (provkey == NULL)
+        /*
+         * Ensure that the key is provided, either natively, or as a cached
+         * export.  We start by fetching the keymgmt with the same name as
+         * |ctx->pkey|, but from the provider of the signature method, using
+         * the same property query as when fetching the signature method.
+         * With the keymgmt we found (if we did), we try to export |ctx->pkey|
+         * to it (evp_pkey_export_to_provider() is smart enough to only actually
+
+         * export it if |tmp_keymgmt| is different from |ctx->pkey|'s keymgmt)
+         */
+        tmp_keymgmt_tofree = tmp_keymgmt =
+            evp_keymgmt_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
+                                        EVP_KEYMGMT_get0_name(ctx->keymgmt),
+                                        ctx->propquery);
+        if (tmp_keymgmt != NULL)
+            provkey = evp_pkey_export_to_provider(ctx->pkey, ctx->libctx,
+                                                  &tmp_keymgmt, ctx->propquery);
+        if (tmp_keymgmt == NULL)
+            EVP_KEYMGMT_free(tmp_keymgmt_tofree);
+    }
+
+    if (provkey == NULL) {
+        EVP_SIGNATURE_free(signature);
         goto legacy;
+    }
 
     ERR_pop_to_mark();
 
diff --git a/doc/build.info b/doc/build.info
index 5f446e3868..97e6bd3b51 100644
--- a/doc/build.info
+++ b/doc/build.info
@@ -1307,10 +1307,10 @@ DEPEND[html/man3/EVP_RAND.html]=man3/EVP_RAND.pod
 GENERATE[html/man3/EVP_RAND.html]=man3/EVP_RAND.pod
 DEPEND[man/man3/EVP_RAND.3]=man3/EVP_RAND.pod
 GENERATE[man/man3/EVP_RAND.3]=man3/EVP_RAND.pod
-DEPEND[html/man3/EVP_SIGNATURE_free.html]=man3/EVP_SIGNATURE_free.pod
-GENERATE[html/man3/EVP_SIGNATURE_free.html]=man3/EVP_SIGNATURE_free.pod
-DEPEND[man/man3/EVP_SIGNATURE_free.3]=man3/EVP_SIGNATURE_free.pod
-GENERATE[man/man3/EVP_SIGNATURE_free.3]=man3/EVP_SIGNATURE_free.pod
+DEPEND[html/man3/EVP_SIGNATURE.html]=man3/EVP_SIGNATURE.pod
+GENERATE[html/man3/EVP_SIGNATURE.html]=man3/EVP_SIGNATURE.pod
+DEPEND[man/man3/EVP_SIGNATURE.3]=man3/EVP_SIGNATURE.pod
+GENERATE[man/man3/EVP_SIGNATURE.3]=man3/EVP_SIGNATURE.pod
 DEPEND[html/man3/EVP_SealInit.html]=man3/EVP_SealInit.pod
 GENERATE[html/man3/EVP_SealInit.html]=man3/EVP_SealInit.pod
 DEPEND[man/man3/EVP_SealInit.3]=man3/EVP_SealInit.pod
@@ -3046,7 +3046,7 @@ html/man3/EVP_PKEY_todata.html \
 html/man3/EVP_PKEY_verify.html \
 html/man3/EVP_PKEY_verify_recover.html \
 html/man3/EVP_RAND.html \
-html/man3/EVP_SIGNATURE_free.html \
+html/man3/EVP_SIGNATURE.html \
 html/man3/EVP_SealInit.html \
 html/man3/EVP_SignInit.html \
 html/man3/EVP_VerifyInit.html \
@@ -3638,7 +3638,7 @@ man/man3/EVP_PKEY_todata.3 \
 man/man3/EVP_PKEY_verify.3 \
 man/man3/EVP_PKEY_verify_recover.3 \
 man/man3/EVP_RAND.3 \
-man/man3/EVP_SIGNATURE_free.3 \
+man/man3/EVP_SIGNATURE.3 \
 man/man3/EVP_SealInit.3 \
 man/man3/EVP_SignInit.3 \
 man/man3/EVP_VerifyInit.3 \
diff --git a/doc/man3/EVP_SIGNATURE_free.pod b/doc/man3/EVP_SIGNATURE.pod
index 4642f40efc..9fb389e7ae 100644
--- a/doc/man3/EVP_SIGNATURE_free.pod
+++ b/doc/man3/EVP_SIGNATURE.pod
@@ -2,6 +2,7 @@
 
 =head1 NAME
 
+EVP_SIGNATURE,
 EVP_SIGNATURE_fetch, EVP_SIGNATURE_free, EVP_SIGNATURE_up_ref,
 EVP_SIGNATURE_is_a, EVP_SIGNATURE_get0_provider,
 EVP_SIGNATURE_do_all_provided, EVP_SIGNATURE_names_do_all,
@@ -13,6 +14,8 @@ EVP_SIGNATURE_gettable_ctx_params, EVP_SIGNATURE_settable_ctx_params
 
  #include <openssl/evp.h>
 
+ typedef struct evp_signature_st EVP_SIGNATURE;
+
  EVP_SIGNATURE *EVP_SIGNATURE_fetch(OSSL_LIB_CTX *ctx, const char *algorithm,
                                     const char *properties);
  void EVP_SIGNATURE_free(EVP_SIGNATURE *signature);
diff --git a/doc/man7/crypto.pod b/doc/man7/crypto.pod
index 16a07fc0ac..9aa667118d 100644
--- a/doc/man7/crypto.pod
+++ b/doc/man7/crypto.pod
@@ -181,6 +181,35 @@ is supplied. In this case an algorithm implementation is implicitly fetched
 using default search criteria and an algorithm name that is consistent with
 the context in which it is being used.
 
+Functions that revolve around B<EVP_PKEY_CTX> and L<EVP_PKEY(3)>, such as
+L<EVP_DigestSignInit(3)> and friends, all fetch the implementations
+implicitly.  Because these functions involve both an operation type (such as
+L<EVP_SIGNATURE(3)>) and an L<EVP_KEYMGMT(3)> for the L<EVP_PKEY(3)>, they try
+the following:
+
+=over 4
+
+=item 1.
+
+Fetch the operation type implementation from any provider given a library
+context and property string stored in the B<EVP_PKEY_CTX>.
+
+If the provider of the operation type implementation is different from the
+provider of the L<EVP_PKEY(3)>'s L<EVP_KEYMGMT(3)> implementation, try to
+fetch a L<EVP_KEYMGMT(3)> implementation in the same provider as the operation
+type implementation and export the L<EVP_PKEY(3)> to it (effectively making a
+temporary copy of the original key).
+
+If anything in this step fails, the next step is used as a fallback.
+
+=item 2.
+
+As a fallback, try to fetch the operation type implementation from the same
+provider as the original L<EVP_PKEY(3)>'s L<EVP_KEYMGMT(3)>, still using the
+propery string from the B<EVP_PKEY_CTX>.
+
+=back
+
 =head1 FETCHING EXAMPLES
 
 The following section provides a series of examples of fetching algorithm
diff --git a/util/other.syms b/util/other.syms
index 38aaacd6cf..1ebffd1d26 100644
--- a/util/other.syms
+++ b/util/other.syms
@@ -51,6 +51,7 @@ EVP_PKEY_METHOD                         datatype
 EVP_PKEY_ASN1_METHOD                    datatype
 EVP_RAND                                datatype
 EVP_RAND_CTX                            datatype
+EVP_SIGNATURE                           datatype
 GEN_SESSION_CB                          datatype
 OPENSSL_Applink                         external
 OSSL_LIB_CTX                            datatype