diff --git a/include/mbedtls/config_psa.h b/include/mbedtls/config_psa.h
index b1bb067..7718f85 100644
--- a/include/mbedtls/config_psa.h
+++ b/include/mbedtls/config_psa.h
@@ -268,7 +268,6 @@
 #if (defined(PSA_WANT_ALG_CTR) && !defined(MBEDTLS_PSA_ACCEL_ALG_CTR)) || \
     (defined(PSA_WANT_ALG_CFB) && !defined(MBEDTLS_PSA_ACCEL_ALG_CFB)) || \
     (defined(PSA_WANT_ALG_OFB) && !defined(MBEDTLS_PSA_ACCEL_ALG_OFB)) || \
-    (defined(PSA_WANT_ALG_XTS) && !defined(MBEDTLS_PSA_ACCEL_ALG_XTS)) || \
     defined(PSA_WANT_ALG_ECB_NO_PADDING) || \
     (defined(PSA_WANT_ALG_CBC_NO_PADDING) && \
      !defined(MBEDTLS_PSA_ACCEL_ALG_CBC_NO_PADDING)) || \
@@ -390,14 +389,6 @@
 #endif
 #endif /* PSA_WANT_ALG_OFB */
 
-#if defined(PSA_WANT_ALG_XTS)
-#if !defined(MBEDTLS_PSA_ACCEL_ALG_XTS) || \
-    defined(PSA_HAVE_SOFT_BLOCK_CIPHER)
-#define MBEDTLS_PSA_BUILTIN_ALG_XTS 1
-#define MBEDTLS_CIPHER_MODE_XTS
-#endif
-#endif /* PSA_WANT_ALG_XTS */
-
 #if defined(PSA_WANT_ALG_ECB_NO_PADDING) &&     \
     !defined(MBEDTLS_PSA_ACCEL_ALG_ECB_NO_PADDING)
 #define MBEDTLS_PSA_BUILTIN_ALG_ECB_NO_PADDING 1
@@ -734,11 +725,6 @@
 #define PSA_WANT_ALG_OFB 1
 #endif
 
-#if defined(MBEDTLS_CIPHER_MODE_XTS)
-#define MBEDTLS_PSA_BUILTIN_ALG_XTS 1
-#define PSA_WANT_ALG_XTS 1
-#endif
-
 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
 #define MBEDTLS_PSA_BUILTIN_ECC_BRAINPOOL_P_R1_256 1
 #define PSA_WANT_ECC_BRAINPOOL_P_R1_256
diff --git a/include/psa/crypto_builtin_primitives.h b/include/psa/crypto_builtin_primitives.h
index d3cf33a..35f3a8b 100644
--- a/include/psa/crypto_builtin_primitives.h
+++ b/include/psa/crypto_builtin_primitives.h
@@ -94,7 +94,6 @@
     defined(MBEDTLS_PSA_BUILTIN_ALG_CTR) || \
     defined(MBEDTLS_PSA_BUILTIN_ALG_CFB) || \
     defined(MBEDTLS_PSA_BUILTIN_ALG_OFB) || \
-    defined(MBEDTLS_PSA_BUILTIN_ALG_XTS) || \
     defined(MBEDTLS_PSA_BUILTIN_ALG_ECB_NO_PADDING) || \
     defined(MBEDTLS_PSA_BUILTIN_ALG_CBC_NO_PADDING) || \
     defined(MBEDTLS_PSA_BUILTIN_ALG_CBC_PKCS7)
diff --git a/include/psa/crypto_config.h b/include/psa/crypto_config.h
index d290971..46cf126 100644
--- a/include/psa/crypto_config.h
+++ b/include/psa/crypto_config.h
@@ -87,7 +87,9 @@
 #define PSA_WANT_ALG_STREAM_CIPHER              1
 #define PSA_WANT_ALG_TLS12_PRF                  1
 #define PSA_WANT_ALG_TLS12_PSK_TO_MS            1
-#define PSA_WANT_ALG_XTS                        1
+/* PBKDF2-HMAC is not yet supported via the PSA API in Mbed TLS.
+ * Note: when adding support, also adjust include/mbedtls/config_psa.h */
+//#define PSA_WANT_ALG_XTS                        1
 
 #define PSA_WANT_ECC_BRAINPOOL_P_R1_256         1
 #define PSA_WANT_ECC_BRAINPOOL_P_R1_384         1
diff --git a/scripts/mbedtls_dev/crypto_knowledge.py b/scripts/mbedtls_dev/crypto_knowledge.py
index 1bd011f..592fc0a 100644
--- a/scripts/mbedtls_dev/crypto_knowledge.py
+++ b/scripts/mbedtls_dev/crypto_knowledge.py
@@ -20,11 +20,34 @@
 
 import enum
 import re
-from typing import Dict, Iterable, Optional, Pattern, Tuple
+from typing import FrozenSet, Iterable, List, Optional, Tuple
 
 from mbedtls_dev.asymmetric_key_data import ASYMMETRIC_KEY_DATA
 
 
