Implement functionality for direct use of composite signature algorithms

The following API groups are extended with a new init function, as well
as an update and final function, to allow the use of explicitly fetched
signature implementations for any composite signature algorithm, like
"sha1WithRSAEncryption":

- EVP_PKEY_sign
- EVP_PKEY_verify
- EVP_PKEY_verify_recover

To support this, providers are required to add a few new functions, not
the least one that declares what key types an signature implementation
supports.

While at this, the validity check in evp_signature_from_algorithm() is
also refactored; the SIGNATURE provider functionality is too complex for
counters.  It's better, or at least more readable, to check function
combinations.

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Neil Horman <nhorman@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/23416)

12 files changed, 1137 insertions, 203 deletions

diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt
index a6f1d9b2e7..7cbe4a9b13 100644
--- a/crypto/err/openssl.txt
+++ b/crypto/err/openssl.txt
@@ -779,6 +779,8 @@ EVP_R_ONLY_ONESHOT_SUPPORTED:177:only oneshot supported
 EVP_R_OPERATION_NOT_INITIALIZED:151:operation not initialized
 EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE:150:\
 	operation not supported for this keytype
+EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_SIGNATURE_TYPE:226:\
+	operation not supported for this signature type
 EVP_R_OUTPUT_WOULD_OVERFLOW:202:output would overflow
 EVP_R_PARAMETER_TOO_LARGE:187:parameter too large
 EVP_R_PARTIALLY_OVERLAPPING:162:partially overlapping buffers
@@ -790,6 +792,8 @@ EVP_R_PRIVATE_KEY_ENCODE_ERROR:146:private key encode error
 EVP_R_PUBLIC_KEY_NOT_RSA:106:public key not rsa
 EVP_R_SETTING_XOF_FAILED:227:setting xof failed
 EVP_R_SET_DEFAULT_PROPERTY_FAILURE:209:set default property failure
+EVP_R_SIGNATURE_TYPE_AND_KEY_TYPE_INCOMPATIBLE:228:\
+	signature type and key type incompatible
 EVP_R_TOO_MANY_RECORDS:183:too many records
 EVP_R_UNABLE_TO_ENABLE_LOCKING:212:unable to enable locking
 EVP_R_UNABLE_TO_GET_MAXIMUM_REQUEST_SIZE:215:unable to get maximum request size
