diff --git a/library/psa_crypto.c b/library/psa_crypto.c
index 32be756..40a0db3 100644
--- a/library/psa_crypto.c
+++ b/library/psa_crypto.c
@@ -744,9 +744,6 @@
 static int psa_key_algorithm_permits( psa_algorithm_t policy_alg,
                                       psa_algorithm_t requested_alg )
 {
-    /* A requested algorithm cannot be a wildcard. */
-    if( PSA_ALG_IS_WILDCARD( requested_alg ) )
-        return( 0 );
     /* Common case: the policy only allows requested_alg. */
     if( requested_alg == policy_alg )
         return( 1 );
@@ -804,12 +801,25 @@
 /** Test whether a policy permits an algorithm.
  *
  * The caller must test usage flags separately.
+ *
+ * \retval PSA_SUCCESS                  When \p alg is a specific algorithm
+ *                                      allowed by the \p policy.
+ * \retval PSA_ERROR_INVALID_ARGUMENT   When \p alg is not a specific algorithm
+ * \retval PSA_ERROR_NOT_PERMITTED      When \p alg is a specific algorithm, but
+ *                                      the \p policy does not allow it.
  */
-static int psa_key_policy_permits( const psa_key_policy_t *policy,
-                                   psa_algorithm_t alg )
+static psa_status_t psa_key_policy_permits( const psa_key_policy_t *policy,
+                                            psa_algorithm_t alg )
 {
-    return( psa_key_algorithm_permits( policy->alg, alg ) ||
-            psa_key_algorithm_permits( policy->alg2, alg ) );
+    /* A requested algorithm cannot be a wildcard. */
+    if( PSA_ALG_IS_WILDCARD( alg ) )
+        return( PSA_ERROR_INVALID_ARGUMENT );
+
+    if( psa_key_algorithm_permits( policy->alg, alg ) ||
+        psa_key_algorithm_permits( policy->alg2, alg ) )
+        return( PSA_SUCCESS );
+    else
+        return( PSA_ERROR_NOT_PERMITTED );
 }
 
 /** Restrict a key policy based on a constraint.
@@ -880,8 +890,12 @@
         goto error;
 
     /* Enforce that the usage policy permits the requested algortihm. */
-    if( alg != 0 && ! psa_key_policy_permits( &slot->attr.policy, alg ) )
-        goto error;
+    if( alg != 0 )
+    {
+        status = psa_key_policy_permits( &slot->attr.policy, alg );
+        if( status != PSA_SUCCESS )
+            goto error;
+    }
 
     return( PSA_SUCCESS );
 
diff --git a/tests/suites/test_suite_psa_crypto.data b/tests/suites/test_suite_psa_crypto.data
index c4c340f..6e379a2 100644
--- a/tests/suites/test_suite_psa_crypto.data
+++ b/tests/suites/test_suite_psa_crypto.data
@@ -454,7 +454,7 @@
 
 PSA key policy: MAC, sign-verify, min-length policy used as algorithm
 depends_on:PSA_WANT_ALG_HMAC:PSA_WANT_ALG_SHA_256:PSA_WANT_KEY_TYPE_HMAC
-mac_key_policy:PSA_KEY_USAGE_SIGN_HASH | PSA_KEY_USAGE_VERIFY_HASH:PSA_ALG_AT_LEAST_THIS_LENGTH_MAC(PSA_ALG_HMAC(PSA_ALG_SHA_256), 20):PSA_KEY_TYPE_HMAC:"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa":PSA_ALG_AT_LEAST_THIS_LENGTH_MAC(PSA_ALG_HMAC(PSA_ALG_SHA_256), 20):PSA_ERROR_NOT_PERMITTED
+mac_key_policy:PSA_KEY_USAGE_SIGN_HASH | PSA_KEY_USAGE_VERIFY_HASH:PSA_ALG_AT_LEAST_THIS_LENGTH_MAC(PSA_ALG_HMAC(PSA_ALG_SHA_256), 20):PSA_KEY_TYPE_HMAC:"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa":PSA_ALG_AT_LEAST_THIS_LENGTH_MAC(PSA_ALG_HMAC(PSA_ALG_SHA_256), 20):PSA_ERROR_INVALID_ARGUMENT
 
 PSA key policy: MAC, sign-verify, tag length > exact-length policy
 depends_on:PSA_WANT_ALG_HMAC:PSA_WANT_ALG_SHA_256:PSA_WANT_KEY_TYPE_HMAC
@@ -558,7 +558,7 @@
 
 PSA key policy: AEAD, min-length policy used as algorithm
 depends_on:MBEDTLS_AES_C:MBEDTLS_CCM_C
-aead_key_policy:PSA_KEY_USAGE_ENCRYPT | PSA_KEY_USAGE_DECRYPT:PSA_ALG_AEAD_WITH_AT_LEAST_THIS_LENGTH_TAG(PSA_ALG_CCM, 8):PSA_KEY_TYPE_AES:"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa":13:8:PSA_ALG_AEAD_WITH_AT_LEAST_THIS_LENGTH_TAG(PSA_ALG_CCM, 8):PSA_ERROR_NOT_PERMITTED
+aead_key_policy:PSA_KEY_USAGE_ENCRYPT | PSA_KEY_USAGE_DECRYPT:PSA_ALG_AEAD_WITH_AT_LEAST_THIS_LENGTH_TAG(PSA_ALG_CCM, 8):PSA_KEY_TYPE_AES:"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa":13:8:PSA_ALG_AEAD_WITH_AT_LEAST_THIS_LENGTH_TAG(PSA_ALG_CCM, 8):PSA_ERROR_INVALID_ARGUMENT
 
 PSA key policy: AEAD, tag length > exact-length policy
 depends_on:MBEDTLS_AES_C:MBEDTLS_CCM_C
@@ -2118,9 +2118,7 @@
 
 PSA sign: RSA PKCS#1 v1.5, invalid hash (wildcard)
 depends_on:MBEDTLS_PK_PARSE_C:MBEDTLS_RSA_C:MBEDTLS_MD_C:MBEDTLS_PKCS1_V15
-# Arguably the error should be INVALID_ARGUMENT, but NOT_SUPPORTED is simpler
-# to implement.
-sign_fail:PSA_KEY_TYPE_RSA_KEY_PAIR:"3082025e02010002818100af057d396ee84fb75fdbb5c2b13c7fe5a654aa8aa2470b541ee1feb0b12d25c79711531249e1129628042dbbb6c120d1443524ef4c0e6e1d8956eeb2077af12349ddeee54483bc06c2c61948cd02b202e796aebd94d3a7cbf859c2c1819c324cb82b9cd34ede263a2abffe4733f077869e8660f7d6834da53d690ef7985f6bc3020301000102818100874bf0ffc2f2a71d14671ddd0171c954d7fdbf50281e4f6d99ea0e1ebcf82faa58e7b595ffb293d1abe17f110b37c48cc0f36c37e84d876621d327f64bbe08457d3ec4098ba2fa0a319fba411c2841ed7be83196a8cdf9daa5d00694bc335fc4c32217fe0488bce9cb7202e59468b1ead119000477db2ca797fac19eda3f58c1024100e2ab760841bb9d30a81d222de1eb7381d82214407f1b975cbbfe4e1a9467fd98adbd78f607836ca5be1928b9d160d97fd45c12d6b52e2c9871a174c66b488113024100c5ab27602159ae7d6f20c3c2ee851e46dc112e689e28d5fcbbf990a99ef8a90b8bb44fd36467e7fc1789ceb663abda338652c3c73f111774902e840565927091024100b6cdbd354f7df579a63b48b3643e353b84898777b48b15f94e0bfc0567a6ae5911d57ad6409cf7647bf96264e9bd87eb95e263b7110b9a1f9f94acced0fafa4d024071195eec37e8d257decfc672b07ae639f10cbb9b0c739d0c809968d644a94e3fd6ed9287077a14583f379058f76a8aecd43c62dc8c0f41766650d725275ac4a1024100bb32d133edc2e048d463388b7be9cb4be29f4b6250be603e70e3647501c97ddde20a4e71be95fd5e71784e25aca4baf25be5738aae59bbfe1c997781447a2b24":PSA_ALG_RSA_PKCS1V15_SIGN(PSA_ALG_ANY_HASH):"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa":128:PSA_ERROR_NOT_PERMITTED
+sign_fail:PSA_KEY_TYPE_RSA_KEY_PAIR:"3082025e02010002818100af057d396ee84fb75fdbb5c2b13c7fe5a654aa8aa2470b541ee1feb0b12d25c79711531249e1129628042dbbb6c120d1443524ef4c0e6e1d8956eeb2077af12349ddeee54483bc06c2c61948cd02b202e796aebd94d3a7cbf859c2c1819c324cb82b9cd34ede263a2abffe4733f077869e8660f7d6834da53d690ef7985f6bc3020301000102818100874bf0ffc2f2a71d14671ddd0171c954d7fdbf50281e4f6d99ea0e1ebcf82faa58e7b595ffb293d1abe17f110b37c48cc0f36c37e84d876621d327f64bbe08457d3ec4098ba2fa0a319fba411c2841ed7be83196a8cdf9daa5d00694bc335fc4c32217fe0488bce9cb7202e59468b1ead119000477db2ca797fac19eda3f58c1024100e2ab760841bb9d30a81d222de1eb7381d82214407f1b975cbbfe4e1a9467fd98adbd78f607836ca5be1928b9d160d97fd45c12d6b52e2c9871a174c66b488113024100c5ab27602159ae7d6f20c3c2ee851e46dc112e689e28d5fcbbf990a99ef8a90b8bb44fd36467e7fc1789ceb663abda338652c3c73f111774902e840565927091024100b6cdbd354f7df579a63b48b3643e353b84898777b48b15f94e0bfc0567a6ae5911d57ad6409cf7647bf96264e9bd87eb95e263b7110b9a1f9f94acced0fafa4d024071195eec37e8d257decfc672b07ae639f10cbb9b0c739d0c809968d644a94e3fd6ed9287077a14583f379058f76a8aecd43c62dc8c0f41766650d725275ac4a1024100bb32d133edc2e048d463388b7be9cb4be29f4b6250be603e70e3647501c97ddde20a4e71be95fd5e71784e25aca4baf25be5738aae59bbfe1c997781447a2b24":PSA_ALG_RSA_PKCS1V15_SIGN(PSA_ALG_ANY_HASH):"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa":128:PSA_ERROR_INVALID_ARGUMENT
 
 PSA sign: RSA PKCS#1 v1.5 raw, input too large
 depends_on:PSA_WANT_ALG_RSA_PKCS1V15_SIGN:PSA_WANT_KEY_TYPE_RSA_KEY_PAIR:MBEDTLS_PK_PARSE_C:MBEDTLS_MD_C
@@ -2148,7 +2146,7 @@
 
 PSA sign: deterministic ECDSA SECP256R1, invalid hash algorithm (wildcard)
 depends_on:PSA_WANT_ALG_DETERMINISTIC_ECDSA:PSA_WANT_KEY_TYPE_ECC_KEY_PAIR:MBEDTLS_PK_PARSE_C:MBEDTLS_ECP_DP_SECP256R1_ENABLED:MBEDTLS_MD_C
-sign_fail:PSA_KEY_TYPE_ECC_KEY_PAIR(PSA_ECC_FAMILY_SECP_R1):"ab45435712649cb30bbddac49197eebf2740ffc7f874d9244c3460f54f322d3a":PSA_ALG_DETERMINISTIC_ECDSA( PSA_ALG_ANY_HASH ):"9ac4335b469bbd791439248504dd0d49c71349a295fee5a1c68507f45a9e1c7b":72:PSA_ERROR_NOT_PERMITTED
+sign_fail:PSA_KEY_TYPE_ECC_KEY_PAIR(PSA_ECC_FAMILY_SECP_R1):"ab45435712649cb30bbddac49197eebf2740ffc7f874d9244c3460f54f322d3a":PSA_ALG_DETERMINISTIC_ECDSA( PSA_ALG_ANY_HASH ):"9ac4335b469bbd791439248504dd0d49c71349a295fee5a1c68507f45a9e1c7b":72:PSA_ERROR_INVALID_ARGUMENT
 
 PSA sign: invalid key type, signing with a public key
 depends_on:PSA_WANT_ALG_RSA_PKCS1V15_SIGN:PSA_WANT_KEY_TYPE_RSA_PUBLIC_KEY:MBEDTLS_PK_PARSE_C