diff --git a/include/mbedtls/check_config.h b/include/mbedtls/check_config.h
index 619f842..1251cdf 100644
--- a/include/mbedtls/check_config.h
+++ b/include/mbedtls/check_config.h
@@ -766,7 +766,9 @@
 #error "MBEDTLS_PSA_CRYPTO_C defined, but not all prerequisites (missing RNG)"
 #endif
 
-#if defined(MBEDTLS_PSA_CRYPTO_C) && !defined(MBEDTLS_CIPHER_C )
+#if defined(MBEDTLS_PSA_CRYPTO_C) && \
+    (defined(PSA_HAVE_SOFT_BLOCK_CIPHER) || defined(PSA_HAVE_SOFT_BLOCK_AEAD)) && \
+    !defined(MBEDTLS_CIPHER_C)
 #error "MBEDTLS_PSA_CRYPTO_C defined, but not all prerequisites"
 #endif
 
diff --git a/include/mbedtls/config_adjust_psa_from_legacy.h b/include/mbedtls/config_adjust_psa_from_legacy.h
index 088711d..296d624 100644
--- a/include/mbedtls/config_adjust_psa_from_legacy.h
+++ b/include/mbedtls/config_adjust_psa_from_legacy.h
@@ -238,9 +238,12 @@
 
 #if defined(MBEDTLS_CHACHA20_C)
 #define PSA_WANT_KEY_TYPE_CHACHA20 1
-#define PSA_WANT_ALG_STREAM_CIPHER 1
 #define MBEDTLS_PSA_BUILTIN_KEY_TYPE_CHACHA20 1
+/* ALG_STREAM_CIPHER requires CIPHER_C in order to be supported in PSA */
+#if defined(MBEDTLS_CIPHER_C)
+#define PSA_WANT_ALG_STREAM_CIPHER 1
 #define MBEDTLS_PSA_BUILTIN_ALG_STREAM_CIPHER 1
+#endif
 #if defined(MBEDTLS_CHACHAPOLY_C)
 #define PSA_WANT_ALG_CHACHA20_POLY1305 1
 #define MBEDTLS_PSA_BUILTIN_ALG_CHACHA20_POLY1305 1