+def short_expression(original: str, level: int = 0) -> str:
+    """Abbreviate the expression, keeping it human-readable.
+
+    If `level` is 0, just remove parts that are implicit from context,
+    such as a leading ``PSA_KEY_TYPE_``.
+    For larger values of `level`, also abbreviate some names in an
+    unambiguous, but ad hoc way.
+    """
+    short = original
+    short = re.sub(r'\bPSA_(?:ALG|ECC_FAMILY|KEY_[A-Z]+)_', r'', short)
+    short = re.sub(r' +', r'', short)
+    if level >= 1:
+        short = re.sub(r'PUBLIC_KEY\b', r'PUB', short)
+        short = re.sub(r'KEY_PAIR\b', r'PAIR', short)
+        short = re.sub(r'\bBRAINPOOL_P', r'BP', short)
+        short = re.sub(r'\bMONTGOMERY\b', r'MGM', short)
+        short = re.sub(r'AEAD_WITH_SHORTENED_TAG\b', r'AEAD_SHORT', short)
+        short = re.sub(r'\bDETERMINISTIC_', r'DET_', short)
+        short = re.sub(r'\bKEY_AGREEMENT\b', r'KA', short)
+        short = re.sub(r'_PSK_TO_MS\b', r'_PSK2MS', short)
+    return short
+
+
 BLOCK_CIPHERS = frozenset(['AES', 'ARIA', 'CAMELLIA', 'DES'])
 BLOCK_MAC_MODES = frozenset(['CBC_MAC', 'CMAC'])
 BLOCK_CIPHER_MODES = frozenset([
@@ -104,6 +127,13 @@
         `self.name`.
         """
 
+    def short_expression(self, level: int = 0) -> str:
+        """Abbreviate the expression, keeping it human-readable.
+
+        See `crypto_knowledge.short_expression`.
+        """
+        return short_expression(self.expression, level=level)
+
     def is_public(self) -> bool:
         """Whether the key type is for public keys."""
         return self.name.endswith('_PUBLIC_KEY')
@@ -178,35 +208,31 @@
         return b''.join([self.DATA_BLOCK] * (length // len(self.DATA_BLOCK)) +
                         [self.DATA_BLOCK[:length % len(self.DATA_BLOCK)]])
 
-    KEY_TYPE_FOR_SIGNATURE = {
-        'PSA_KEY_USAGE_SIGN_HASH': re.compile('.*KEY_PAIR'),
-        'PSA_KEY_USAGE_VERIFY_HASH': re.compile('.*KEY.*')
-    } #type: Dict[str, Pattern]
-    """Use a regexp to determine key types for which signature is possible
-       when using the actual usage flag.
-    """
-    def is_valid_for_signature(self, usage: str) -> bool:
-        """Determine if the key type is compatible with the specified
-           signitute type.
-
-        """
-        # This is just temporaly solution for the implicit usage flags.
-        return re.match(self.KEY_TYPE_FOR_SIGNATURE[usage], self.name) is not None
-
     def can_do(self, alg: 'Algorithm') -> bool:
         """Whether this key type can be used for operations with the given algorithm.
 
         This function does not currently handle key derivation or PAKE.
         """
-        #pylint: disable=too-many-return-statements
+        #pylint: disable=too-many-branches,too-many-return-statements
         if alg.is_wildcard:
             return False
+        if alg.is_invalid_truncation():
+            return False
         if self.head == 'HMAC' and alg.head == 'HMAC':
             return True
+        if self.head == 'DES':
+            # 64-bit block ciphers only allow a reduced set of modes.
+            return alg.head in [
+                'CBC_NO_PADDING', 'CBC_PKCS7',
+                'ECB_NO_PADDING',
+            ]
         if self.head in BLOCK_CIPHERS and \
            alg.head in frozenset.union(BLOCK_MAC_MODES,
                                        BLOCK_CIPHER_MODES,
                                        BLOCK_AEAD_MODES):
+            if alg.head in ['CMAC', 'OFB'] and \
+               self.head in ['ARIA', 'CAMELLIA']:
+                return False # not implemented in Mbed TLS
             return True
         if self.head == 'CHACHA20' and alg.head == 'CHACHA20_POLY1305':
             return True
@@ -215,6 +241,13 @@
             return True
         if self.head == 'RSA' and alg.head.startswith('RSA_'):
             return True
+        if alg.category == AlgorithmCategory.KEY_AGREEMENT and \
+           self.is_public():
+            # The PSA API does not use public key objects in key agreement
+            # operations: it imports the public key as a formatted byte string.
+            # So a public key object with a key agreement algorithm is not
+            # a valid combination.
+            return False
         if self.head == 'ECC':
             assert self.params is not None
             eccc = EllipticCurveCategory.from_family(self.params[0])
@@ -391,11 +424,113 @@
         # Assume kdf_alg is either a valid KDF or 0.
         return not re.match(r'(?:0[Xx])?0+\s*\Z', kdf_alg)
 
+
+    def short_expression(self, level: int = 0) -> str:
+        """Abbreviate the expression, keeping it human-readable.
+
+        See `crypto_knowledge.short_expression`.
+        """
+        return short_expression(self.expression, level=level)
+
+    HASH_LENGTH = {
+        'PSA_ALG_MD5': 16,
+        'PSA_ALG_SHA_1': 20,
+    }
+    HASH_LENGTH_BITS_RE = re.compile(r'([0-9]+)\Z')
+    @classmethod
+    def hash_length(cls, alg: str) -> int:
+        """The length of the given hash algorithm, in bytes."""
+        if alg in cls.HASH_LENGTH:
+            return cls.HASH_LENGTH[alg]
+        m = cls.HASH_LENGTH_BITS_RE.search(alg)
+        if m:
+            return int(m.group(1)) // 8
+        raise ValueError('Unknown hash length for ' + alg)
+
+    PERMITTED_TAG_LENGTHS = {
+        'PSA_ALG_CCM': frozenset([4, 6, 8, 10, 12, 14, 16]),
+        'PSA_ALG_CHACHA20_POLY1305': frozenset([16]),
+        'PSA_ALG_GCM': frozenset([4, 8, 12, 13, 14, 15, 16]),
+    }
+    MAC_LENGTH = {
+        'PSA_ALG_CBC_MAC': 16, # actually the block cipher length
+        'PSA_ALG_CMAC': 16, # actually the block cipher length
+    }
+    HMAC_RE = re.compile(r'PSA_ALG_HMAC\((.*)\)\Z')
+    @classmethod
+    def permitted_truncations(cls, base: str) -> FrozenSet[int]:
+        """Permitted output lengths for the given MAC or AEAD base algorithm.
+
+        For a MAC algorithm, this is the set of truncation lengths that
+        Mbed TLS supports.
+        For an AEAD algorithm, this is the set of truncation lengths that
+        are permitted by the algorithm specification.
+        """
+        if base in cls.PERMITTED_TAG_LENGTHS:
+            return cls.PERMITTED_TAG_LENGTHS[base]
+        max_length = cls.MAC_LENGTH.get(base, None)
+        if max_length is None:
+            m = cls.HMAC_RE.match(base)
+            if m:
+                max_length = cls.hash_length(m.group(1))
+        if max_length is None:
+            raise ValueError('Unknown permitted lengths for ' + base)
+        return frozenset(range(4, max_length + 1))
+
+    TRUNCATED_ALG_RE = re.compile(
+        r'(?P<face>PSA_ALG_(?:AEAD_WITH_SHORTENED_TAG|TRUNCATED_MAC))'
+        r'\((?P<base>.*),'
+        r'(?P<length>0[Xx][0-9A-Fa-f]+|[1-9][0-9]*|0[0-7]*)[LUlu]*\)\Z')
+    def is_invalid_truncation(self) -> bool:
+        """False for a MAC or AEAD algorithm truncated to an invalid length.
+
+        True for a MAC or AEAD algorithm truncated to a valid length or to
+        a length that cannot be determined. True for anything other than
+        a truncated MAC or AEAD.
+        """
+        m = self.TRUNCATED_ALG_RE.match(self.expression)
+        if m:
+            base = m.group('base')
+            to_length = int(m.group('length'), 0)
+            permitted_lengths = self.permitted_truncations(base)
+            if to_length not in permitted_lengths:
+                return True
+        return False
+
     def can_do(self, category: AlgorithmCategory) -> bool:
-        """Whether this algorithm fits the specified operation category."""
+        """Whether this algorithm can perform operations in the given category.
+        """
         if category == self.category:
             return True
         if category == AlgorithmCategory.KEY_DERIVATION and \
            self.is_key_agreement_with_derivation():
             return True
         return False
+
+    def usage_flags(self, public: bool = False) -> List[str]:
+        """The list of usage flags describing operations that can perform this algorithm.
+
+        If public is true, only return public-key operations, not private-key operations.
+        """
+        if self.category == AlgorithmCategory.HASH:
+            flags = []
+        elif self.category == AlgorithmCategory.MAC:
+            flags = ['SIGN_HASH', 'SIGN_MESSAGE',
+                     'VERIFY_HASH', 'VERIFY_MESSAGE']
+        elif self.category == AlgorithmCategory.CIPHER or \
+             self.category == AlgorithmCategory.AEAD:
+            flags = ['DECRYPT', 'ENCRYPT']
+        elif self.category == AlgorithmCategory.SIGN:
+            flags = ['VERIFY_HASH', 'VERIFY_MESSAGE']
+            if not public:
+                flags += ['SIGN_HASH', 'SIGN_MESSAGE']
+        elif self.category == AlgorithmCategory.ASYMMETRIC_ENCRYPTION:
+            flags = ['ENCRYPT']
+            if not public:
+                flags += ['DECRYPT']
+        elif self.category == AlgorithmCategory.KEY_DERIVATION or \
+             self.category == AlgorithmCategory.KEY_AGREEMENT:
+            flags = ['DERIVE']
+        else:
+            raise AlgorithmNotRecognized(self.expression)
+        return ['PSA_KEY_USAGE_' + flag for flag in flags]
diff --git a/scripts/mbedtls_dev/macro_collector.py b/scripts/mbedtls_dev/macro_collector.py
index 987779d..3cad2a3 100644
--- a/scripts/mbedtls_dev/macro_collector.py
+++ b/scripts/mbedtls_dev/macro_collector.py
@@ -186,7 +186,7 @@
                 for value in argument_lists[i][1:]:
                     arguments[i] = value
                     yield self._format_arguments(name, arguments)
-                arguments[i] = argument_lists[0][0]
+                arguments[i] = argument_lists[i][0]
         except BaseException as e:
             raise Exception('distribute_arguments({})'.format(name)) from e
 
@@ -400,10 +400,26 @@
             'other_algorithm': [],
             'lifetime': [self.lifetimes],
         } #type: Dict[str, List[Set[str]]]
-        self.arguments_for['mac_length'] += ['1', '63']
-        self.arguments_for['min_mac_length'] += ['1', '63']
-        self.arguments_for['tag_length'] += ['1', '63']
-        self.arguments_for['min_tag_length'] += ['1', '63']
+        mac_lengths = [str(n) for n in [
+            1,  # minimum expressible
+            4,  # minimum allowed by policy
+            13, # an odd size in a plausible range
+            14, # an even non-power-of-two size in a plausible range
+            16, # same as full size for at least one algorithm
+            63, # maximum expressible
+        ]]
+        self.arguments_for['mac_length'] += mac_lengths
+        self.arguments_for['min_mac_length'] += mac_lengths
+        aead_lengths = [str(n) for n in [
+            1,  # minimum expressible
+            4,  # minimum allowed by policy
+            13, # an odd size in a plausible range
+            14, # an even non-power-of-two size in a plausible range
+            16, # same as full size for at least one algorithm
+            63, # maximum expressible
+        ]]
+        self.arguments_for['tag_length'] += aead_lengths
+        self.arguments_for['min_tag_length'] += aead_lengths
 
     def add_numerical_values(self) -> None:
         """Add numerical values that are not supported to the known identifiers."""
diff --git a/tests/scripts/generate_psa_tests.py b/tests/scripts/generate_psa_tests.py
index ca94d7d..492810b 100755
--- a/tests/scripts/generate_psa_tests.py
+++ b/tests/scripts/generate_psa_tests.py
@@ -145,7 +145,7 @@
     """
     hack_dependencies_not_implemented(dependencies)
     tc = test_case.TestCase()
-    short_key_type = re.sub(r'PSA_(KEY_TYPE|ECC_FAMILY)_', r'', key_type)
+    short_key_type = crypto_knowledge.short_expression(key_type)
     adverb = 'not' if dependencies else 'never'
     if param_descr:
         adverb = param_descr + ' ' + adverb
@@ -206,7 +206,7 @@
                 continue
                 # For public key we expect that key generation fails with
                 # INVALID_ARGUMENT. It is handled by KeyGenerate class.
-            if not kt.name.endswith('_PUBLIC_KEY'):
+            if not kt.is_public():
                 yield test_case_for_key_type_not_supported(
                     'generate', kt.expression, bits,
                     finish_family_dependencies(generate_dependencies, bits),
@@ -243,7 +243,7 @@
     """
     hack_dependencies_not_implemented(dependencies)
     tc = test_case.TestCase()
-    short_key_type = re.sub(r'PSA_(KEY_TYPE|ECC_FAMILY)_', r'', key_type)
+    short_key_type = crypto_knowledge.short_expression(key_type)
     tc.set_description('PSA {} {}-bit'
                        .format(short_key_type, bits))
     tc.set_dependencies(dependencies)
@@ -335,7 +335,7 @@
         """Construct a failure test case for a one-key or keyless operation."""
         #pylint: disable=too-many-arguments,too-many-locals
         tc = test_case.TestCase()
-        pretty_alg = re.sub(r'PSA_ALG_', r'', alg.expression)
+        pretty_alg = alg.short_expression()
         if reason == self.Reason.NOT_SUPPORTED:
             short_deps = [re.sub(r'PSA_WANT_ALG_', r'', dep)
                           for dep in not_deps]
@@ -344,7 +344,7 @@
             pretty_reason = reason.name.lower()
         if kt:
             key_type = kt.expression
-            pretty_type = re.sub(r'PSA_KEY_TYPE_', r'', key_type)
+            pretty_type = kt.short_expression()
         else:
             key_type = ''
             pretty_type = ''
@@ -456,7 +456,7 @@
 
     def __init__(
             self,
-            usage: str,
+            usage: Iterable[str],
             without_implicit_usage: Optional[bool] = False,
             **kwargs
     ) -> None:
@@ -465,13 +465,16 @@
         * `usage`                 : The usage flags used for the key.
         * `without_implicit_usage`: Flag to defide to apply the usage extension
         """
-        super().__init__(usage=usage, **kwargs)
-
+        usage_flags = set(usage)
         if not without_implicit_usage:
-            for flag, implicit in self.IMPLICIT_USAGE_FLAGS.items():
-                if self.usage.value() & psa_storage.Expr(flag).value() and \
-                   self.usage.value() & psa_storage.Expr(implicit).value() == 0:
-                    self.usage = psa_storage.Expr(self.usage.string + ' | ' + implicit)
+            for flag in sorted(usage_flags):
+                if flag in self.IMPLICIT_USAGE_FLAGS:
+                    usage_flags.add(self.IMPLICIT_USAGE_FLAGS[flag])
+        if usage_flags:
+            usage_expression = ' | '.join(sorted(usage_flags))
+        else:
+            usage_expression = '0'
+        super().__init__(usage=usage_expression, **kwargs)
 
 class StorageTestData(StorageKey):
     """Representation of test case data for storage format testing."""
@@ -479,7 +482,7 @@
     def __init__(
             self,
             description: str,
-            expected_usage: Optional[str] = None,
+            expected_usage: Optional[List[str]] = None,
             **kwargs
     ) -> None:
         """Prepare to generate test data
@@ -491,7 +494,12 @@
         """
         super().__init__(**kwargs)
         self.description = description #type: str
-        self.expected_usage = expected_usage if expected_usage else self.usage.string #type: str
+        if expected_usage is None:
+            self.expected_usage = self.usage #type: psa_storage.Expr
+        elif expected_usage:
+            self.expected_usage = psa_storage.Expr(' | '.join(expected_usage))
+        else:
+            self.expected_usage = psa_storage.Expr(0)
 
 class StorageFormat:
     """Storage format stability test cases."""
@@ -510,6 +518,47 @@
         self.version = version #type: int
         self.forward = forward #type: bool
 
+    RSA_OAEP_RE = re.compile(r'PSA_ALG_RSA_OAEP\((.*)\)\Z')
+    BRAINPOOL_RE = re.compile(r'PSA_KEY_TYPE_\w+\(PSA_ECC_FAMILY_BRAINPOOL_\w+\)\Z')
+    @classmethod
+    def exercise_key_with_algorithm(
+            cls,
+            key_type: psa_storage.Expr, bits: int,
+            alg: psa_storage.Expr
+    ) -> bool:
+        """Whether to the given key with the given algorithm.
+
+        Normally only the type and algorithm matter for compatibility, and
+        this is handled in crypto_knowledge.KeyType.can_do(). This function
+        exists to detect exceptional cases. Exceptional cases detected here
+        are not tested in OpFail and should therefore have manually written
+        test cases.
+        """
+        # Some test keys have the RAW_DATA type and attributes that don't
+        # necessarily make sense. We do this to validate numerical
+        # encodings of the attributes.
+        # Raw data keys have no useful exercise anyway so there is no
+        # loss of test coverage.
+        if key_type.string == 'PSA_KEY_TYPE_RAW_DATA':
+            return False
+        # OAEP requires room for two hashes plus wrapping
+        m = cls.RSA_OAEP_RE.match(alg.string)
+        if m:
+            hash_alg = m.group(1)
+            hash_length = crypto_knowledge.Algorithm.hash_length(hash_alg)
+            key_length = (bits + 7) // 8
+            # Leave enough room for at least one byte of plaintext
+            return key_length > 2 * hash_length + 2
+        # There's nothing wrong with ECC keys on Brainpool curves,
+        # but operations with them are very slow. So we only exercise them
+        # with a single algorithm, not with all possible hashes. We do
+        # exercise other curves with all algorithms so test coverage is
+        # perfectly adequate like this.
+        m = cls.BRAINPOOL_RE.match(key_type.string)
+        if m and alg.string != 'PSA_ALG_ECDSA_ANY':
+            return False
+        return True
+
     def make_test_case(self, key: StorageTestData) -> test_case.TestCase:
         """Construct a storage format test case for the given key.
 
@@ -521,10 +570,10 @@
         """
         verb = 'save' if self.forward else 'read'
         tc = test_case.TestCase()
-        tc.set_description('PSA storage {}: {}'.format(verb, key.description))
+        tc.set_description(verb + ' ' + key.description)
         dependencies = automatic_dependencies(
             key.lifetime.string, key.type.string,
-            key.expected_usage, key.alg.string, key.alg2.string,
+            key.alg.string, key.alg2.string,
         )
         dependencies = finish_family_dependencies(dependencies, key.bits)
         tc.set_dependencies(dependencies)
@@ -533,19 +582,15 @@
             extra_arguments = []
         else:
             flags = []
-            # Some test keys have the RAW_DATA type and attributes that don't
-            # necessarily make sense. We do this to validate numerical
-            # encodings of the attributes.
-            # Raw data keys have no useful exercise anyway so there is no
-            # loss of test coverage.
-            if key.type.string != 'PSA_KEY_TYPE_RAW_DATA':
+            if self.exercise_key_with_algorithm(key.type, key.bits, key.alg):
                 flags.append('TEST_FLAG_EXERCISE')
             if 'READ_ONLY' in key.lifetime.string:
                 flags.append('TEST_FLAG_READ_ONLY')
             extra_arguments = [' | '.join(flags) if flags else '0']
         tc.set_arguments([key.lifetime.string,
                           key.type.string, str(key.bits),
-                          key.expected_usage, key.alg.string, key.alg2.string,
+                          key.expected_usage.string,
+                          key.alg.string, key.alg2.string,
                           '"' + key.material.hex() + '"',
                           '"' + key.hex() + '"',
                           *extra_arguments])
@@ -559,12 +604,12 @@
         short = lifetime
         short = re.sub(r'PSA_KEY_LIFETIME_FROM_PERSISTENCE_AND_LOCATION',
                        r'', short)
-        short = re.sub(r'PSA_KEY_[A-Z]+_', r'', short)
+        short = crypto_knowledge.short_expression(short)
         description = 'lifetime: ' + short
         key = StorageTestData(version=self.version,
                               id=1, lifetime=lifetime,
                               type='PSA_KEY_TYPE_RAW_DATA', bits=8,
-                              usage='PSA_KEY_USAGE_EXPORT', alg=0, alg2=0,
+                              usage=['PSA_KEY_USAGE_EXPORT'], alg=0, alg2=0,
                               material=b'L',
                               description=description)
         return key
@@ -590,19 +635,21 @@
             test_implicit_usage: Optional[bool] = True
     ) -> StorageTestData:
         """Construct a test key for the given key usage."""
-        usage = ' | '.join(usage_flags) if usage_flags else '0'
-        if short is None:
-            short = re.sub(r'\bPSA_KEY_USAGE_', r'', usage)
         extra_desc = ' without implication' if test_implicit_usage else ''
-        description = 'usage' + extra_desc + ': ' + short
+        description = 'usage' + extra_desc + ': '
         key1 = StorageTestData(version=self.version,
                                id=1, lifetime=0x00000001,
                                type='PSA_KEY_TYPE_RAW_DATA', bits=8,
-                               expected_usage=usage,
+                               expected_usage=usage_flags,
                                without_implicit_usage=not test_implicit_usage,
-                               usage=usage, alg=0, alg2=0,
+                               usage=usage_flags, alg=0, alg2=0,
                                material=b'K',
                                description=description)
+        if short is None:
+            usage_expr = key1.expected_usage.string
+            key1.description += crypto_knowledge.short_expression(usage_expr)
+        else:
+            key1.description += short
         return key1
 
     def generate_keys_for_usage_flags(self, **kwargs) -> Iterator[StorageTestData]:
@@ -623,49 +670,70 @@
         yield from self.generate_keys_for_usage_flags()
         yield from self.generate_key_for_all_usage_flags()
 
+    def key_for_type_and_alg(
+            self,
+            kt: crypto_knowledge.KeyType,
+            bits: int,
+            alg: Optional[crypto_knowledge.Algorithm] = None,
+    ) -> StorageTestData:
+        """Construct a test key of the given type.
+
+        If alg is not None, this key allows it.
+        """
+        usage_flags = ['PSA_KEY_USAGE_EXPORT']
+        alg1 = 0 #type: psa_storage.Exprable
+        alg2 = 0
+        if alg is not None:
+            alg1 = alg.expression
+            usage_flags += alg.usage_flags(public=kt.is_public())
+        key_material = kt.key_material(bits)
+        description = 'type: {} {}-bit'.format(kt.short_expression(1), bits)
+        if alg is not None:
+            description += ', ' + alg.short_expression(1)
+        key = StorageTestData(version=self.version,
+                              id=1, lifetime=0x00000001,
+                              type=kt.expression, bits=bits,
+                              usage=usage_flags, alg=alg1, alg2=alg2,
+                              material=key_material,
+                              description=description)
+        return key
+
     def keys_for_type(
             self,
             key_type: str,
-            params: Optional[Iterable[str]] = None
+            all_algorithms: List[crypto_knowledge.Algorithm],
     ) -> Iterator[StorageTestData]:
-        """Generate test keys for the given key type.
-
-        For key types that depend on a parameter (e.g. elliptic curve family),
-        `param` is the parameter to pass to the constructor. Only a single
-        parameter is supported.
-        """
-        kt = crypto_knowledge.KeyType(key_type, params)
+        """Generate test keys for the given key type."""
+        kt = crypto_knowledge.KeyType(key_type)
         for bits in kt.sizes_to_test():
-            usage_flags = 'PSA_KEY_USAGE_EXPORT'
-            alg = 0
-            alg2 = 0
-            key_material = kt.key_material(bits)
-            short_expression = re.sub(r'\bPSA_(?:KEY_TYPE|ECC_FAMILY)_',
-                                      r'',
-                                      kt.expression)
-            description = 'type: {} {}-bit'.format(short_expression, bits)
-            key = StorageTestData(version=self.version,
-                                  id=1, lifetime=0x00000001,
-                                  type=kt.expression, bits=bits,
-                                  usage=usage_flags, alg=alg, alg2=alg2,
-                                  material=key_material,
-                                  description=description)
-            yield key
+            # Test a non-exercisable key, as well as exercisable keys for
+            # each compatible algorithm.
+            # To do: test reading a key from storage with an incompatible
+            # or unsupported algorithm.
+            yield self.key_for_type_and_alg(kt, bits)
+            compatible_algorithms = [alg for alg in all_algorithms
+                                     if kt.can_do(alg)]
+            for alg in compatible_algorithms:
+                yield self.key_for_type_and_alg(kt, bits, alg)
 
     def all_keys_for_types(self) -> Iterator[StorageTestData]:
         """Generate test keys covering key types and their representations."""
         key_types = sorted(self.constructors.key_types)
+        all_algorithms = [crypto_knowledge.Algorithm(alg)
+                          for alg in self.constructors.generate_expressions(
+                              sorted(self.constructors.algorithms)
+                          )]
         for key_type in self.constructors.generate_expressions(key_types):
-            yield from self.keys_for_type(key_type)
+            yield from self.keys_for_type(key_type, all_algorithms)
 
     def keys_for_algorithm(self, alg: str) -> Iterator[StorageTestData]:
-        """Generate test keys for the specified algorithm."""
-        # For now, we don't have information on the compatibility of key
-        # types and algorithms. So we just test the encoding of algorithms,
-        # and not that operations can be performed with them.
-        descr = re.sub(r'PSA_ALG_', r'', alg)
-        descr = re.sub(r',', r', ', re.sub(r' +', r'', descr))
-        usage = 'PSA_KEY_USAGE_EXPORT'
+        """Generate test keys for the encoding of the specified algorithm."""
+        # These test cases only validate the encoding of algorithms, not
+        # whether the key read from storage is suitable for an operation.
+        # `keys_for_types` generate read tests with an algorithm and a
+        # compatible key.
+        descr = crypto_knowledge.short_expression(alg, 1)
+        usage = ['PSA_KEY_USAGE_EXPORT']
         key1 = StorageTestData(version=self.version,
                                id=1, lifetime=0x00000001,
                                type='PSA_KEY_TYPE_RAW_DATA', bits=8,
@@ -738,17 +806,14 @@
         """
         bits = key_type.sizes_to_test()[0]
         implicit_usage = StorageKey.IMPLICIT_USAGE_FLAGS[implyer_usage]
-        usage_flags = 'PSA_KEY_USAGE_EXPORT'
-        material_usage_flags = usage_flags + ' | ' + implyer_usage
-        expected_usage_flags = material_usage_flags + ' | ' + implicit_usage
+        usage_flags = ['PSA_KEY_USAGE_EXPORT']
+        material_usage_flags = usage_flags + [implyer_usage]
+        expected_usage_flags = material_usage_flags + [implicit_usage]
         alg2 = 0
         key_material = key_type.key_material(bits)
-        usage_expression = re.sub(r'PSA_KEY_USAGE_', r'', implyer_usage)
-        alg_expression = re.sub(r'PSA_ALG_', r'', alg)
-        alg_expression = re.sub(r',', r', ', re.sub(r' +', r'', alg_expression))
-        key_type_expression = re.sub(r'\bPSA_(?:KEY_TYPE|ECC_FAMILY)_',
-                                     r'',
-                                     key_type.expression)
+        usage_expression = crypto_knowledge.short_expression(implyer_usage, 1)
+        alg_expression = crypto_knowledge.short_expression(alg, 1)
+        key_type_expression = key_type.short_expression(1)
         description = 'implied by {}: {} {} {}-bit'.format(
             usage_expression, alg_expression, key_type_expression, bits)
         key = StorageTestData(version=self.version,
@@ -822,8 +887,10 @@
                 for key_type in sorted(alg_with_keys[alg]):
                     # The key types must be filtered to fit the specific usage flag.
                     kt = crypto_knowledge.KeyType(key_type)
-                    if kt.is_valid_for_signature(usage):
-                        yield self.keys_for_implicit_usage(usage, alg, kt)
+                    if kt.is_public() and '_SIGN_' in usage:
+                        # Can't sign with a public key
+                        continue
+                    yield self.keys_for_implicit_usage(usage, alg, kt)
 
     def generate_all_keys(self) -> Iterator[StorageTestData]:
         yield from super().generate_all_keys()
diff --git a/tests/scripts/test_psa_constant_names.py b/tests/scripts/test_psa_constant_names.py
index 07c8ab2..e43a0ba 100755
--- a/tests/scripts/test_psa_constant_names.py
+++ b/tests/scripts/test_psa_constant_names.py
@@ -77,6 +77,22 @@
     """
     return re.sub(NORMALIZE_STRIP_RE, '', expr)
 
+ALG_TRUNCATED_TO_SELF_RE = \
+    re.compile(r'PSA_ALG_AEAD_WITH_SHORTENED_TAG\('
+               r'PSA_ALG_(?:CCM|CHACHA20_POLY1305|GCM)'
+               r', *16\)\Z')
+
+def is_simplifiable(expr: str) -> bool:
+    """Determine whether an expression is simplifiable.
+
+    Simplifiable expressions can't be output in their input form, since
+    the output will be the simple form. Therefore they must be excluded
+    from testing.
+    """
+    if ALG_TRUNCATED_TO_SELF_RE.match(expr):
+        return True
+    return False
+
 def collect_values(inputs: InputsForTest,
                    type_word: str,
                    include_path: Optional[str] = None,
@@ -87,7 +103,9 @@
     value is a string representation of its integer value.
     """
     names = inputs.get_names(type_word)
-    expressions = sorted(inputs.generate_expressions(names))
+    expressions = sorted(expr
+                         for expr in inputs.generate_expressions(names)
+                         if not is_simplifiable(expr))
     values = run_c(type_word, expressions,
                    include_path=include_path, keep_c=keep_c)
     return expressions, values
diff --git a/tests/src/psa_exercise_key.c b/tests/src/psa_exercise_key.c
index 71a1b78..9576afd 100644
--- a/tests/src/psa_exercise_key.c
+++ b/tests/src/psa_exercise_key.c
@@ -164,20 +164,29 @@
                                 psa_algorithm_t alg )
 {
     psa_cipher_operation_t operation = PSA_CIPHER_OPERATION_INIT;
-    unsigned char iv[16] = {0};
-    size_t iv_length = sizeof( iv );
+    unsigned char iv[PSA_CIPHER_IV_MAX_SIZE] = {0};
+    size_t iv_length;
+    psa_key_attributes_t attributes = PSA_KEY_ATTRIBUTES_INIT;
+    psa_key_type_t key_type;
     const unsigned char plaintext[16] = "Hello, world...";
     unsigned char ciphertext[32] = "(wabblewebblewibblewobblewubble)";
     size_t ciphertext_length = sizeof( ciphertext );
     unsigned char decrypted[sizeof( ciphertext )];
     size_t part_length;
 
+    PSA_ASSERT( psa_get_key_attributes( key, &attributes ) );
+    key_type = psa_get_key_type( &attributes );
+    iv_length = PSA_CIPHER_IV_LENGTH( key_type, alg );
+
     if( usage & PSA_KEY_USAGE_ENCRYPT )
     {
         PSA_ASSERT( psa_cipher_encrypt_setup( &operation, key, alg ) );
-        PSA_ASSERT( psa_cipher_generate_iv( &operation,
-                                            iv, sizeof( iv ),
-                                            &iv_length ) );
+        if( iv_length != 0 )
+        {
+            PSA_ASSERT( psa_cipher_generate_iv( &operation,
+                                                iv, sizeof( iv ),
+                                                &iv_length ) );
+        }
         PSA_ASSERT( psa_cipher_update( &operation,
                                        plaintext, sizeof( plaintext ),
                                        ciphertext, sizeof( ciphertext ),
@@ -195,18 +204,14 @@
         int maybe_invalid_padding = 0;
         if( ! ( usage & PSA_KEY_USAGE_ENCRYPT ) )
         {
-            psa_key_attributes_t attributes = PSA_KEY_ATTRIBUTES_INIT;
-            PSA_ASSERT( psa_get_key_attributes( key, &attributes ) );
-            /* This should be PSA_CIPHER_GET_IV_SIZE but the API doesn't
-             * have this macro yet. */
-            iv_length = PSA_BLOCK_CIPHER_BLOCK_LENGTH(
-                psa_get_key_type( &attributes ) );
             maybe_invalid_padding = ! PSA_ALG_IS_STREAM_CIPHER( alg );
-            psa_reset_key_attributes( &attributes );
         }
         PSA_ASSERT( psa_cipher_decrypt_setup( &operation, key, alg ) );
-        PSA_ASSERT( psa_cipher_set_iv( &operation,
-                                       iv, iv_length ) );
+        if( iv_length != 0 )
+        {
+            PSA_ASSERT( psa_cipher_set_iv( &operation,
+                                           iv, iv_length ) );
+        }
         PSA_ASSERT( psa_cipher_update( &operation,
                                        ciphertext, ciphertext_length,
                                        decrypted, sizeof( decrypted ),
@@ -229,6 +234,7 @@
 
 exit:
     psa_cipher_abort( &operation );
+    psa_reset_key_attributes( &attributes );
     return( 0 );
 }
 
@@ -236,8 +242,10 @@
                               psa_key_usage_t usage,
                               psa_algorithm_t alg )
 {
-    unsigned char nonce[16] = {0};
-    size_t nonce_length = sizeof( nonce );
+    unsigned char nonce[PSA_AEAD_NONCE_MAX_SIZE] = {0};
+    size_t nonce_length;
+    psa_key_attributes_t attributes = PSA_KEY_ATTRIBUTES_INIT;
+    psa_key_type_t key_type;
     unsigned char plaintext[16] = "Hello, world...";
     unsigned char ciphertext[48] = "(wabblewebblewibblewobblewubble)";
     size_t ciphertext_length = sizeof( ciphertext );
@@ -249,19 +257,9 @@
         alg = PSA_ALG_AEAD_WITH_SHORTENED_TAG( alg, PSA_ALG_AEAD_GET_TAG_LENGTH( alg ) );
     }
 
-    /* Default IV length for AES-GCM is 12 bytes */
-    if( PSA_ALG_AEAD_WITH_SHORTENED_TAG( alg, 0 ) ==
-        PSA_ALG_AEAD_WITH_SHORTENED_TAG( PSA_ALG_GCM, 0 ) )
-    {
-        nonce_length = 12;
-    }
-
-    /* IV length for CCM needs to be between 7 and 13 bytes */
-    if( PSA_ALG_AEAD_WITH_SHORTENED_TAG( alg, 0 ) ==
-        PSA_ALG_AEAD_WITH_SHORTENED_TAG( PSA_ALG_CCM, 0 ) )
-    {
-        nonce_length = 12;
-    }
+    PSA_ASSERT( psa_get_key_attributes( key, &attributes ) );
+    key_type = psa_get_key_type( &attributes );
+    nonce_length = PSA_AEAD_NONCE_LENGTH( key_type, alg );
 
     if( usage & PSA_KEY_USAGE_ENCRYPT )
     {
@@ -291,9 +289,21 @@
     return( 1 );
 
 exit:
+    psa_reset_key_attributes( &attributes );
     return( 0 );
 }
 
+static int can_sign_or_verify_message( psa_key_usage_t usage,
+                                       psa_algorithm_t alg )
+{
+    /* Sign-the-unspecified-hash algorithms can only be used with
+     * {sign,verify}_hash, not with {sign,verify}_message. */
+    if( alg == PSA_ALG_ECDSA_ANY || alg == PSA_ALG_RSA_PKCS1V15_SIGN_RAW )
+        return( 0 );
+    return( usage & ( PSA_KEY_USAGE_SIGN_MESSAGE |
+                      PSA_KEY_USAGE_VERIFY_MESSAGE ) );
+}
+
 static int exercise_signature_key( mbedtls_svc_key_id_t key,
                                    psa_key_usage_t usage,
                                    psa_algorithm_t alg )
@@ -344,7 +354,7 @@
         }
     }
 
-    if( usage & ( PSA_KEY_USAGE_SIGN_MESSAGE | PSA_KEY_USAGE_VERIFY_MESSAGE ) )
+    if( can_sign_or_verify_message( usage, alg ) )
     {
         unsigned char message[256] = "Hello, world...";
         unsigned char signature[PSA_SIGNATURE_MAX_SIZE] = {0};
@@ -613,15 +623,39 @@
                                        psa_algorithm_t alg )
 {
     psa_key_derivation_operation_t operation = PSA_KEY_DERIVATION_OPERATION_INIT;
+    unsigned char input[1];
     unsigned char output[1];
     int ok = 0;
+    psa_algorithm_t kdf_alg = PSA_ALG_KEY_AGREEMENT_GET_KDF( alg );
 
     if( usage & PSA_KEY_USAGE_DERIVE )
     {
         /* We need two keys to exercise key agreement. Exercise the
          * private key against its own public key. */
         PSA_ASSERT( psa_key_derivation_setup( &operation, alg ) );
+        if( PSA_ALG_IS_TLS12_PRF( kdf_alg ) ||
+            PSA_ALG_IS_TLS12_PSK_TO_MS( kdf_alg ) )
+        {
+            PSA_ASSERT( psa_key_derivation_input_bytes(
+                            &operation, PSA_KEY_DERIVATION_INPUT_SEED,
+                            input, sizeof( input ) ) );
+        }
+
         PSA_ASSERT( mbedtls_test_psa_key_agreement_with_self( &operation, key ) );
+
+        if( PSA_ALG_IS_TLS12_PRF( kdf_alg ) ||
+            PSA_ALG_IS_TLS12_PSK_TO_MS( kdf_alg ) )
+        {
+            PSA_ASSERT( psa_key_derivation_input_bytes(
+                            &operation, PSA_KEY_DERIVATION_INPUT_LABEL,
+                            input, sizeof( input ) ) );
+        }
+        else if( PSA_ALG_IS_HKDF( kdf_alg ) )
+        {
+            PSA_ASSERT( psa_key_derivation_input_bytes(
+                            &operation, PSA_KEY_DERIVATION_INPUT_INFO,
+                            input, sizeof( input ) ) );
+        }
         PSA_ASSERT( psa_key_derivation_output_bytes( &operation,
                                                      output,
                                                      sizeof( output ) ) );
diff --git a/tests/suites/test_suite_psa_crypto.data b/tests/suites/test_suite_psa_crypto.data
index 5939b39..14343aa 100644
--- a/tests/suites/test_suite_psa_crypto.data
+++ b/tests/suites/test_suite_psa_crypto.data
@@ -2109,23 +2109,23 @@
 
 PSA symmetric encrypt: AES-ECB, 0 bytes, good
 depends_on:PSA_WANT_ALG_ECB_NO_PADDING:PSA_WANT_KEY_TYPE_AES
-cipher_encrypt_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_AES:"2b7e151628aed2a6abf7158809cf4f3c":"":""
+cipher_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_AES:"2b7e151628aed2a6abf7158809cf4f3c":"":""
 
 PSA symmetric encrypt: AES-ECB, 16 bytes, good
 depends_on:PSA_WANT_ALG_ECB_NO_PADDING:PSA_WANT_KEY_TYPE_AES
-cipher_encrypt_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_AES:"2b7e151628aed2a6abf7158809cf4f3c":"6bc1bee22e409f96e93d7e117393172a":"3ad77bb40d7a3660a89ecaf32466ef97"
+cipher_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_AES:"2b7e151628aed2a6abf7158809cf4f3c":"6bc1bee22e409f96e93d7e117393172a":"3ad77bb40d7a3660a89ecaf32466ef97"
 
 PSA symmetric encrypt: AES-ECB, 32 bytes, good
 depends_on:PSA_WANT_ALG_ECB_NO_PADDING:PSA_WANT_KEY_TYPE_AES
-cipher_encrypt_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_AES:"2b7e151628aed2a6abf7158809cf4f3c":"6bc1bee22e409f96e93d7e117393172a3ad77bb40d7a3660a89ecaf32466ef97":"3ad77bb40d7a3660a89ecaf32466ef972249a2638c6f1c755a84f9681a9f08c1"
+cipher_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_AES:"2b7e151628aed2a6abf7158809cf4f3c":"6bc1bee22e409f96e93d7e117393172a3ad77bb40d7a3660a89ecaf32466ef97":"3ad77bb40d7a3660a89ecaf32466ef972249a2638c6f1c755a84f9681a9f08c1"
 
 PSA symmetric encrypt: 2-key 3DES-ECB, 8 bytes, good
 depends_on:PSA_WANT_ALG_ECB_NO_PADDING:PSA_WANT_KEY_TYPE_DES
-cipher_encrypt_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_DES:"01020407080b0d0ec1c2c4c7c8cbcdce":"c78e2b38139610e3":"5d0652429c5b0ac7"
+cipher_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_DES:"01020407080b0d0ec1c2c4c7c8cbcdce":"c78e2b38139610e3":"5d0652429c5b0ac7"
 
 PSA symmetric encrypt: 3-key 3DES-ECB, 8 bytes, good
 depends_on:PSA_WANT_ALG_ECB_NO_PADDING:PSA_WANT_KEY_TYPE_DES
-cipher_encrypt_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_DES:"01020407080b0d0ec1c2c4c7c8cbcdce31323437383b3d3e":"c78e2b38139610e3":"817ca7d69b80d86a"
+cipher_alg_without_iv:PSA_ALG_ECB_NO_PADDING:PSA_KEY_TYPE_DES:"01020407080b0d0ec1c2c4c7c8cbcdce31323437383b3d3e":"c78e2b38139610e3":"817ca7d69b80d86a"
 
 PSA symmetric encrypt validation: AES-CBC-nopad, 16 bytes, good
 depends_on:PSA_WANT_ALG_CBC_NO_PADDING:PSA_WANT_KEY_TYPE_AES
diff --git a/tests/suites/test_suite_psa_crypto.function b/tests/suites/test_suite_psa_crypto.function
index ea0d5c4..6cd6bee 100644
--- a/tests/suites/test_suite_psa_crypto.function
+++ b/tests/suites/test_suite_psa_crypto.function
@@ -3304,72 +3304,117 @@
 /* END_CASE */
 
 /* BEGIN_CASE */
-void cipher_encrypt_alg_without_iv( int alg_arg,
-                                    int key_type_arg,
-                                    data_t *key_data,
-                                    data_t *input,
-                                    data_t *expected_output )
+void cipher_alg_without_iv( int alg_arg, int key_type_arg, data_t *key_data,
+                            data_t *plaintext, data_t *ciphertext )
 {
     mbedtls_svc_key_id_t key = MBEDTLS_SVC_KEY_ID_INIT;
     psa_key_type_t key_type = key_type_arg;
     psa_algorithm_t alg = alg_arg;
     psa_cipher_operation_t operation = PSA_CIPHER_OPERATION_INIT;
     uint8_t iv[1] = { 0x5a };
-    size_t iv_length;
     unsigned char *output = NULL;
     size_t output_buffer_size = 0;
-    size_t output_length = 0;
+    size_t output_length, length;
     psa_key_attributes_t attributes = PSA_KEY_ATTRIBUTES_INIT;
 
     PSA_ASSERT( psa_crypto_init( ) );
 
-    psa_set_key_usage_flags( &attributes, PSA_KEY_USAGE_ENCRYPT );
+    /* Validate size macros */
+    TEST_ASSERT( ciphertext->len <=
+                 PSA_CIPHER_ENCRYPT_OUTPUT_SIZE( key_type, alg, plaintext->len ) );
+    TEST_ASSERT( PSA_CIPHER_ENCRYPT_OUTPUT_SIZE( key_type, alg, plaintext->len ) <=
+                 PSA_CIPHER_ENCRYPT_OUTPUT_MAX_SIZE( plaintext->len ) );
+    TEST_ASSERT( plaintext->len <=
+                 PSA_CIPHER_DECRYPT_OUTPUT_SIZE( key_type, alg, ciphertext->len ) );
+    TEST_ASSERT( PSA_CIPHER_DECRYPT_OUTPUT_SIZE( key_type, alg, ciphertext->len ) <=
+                 PSA_CIPHER_DECRYPT_OUTPUT_MAX_SIZE( ciphertext->len ) );
+
+
+    /* Set up key and output buffer */
+    psa_set_key_usage_flags( &attributes,
+                             PSA_KEY_USAGE_ENCRYPT | PSA_KEY_USAGE_DECRYPT );
     psa_set_key_algorithm( &attributes, alg );
     psa_set_key_type( &attributes, key_type );
-
-    output_buffer_size = PSA_CIPHER_ENCRYPT_OUTPUT_SIZE( key_type, alg, input->len );
-    ASSERT_ALLOC( output, output_buffer_size );
-
     PSA_ASSERT( psa_import_key( &attributes, key_data->x, key_data->len,
                                 &key ) );
+    output_buffer_size = PSA_CIPHER_ENCRYPT_OUTPUT_SIZE( key_type, alg,
+                                                         plaintext->len );
+    ASSERT_ALLOC( output, output_buffer_size );
 
+    /* set_iv() is not allowed */
     PSA_ASSERT( psa_cipher_encrypt_setup( &operation, key, alg ) );
     TEST_EQUAL( psa_cipher_set_iv( &operation, iv, sizeof( iv ) ),
                 PSA_ERROR_BAD_STATE );
-    PSA_ASSERT( psa_cipher_encrypt_setup( &operation, key, alg ) );
-    TEST_EQUAL( psa_cipher_generate_iv( &operation, iv, sizeof( iv ),
-                                        &iv_length ),
+    PSA_ASSERT( psa_cipher_decrypt_setup( &operation, key, alg ) );
+    TEST_EQUAL( psa_cipher_set_iv( &operation, iv, sizeof( iv ) ),
                 PSA_ERROR_BAD_STATE );
 
-    /* Encrypt, one-shot */
-    PSA_ASSERT( psa_cipher_encrypt( key, alg, input->x, input->len, output,
-                                    output_buffer_size, &output_length ) );
-    TEST_ASSERT( output_length <=
-                 PSA_CIPHER_ENCRYPT_OUTPUT_SIZE( key_type, alg, input->len ) );
-    TEST_ASSERT( output_length <=
-                 PSA_CIPHER_ENCRYPT_OUTPUT_MAX_SIZE( input->len ) );
+    /* generate_iv() is not allowed */
+    PSA_ASSERT( psa_cipher_encrypt_setup( &operation, key, alg ) );
+    TEST_EQUAL( psa_cipher_generate_iv( &operation, iv, sizeof( iv ),
+                                        &length ),
+                PSA_ERROR_BAD_STATE );
+    PSA_ASSERT( psa_cipher_decrypt_setup( &operation, key, alg ) );
+    TEST_EQUAL( psa_cipher_generate_iv( &operation, iv, sizeof( iv ),
+                                        &length ),
+                PSA_ERROR_BAD_STATE );
 
-    ASSERT_COMPARE( expected_output->x, expected_output->len,
+    /* Multipart encryption */
+    PSA_ASSERT( psa_cipher_encrypt_setup( &operation, key, alg ) );
+    output_length = 0;
+    length = ~0;
+    PSA_ASSERT( psa_cipher_update( &operation,
+                                   plaintext->x, plaintext->len,
+                                   output, output_buffer_size,
+                                   &length ) );
+    TEST_ASSERT( length <= output_buffer_size );
+    output_length += length;
+    PSA_ASSERT( psa_cipher_finish( &operation,
+                                   output + output_length,
+                                   output_buffer_size - output_length,
+                                   &length ) );
+    output_length += length;
+    ASSERT_COMPARE( ciphertext->x, ciphertext->len,
                     output, output_length );
 
-    /* Encrypt, multi-part */
-    PSA_ASSERT( psa_cipher_abort( &operation ) );
-    PSA_ASSERT( psa_cipher_encrypt_setup( &operation, key, alg ) );
-
-    PSA_ASSERT( psa_cipher_update( &operation, input->x, input->len,
+    /* Multipart encryption */
+    PSA_ASSERT( psa_cipher_decrypt_setup( &operation, key, alg ) );
+    output_length = 0;
+    length = ~0;
+    PSA_ASSERT( psa_cipher_update( &operation,
+                                   ciphertext->x, ciphertext->len,
                                    output, output_buffer_size,
-                                   &output_length) );
-    TEST_ASSERT( output_length <=
-                 PSA_CIPHER_ENCRYPT_OUTPUT_SIZE( key_type, alg, input->len ) );
-    TEST_ASSERT( output_length <=
-                 PSA_CIPHER_ENCRYPT_OUTPUT_MAX_SIZE( input->len ) );
+                                   &length ) );
+    TEST_ASSERT( length <= output_buffer_size );
+    output_length += length;
+    PSA_ASSERT( psa_cipher_finish( &operation,
+                                   output + output_length,
+                                   output_buffer_size - output_length,
+                                   &length ) );
+    output_length += length;
+    ASSERT_COMPARE( plaintext->x, plaintext->len,
+                    output, output_length );
 
-    ASSERT_COMPARE( expected_output->x, expected_output->len,
+    /* One-shot encryption */
+    output_length = ~0;
+    PSA_ASSERT( psa_cipher_encrypt( key, alg, plaintext->x, plaintext->len,
+                                    output, output_buffer_size,
+                                    &output_length ) );
+    ASSERT_COMPARE( ciphertext->x, ciphertext->len,
+                    output, output_length );
+
+    /* One-shot decryption */
+    output_length = ~0;
+    PSA_ASSERT( psa_cipher_decrypt( key, alg, ciphertext->x, ciphertext->len,
+                                    output, output_buffer_size,
+                                    &output_length ) );
+    ASSERT_COMPARE( plaintext->x, plaintext->len,
                     output, output_length );
 
 exit:
     PSA_ASSERT( psa_cipher_abort( &operation ) );
     mbedtls_free( output );
+    psa_cipher_abort( &operation );
     psa_destroy_key( key );
     PSA_DONE( );
 }
diff --git a/tests/suites/test_suite_psa_crypto_storage_format.function b/tests/suites/test_suite_psa_crypto_storage_format.function
index b90ef6e..c52dae1 100644
--- a/tests/suites/test_suite_psa_crypto_storage_format.function
+++ b/tests/suites/test_suite_psa_crypto_storage_format.function
@@ -60,6 +60,155 @@
         return( 0 );
 }
 
+#if defined(MBEDTLS_TEST_LIBTESTDRIVER1)
+static int is_accelerated_rsa( psa_algorithm_t alg )
+{
+#if defined(MBEDTLS_PSA_ACCEL_ALG_RSA_PKCS1V15_SIGN)
+    if ( PSA_ALG_IS_RSA_PKCS1V15_SIGN( alg ) )
+        return( 1 );
+#endif
+#if defined(MBEDTLS_PSA_ACCEL_ALG_RSA_PSS)
+    if( PSA_ALG_IS_RSA_PSS( alg ) )
+        return( 1 );
+#endif
+#if defined(MBEDTLS_PSA_ACCEL_ALG_RSA_OAEP)
+    if( PSA_ALG_IS_RSA_OAEP( alg ) )
+        return( 1 );
+#endif
+    (void) alg;
+    return( 0 );
+}
+
+/* Whether the algorithm is implemented as a builtin, i.e. not accelerated,
+ * and calls mbedtls_md() functions that require the hash algorithm to
+ * also be built-in. */
+static int is_builtin_calling_md( psa_algorithm_t alg )
+{
+#if defined(MBEDTLS_PSA_BUILTIN_ALG_RSA_PKCS1V15_SIGN)
+    if( PSA_ALG_IS_RSA_PKCS1V15_SIGN( alg ) )
+        return( 1 );
+#endif
+#if defined(MBEDTLS_PSA_BUILTIN_ALG_RSA_PSS)
+    if( PSA_ALG_IS_RSA_PSS( alg ) )
+        return( 1 );
+#endif
+#if defined(MBEDTLS_PSA_BUILTIN_ALG_RSA_OAEP)
+    if( PSA_ALG_IS_RSA_OAEP( alg ) )
+        return( 1 );
+#endif
+#if defined(MBEDTLS_PSA_BUILTIN_ALG_DETERMINISTIC_ECDSA)
+    if( PSA_ALG_IS_DETERMINISTIC_ECDSA( alg ) )
+        return( 1 );
+#endif
+    (void) alg;
+    return( 0 );
+}
+
+static int has_builtin_hash( psa_algorithm_t alg )
+{
+#if !defined(MBEDTLS_MD5_C)
+    if( alg == PSA_ALG_MD5 )
+        return( 0 );
+#endif
+#if !defined(MBEDTLS_RIPEMD160_C)
+    if( alg == PSA_ALG_RIPEMD160 )
+        return( 0 );
+#endif
+#if !defined(MBEDTLS_SHA1_C)
+    if( alg == PSA_ALG_SHA_1 )
+        return( 0 );
+#endif
+#if !defined(MBEDTLS_SHA224_C)
+    if( alg == PSA_ALG_SHA_224 )
+        return( 0 );
+#endif
+#if !defined(MBEDTLS_SHA256_C)
+    if( alg == PSA_ALG_SHA_256 )
+        return( 0 );
+#endif
+#if !defined(MBEDTLS_SHA384_C)
+    if( alg == PSA_ALG_SHA_384 )
+        return( 0 );
+#endif
+#if !defined(MBEDTLS_SHA512_C)
+    if( alg == PSA_ALG_SHA_512 )
+        return( 0 );
+#endif
+    (void) alg;
+    return( 1 );
+}
+#endif
+
+/* Mbed TLS doesn't support certain combinations of key type and algorithm
+ * in certain configurations. */
+static int can_exercise( const psa_key_attributes_t *attributes )
+{
+    psa_key_type_t key_type = psa_get_key_type( attributes );
+    psa_algorithm_t alg = psa_get_key_algorithm( attributes );
+    psa_algorithm_t hash_alg =
+        PSA_ALG_IS_HASH_AND_SIGN( alg ) ? PSA_ALG_SIGN_GET_HASH( alg ) :
+        PSA_ALG_IS_RSA_OAEP( alg ) ? PSA_ALG_RSA_OAEP_GET_HASH( alg ) :
+        PSA_ALG_NONE;
+    psa_key_usage_t usage = psa_get_key_usage_flags( attributes );
+
+#if defined(MBEDTLS_TEST_LIBTESTDRIVER1)
+    /* We test some configurations using drivers where the driver doesn't
+     * support certain hash algorithms, but declares that it supports
+     * compound algorithms that use those hashes. Until this is fixed,
+     * in those configurations, don't try to actually perform operations.
+     *
+     * Hash-and-sign algorithms where the asymmetric part doesn't use
+     * a hash operation are ok. So randomized ECDSA signature is fine,
+     * ECDSA verification is fine, but deterministic ECDSA signature is
+     * affected. All RSA signatures are affected except raw PKCS#1v1.5.
+     * OAEP is also affected.
+     */
+    if( PSA_ALG_IS_DETERMINISTIC_ECDSA( alg ) &&
+        ! ( usage & ( PSA_KEY_USAGE_SIGN_HASH | PSA_KEY_USAGE_SIGN_MESSAGE ) ) )
+    {
+        /* Verification only. Verification doesn't use the hash algorithm. */
+        return( 1 );
+    }
+
+#if defined(MBEDTLS_PSA_ACCEL_ALG_DETERMINISTIC_ECDSA)
+    if( PSA_ALG_IS_DETERMINISTIC_ECDSA( alg ) &&
+        ( hash_alg == PSA_ALG_MD5 ||
+          hash_alg == PSA_ALG_RIPEMD160 ||
+          hash_alg == PSA_ALG_SHA_1 ) )
+    {
+        return( 0 );
+    }
+#endif
+    if( is_accelerated_rsa( alg ) &&
+        ( hash_alg == PSA_ALG_RIPEMD160 || hash_alg == PSA_ALG_SHA_384 ) )
+    {
+            return( 0 );
+    }
+#if defined(MBEDTLS_PSA_ACCEL_ALG_RSA_OAEP)
+    if( PSA_ALG_IS_RSA_OAEP( alg ) &&
+        ( hash_alg == PSA_ALG_RIPEMD160 || hash_alg == PSA_ALG_SHA_384 ) )
+    {
+        return( 0 );
+    }
+#endif
+
+    /* The built-in implementation of asymmetric algorithms that use a
+     * hash internally only dispatch to the internal md module, not to
+     * PSA. Until this is supported, don't try to actually perform
+     * operations when the operation is built-in and the hash isn't.  */
+    if( is_builtin_calling_md( alg ) && ! has_builtin_hash( hash_alg ) )
+    {
+        return( 0 );
+    }
+#endif /* MBEDTLS_TEST_LIBTESTDRIVER1 */
+
+    (void) key_type;
+    (void) alg;
+    (void) hash_alg;
+    (void) usage;
+    return( 1 );
+}
+
 /** Write a key with the given representation to storage, then check
  * that it has the given attributes and (if exportable) key material.
  *
@@ -108,7 +257,7 @@
                         exported_material, length );
     }
 
-    if( flags & TEST_FLAG_EXERCISE )
+    if( ( flags & TEST_FLAG_EXERCISE ) && can_exercise( &actual_attributes ) )
     {
         TEST_ASSERT( mbedtls_test_psa_exercise_key(
                          key_id,