diff --git a/crypto/evp/evp_err.c b/crypto/evp/evp_err.c
index 42dd7e4009..ffac813db2 100644
--- a/crypto/evp/evp_err.c
+++ b/crypto/evp/evp_err.c
@@ -1,6 +1,6 @@
 /*
  * Generated by util/mkerr.pl DO NOT EDIT
- * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -132,6 +132,8 @@ static const ERR_STRING_DATA EVP_str_reasons[] = {
     "operation not initialized"},
     {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE),
     "operation not supported for this keytype"},
+    {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_SIGNATURE_TYPE),
+    "operation not supported for this signature type"},
     {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_OUTPUT_WOULD_OVERFLOW),
     "output would overflow"},
     {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_PARAMETER_TOO_LARGE),
@@ -149,6 +151,8 @@ static const ERR_STRING_DATA EVP_str_reasons[] = {
     {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_SETTING_XOF_FAILED), "setting xof failed"},
     {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_SET_DEFAULT_PROPERTY_FAILURE),
     "set default property failure"},
+    {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_SIGNATURE_TYPE_AND_KEY_TYPE_INCOMPATIBLE),
+    "signature type and key type incompatible"},
     {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_TOO_MANY_RECORDS), "too many records"},
     {ERR_PACK(ERR_LIB_EVP, 0, EVP_R_UNABLE_TO_ENABLE_LOCKING),
     "unable to enable locking"},
diff --git a/crypto/evp/evp_local.h b/crypto/evp/evp_local.h
index 46650f1c59..ae8c7bb8a8 100644
--- a/crypto/evp/evp_local.h
+++ b/crypto/evp/evp_local.h
@@ -167,8 +167,14 @@ struct evp_signature_st {
     OSSL_FUNC_signature_newctx_fn *newctx;
     OSSL_FUNC_signature_sign_init_fn *sign_init;
     OSSL_FUNC_signature_sign_fn *sign;
+    OSSL_FUNC_signature_sign_message_init_fn *sign_message_init;
+    OSSL_FUNC_signature_sign_message_update_fn *sign_message_update;
+    OSSL_FUNC_signature_sign_message_final_fn *sign_message_final;
     OSSL_FUNC_signature_verify_init_fn *verify_init;
     OSSL_FUNC_signature_verify_fn *verify;
+    OSSL_FUNC_signature_verify_message_init_fn *verify_message_init;
+    OSSL_FUNC_signature_verify_message_update_fn *verify_message_update;
+    OSSL_FUNC_signature_verify_message_final_fn *verify_message_final;
     OSSL_FUNC_signature_verify_recover_init_fn *verify_recover_init;
     OSSL_FUNC_signature_verify_recover_fn *verify_recover;
     OSSL_FUNC_signature_digest_sign_init_fn *digest_sign_init;
@@ -189,6 +195,9 @@ struct evp_signature_st {
     OSSL_FUNC_signature_gettable_ctx_md_params_fn *gettable_ctx_md_params;
     OSSL_FUNC_signature_set_ctx_md_params_fn *set_ctx_md_params;
     OSSL_FUNC_signature_settable_ctx_md_params_fn *settable_ctx_md_params;
+
+    /* Signature object checking */
+    OSSL_FUNC_signature_query_key_types_fn *query_key_types;
 } /* EVP_SIGNATURE */;
 
 struct evp_asym_cipher_st {
diff --git a/crypto/evp/signature.c b/crypto/evp/signature.c
index c05eb78b51..33910e5bc3 100644
--- a/crypto/evp/signature.c
+++ b/crypto/evp/signature.c
@@ -7,8 +7,10 @@
  * https://www.openssl.org/source/license.html
  */
 
+#include <openssl/err.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <openssl/core_names.h>
 #include <openssl/objects.h>
 #include <openssl/evp.h>
 #include "internal/numbers.h"   /* includes SIZE_MAX */
@@ -42,9 +44,15 @@ static void *evp_signature_from_algorithm(int name_id,
 {
     const OSSL_DISPATCH *fns = algodef->implementation;
     EVP_SIGNATURE *signature = NULL;
-    int ctxfncnt = 0, signfncnt = 0, verifyfncnt = 0, verifyrecfncnt = 0;
-    int digsignfncnt = 0, digverifyfncnt = 0;
+    /* Counts newctx / freectx */
+    int ctxfncnt = 0;
+    /* Counts all init functions  */
+    int initfncnt = 0;
+    /* Counts all performance functions (oneshot / update / final) */
+    int fncnt = 0;
+    /* Counts all parameter functions */
     int gparamfncnt = 0, sparamfncnt = 0, gmdparamfncnt = 0, smdparamfncnt = 0;
+    int valid = 0;
 
     if ((signature = evp_signature_new(prov)) == NULL) {
         ERR_raise(ERR_LIB_EVP, ERR_R_EVP_LIB);
@@ -68,91 +76,137 @@ static void *evp_signature_from_algorithm(int name_id,
             if (signature->sign_init != NULL)
                 break;
             signature->sign_init = OSSL_FUNC_signature_sign_init(fns);
-            signfncnt++;
+            initfncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_SIGN:
             if (signature->sign != NULL)
                 break;
             signature->sign = OSSL_FUNC_signature_sign(fns);
-            signfncnt++;
+            fncnt++;
+            break;
+        case OSSL_FUNC_SIGNATURE_SIGN_MESSAGE_INIT:
+            if (signature->sign_message_init != NULL)
+                break;
+            signature->sign_message_init
+                = OSSL_FUNC_signature_sign_message_init(fns);
+            initfncnt++;
+            break;
+        case OSSL_FUNC_SIGNATURE_SIGN_MESSAGE_UPDATE:
+            if (signature->sign_message_update != NULL)
+                break;
+            signature->sign_message_update
+                = OSSL_FUNC_signature_sign_message_update(fns);
+            fncnt++;
+            break;
+        case OSSL_FUNC_SIGNATURE_SIGN_MESSAGE_FINAL:
+            if (signature->sign_message_final != NULL)
+                break;
+            signature->sign_message_final
+                = OSSL_FUNC_signature_sign_message_final(fns);
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_VERIFY_INIT:
             if (signature->verify_init != NULL)
                 break;
             signature->verify_init = OSSL_FUNC_signature_verify_init(fns);
-            verifyfncnt++;
+            initfncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_VERIFY:
             if (signature->verify != NULL)
                 break;
             signature->verify = OSSL_FUNC_signature_verify(fns);
-            verifyfncnt++;
+            fncnt++;
+            break;
+        case OSSL_FUNC_SIGNATURE_VERIFY_MESSAGE_INIT:
+            if (signature->verify_message_init != NULL)
+                break;
+            signature->verify_message_init
+                = OSSL_FUNC_signature_verify_message_init(fns);
+            initfncnt++;
+            break;
+        case OSSL_FUNC_SIGNATURE_VERIFY_MESSAGE_UPDATE:
+            if (signature->verify_message_update != NULL)
+                break;
+            signature->verify_message_update
+                = OSSL_FUNC_signature_verify_message_update(fns);
+            fncnt++;
+            break;
+        case OSSL_FUNC_SIGNATURE_VERIFY_MESSAGE_FINAL:
+            if (signature->verify_message_final != NULL)
+                break;
+            signature->verify_message_final
+                = OSSL_FUNC_signature_verify_message_final(fns);
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_VERIFY_RECOVER_INIT:
             if (signature->verify_recover_init != NULL)
                 break;
             signature->verify_recover_init
                 = OSSL_FUNC_signature_verify_recover_init(fns);
-            verifyrecfncnt++;
+            initfncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_VERIFY_RECOVER:
             if (signature->verify_recover != NULL)
                 break;
             signature->verify_recover
                 = OSSL_FUNC_signature_verify_recover(fns);
-            verifyrecfncnt++;
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_DIGEST_SIGN_INIT:
             if (signature->digest_sign_init != NULL)
                 break;
             signature->digest_sign_init
                 = OSSL_FUNC_signature_digest_sign_init(fns);
+            initfncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_DIGEST_SIGN_UPDATE:
             if (signature->digest_sign_update != NULL)
                 break;
             signature->digest_sign_update
                 = OSSL_FUNC_signature_digest_sign_update(fns);
-            digsignfncnt++;
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_DIGEST_SIGN_FINAL:
             if (signature->digest_sign_final != NULL)
                 break;
             signature->digest_sign_final
                 = OSSL_FUNC_signature_digest_sign_final(fns);
-            digsignfncnt++;
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_DIGEST_SIGN:
             if (signature->digest_sign != NULL)
                 break;
             signature->digest_sign
                 = OSSL_FUNC_signature_digest_sign(fns);
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_DIGEST_VERIFY_INIT:
             if (signature->digest_verify_init != NULL)
                 break;
             signature->digest_verify_init
                 = OSSL_FUNC_signature_digest_verify_init(fns);
+            initfncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_DIGEST_VERIFY_UPDATE:
             if (signature->digest_verify_update != NULL)
                 break;
             signature->digest_verify_update
                 = OSSL_FUNC_signature_digest_verify_update(fns);
-            digverifyfncnt++;
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_DIGEST_VERIFY_FINAL:
             if (signature->digest_verify_final != NULL)
                 break;
             signature->digest_verify_final
                 = OSSL_FUNC_signature_digest_verify_final(fns);
-            digverifyfncnt++;
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_DIGEST_VERIFY:
             if (signature->digest_verify != NULL)
                 break;
             signature->digest_verify
                 = OSSL_FUNC_signature_digest_verify(fns);
+            fncnt++;
             break;
         case OSSL_FUNC_SIGNATURE_FREECTX:
             if (signature->freectx != NULL)
@@ -221,48 +275,109 @@ static void *evp_signature_from_algorithm(int name_id,
                 = OSSL_FUNC_signature_settable_ctx_md_params(fns);
             smdparamfncnt++;
             break;
+        case OSSL_FUNC_SIGNATURE_QUERY_KEY_TYPES:
+            if (signature->query_key_types != NULL)
+                break;
+            signature->query_key_types
+                = OSSL_FUNC_signature_query_key_types(fns);
+            break;
         }
     }
-    if (ctxfncnt != 2
-        || (signfncnt == 0
-            && verifyfncnt == 0
-            && verifyrecfncnt == 0
-            && digsignfncnt == 0
-            && digverifyfncnt == 0
+    /*
+     * In order to be a consistent set of functions we must have at least
+     * a set of context functions (newctx and freectx) as well as a set of
+     * "signature" functions.  Because there's an overlap between some sets
+     * of functions, counters don't always cut it, we must test known
+     * combinations.
+     * We start by assuming the implementation is valid, and then look for
+     * reasons it's not.
+     */
+    valid = 1;
+    /* Start with the ones where counters say enough */
+    if (ctxfncnt != 2)
+        /* newctx or freectx missing */
+        valid = 0;
+    if (valid
+        && ((gparamfncnt != 0 && gparamfncnt != 2)
+            || (sparamfncnt != 0 && sparamfncnt != 2)
+            || (gmdparamfncnt != 0 && gmdparamfncnt != 2)
+            || (smdparamfncnt != 0 && smdparamfncnt != 2)))
+        /*
+         * Params functions are optional, but if defined, they must
+         * be pairwise complete sets, i.e. a getter must have an
+         * associated gettable, etc
+         */
+        valid = 0;
+    if (valid && (initfncnt == 0 || fncnt < initfncnt))
+        /*
+         * No init functions, or fewer execution functions than init functions
+         */
+        valid = 0;
+
+    /* Now we check for function combinations */
+    if (valid
+        && ((signature->sign_init != NULL
+             && signature->sign == NULL)
+            || (signature->sign_message_init != NULL
+                && signature->sign == NULL
+                && (signature->sign_message_update == NULL
+                    || signature->sign_message_final == NULL))))
+        /* sign_init functions with no signing function?  That's weird */
+        valid = 0;
+    if (valid
+        && (signature->sign != NULL
+            || signature->sign_message_update != NULL
+            || signature->sign_message_final != NULL)
+        && signature->sign_init == NULL
+        && signature->sign_message_init == NULL)
+        /* signing functions with no sign_init? That's odd */
+        valid = 0;
+
+    if (valid
+        && ((signature->verify_init != NULL
+             && signature->verify == NULL)
+            || (signature->verify_message_init != NULL
+                && signature->verify == NULL
+                && (signature->verify_message_update == NULL
+                    || signature->verify_message_final == NULL))))
+        /* verify_init functions with no verification function?  That's weird */
+        valid = 0;
+    if (valid
+        && (signature->verify != NULL
+            || signature->verify_message_update != NULL
+            || signature->verify_message_final != NULL)
+        && signature->verify_init == NULL
+        && signature->verify_message_init == NULL)
+        /* verification functions with no verify_init? That's odd */
+        valid = 0;
+
+    if (valid
+        && (signature->verify_recover_init != NULL)
+            && (signature->verify_recover == NULL))
+        /* verify_recover_init functions with no verify_recover?  How quaint */
+        valid = 0;
+
+    if (valid
+        && (signature->digest_sign_init != NULL
             && signature->digest_sign == NULL
-            && signature->digest_verify == NULL)
-        || (signfncnt != 0 && signfncnt != 2)
-        || (verifyfncnt != 0 && verifyfncnt != 2)
-        || (verifyrecfncnt != 0 && verifyrecfncnt != 2)
-        || (digsignfncnt != 0 && digsignfncnt != 2)
-        || (digsignfncnt == 2 && signature->digest_sign_init == NULL)
-        || (digverifyfncnt != 0 && digverifyfncnt != 2)
-        || (digverifyfncnt == 2 && signature->digest_verify_init == NULL)
-        || (signature->digest_sign != NULL
-            && signature->digest_sign_init == NULL)
-        || (signature->digest_verify != NULL
-            && signature->digest_verify_init == NULL)
-        || (gparamfncnt != 0 && gparamfncnt != 2)
-        || (sparamfncnt != 0 && sparamfncnt != 2)
-        || (gmdparamfncnt != 0 && gmdparamfncnt != 2)
-        || (smdparamfncnt != 0 && smdparamfncnt != 2)) {
+            && (signature->digest_sign_update == NULL
+                || signature->digest_sign_final == NULL)))
         /*
-         * In order to be a consistent set of functions we must have at least
-         * a set of context functions (newctx and freectx) as well as a set of
-         * "signature" functions:
-         *  (sign_init, sign) or
-         *  (verify_init verify) or
-         *  (verify_recover_init, verify_recover) or
-         *  (digest_sign_init, digest_sign_update, digest_sign_final) or
-         *  (digest_verify_init, digest_verify_update, digest_verify_final) or
-         *  (digest_sign_init, digest_sign) or
-         *  (digest_verify_init, digest_verify).
-         *
-         * set_ctx_params and settable_ctx_params are optional, but if one of
-         * them is present then the other one must also be present. The same
-         * applies to get_ctx_params and gettable_ctx_params. The same rules
-         * apply to the "md_params" functions. The dupctx function is optional.
+         * You can't have a digest_sign_init without *some* performing functions
          */
+        valid = 0;
+
+    if (valid
+        && ((signature->digest_verify_init != NULL
+             && signature->digest_verify == NULL
+             && (signature->digest_verify_update == NULL
+                 || signature->digest_verify_final == NULL))))
+        /*
+         * You can't have a digest_verify_init without *some* performing functions
+         */
+        valid = 0;
+
+    if (!valid) {
         ERR_raise(ERR_LIB_EVP, EVP_R_INVALID_PROVIDER_FUNCTIONS);
         goto err;
     }
@@ -387,12 +502,11 @@ const OSSL_PARAM *EVP_SIGNATURE_settable_ctx_params(const EVP_SIGNATURE *sig)
     return sig->settable_ctx_params(NULL, provctx);
 }
 
-static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation,
-                                   const OSSL_PARAM params[])
+static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, EVP_SIGNATURE *signature,
+                                   int operation, const OSSL_PARAM params[])
 {
     int ret = 0;
     void *provkey = NULL;
-    EVP_SIGNATURE *signature = NULL;
     EVP_KEYMGMT *tmp_keymgmt = NULL;
     const OSSL_PROVIDER *tmp_prov = NULL;
     const char *supported_sig = NULL;
@@ -406,91 +520,30 @@ static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation,
     evp_pkey_ctx_free_old_ops(ctx);
     ctx->operation = operation;
 
-    ERR_set_mark();
-
-    if (evp_pkey_ctx_is_legacy(ctx))
-        goto legacy;
-
-    if (ctx->pkey == NULL) {
-        ERR_clear_last_mark();
-        ERR_raise(ERR_LIB_EVP, EVP_R_NO_KEY_SET);
-        goto err;
-    }
-
-    /*
-     * Try to derive the supported signature from |ctx->keymgmt|.
-     */
-    if (!ossl_assert(ctx->pkey->keymgmt == NULL
-                     || ctx->pkey->keymgmt == ctx->keymgmt)) {
-        ERR_clear_last_mark();
-        ERR_raise(ERR_LIB_EVP, ERR_R_INTERNAL_ERROR);
-        goto err;
-    }
-    supported_sig = evp_keymgmt_util_query_operation_name(ctx->keymgmt,
-                                                          OSSL_OP_SIGNATURE);
-    if (supported_sig == NULL) {
-        ERR_clear_last_mark();
-        ERR_raise(ERR_LIB_EVP, EVP_R_INITIALIZATION_ERROR);
-        goto err;
-    }
+    if (signature != NULL) {
+        /*
+         * It's important to figure out what the key type should be, and if
+         * that is what we have in ctx.
+         */
 
-    /*
-     * 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.
-     */
-    for (iter = 1; 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(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 (ctx->pkey == NULL) {
+            ERR_raise(ERR_LIB_EVP, EVP_R_NO_KEY_SET);
+            goto err;
         }
-        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)
+         * 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_prov = EVP_SIGNATURE_get0_provider(signature);
         tmp_keymgmt_tofree = tmp_keymgmt =
             evp_keymgmt_fetch_from_prov((OSSL_PROVIDER *)tmp_prov,
                                         EVP_KEYMGMT_get0_name(ctx->keymgmt),
@@ -500,14 +553,163 @@ static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation,
                                                   &tmp_keymgmt, ctx->propquery);
         if (tmp_keymgmt == NULL)
             EVP_KEYMGMT_free(tmp_keymgmt_tofree);
-    }
 
-    if (provkey == NULL) {
-        EVP_SIGNATURE_free(signature);
-        goto legacy;
-    }
+        if (provkey == NULL)
+            goto end;
 
-    ERR_pop_to_mark();
+        /*
+         * Check that the signature matches the given key.  This is not
+         * designed to work with legacy keys, so has to be done after we've
+         * ensured that the key is at least exported to a provider (above).
+         */
+        if (signature->query_key_types != NULL) {
+            /* This is expect to be a NULL terminated array */
+            const char **keytypes;
+
+            keytypes = signature->query_key_types();
+            for (; *keytypes != NULL; keytypes++)
+                if (EVP_PKEY_CTX_is_a(ctx, *keytypes))
+                    break;
+            if (*keytypes == NULL) {
+                ERR_raise(ERR_LIB_EVP, EVP_R_SIGNATURE_TYPE_AND_KEY_TYPE_INCOMPATIBLE);
+                return -2;
+            }
+        } else {
+            /*
+             * Fallback 1:
+             * check if the keytype is the same as the signature algorithm name
+             */
+            const char *keytype = EVP_KEYMGMT_get0_name(ctx->keymgmt);
+            int ok = EVP_SIGNATURE_is_a(signature, keytype);
+
+            /*
+             * Fallback 2:
+             * query the pkey for a default signature algorithm name, and check
+             * if it matches the signature implementation
+             */
+            if (!ok) {
+                const char *signame
+                    = evp_keymgmt_util_query_operation_name(ctx->keymgmt,
+                                                            OSSL_OP_SIGNATURE);
+
+                ok = EVP_SIGNATURE_is_a(signature, signame);
+            }
+
+            /* If none of the fallbacks helped, we're lost */
+            if (!ok) {
+                ERR_raise(ERR_LIB_EVP, EVP_R_SIGNATURE_TYPE_AND_KEY_TYPE_INCOMPATIBLE);
+                return -2;
+            }
+        }
+
+        if (!EVP_SIGNATURE_up_ref(signature))
+            return 0;
+    } else {
+        /* Without a pre-fetched signature, it must be figured out somehow */
+        ERR_set_mark();
+
+        if (evp_pkey_ctx_is_legacy(ctx))
+            goto legacy;
+
+        if (ctx->pkey == NULL) {
+            ERR_clear_last_mark();
+            ERR_raise(ERR_LIB_EVP, EVP_R_NO_KEY_SET);
+            goto err;
+        }
+
+        /*
+         * Try to derive the supported signature from |ctx->keymgmt|.
+         */
+        if (!ossl_assert(ctx->pkey->keymgmt == NULL
+                         || ctx->pkey->keymgmt == ctx->keymgmt)) {
+            ERR_clear_last_mark();
+            ERR_raise(ERR_LIB_EVP, ERR_R_INTERNAL_ERROR);
+            goto err;
+        }
+        supported_sig
+            = evp_keymgmt_util_query_operation_name(ctx->keymgmt,
+                                                    OSSL_OP_SIGNATURE);
+        if (supported_sig == NULL) {
+            ERR_clear_last_mark();
+            ERR_raise(ERR_LIB_EVP, EVP_R_INITIALIZATION_ERROR);
+            goto err;
+        }
+
+        /*
+         * 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.
+         */
+        for (iter = 1; 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(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_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();
+    }
 
     /* No more legacy from here down to legacy: */
 
@@ -529,6 +731,14 @@ static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation,
         }
         ret = signature->sign_init(ctx->op.sig.algctx, provkey, params);
         break;
+    case EVP_PKEY_OP_SIGNMSG:
+        if (signature->sign_message_init == NULL) {
+            ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
+            ret = -2;
+            goto err;
+        }
+        ret = signature->sign_message_init(ctx->op.sig.algctx, provkey, params);
+        break;
     case EVP_PKEY_OP_VERIFY:
         if (signature->verify_init == NULL) {
             ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
@@ -537,14 +747,21 @@ static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation,
         }
         ret = signature->verify_init(ctx->op.sig.algctx, provkey, params);
         break;
+    case EVP_PKEY_OP_VERIFYMSG:
+        if (signature->verify_message_init == NULL) {
+            ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
+            ret = -2;
+            goto err;
+        }
+        ret = signature->verify_message_init(ctx->op.sig.algctx, provkey, params);
+        break;
     case EVP_PKEY_OP_VERIFYRECOVER:
         if (signature->verify_recover_init == NULL) {
             ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
             ret = -2;
             goto err;
         }
-        ret = signature->verify_recover_init(ctx->op.sig.algctx, provkey,
-                                             params);
+        ret = signature->verify_recover_init(ctx->op.sig.algctx, provkey, params);
         break;
     default:
         ERR_raise(ERR_LIB_EVP, EVP_R_INITIALIZATION_ERROR);
@@ -615,12 +832,69 @@ static int evp_pkey_signature_init(EVP_PKEY_CTX *ctx, int operation,
 
 int EVP_PKEY_sign_init(EVP_PKEY_CTX *ctx)
 {
-    return evp_pkey_signature_init(ctx, EVP_PKEY_OP_SIGN, NULL);
+    return evp_pkey_signature_init(ctx, NULL, EVP_PKEY_OP_SIGN, NULL);
 }
 
 int EVP_PKEY_sign_init_ex(EVP_PKEY_CTX *ctx, const OSSL_PARAM params[])
 {
-    return evp_pkey_signature_init(ctx, EVP_PKEY_OP_SIGN, params);
+    return evp_pkey_signature_init(ctx, NULL, EVP_PKEY_OP_SIGN, params);
+}
+
+int EVP_PKEY_sign_init_ex2(EVP_PKEY_CTX *ctx,
+                           EVP_SIGNATURE *algo, const OSSL_PARAM params[])
+{
+    return evp_pkey_signature_init(ctx, algo, EVP_PKEY_OP_SIGN, params);
+}
+
+int EVP_PKEY_sign_message_init(EVP_PKEY_CTX *ctx,
+                               EVP_SIGNATURE *algo, const OSSL_PARAM params[])
+{
+    return evp_pkey_signature_init(ctx, algo, EVP_PKEY_OP_SIGNMSG, params);
+}
+
+int EVP_PKEY_sign_message_update(EVP_PKEY_CTX *ctx,
+                                 const unsigned char *in, size_t inlen)
+{
+    if (ctx == NULL) {
+        ERR_raise(ERR_LIB_EVP, ERR_R_PASSED_NULL_PARAMETER);
+        return -1;
+    }
+
+    if (ctx->operation != EVP_PKEY_OP_SIGNMSG) {
+        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_INITIALIZED);
+        return -1;
+    }
+
+    if (ctx->op.sig.signature->sign_message_update == NULL) {
+        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
+        return -2;
+    }
+
+    return ctx->op.sig.signature->sign_message_update(ctx->op.sig.algctx,
+                                                      in, inlen);
+}
+
+int EVP_PKEY_sign_message_final(EVP_PKEY_CTX *ctx,
+                                unsigned char *sig, size_t *siglen)
+{
+    if (ctx == NULL) {
+        ERR_raise(ERR_LIB_EVP, ERR_R_PASSED_NULL_PARAMETER);
+        return -1;
+    }
+
+    if (ctx->operation != EVP_PKEY_OP_SIGNMSG) {
+        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_INITIALIZED);
+        return -1;
+    }
+
+    if (ctx->op.sig.signature->sign_message_final == NULL) {
+        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
+        return -2;
+    }
+
+    return ctx->op.sig.signature->sign_message_final(ctx->op.sig.algctx,
+                                                     sig, siglen,
+                                                     (sig == NULL) ? 0 : *siglen);
 }
 
 int EVP_PKEY_sign(EVP_PKEY_CTX *ctx,
@@ -634,7 +908,8 @@ int EVP_PKEY_sign(EVP_PKEY_CTX *ctx,
         return -1;
     }
 
-    if (ctx->operation != EVP_PKEY_OP_SIGN) {
+    if (ctx->operation != EVP_PKEY_OP_SIGN
+        && ctx->operation != EVP_PKEY_OP_SIGNMSG) {
         ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_INITIALIZED);
         return -1;
     }
@@ -664,12 +939,88 @@ int EVP_PKEY_sign(EVP_PKEY_CTX *ctx,
 
 int EVP_PKEY_verify_init(EVP_PKEY_CTX *ctx)
 {
-    return evp_pkey_signature_init(ctx, EVP_PKEY_OP_VERIFY, NULL);
+    return evp_pkey_signature_init(ctx, NULL, EVP_PKEY_OP_VERIFY, NULL);
 }
 
 int EVP_PKEY_verify_init_ex(EVP_PKEY_CTX *ctx, const OSSL_PARAM params[])
 {
-    return evp_pkey_signature_init(ctx, EVP_PKEY_OP_VERIFY, params);
+    return evp_pkey_signature_init(ctx, NULL, EVP_PKEY_OP_VERIFY, params);
+}
+
+int EVP_PKEY_verify_init_ex2(EVP_PKEY_CTX *ctx,
+                             EVP_SIGNATURE *algo, const OSSL_PARAM params[])
+{
+    return evp_pkey_signature_init(ctx, algo, EVP_PKEY_OP_VERIFY, params);
+}
+
+int EVP_PKEY_verify_message_init(EVP_PKEY_CTX *ctx,
+                                 EVP_SIGNATURE *algo, const OSSL_PARAM params[])
+{
+    return evp_pkey_signature_init(ctx, algo, EVP_PKEY_OP_VERIFYMSG, params);
+}
+
+int EVP_PKEY_CTX_set_signature(EVP_PKEY_CTX *ctx,
+                               const unsigned char *sig, size_t siglen)
+{
+    OSSL_PARAM sig_params[2], *p = sig_params;
+
+    if (ctx == NULL) {
+        ERR_raise(ERR_LIB_EVP, ERR_R_PASSED_NULL_PARAMETER);
+        return 0;
+    }
+
+    *p++ = OSSL_PARAM_construct_octet_string(OSSL_SIGNATURE_PARAM_SIGNATURE,
+                                             /*
+                                              * Cast away the const. This is
+                                              * read only so should be safe
+                                              */
+                                             (char *)sig, siglen);
+    *p = OSSL_PARAM_construct_end();
+
+    return EVP_PKEY_CTX_set_params(ctx, sig_params);
+}
+
+int EVP_PKEY_verify_message_update(EVP_PKEY_CTX *ctx,
+                                   const unsigned char *in, size_t inlen)
+{
+    if (ctx == NULL) {
+        ERR_raise(ERR_LIB_EVP, ERR_R_PASSED_NULL_PARAMETER);
+        return -1;
+    }
+
+    if (ctx->operation != EVP_PKEY_OP_VERIFYMSG) {
+        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_INITIALIZED);
+        return -1;
+    }
+
+    if (ctx->op.sig.signature->verify_message_update == NULL) {
+        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
+        return -2;
+    }
+
+    return ctx->op.sig.signature->verify_message_update(ctx->op.sig.algctx,
+                                                        in, inlen);
+}
+
+int EVP_PKEY_verify_message_final(EVP_PKEY_CTX *ctx)
+{
+    if (ctx == NULL) {
+        ERR_raise(ERR_LIB_EVP, ERR_R_PASSED_NULL_PARAMETER);
+        return -1;
+    }
+
+    if (ctx->operation != EVP_PKEY_OP_VERIFYMSG) {
+        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_INITIALIZED);
+        return -1;
+    }
+
+    if (ctx->op.sig.signature->verify_message_final == NULL) {
+        ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE);
+        return -2;
+    }
+
+    /* The signature must have been set with EVP_PKEY_CTX_set_signature() */
+    return ctx->op.sig.signature->verify_message_final(ctx->op.sig.algctx);
 }
 
 int EVP_PKEY_verify(EVP_PKEY_CTX *ctx,
@@ -683,7 +1034,8 @@ int EVP_PKEY_verify(EVP_PKEY_CTX *ctx,
         return -1;
     }
 
-    if (ctx->operation != EVP_PKEY_OP_VERIFY) {
+    if (ctx->operation != EVP_PKEY_OP_VERIFY
+        && ctx->operation != EVP_PKEY_OP_VERIFYMSG) {
         ERR_raise(ERR_LIB_EVP, EVP_R_OPERATION_NOT_INITIALIZED);
         return -1;
     }
@@ -711,13 +1063,19 @@ int EVP_PKEY_verify(EVP_PKEY_CTX *ctx,
 
 int EVP_PKEY_verify_recover_init(EVP_PKEY_CTX *ctx)
 {
-    return evp_pkey_signature_init(ctx, EVP_PKEY_OP_VERIFYRECOVER, NULL);
+    return evp_pkey_signature_init(ctx, NULL, EVP_PKEY_OP_VERIFYRECOVER, NULL);
 }
 
 int EVP_PKEY_verify_recover_init_ex(EVP_PKEY_CTX *ctx,
                                     const OSSL_PARAM params[])
 {
-    return evp_pkey_signature_init(ctx, EVP_PKEY_OP_VERIFYRECOVER, params);
+    return evp_pkey_signature_init(ctx, NULL, EVP_PKEY_OP_VERIFYRECOVER, params);
+}
+
+int EVP_PKEY_verify_recover_init_ex2(EVP_PKEY_CTX *ctx,
+                                     EVP_SIGNATURE *algo, const OSSL_PARAM params[])
+{
+    return evp_pkey_signature_init(ctx, algo, EVP_PKEY_OP_VERIFYRECOVER, params);
 }
 
 int EVP_PKEY_verify_recover(EVP_PKEY_CTX *ctx,
diff --git a/doc/man3/EVP_PKEY_sign.pod b/doc/man3/EVP_PKEY_sign.pod
index 6752432bd5..18e09bbdd8 100644
--- a/doc/man3/EVP_PKEY_sign.pod
+++ b/doc/man3/EVP_PKEY_sign.pod
@@ -2,8 +2,9 @@
 
 =head1 NAME
 
-EVP_PKEY_sign_init, EVP_PKEY_sign_init_ex, EVP_PKEY_sign
-- sign using a public key algorithm
+EVP_PKEY_sign_init, EVP_PKEY_sign_init_ex, EVP_PKEY_sign_init_ex2,
+EVP_PKEY_sign, EVP_PKEY_sign_message_init, EVP_PKEY_sign_message_update,
+EVP_PKEY_sign_message_final - sign using a public key algorithm
 
 =head1 SYNOPSIS
 
@@ -11,6 +12,14 @@ EVP_PKEY_sign_init, EVP_PKEY_sign_init_ex, EVP_PKEY_sign
 
  int EVP_PKEY_sign_init(EVP_PKEY_CTX *ctx);
  int EVP_PKEY_sign_init_ex(EVP_PKEY_CTX *ctx, const OSSL_PARAM params[]);
+ int EVP_PKEY_sign_init_ex2(EVP_PKEY_CTX *ctx, EVP_SIGNATURE *algo,
+                            const OSSL_PARAM params[]);
+ int EVP_PKEY_sign_message_init(EVP_PKEY_CTX *ctx, EVP_SIGNATURE *algo,
+                                const OSSL_PARAM params[]);
+ int EVP_PKEY_sign_message_update(EVP_PKEY_CTX *ctx,
+                                  unsigned char *in, size_t inlen);
+ int EVP_PKEY_sign_message_final(EVP_PKEY_CTX *ctx, unsigned char *sig,
+                                 size_t *siglen, size_t sigsize);
  int EVP_PKEY_sign(EVP_PKEY_CTX *ctx,
                    unsigned char *sig, size_t *siglen,
                    const unsigned char *tbs, size_t tbslen);
@@ -26,37 +35,120 @@ for more information about implicit fetches.
 EVP_PKEY_sign_init_ex() is the same as EVP_PKEY_sign_init() but additionally
 sets the passed parameters I<params> on the context before returning.
 
-The EVP_PKEY_sign() function performs a public key signing operation
-using I<ctx>. The data to be signed is specified using the I<tbs> and
-I<tbslen> parameters. If I<sig> is NULL then the maximum size of the output
-buffer is written to the I<siglen> parameter. If I<sig> is not NULL then
-before the call the I<siglen> parameter should contain the length of the
-I<sig> buffer, if the call is successful the signature is written to
-I<sig> and the amount of data written to I<siglen>.
+EVP_PKEY_sign_init_ex2() initializes a public key algorithm context I<ctx> for
+signing a pre-computed message digest using the algorithm given by I<algo> and
+the key given through L<EVP_PKEY_CTX_new(3)> or L<EVP_PKEY_CTX_new_from_pkey(3)>.
+A context I<ctx> without a pre-loaded key cannot be used with this function.
+This function provides almost the same functionality as EVP_PKEY_sign_init_ex(),
+but is uniquely intended to be used with a pre-computed messsage digest, and
+allows pre-determining the exact conditions for that message digest, if a
+composite signature algorithm (such as RSA-SHA256) was fetched.
+Following a call to this function, setting parameters that modifies the digest
+implementation or padding is not normally supported.
+
+EVP_PKEY_sign_message_init() initializes a public key algorithm context I<ctx>
+for signing an unlimited size message using the algorithm given by I<algo> and
+the key given through L<EVP_PKEY_CTX_new(3)> or L<EVP_PKEY_CTX_new_from_pkey(3)>.
+Passing the message is supported both in a one-shot fashion using
+EVP_PKEY_sign(), and through the combination of EVP_PKEY_sign_message_update()
+and EVP_PKEY_sign_message_final().
+This function enables using algorithms that can process input of arbitrary
+length, such as ED25519, RSA-SHA256 and similar.
+
+EVP_PKEY_sign_message_update() adds I<inlen> bytes from I<in> to the data to be
+processed for signature.  The signature algorithm specification and
+implementation determine how the input bytes are processed and if there's a
+limit on the total size of the input.  See L</NOTES> below for a deeper
+explanation.
+
+EVP_PKEY_sign_message_final() signs the processed data and places the data in
+I<sig>, and the number of signature bytes in I<*siglen>, if the number of
+bytes doesn't surpass the size given by I<sigsize>.
+I<sig> may be NULL, and in that case, only I<*siglen> is updated with the
+number of signature bytes.
+
+EVP_PKEY_sign() is a one-shot function that can be used with all the init
+functions above.
+When initialization was done with EVP_PKEY_sign_init(), EVP_PKEY_sign_init_ex()
+or EVP_PKEY_sign_init_ex2(), the data specified by I<tbs> and I<tbslen> is
+signed after appropriate padding.
+When initialization was done with EVP_PKEY_sign_message_init(), the data
+specified by I<tbs> and I<tbslen> is digested by the implied message digest
+algorithm, and the result is signed after appropriate padding.
+If I<sig> is NULL then the maximum size of the output buffer is written to the
+I<siglen> parameter.
+If I<sig> is not NULL, then before the call the I<siglen> parameter should
+contain the length of the I<sig> buffer, and if the call is successful the
+signature is written to I<sig> and the amount of data written to I<siglen>.
 
 =head1 NOTES
 
-EVP_PKEY_sign() does not hash the data to be signed, and therefore is
-normally used to sign digests. For signing arbitrary messages, see the
-L<EVP_DigestSignInit(3)> and
-L<EVP_SignInit(3)> signing interfaces instead.
+=begin comment
 
-After the call to EVP_PKEY_sign_init() algorithm specific control
-operations can be performed to set any appropriate parameters for the
-operation (see L<EVP_PKEY_CTX_ctrl(3)>).
+These notes are largely replicated in EVP_PKEY_verify.pod, please keep them
+in sync.
 
-The function EVP_PKEY_sign() can be called more than once on the same
-context if several operations are performed using the same parameters.
+=end comment
+
+=head2 General
+
+Some signature implementations only accumulate the input data and do no
+further processing before signing it (they expect the input to be a digest),
+while others compress the data, typically by internally producing a digest,
+and signing the result.
+Some of them support both modes of operation at the same time.
+The caller is expected to know how the chosen algorithm is supposed to behave
+and under what conditions.
+
+For example, an RSA implementation can be expected to only expect a message
+digest as input, while ED25519 can be expected to process the input with a hash,
+i.e. to produce the message digest internally, and while RSA-SHA256 can be
+expected to handle either mode of operation, depending on if the operation was
+initialized with EVP_PKEY_sign_init_ex2() or with EVP_PKEY_sign_message_init(). 
+
+Similarly, an RSA implementation usually expects additional details to be set,
+like the message digest algorithm that the input is supposed to be digested
+with, as well as the padding mode (see L<EVP_PKEY_CTX_set_signature_md(3)> and
+L<EVP_PKEY_CTX_set_rsa_padding(3)> and similar others), while an RSA-SHA256
+implementation usually has these details pre-set and immutable.
+
+The functions described here can't be used to combine separate algorithms.  In
+particular, neither L<EVP_PKEY_CTX_set_signature_md(3)> nor the B<OSSL_PARAM>
+parameter "digest" (B<OSSL_SIGNATURE_PARAM_DIGEST>) can be used to combine a
+signature algorithm with a hash algorithm to process the input.  In other
+words, it's not possible to specify a I<ctx> pre-loaded with an RSA pkey, or
+an I<algo> that fetched C<RSA> and try to specify SHA256 separately to get the
+functionality of RSA-SHA256.  If combining algorithms in that manner is
+desired, please use L<EVP_DigestSignInit(3)> and associated functions.
+
+=head2 Performing multiple signatures
+
+When initialized using EVP_PKEY_sign_init_ex() or  EVP_PKEY_sign_init_ex2(),
+EVP_PKEY_sign() can be called more than once on the same context to have
+several one-shot operations performed using the same parameters.
+
+When initialized using EVP_PKEY_sign_message_init(), it's not possible to
+call EVP_PKEY_sign() multiple times.
 
 =head1 RETURN VALUES
 
-EVP_PKEY_sign_init() and EVP_PKEY_sign() return 1 for success and 0
-or a negative value for failure. In particular a return value of -2
-indicates the operation is not supported by the public key algorithm.
+All functions return 1 for success and 0 or a negative value for failure.
+
+In particular, EVP_PKEY_sign_init() and its other variants may return -2 to
+indicate that the operation is not supported by the public key algorithm.
 
 =head1 EXAMPLES
 
-Sign data using RSA with PKCS#1 padding and SHA256 digest:
+=begin comment
+
+These examples are largely replicated in EVP_PKEY_verify.pod, please keep them
+in sync.
+
+=end comment
+
+=head2 RSA with PKCS#1 padding for SHA256
+
+Sign data using RSA with PKCS#1 padding and a SHA256 digest as input:
 
  #include <openssl/evp.h>
  #include <openssl/rsa.h>
@@ -73,7 +165,7 @@ Sign data using RSA with PKCS#1 padding and SHA256 digest:
   * point to the SHA-256 digest to be signed.
   */
  ctx = EVP_PKEY_CTX_new(signing_key, NULL /* no engine */);
- if (!ctx)
+ if (ctx == NULL)
      /* Error occurred */
  if (EVP_PKEY_sign_init(ctx) <= 0)
      /* Error */
@@ -88,7 +180,50 @@ Sign data using RSA with PKCS#1 padding and SHA256 digest:
 
  sig = OPENSSL_malloc(siglen);
 
- if (!sig)
+ if (sig == NULL)
+     /* malloc failure */
+
+ if (EVP_PKEY_sign(ctx, sig, &siglen, md, mdlen) <= 0)
+     /* Error */
+
+ /* Signature is siglen bytes written to buffer sig */
+
+=head2 RSA-SHA256 with a pre-computed digest
+
+Sign a digest with RSA-SHA256 using one-shot functions.  To be noted is that
+RSA-SHA256 is assumed to be an implementation of C<sha256WithRSAEncryption>,
+for which the padding is pre-determined to be B<RSA_PKCS1_PADDING>, and the
+input digest is assumed to have been computed using SHA256.
+
+ #include <openssl/evp.h>
+ #include <openssl/rsa.h>
+
+ EVP_PKEY_CTX *ctx;
+ /* md is a SHA-256 digest in this example. */
+ unsigned char *md, *sig;
+ size_t mdlen = 32, siglen;
+ EVP_PKEY *signing_key;
+
+ /*
+  * NB: assumes signing_key and md are set up before the next
+  * step. signing_key must be an RSA private key and md must
+  * point to the SHA-256 digest to be signed.
+  */
+ ctx = EVP_PKEY_CTX_new(signing_key, NULL /* no engine */);
+ alg = EVP_SIGNATURE_fetch(NULL, "RSA-SHA256", NULL);
+
+ if (ctx == NULL)
+     /* Error occurred */
+ if (EVP_PKEY_sign_init_ex2(ctx, alg, NULL) <= 0)
+     /* Error */
+
+ /* Determine buffer length */
+ if (EVP_PKEY_sign(ctx, NULL, &siglen, md, mdlen) <= 0)
+     /* Error */
+
+ sig = OPENSSL_malloc(siglen);
+
+ if (sig == NULL)
      /* malloc failure */
 
  if (EVP_PKEY_sign(ctx, sig, &siglen, md, mdlen) <= 0)
@@ -97,6 +232,109 @@ Sign data using RSA with PKCS#1 padding and SHA256 digest:
  /* Signature is siglen bytes written to buffer sig */
 
 
+=head2 RSA-SHA256, one-shot
+
+Sign a document with RSA-SHA256 using one-shot functions.
+To be noted is that RSA-SHA256 is assumed to be an implementation of
+C<sha256WithRSAEncryption>, for which the padding is pre-determined to be
+B<RSA_PKCS1_PADDING>.
+
+ #include <openssl/evp.h>
+ #include <openssl/rsa.h>
+
+ EVP_PKEY_CTX *ctx;
+ /* in is the input in this example. */
+ unsigned char *in, *sig;
+ /* inlen is the length of the input in this example. */
+ size_t inlen, siglen;
+ EVP_PKEY *signing_key;
+ EVP_SIGNATURE *alg;
+
+ /*
+  * NB: assumes signing_key, in and inlen are set up before
+  * the next step. signing_key must be an RSA private key,
+  * in must point to data to be digested and signed, and
+  * inlen must be the size of the data in bytes.
+  */
+ ctx = EVP_PKEY_CTX_new(signing_key, NULL /* no engine */);
+ alg = EVP_SIGNATURE_fetch(NULL, "RSA-SHA256", NULL);
+
+ if (ctx == NULL || alg == NULL)
+     /* Error occurred */
+ if (EVP_PKEY_sign_message_init(ctx, alg, NULL) <= 0)
+     /* Error */
+
+ /* Determine sig buffer length */
+ if (EVP_PKEY_sign(ctx, NULL, &siglen, in, inlen) <= 0)
+     /* Error */
+
+ sig = OPENSSL_malloc(siglen);
+
+ if (sig == NULL)
+     /* malloc failure */
+
+ if (EVP_PKEY_sign(ctx, sig, &siglen, in, inlen) <= 0)
+     /* Error */
+
+ /* Signature is siglen bytes written to buffer sig */
+
+
+=head2 RSA-SHA256, using update and final
+
+This is the same as the previous example, but allowing stream-like
+functionality.
+
+ #include <openssl/evp.h>
+ #include <openssl/rsa.h>
+
+ EVP_PKEY_CTX *ctx;
+ /* in is the input in this example. */
+ unsigned char *in, *sig;
+ /* inlen is the length of the input in this example. */
+ size_t inlen, siglen;
+ EVP_PKEY *signing_key;
+ EVP_SIGNATURE *alg;
+
+ /*
+  * NB: assumes signing_key, in and inlen are set up before
+  * the next step. signing_key must be an RSA private key,
+  * in must point to data to be digested and signed, and
+  * inlen must be the size of the data in bytes.
+  */
+ ctx = EVP_PKEY_CTX_new(signing_key, NULL /* no engine */);
+ alg = EVP_SIGNATURE_fetch(NULL, "RSA-SHA256", NULL);
+
+ if (ctx == NULL || alg == NULL)
+     /* Error occurred */
+ if (EVP_PKEY_sign_message_init(ctx, alg, NULL) <= 0)
+     /* Error */
+
+ while (inlen > 0) {
+     if (EVP_PKEY_sign_message_update(ctx, in, inlen)) <= 0)
+         /* Error */
+     if (inlen > 256) {
+         inlen -= 256;
+         in += 256;
+     } else {
+         inlen = 0;
+     }
+ }
+
+ /* Determine sig buffer length */
+ if (EVP_PKEY_sign_message_final(ctx, NULL, &siglen) <= 0)
+     /* Error */
+
+ sig = OPENSSL_malloc(siglen);
+
+ if (sig == NULL)
+     /* malloc failure */
+
+ if (EVP_PKEY_sign_message_final(ctx, sig, &siglen) <= 0)
+     /* Error */
+
+ /* Signature is siglen bytes written to buffer sig */
+
+
 =head1 SEE ALSO
 
 L<EVP_PKEY_CTX_new(3)>,
@@ -114,6 +352,10 @@ OpenSSL 1.0.0.
 
 The EVP_PKEY_sign_init_ex() function was added in OpenSSL 3.0.
 
+The EVP_PKEY_sign_init_ex2(), EVP_PKEY_sign_message_init(),
+EVP_PKEY_sign_message_update() and EVP_PKEY_sign_message_final() functions
+where added in OpenSSL 3.4.
+
 =head1 COPYRIGHT
 
 Copyright 2006-2021 The OpenSSL Project Authors. All Rights Reserved.
diff --git a/doc/man3/EVP_PKEY_verify.pod b/doc/man3/EVP_PKEY_verify.pod
index 77023cab87..26b1794f99 100644
--- a/doc/man3/EVP_PKEY_verify.pod
+++ b/doc/man3/EVP_PKEY_verify.pod
@@ -2,8 +2,10 @@
 
 =head1 NAME
 
-EVP_PKEY_verify_init, EVP_PKEY_verify_init_ex, EVP_PKEY_verify
-- signature verification using a public key algorithm
+EVP_PKEY_verify_init, EVP_PKEY_verify_init_ex, EVP_PKEY_verify_init_ex2,
+EVP_PKEY_verify, EVP_PKEY_verify_message_init, EVP_PKEY_verify_message_update,
+EVP_PKEY_verify_message_final, EVP_PKEY_CTX_set_signature - signature
+verification using a public key algorithm
 
 =head1 SYNOPSIS
 
@@ -11,6 +13,15 @@ EVP_PKEY_verify_init, EVP_PKEY_verify_init_ex, EVP_PKEY_verify
 
  int EVP_PKEY_verify_init(EVP_PKEY_CTX *ctx);
  int EVP_PKEY_verify_init_ex(EVP_PKEY_CTX *ctx, const OSSL_PARAM params[]);
+ int EVP_PKEY_verify_init_ex2(EVP_PKEY_CTX *ctx, EVP_SIGNATURE *algo,
+                              const OSSL_PARAM params[]);
+ int EVP_PKEY_verify_message_init(EVP_PKEY_CTX *ctx, EVP_SIGNATURE *algo,
+                                  const OSSL_PARAM params[]);
+ int EVP_PKEY_CTX_set_signature(EVP_PKEY_CTX *pctx,
+                                const unsigned char *sig, size_t siglen);
+ int EVP_PKEY_verify_message_update(EVP_PKEY_CTX *ctx,
+                                    unsigned char *in, size_t inlen);
+ int EVP_PKEY_verify_message_final(EVP_PKEY_CTX *ctx);
  int EVP_PKEY_verify(EVP_PKEY_CTX *ctx,
                      const unsigned char *sig, size_t siglen,
                      const unsigned char *tbs, size_t tbslen);
@@ -18,7 +29,7 @@ EVP_PKEY_verify_init, EVP_PKEY_verify_init_ex, EVP_PKEY_verify
 =head1 DESCRIPTION
 
 EVP_PKEY_verify_init() initializes a public key algorithm context I<ctx> for
-signing using the algorithm given when the context was created
+verification using the algorithm given when the context was created
 using L<EVP_PKEY_CTX_new(3)> or variants thereof.  The algorithm is used to
 fetch a B<EVP_SIGNATURE> method implicitly, see L<provider(7)/Implicit fetch>
 for more information about implicit fetches.
@@ -26,27 +37,113 @@ for more information about implicit fetches.
 EVP_PKEY_verify_init_ex() is the same as EVP_PKEY_verify_init() but additionally
 sets the passed parameters I<params> on the context before returning.
 
-The EVP_PKEY_verify() function performs a public key verification operation
-using I<ctx>. The signature is specified using the I<sig> and
-I<siglen> parameters. The verified data (i.e. the data believed originally
-signed) is specified using the I<tbs> and I<tbslen> parameters.
+EVP_PKEY_verify_init_ex2() is the same as EVP_PKEY_verify_init_ex(), but works
+with an explicitly fetched B<EVP_SIGNATURE> I<algo>.
+A context I<ctx> without a pre-loaded key cannot be used with this function.
+Depending on what algorithm was fetched, certain details revolving around the
+treatment of the input to EVP_PKEY_verify() may be pre-determined, and in that
+case, those details may normally not be changed.
+See L</NOTES> below for a deeper explanation.
+
+EVP_PKEY_verify_message_init() initializes a public key algorithm context
+I<ctx> for verifying an unlimited size message using the algorithm given by
+I<algo> and the key given through L<EVP_PKEY_CTX_new(3)> or
+L<EVP_PKEY_CTX_new_from_pkey(3)>.
+Passing the message is supported both in a one-shot fashion using
+EVP_PKEY_verify(), and through the combination of EVP_PKEY_verify_update() and
+EVP_PKEY_verify_final().
+This function enables using algorithms that can process input of arbitrary
+length, such as ED25519, RSA-SHA256 and similar.
+
+EVP_PKEY_CTX_set_signature() specifies the I<siglen> bytes long signature
+I<sig> to be verified against by EVP_PKEY_verify_final().
+It I<must> be used together with EVP_PKEY_verify_update() and
+EVP_PKEY_verify_final().
+See L</NOTES> below for a deeper explanation.
+
+EVP_PKEY_verify_update() adds I<inlen> bytes from I<in> to the data to be
+processed for verification.  The signature algorithm specification and
+implementation determine how the input bytes are processed and if there's a
+limit on the total size of the input.  See L</NOTES> below for a deeper
+explanation.
+
+EVP_PKEY_verify_final() verifies the processed data, given only I<ctx>.
+The signature to verify against must have been given with
+EVP_PKEY_CTX_set_signature().
+
+EVP_PKEY_verify() is a one-shot function that performs the same thing as
+EVP_PKEY_CTX_set_signature() call with I<sig> and I<siglen> as parameters,
+followed by a single EVP_PKEY_verify_update() call with I<tbs> and I<tbslen>,
+followed by EVP_PKEY_verify_final() call.
 
 =head1 NOTES
 
-After the call to EVP_PKEY_verify_init() algorithm specific control
-operations can be performed to set any appropriate parameters for the
-operation.
+=begin comment
+
+These notes are largely replicated in EVP_PKEY_sign.pod, please keep them
+in sync.
+
+=end comment
+
+=head2 General
+
+Some signature implementations only accumulate the input data and do no
+further processing before verifying it (they expect the input to be a digest),
+while others compress the data, typically by internally producing a digest,
+and signing the result, which is then verified against a given signature.
+Some of them support both modes of operation at the same time.
+The caller is expected to know how the chosen algorithm is supposed to behave
+and under what conditions.
+
+For example, an RSA implementation can be expected to only expect a digest as
+input, while ED25519 can be expected to process the input with a hash, i.e.
+to produce the digest internally, and while RSA-SHA256 can be expected to
+handle either mode of operation, depending on if the operation was initialized
+with EVP_PKEY_verify_init_ex2() or with EVP_PKEY_verify_message_init().
+
+Similarly, an RSA implementation usually expects additional details to be set,
+like the message digest algorithm that the input is supposed to be digested
+with, as well as the padding mode (see L<EVP_PKEY_CTX_set_signature_md(3)> and
+L<EVP_PKEY_CTX_set_rsa_padding(3)> and similar others), while an RSA-SHA256
+implementation usually has these details pre-set and immutable.
 
-The function EVP_PKEY_verify() can be called more than once on the same
-context if several operations are performed using the same parameters.
+The functions described here can't be used to combine separate algorithms.  In
+particular, neither L<EVP_PKEY_CTX_set_signature_md(3)> nor the B<OSSL_PARAM>
+parameter "digest" (B<OSSL_SIGNATURE_PARAM_DIGEST>) can be used to combine a
+signature algorithm with a hash algorithm to process the input.  In other
+words, it's not possible to specify a I<ctx> pre-loaded with an RSA pkey, or
+an I<algo> that fetched C<RSA> and try to specify SHA256 separately to get the
+functionality of RSA-SHA256.  If combining algorithms in that manner is
+desired, please use L<EVP_DigestVerifyInit(3)> and associated functions, or
+L<EVP_VerifyInit(3)> and associated functions.
+
+=head2 Performing multiple verifications
+
+When initialized using EVP_PKEY_verify_init_ex() or  EVP_PKEY_verify_init_ex2(),
+EVP_PKEY_verify() can be called more than once on the same context to have
+several one-shot operations performed using the same parameters.
+
+When initialized using EVP_PKEY_verify_message_init(), it's not possible to
+call EVP_PKEY_verify() multiple times.
+
+=head2 On EVP_PKEY_CTX_set_signature()
+
+Some signature algorithms (such as LMS) require the signature verification
+data be specified before verifying the message.
+Other algorithms allow the signature to be specified late.
+To allow either way (which may depend on the application's flow of input), the
+signature to be verified against I<must> be specified using this function when
+using EVP_PKEY_verify_message_update() and EVP_PKEY_verify_message_final() to
+perform the verification.
 
 =head1 RETURN VALUES
 
-EVP_PKEY_verify_init() and EVP_PKEY_verify() return 1 if the verification was
-successful and 0 if it failed. Unlike other functions the return value 0 from
-EVP_PKEY_verify() only indicates that the signature did not verify
-successfully (that is tbs did not match the original data or the signature was
-of invalid form) it is not an indication of a more serious error.
+All functions return 1 for success and 0 or a negative value for failure.
+However, unlike other functions, the return value 0 from EVP_PKEY_verify(),
+EVP_PKEY_verify_recover() and EVP_PKEY_verify_message_final() only indicates
+that the signature did not verify successfully (that is tbs did not match the
+original data or the signature was of invalid form) it is not an indication of
+a more serious error.
 
 A negative value indicates an error other that signature verification failure.
 In particular a return value of -2 indicates the operation is not supported by
@@ -54,7 +151,16 @@ the public key algorithm.
 
 =head1 EXAMPLES
 
-Verify signature using PKCS#1 and SHA256 digest:
+=begin comment
+
+These examples are largely replicated in EVP_PKEY_sign.pod, please keep them
+in sync.
+
+=end comment
+
+=head2 RSA with PKCS#1 padding for SHA256
+
+Verify signature using PKCS#1 padding and a SHA256 digest as input:
 
  #include <openssl/evp.h>
  #include <openssl/rsa.h>
@@ -69,7 +175,7 @@ Verify signature using PKCS#1 and SHA256 digest:
   * and that verify_key is an RSA public key
   */
  ctx = EVP_PKEY_CTX_new(verify_key, NULL /* no engine */);
- if (!ctx)
+ if (ctx == NULL)
      /* Error occurred */
  if (EVP_PKEY_verify_init(ctx) <= 0)
      /* Error */
@@ -86,6 +192,138 @@ Verify signature using PKCS#1 and SHA256 digest:
   * other error.
   */
 
+=head2 RSA-SHA256 with a pre-computed digest
+
+Verify a digest with RSA-SHA256 using one-shot functions.  To be noted is that
+RSA-SHA256 is assumed to be an implementation of C<sha256WithRSAEncryption>,
+for which the padding is pre-determined to be B<RSA_PKCS1_PADDING>, and the
+input digest is assumed to have been computed using SHA256.
+
+ #include <openssl/evp.h>
+ #include <openssl/rsa.h>
+
+ EVP_PKEY_CTX *ctx;
+ /* md is a SHA-256 digest in this example. */
+ unsigned char *md, *sig;
+ size_t mdlen = 32, siglen;
+ EVP_PKEY *signing_key;
+
+ /*
+  * NB: assumes verify_key, sig, siglen, md and mdlen are already set up
+  * and that verify_key is an RSA public key
+  */
+ ctx = EVP_PKEY_CTX_new(signing_key, NULL /* no engine */);
+ alg = EVP_SIGNATURE_fetch(NULL, "RSA-SHA256", NULL);
+
+ if (ctx == NULL)
+     /* Error occurred */
+ if (EVP_PKEY_verify_init_ex2(ctx, alg, NULL) <= 0)
+     /* Error */
+
+ /* Determine buffer length */
+ if (EVP_PKEY_verify(ctx, sig, siglen, md, mdlen) <= 0)
+     /* Error or signature doesn't verify */
+
+ /* Perform operation */
+ ret = EVP_PKEY_verify(ctx, sig, siglen, md, mdlen);
+
+ /*
+  * ret == 1 indicates success, 0 verify failure and < 0 for some
+  * other error.
+  */
+
+=head2 RSA-SHA256, one-shot
+
+Verify a document with RSA-SHA256 using one-shot functions.
+To be noted is that RSA-SHA256 is assumed to be an implementation of
+C<sha256WithRSAEncryption>, for which the padding is pre-determined to be
+B<RSA_PKCS1_PADDING>.
+
+ #include <openssl/evp.h>
+ #include <openssl/rsa.h>
+
+ EVP_PKEY_CTX *ctx;
+ /* in the input in this example. */
+ unsigned char *in, *sig;
+ /* inlen is the length of the input in this example. */
+ size_t inlen, siglen;
+ EVP_PKEY *signing_key;
+ EVP_SIGNATURE *alg;
+
+ /*
+  * NB: assumes signing_key, in and inlen are set up before
+  * the next step. signing_key must be an RSA private key,
+  * in must point to data to be digested and signed, and
+  * inlen must be the size of the data in bytes.
+  */
+ ctx = EVP_PKEY_CTX_new(signing_key, NULL /* no engine */);
+ alg = EVP_SIGNATURE_fetch(NULL, "RSA-SHA256", NULL);
+
+ if (ctx == NULL || alg == NULL)
+     /* Error occurred */
+ if (EVP_PKEY_verify_message_init(ctx, alg, NULL) <= 0)
+     /* Error */
+
+ /* Perform operation */
+ ret = EVP_PKEY_verify(ctx, sig, siglen, in, inlen);
+
+ /*
+  * ret == 1 indicates success, 0 verify failure and < 0 for some
+  * other error.
+  */
+
+=head2 RSA-SHA256, using update and final
+
+This is the same as the previous example, but allowing stream-like
+functionality.
+
+ #include <openssl/evp.h>
+ #include <openssl/rsa.h>
+
+ EVP_PKEY_CTX *ctx;
+ /* in is the input in this example. */
+ unsigned char *in, *sig;
+ /* inlen is the length of the input in this example. */
+ size_t inlen, siglen;
+ EVP_PKEY *signing_key;
+ EVP_SIGNATURE *alg;
+
+ /*
+  * NB: assumes signing_key, in and inlen are set up before
+  * the next step. signing_key must be an RSA private key,
+  * in must point to data to be digested and signed, and
+  * inlen must be the size of the data in bytes.
+  */
+ ctx = EVP_PKEY_CTX_new(signing_key, NULL /* no engine */);
+ alg = EVP_SIGNATURE_fetch(NULL, "RSA-SHA256", NULL);
+
+ if (ctx == NULL || alg == NULL)
+     /* Error occurred */
+ if (EVP_PKEY_verify_message_init(ctx, alg, NULL) <= 0)
+     /* Error */
+
+ /* We have the signature, specify it early */
+ EVP_PKEY_CTX_set_signature(ctx, sig, siglen);
+
+ /* Perform operation */
+ while (inlen > 0) {
+     if (EVP_PKEY_verify_message_update(ctx, in, inlen)) <= 0)
+         /* Error */
+     if (inlen > 256) {
+         inlen -= 256;
+         in += 256;
+     } else {
+         inlen = 0;
+     }
+ }
+ ret = EVP_PKEY_verify_message_final(ctx);
+
+ /*
+  * ret == 1 indicates success, 0 verify failure and < 0 for some
+  * other error.
+  */
+
+
 =head1 SEE ALSO
 
 L<EVP_PKEY_CTX_new(3)>,
@@ -102,6 +340,10 @@ OpenSSL 1.0.0.
 
 The EVP_PKEY_verify_init_ex() function was added in OpenSSL 3.0.
 
+The EVP_PKEY_verify_init_ex2(), EVP_PKEY_verify_message_init(),
+EVP_PKEY_verify_message_update(), EVP_PKEY_verify_message_final() and
+EVP_PKEY_CTX_set_signature() functions where added in OpenSSL 3.4.
+
 =head1 COPYRIGHT
 
 Copyright 2006-2021 The OpenSSL Project Authors. All Rights Reserved.
diff --git a/doc/man3/EVP_PKEY_verify_recover.pod b/doc/man3/EVP_PKEY_verify_recover.pod
index 7f0a06c039..fd70031378 100644
--- a/doc/man3/EVP_PKEY_verify_recover.pod
+++ b/doc/man3/EVP_PKEY_verify_recover.pod
@@ -3,7 +3,7 @@
 =head1 NAME
 
 EVP_PKEY_verify_recover_init, EVP_PKEY_verify_recover_init_ex,
-EVP_PKEY_verify_recover
+EVP_PKEY_verify_recover_init_ex2, EVP_PKEY_verify_recover
 - recover signature using a public key algorithm
 
 =head1 SYNOPSIS
@@ -13,6 +13,8 @@ EVP_PKEY_verify_recover
  int EVP_PKEY_verify_recover_init(EVP_PKEY_CTX *ctx);
  int EVP_PKEY_verify_recover_init_ex(EVP_PKEY_CTX *ctx,
                                      const OSSL_PARAM params[]);
+ int EVP_PKEY_verify_recover_init_ex2(EVP_PKEY_CTX *ctx, EVP_SIGNATURE *algo,
+                                      const OSSL_PARAM params[]);
  int EVP_PKEY_verify_recover(EVP_PKEY_CTX *ctx,
                              unsigned char *rout, size_t *routlen,
                              const unsigned char *sig, size_t siglen);
@@ -29,6 +31,14 @@ EVP_PKEY_verify_recover_init_ex() is the same as
 EVP_PKEY_verify_recover_init() but additionally sets the passed parameters
 I<params> on the context before returning.
 
+EVP_PKEY_verify_recover_init_ex2() is the same as EVP_PKEY_verify_recover_init_ex(),
+but works with an explicitly fetched B<EVP_SIGNATURE> I<algo>.
+A context I<ctx> without a pre-loaded key cannot be used with this function.
+Depending on what algorithm was fetched, certain details revolving around the
+treatment of the input to EVP_PKEY_verify() may be pre-determined, and in that
+case, those details may normally not be changed.
+See L</NOTES> below for a deeper explanation.
+
 The EVP_PKEY_verify_recover() function recovers signed data
 using I<ctx>. The signature is specified using the I<sig> and
 I<siglen> parameters. If I<rout> is NULL then the maximum size of the output
@@ -51,6 +61,10 @@ After the call to EVP_PKEY_verify_recover_init() algorithm specific control
 operations can be performed to set any appropriate parameters for the
 operation.
 
+After the call to EVP_PKEY_verify_recover_init_ex2(), algorithm specific control
+operations may not be needed if the chosen algorithm implies that those controls
+pre-set (and immutable).
+
 The function EVP_PKEY_verify_recover() can be called more than once on the same
 context if several operations are performed using the same parameters.
 
diff --git a/include/openssl/core_dispatch.h b/include/openssl/core_dispatch.h
index 2769e75392..68b3321505 100644
--- a/include/openssl/core_dispatch.h
+++ b/include/openssl/core_dispatch.h
@@ -741,22 +741,45 @@ OSSL_CORE_MAKE_FUNC(const OSSL_PARAM *, keyexch_gettable_ctx_params,
 # define OSSL_FUNC_SIGNATURE_GETTABLE_CTX_MD_PARAMS 23
 # define OSSL_FUNC_SIGNATURE_SET_CTX_MD_PARAMS      24
 # define OSSL_FUNC_SIGNATURE_SETTABLE_CTX_MD_PARAMS 25
+# define OSSL_FUNC_SIGNATURE_QUERY_KEY_TYPES        26
+# define OSSL_FUNC_SIGNATURE_SIGN_MESSAGE_INIT      27
+# define OSSL_FUNC_SIGNATURE_SIGN_MESSAGE_UPDATE    28
+# define OSSL_FUNC_SIGNATURE_SIGN_MESSAGE_FINAL     29
+# define OSSL_FUNC_SIGNATURE_VERIFY_MESSAGE_INIT    30
+# define OSSL_FUNC_SIGNATURE_VERIFY_MESSAGE_UPDATE  31
+# define OSSL_FUNC_SIGNATURE_VERIFY_MESSAGE_FINAL   32
 
 OSSL_CORE_MAKE_FUNC(void *, signature_newctx, (void *provctx,
-                                                  const char *propq))
+                                               const char *propq))
 OSSL_CORE_MAKE_FUNC(int, signature_sign_init, (void *ctx, void *provkey,
                                                const OSSL_PARAM params[]))
 OSSL_CORE_MAKE_FUNC(int, signature_sign, (void *ctx,  unsigned char *sig,
-                                             size_t *siglen, size_t sigsize,
-                                             const unsigned char *tbs,
-                                             size_t tbslen))
+                                          size_t *siglen, size_t sigsize,
+                                          const unsigned char *tbs,
+                                          size_t tbslen))
+OSSL_CORE_MAKE_FUNC(int, signature_sign_message_init,
+                    (void *ctx, void *provkey, const OSSL_PARAM params[]))
+OSSL_CORE_MAKE_FUNC(int, signature_sign_message_update,
+                    (void *ctx, const unsigned char *in, size_t inlen))
+OSSL_CORE_MAKE_FUNC(int, signature_sign_message_final,
+                    (void *ctx, unsigned char *sig,
+                     size_t *siglen, size_t sigsize))
 OSSL_CORE_MAKE_FUNC(int, signature_verify_init, (void *ctx, void *provkey,
                                                  const OSSL_PARAM params[]))
 OSSL_CORE_MAKE_FUNC(int, signature_verify, (void *ctx,
-                                               const unsigned char *sig,
-                                               size_t siglen,
-                                               const unsigned char *tbs,
-                                               size_t tbslen))
+                                            const unsigned char *sig,
+                                            size_t siglen,
+                                            const unsigned char *tbs,
+                                            size_t tbslen))
+OSSL_CORE_MAKE_FUNC(int, signature_verify_message_init,
+                    (void *ctx, void *provkey, const OSSL_PARAM params[]))
+OSSL_CORE_MAKE_FUNC(int, signature_verify_message_update,
+                    (void *ctx, const unsigned char *in, size_t inlen))
+/*
+ * signature_verify_final requires that the signature to be verified against
+ * is specified via an OSSL_PARAM.
+ */
+OSSL_CORE_MAKE_FUNC(int, signature_verify_message_final, (void *ctx))
 OSSL_CORE_MAKE_FUNC(int, signature_verify_recover_init,
                     (void *ctx, void *provkey, const OSSL_PARAM params[]))
 OSSL_CORE_MAKE_FUNC(int, signature_verify_recover,
@@ -801,7 +824,7 @@ OSSL_CORE_MAKE_FUNC(int, signature_set_ctx_md_params,
                     (void *ctx, const OSSL_PARAM params[]))
 OSSL_CORE_MAKE_FUNC(const OSSL_PARAM *, signature_settable_ctx_md_params,
                     (void *ctx))
-
+OSSL_CORE_MAKE_FUNC(const char **, signature_query_key_types, (void))
 
 /* Asymmetric Ciphers */
 
diff --git a/include/openssl/evp.h b/include/openssl/evp.h
index 5ce5dbb234..97ca2a0831 100644
--- a/include/openssl/evp.h
+++ b/include/openssl/evp.h
@@ -1703,11 +1703,15 @@ const char *EVP_PKEY_get0_type_name(const EVP_PKEY *key);
 # define EVP_PKEY_OP_DERIVE              (1 << 11)
 # define EVP_PKEY_OP_ENCAPSULATE         (1 << 12)
 # define EVP_PKEY_OP_DECAPSULATE         (1 << 13)
+# define EVP_PKEY_OP_SIGNMSG             (1 << 14)
+# define EVP_PKEY_OP_VERIFYMSG           (1 << 15)
 /* Update the following when adding new EVP_PKEY_OPs */
-# define EVP_PKEY_OP_ALL                ((1 << 14) - 1)
+# define EVP_PKEY_OP_ALL                ((1 << 16) - 1)
 
 # define EVP_PKEY_OP_TYPE_SIG                                           \
-    (EVP_PKEY_OP_SIGN | EVP_PKEY_OP_VERIFY | EVP_PKEY_OP_VERIFYRECOVER  \
+    (EVP_PKEY_OP_SIGN | EVP_PKEY_OP_SIGNMSG                             \
+     | EVP_PKEY_OP_VERIFY | EVP_PKEY_OP_VERIFYMSG                       \
+     | EVP_PKEY_OP_VERIFYRECOVER                                        \
      | EVP_PKEY_OP_SIGNCTX | EVP_PKEY_OP_VERIFYCTX)
 
 # define EVP_PKEY_OP_TYPE_CRYPT                                         \
@@ -1857,6 +1861,9 @@ EVP_PKEY *EVP_PKEY_CTX_get0_peerkey(EVP_PKEY_CTX *ctx);
 void EVP_PKEY_CTX_set_app_data(EVP_PKEY_CTX *ctx, void *data);
 void *EVP_PKEY_CTX_get_app_data(EVP_PKEY_CTX *ctx);
 
+int EVP_PKEY_CTX_set_signature(EVP_PKEY_CTX *pctx,
+                               const unsigned char *sig, size_t siglen);
+
 void EVP_SIGNATURE_free(EVP_SIGNATURE *signature);
 int EVP_SIGNATURE_up_ref(EVP_SIGNATURE *signature);
 OSSL_PROVIDER *EVP_SIGNATURE_get0_provider(const EVP_SIGNATURE *signature);
@@ -1910,17 +1917,35 @@ const OSSL_PARAM *EVP_KEM_settable_ctx_params(const EVP_KEM *kem);
 
 int EVP_PKEY_sign_init(EVP_PKEY_CTX *ctx);
 int EVP_PKEY_sign_init_ex(EVP_PKEY_CTX *ctx, const OSSL_PARAM params[]);
+int EVP_PKEY_sign_init_ex2(EVP_PKEY_CTX *ctx,
+                           EVP_SIGNATURE *algo, const OSSL_PARAM params[]);
 int EVP_PKEY_sign(EVP_PKEY_CTX *ctx,
                   unsigned char *sig, size_t *siglen,
                   const unsigned char *tbs, size_t tbslen);
+int EVP_PKEY_sign_message_init(EVP_PKEY_CTX *ctx,
+                               EVP_SIGNATURE *algo, const OSSL_PARAM params[]);
+int EVP_PKEY_sign_message_update(EVP_PKEY_CTX *ctx,
+                                 const unsigned char *in, size_t inlen);
+int EVP_PKEY_sign_message_final(EVP_PKEY_CTX *ctx,
+                                unsigned char *sig, size_t *siglen);
 int EVP_PKEY_verify_init(EVP_PKEY_CTX *ctx);
 int EVP_PKEY_verify_init_ex(EVP_PKEY_CTX *ctx, const OSSL_PARAM params[]);
+int EVP_PKEY_verify_init_ex2(EVP_PKEY_CTX *ctx,
+                             EVP_SIGNATURE *algo, const OSSL_PARAM params[]);
 int EVP_PKEY_verify(EVP_PKEY_CTX *ctx,
                     const unsigned char *sig, size_t siglen,
                     const unsigned char *tbs, size_t tbslen);
+int EVP_PKEY_verify_message_init(EVP_PKEY_CTX *ctx,
+                                 EVP_SIGNATURE *algo, const OSSL_PARAM params[]);
+int EVP_PKEY_verify_message_update(EVP_PKEY_CTX *ctx,
+                                   const unsigned char *in, size_t inlen);
+int EVP_PKEY_verify_message_final(EVP_PKEY_CTX *ctx);
 int EVP_PKEY_verify_recover_init(EVP_PKEY_CTX *ctx);
 int EVP_PKEY_verify_recover_init_ex(EVP_PKEY_CTX *ctx,
                                     const OSSL_PARAM params[]);
+int EVP_PKEY_verify_recover_init_ex2(EVP_PKEY_CTX *ctx,
+                                     EVP_SIGNATURE *algo,
+                                     const OSSL_PARAM params[]);
 int EVP_PKEY_verify_recover(EVP_PKEY_CTX *ctx,
                             unsigned char *rout, size_t *routlen,
                             const unsigned char *sig, size_t siglen);
diff --git a/include/openssl/evperr.h b/include/openssl/evperr.h
index 11f3faa459..2d87934224 100644
--- a/include/openssl/evperr.h
+++ b/include/openssl/evperr.h
@@ -1,6 +1,6 @@
 /*
  * Generated by util/mkerr.pl DO NOT EDIT
- * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -94,6 +94,7 @@
 # define EVP_R_ONLY_ONESHOT_SUPPORTED                     177
 # define EVP_R_OPERATION_NOT_INITIALIZED                  151
 # define EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE   150
+# define EVP_R_OPERATION_NOT_SUPPORTED_FOR_THIS_SIGNATURE_TYPE 226
 # define EVP_R_OUTPUT_WOULD_OVERFLOW                      202
 # define EVP_R_PARAMETER_TOO_LARGE                        187
 # define EVP_R_PARTIALLY_OVERLAPPING                      162
@@ -104,6 +105,7 @@
 # define EVP_R_PUBLIC_KEY_NOT_RSA                         106
 # define EVP_R_SETTING_XOF_FAILED                         227
 # define EVP_R_SET_DEFAULT_PROPERTY_FAILURE               209
+# define EVP_R_SIGNATURE_TYPE_AND_KEY_TYPE_INCOMPATIBLE   228
 # define EVP_R_TOO_MANY_RECORDS                           183
 # define EVP_R_UNABLE_TO_ENABLE_LOCKING                   212
 # define EVP_R_UNABLE_TO_GET_MAXIMUM_REQUEST_SIZE         215
diff --git a/util/libcrypto.num b/util/libcrypto.num
index ef11c0302e..57c1e4686c 100644
--- a/util/libcrypto.num
+++ b/util/libcrypto.num
@@ -5716,3 +5716,13 @@ OSSL_BASIC_ATTR_CONSTRAINTS_free        ?	3_4_0	EXIST::FUNCTION:
 OSSL_BASIC_ATTR_CONSTRAINTS_new         ?	3_4_0	EXIST::FUNCTION:
 OSSL_BASIC_ATTR_CONSTRAINTS_it          ?	3_4_0	EXIST::FUNCTION:
 EVP_KEYMGMT_gen_gettable_params         ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_CTX_set_signature              ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_sign_init_ex2                  ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_sign_message_init              ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_sign_message_update            ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_sign_message_final             ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_verify_init_ex2                ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_verify_message_init            ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_verify_message_update          ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_verify_message_final           ?	3_4_0	EXIST::FUNCTION:
+EVP_PKEY_verify_recover_init_ex2        ?	3_4_0	EXIST::FUNCTION:
diff --git a/util/perl/OpenSSL/paramnames.pm b/util/perl/OpenSSL/paramnames.pm
index e4edb550be..9117b62152 100644
--- a/util/perl/OpenSSL/paramnames.pm
+++ b/util/perl/OpenSSL/paramnames.pm
@@ -434,6 +434,7 @@ my %params = (
     'SIGNATURE_PARAM_FIPS_RSA_PSS_SALTLEN_CHECK' => "rsa-pss-saltlen-check",
     'SIGNATURE_PARAM_FIPS_SIGN_X931_PAD_CHECK' => "sign-x931-pad-check",
     'SIGNATURE_PARAM_FIPS_APPROVED_INDICATOR' => '*ALG_PARAM_FIPS_APPROVED_INDICATOR',
+    'SIGNATURE_PARAM_SIGNATURE' =>          "signature",
 
 # Asym cipher parameters
     'ASYM_CIPHER_PARAM_DIGEST' =>                   '*PKEY_PARAM_DIGEST',