diff --git a/library/psa_crypto_aead.c b/library/psa_crypto_aead.c
index 85d1f39..6f026a0 100644
--- a/library/psa_crypto_aead.c
+++ b/library/psa_crypto_aead.c
@@ -43,19 +43,15 @@
     psa_algorithm_t alg)
 {
     psa_status_t status = PSA_ERROR_CORRUPTION_DETECTED;
-    size_t key_bits;
-    const mbedtls_cipher_info_t *cipher_info;
     mbedtls_cipher_id_t cipher_id;
-
+    mbedtls_cipher_mode_t mode;
+    size_t key_bits = attributes->core.bits;
     (void) key_buffer_size;
 
-    key_bits = attributes->core.bits;
-
-    cipher_info = mbedtls_cipher_info_from_psa(alg,
-                                               attributes->core.type, key_bits,
-                                               &cipher_id);
-    if (cipher_info == NULL) {
-        return PSA_ERROR_NOT_SUPPORTED;
+    status = mbedtls_cipher_values_from_psa(alg, attributes->core.type,
+                                            &key_bits, &mode, &cipher_id);
+    if (status != PSA_SUCCESS) {
+        return status;
     }
 
     switch (PSA_ALG_AEAD_WITH_SHORTENED_TAG(alg, 0)) {
diff --git a/library/psa_crypto_cipher.c b/library/psa_crypto_cipher.c
index b997a07..38be84b 100644
--- a/library/psa_crypto_cipher.c
+++ b/library/psa_crypto_cipher.c
@@ -31,14 +31,70 @@
 
 #include <string.h>
 
-const mbedtls_cipher_info_t *mbedtls_cipher_info_from_psa(
+/* mbedtls_cipher_values_from_psa() below only checks if the proper build symbols
+ * are enabled, but it does not provide any compatibility check between them
+ * (i.e. if the specified key works with the specified algorithm). This helper
+ * function is meant to provide this support.
+ * mbedtls_cipher_info_from_psa() might be used for the same purpose, but it
+ * requires CIPHER_C to be enabled.
+ */
+static psa_status_t mbedtls_cipher_validate_values(
+    psa_algorithm_t alg,
+    psa_key_type_t key_type)
+{
+    switch (alg) {
+        case PSA_ALG_STREAM_CIPHER:
+        case PSA_ALG_AEAD_WITH_SHORTENED_TAG(PSA_ALG_CHACHA20_POLY1305, 0):
+            if (key_type != PSA_KEY_TYPE_CHACHA20) {
+                return PSA_ERROR_NOT_SUPPORTED;
+            }
+            break;
+
+        case PSA_ALG_AEAD_WITH_SHORTENED_TAG(PSA_ALG_CCM, 0):
+        case PSA_ALG_AEAD_WITH_SHORTENED_TAG(PSA_ALG_GCM, 0):
+        case PSA_ALG_CCM_STAR_NO_TAG:
+            if ((key_type != PSA_KEY_TYPE_AES) &&
+                (key_type != PSA_KEY_TYPE_ARIA) &&
+                (key_type != PSA_KEY_TYPE_CAMELLIA)) {
+                return PSA_ERROR_NOT_SUPPORTED;
+            }
+            break;
+
+        case PSA_ALG_CTR:
+        case PSA_ALG_CFB:
+        case PSA_ALG_OFB:
+        case PSA_ALG_XTS:
+        case PSA_ALG_ECB_NO_PADDING:
+        case PSA_ALG_CBC_NO_PADDING:
+        case PSA_ALG_CBC_PKCS7:
+        case PSA_ALG_CMAC:
+            if ((key_type != PSA_KEY_TYPE_AES) &&
+                (key_type != PSA_KEY_TYPE_ARIA) &&
+                (key_type != PSA_KEY_TYPE_DES) &&
+                (key_type != PSA_KEY_TYPE_CAMELLIA)) {
+                return PSA_ERROR_NOT_SUPPORTED;
+            }
+            break;
+
+        default:
+            return PSA_ERROR_NOT_SUPPORTED;
+    }
+
+    return PSA_SUCCESS;
+}
+
+psa_status_t mbedtls_cipher_values_from_psa(
     psa_algorithm_t alg,
     psa_key_type_t key_type,
-    size_t key_bits,
+    size_t *key_bits,
+    mbedtls_cipher_mode_t *mode,
     mbedtls_cipher_id_t *cipher_id)
 {
-    mbedtls_cipher_mode_t mode;
     mbedtls_cipher_id_t cipher_id_tmp;
+    /* Only DES modifies key_bits */
+#if !defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_DES)
+    (void) key_bits;
+#endif
 
     if (PSA_ALG_IS_AEAD(alg)) {
         alg = PSA_ALG_AEAD_WITH_SHORTENED_TAG(alg, 0);
@@ -48,66 +104,66 @@
         switch (alg) {
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_STREAM_CIPHER)
             case PSA_ALG_STREAM_CIPHER:
-                mode = MBEDTLS_MODE_STREAM;
+                *mode = MBEDTLS_MODE_STREAM;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_CTR)
             case PSA_ALG_CTR:
-                mode = MBEDTLS_MODE_CTR;
+                *mode = MBEDTLS_MODE_CTR;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_CFB)
             case PSA_ALG_CFB:
-                mode = MBEDTLS_MODE_CFB;
+                *mode = MBEDTLS_MODE_CFB;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_OFB)
             case PSA_ALG_OFB:
-                mode = MBEDTLS_MODE_OFB;
+                *mode = MBEDTLS_MODE_OFB;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_ECB_NO_PADDING)
             case PSA_ALG_ECB_NO_PADDING:
-                mode = MBEDTLS_MODE_ECB;
+                *mode = MBEDTLS_MODE_ECB;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_CBC_NO_PADDING)
             case PSA_ALG_CBC_NO_PADDING:
-                mode = MBEDTLS_MODE_CBC;
+                *mode = MBEDTLS_MODE_CBC;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_CBC_PKCS7)
             case PSA_ALG_CBC_PKCS7:
-                mode = MBEDTLS_MODE_CBC;
+                *mode = MBEDTLS_MODE_CBC;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_CCM_STAR_NO_TAG)
             case PSA_ALG_CCM_STAR_NO_TAG:
-                mode = MBEDTLS_MODE_CCM_STAR_NO_TAG;
+                *mode = MBEDTLS_MODE_CCM_STAR_NO_TAG;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_CCM)
             case PSA_ALG_AEAD_WITH_SHORTENED_TAG(PSA_ALG_CCM, 0):
-                mode = MBEDTLS_MODE_CCM;
+                *mode = MBEDTLS_MODE_CCM;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_GCM)
             case PSA_ALG_AEAD_WITH_SHORTENED_TAG(PSA_ALG_GCM, 0):
-                mode = MBEDTLS_MODE_GCM;
+                *mode = MBEDTLS_MODE_GCM;
                 break;
 #endif
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_CHACHA20_POLY1305)
             case PSA_ALG_AEAD_WITH_SHORTENED_TAG(PSA_ALG_CHACHA20_POLY1305, 0):
-                mode = MBEDTLS_MODE_CHACHAPOLY;
+                *mode = MBEDTLS_MODE_CHACHAPOLY;
                 break;
 #endif
             default:
-                return NULL;
+                return PSA_ERROR_NOT_SUPPORTED;
         }
     } else if (alg == PSA_ALG_CMAC) {
-        mode = MBEDTLS_MODE_ECB;
+        *mode = MBEDTLS_MODE_ECB;
     } else {
-        return NULL;
+        return PSA_ERROR_NOT_SUPPORTED;
     }
 
     switch (key_type) {
@@ -125,7 +181,7 @@
         case PSA_KEY_TYPE_DES:
             /* key_bits is 64 for Single-DES, 128 for two-key Triple-DES,
              * and 192 for three-key Triple-DES. */
-            if (key_bits == 64) {
+            if (*key_bits == 64) {
                 cipher_id_tmp = MBEDTLS_CIPHER_ID_DES;
             } else {
                 cipher_id_tmp = MBEDTLS_CIPHER_ID_3DES;
@@ -133,8 +189,8 @@
             /* mbedtls doesn't recognize two-key Triple-DES as an algorithm,
              * but two-key Triple-DES is functionally three-key Triple-DES
              * with K1=K3, so that's how we present it to mbedtls. */
-            if (key_bits == 128) {
-                key_bits = 192;
+            if (*key_bits == 128) {
+                *key_bits = 192;
             }
             break;
 #endif
@@ -149,16 +205,38 @@
             break;
 #endif
         default:
-            return NULL;
+            return PSA_ERROR_NOT_SUPPORTED;
     }
     if (cipher_id != NULL) {
         *cipher_id = cipher_id_tmp;
     }
 
-    return mbedtls_cipher_info_from_values(cipher_id_tmp,
-                                           (int) key_bits, mode);
+    return mbedtls_cipher_validate_values(alg, key_type);
 }
 
+#if defined(MBEDTLS_CIPHER_C)
+const mbedtls_cipher_info_t *mbedtls_cipher_info_from_psa(
+    psa_algorithm_t alg,
+    psa_key_type_t key_type,
+    size_t key_bits,
+    mbedtls_cipher_id_t *cipher_id)
+{
+    mbedtls_cipher_mode_t mode;
+    psa_status_t status;
+    mbedtls_cipher_id_t cipher_id_tmp;
+
+    status = mbedtls_cipher_values_from_psa(alg, key_type, &key_bits, &mode, &cipher_id_tmp);
+    if (status != PSA_SUCCESS) {
+        return NULL;
+    }
+    if (cipher_id != NULL) {
+        *cipher_id = cipher_id_tmp;
+    }
+
+    return mbedtls_cipher_info_from_values(cipher_id_tmp, (int) key_bits, mode);
+}
+#endif /* MBEDTLS_CIPHER_C */
+
 #if defined(MBEDTLS_PSA_BUILTIN_CIPHER)
 
 static psa_status_t psa_cipher_setup(
diff --git a/library/psa_crypto_cipher.h b/library/psa_crypto_cipher.h
index bf43ff0..5ed8a77 100644
--- a/library/psa_crypto_cipher.h
+++ b/library/psa_crypto_cipher.h
@@ -28,6 +28,28 @@
  *  as well as the PSA type and size of the key to be used with the cipher
  *  algorithm.
  *
+ * \param[in]      alg          PSA cipher algorithm identifier
+ * \param[in]      key_type     PSA key type
+ * \param[in,out]  key_bits     Size of the key in bits. The value provided in input
+ *                              might be updated if necessary.
+ * \param[out]     mode         Mbed TLS cipher mode
+ * \param[out]     cipher_id    Mbed TLS cipher algorithm identifier
+ *
+ * \return  On success \c PSA_SUCCESS is returned and key_bits, mode and cipher_id
+ *          are properly updated.
+ *          \c PSA_ERROR_NOT_SUPPORTED is returned if the cipher algorithm is not
+ *          supported.
+ */
+
+psa_status_t mbedtls_cipher_values_from_psa(psa_algorithm_t alg, psa_key_type_t key_type,
+                                            size_t *key_bits, mbedtls_cipher_mode_t *mode,
+                                            mbedtls_cipher_id_t *cipher_id);
+
+#if defined(MBEDTLS_CIPHER_C)
+/** Get Mbed TLS cipher information given the cipher algorithm PSA identifier
+ *  as well as the PSA type and size of the key to be used with the cipher
+ *  algorithm.
+ *
  * \param       alg        PSA cipher algorithm identifier
  * \param       key_type   PSA key type
  * \param       key_bits   Size of the key in bits
@@ -39,6 +61,7 @@
 const mbedtls_cipher_info_t *mbedtls_cipher_info_from_psa(
     psa_algorithm_t alg, psa_key_type_t key_type, size_t key_bits,
     mbedtls_cipher_id_t *cipher_id);
+#endif /* MBEDTLS_CIPHER_C */
 
 /**
  * \brief Set the key for a multipart symmetric encryption operation.
diff --git a/tests/scripts/all.sh b/tests/scripts/all.sh
index b0b32fe..1eea025 100755
--- a/tests/scripts/all.sh
+++ b/tests/scripts/all.sh
@@ -1488,13 +1488,13 @@
 }
 
 component_test_full_no_cipher () {
-    msg "build: full minus CIPHER"
+    msg "build: full no CIPHER no PSA_CRYPTO_C"
     scripts/config.py full
     scripts/config.py unset MBEDTLS_CIPHER_C
     # Don't pull in cipher via PSA mechanisms
     # (currently ignored anyway because we completely disable PSA)
     scripts/config.py unset MBEDTLS_PSA_CRYPTO_CONFIG
-    # Direct dependencies
+    # Disable features that depend on CIPHER_C
     scripts/config.py unset MBEDTLS_CCM_C
     scripts/config.py unset MBEDTLS_CMAC_C
     scripts/config.py unset MBEDTLS_GCM_C
@@ -1504,24 +1504,93 @@
     scripts/config.py unset MBEDTLS_PSA_CRYPTO_C
     scripts/config.py unset MBEDTLS_SSL_TLS_C
     scripts/config.py unset MBEDTLS_SSL_TICKET_C
-    # Indirect dependencies
-    scripts/config.py unset MBEDTLS_SSL_CLI_C
+    # Disable features that depend on PSA_CRYPTO_C
     scripts/config.py unset MBEDTLS_PSA_CRYPTO_SE_C
     scripts/config.py unset MBEDTLS_PSA_CRYPTO_STORAGE_C
-    scripts/config.py unset MBEDTLS_SSL_DTLS_ANTI_REPLAY
-    scripts/config.py unset MBEDTLS_SSL_DTLS_CONNECTION_ID
-    scripts/config.py unset MBEDTLS_SSL_DTLS_CONNECTION_ID_COMPAT
-    scripts/config.py unset MBEDTLS_SSL_PROTO_TLS1_3
-    scripts/config.py unset MBEDTLS_SSL_SRV_C
     scripts/config.py unset MBEDTLS_USE_PSA_CRYPTO
     scripts/config.py unset MBEDTLS_LMS_C
     scripts/config.py unset MBEDTLS_LMS_PRIVATE
     make
 
-    msg "test: full minus CIPHER"
+    msg "test: full no CIPHER no PSA_CRYPTO_C"
     make test
 }
 
+# This is a common configurator and test function that is used in:
+# - component_test_full_no_cipher_with_crypto
+# - component_test_full_no_cipher_with_crypto_config
+# It accepts 2 input parameters:
+# - $1: boolean value which basically reflects status of MBEDTLS_PSA_CRYPTO_CONFIG
+# - $2: a text string which describes the test component
+common_test_full_no_cipher_with_psa_crypto () {
+    USE_CRYPTO_CONFIG="$1"
+    COMPONENT_DESCRIPTION="$2"
+
+    msg "build: $COMPONENT_DESCRIPTION"
+
+    scripts/config.py full
+    scripts/config.py unset MBEDTLS_CIPHER_C
+
+    if [ "$USE_CRYPTO_CONFIG" -eq 1 ]; then
+        # The built-in implementation of the following algs/key-types depends
+        # on CIPHER_C so we disable them.
+        # This does not hold for KEY_TYPE_CHACHA20 and ALG_CHACHA20_POLY1305
+        # so we keep them enabled.
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_CCM
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_CCM_STAR_NO_TAG
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_GCM
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_CMAC
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_CBC_NO_PADDING
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_CBC_PKCS7
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_CFB
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_CTR
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_ECB_NO_PADDING
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_OFB
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_ALG_STREAM_CIPHER
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_KEY_TYPE_AES
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_KEY_TYPE_DES
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_KEY_TYPE_CAMELLIA
+        scripts/config.py -f $CRYPTO_CONFIG_H unset PSA_WANT_KEY_TYPE_ARIA
+    else
+        # Don't pull in cipher via PSA mechanisms
+        scripts/config.py unset MBEDTLS_PSA_CRYPTO_CONFIG
+        # Disable cipher modes/keys that make PSA depend on CIPHER_C.
+        # Keep CHACHA20 and CHACHAPOLY enabled since they do not depend on CIPHER_C.
+        scripts/config.py unset-all MBEDTLS_CIPHER_MODE
+        scripts/config.py unset MBEDTLS_AES_C
+        scripts/config.py unset MBEDTLS_DES_C
+        scripts/config.py unset MBEDTLS_ARIA_C
+        scripts/config.py unset MBEDTLS_CAMELLIA_C
+        # Dependencies on AES_C
+        scripts/config.py unset MBEDTLS_CTR_DRBG_C
+    fi
+    # The following modules directly depends on CIPHER_C
+    scripts/config.py unset MBEDTLS_CCM_C
+    scripts/config.py unset MBEDTLS_CMAC_C
+    scripts/config.py unset MBEDTLS_GCM_C
+    scripts/config.py unset MBEDTLS_NIST_KW_C
+    scripts/config.py unset MBEDTLS_PKCS12_C
+    scripts/config.py unset MBEDTLS_PKCS5_C
+    scripts/config.py unset MBEDTLS_SSL_TLS_C
+    scripts/config.py unset MBEDTLS_SSL_TICKET_C
+
+    make
+
+    # Ensure that CIPHER_C was not re-enabled
+    not grep mbedtls_cipher_init library/cipher.o
+
+    msg "test: $COMPONENT_DESCRIPTION"
+    make test
+}
+
+component_test_full_no_cipher_with_crypto() {
+    common_test_full_no_cipher_with_psa_crypto 0 "full no CIPHER no CRYPTO_CONFIG"
+}
+
+component_test_full_no_cipher_with_crypto_config() {
+    common_test_full_no_cipher_with_psa_crypto 1 "full no CIPHER"
+}
+
 component_test_full_no_bignum () {
     msg "build: full minus bignum"
     scripts/config.py full