Interruptible/bounded-latency asymmetric operations

Use case

There are some systems in which there is a requirement for asymmetric cryptographic operations in execution contexts that cannot tolerate long-running functions. However, some asymmetric operations have long, very long, or even arbitrary execution times.

For example, these use cases can arise in constrained microcontrollers that have real-time response requirements, or in firmware that executes in highly-privileged execution modes.

Proposal

The long-duration asymmetric operations are typically composed of many repeated smaller steps. If the Crypto API exposed a mechanism for the application to perform the operation in a step-wise — 'interruptible' — manner, then the application can meet the bounded-latency requirement by repeatedly calling the API to make progress on the operation.

Mbed-TLS now has a prototype API for interruptible hash signature operations (sigh-hash and verify-hash), which effectively proposes a general pattern for this type of API.

The API is composed of the following building-blocks. For details of the proposal please see https://github.com/Mbed-TLS/mbedtls/pull/6279.

`PSA_OPERATION_INCOMPLETE` (macro)

This is a non-error status code to indicate an incomplete interruptible operation. This is already defined in the Status code API.

ops

This is a term used to describe a 'unit of work' that can be carried out within an interruptible operation. The actual 'size' or time duration for one op is implementation- and function- specific, and can also be dependent on the algorithm inputs (such as the key size).

An application can set a global 'max ops' value, that limits the ops performed within any interruptible function. If an interruptible function does not complete before reaching this threshold it will return PSA_OPERATION_INCOMPLETE instead of an error or success status.

The current threshold can also be queried. When an interruptible operation completes, the application can also query the total number of ops required: this can allow an application to tune the threshold value it uses.

Interruptible operation object

An interruptible operation requires the management of state relating to the operation. This is held (or referenced, depending on implementation) in an implementation-defined object that this allocated by the application. The allocation and lifecycle of these objects follows a similar pattern to that used for multi-part operations in the existing API.

Interruptible operation objects must be initialized before first use, also like the multi-part operation objects.

Interruptible operation sequence

Each interruptible operation will have a set-up function to provide the input parameters. This is typically named psa_xxx_start(), for example, psa_sign_hash_start().

To progress the operation, a matching psa_xxx_complete() function is called repeatedly, providing any required output parameters:

If the operation finishes, the output is provided and PSA_SUCCESS is returned.
If the operation fails, then an appropriate error status is returned
If the operation has not completed yet, PSA_OPERATION_INCOMPLETE is returned. The caller should invoke the psa_xxx_complete() function again

On successful completion, the operation object is reset, but can still be queried to determine the number of ops required.

On error, the operation object enters an error state, and must be reset by a call to psa_xxx_abort(). The application can also call psa_xxx_abort() to cancel an in-progress interruptible operation.

Counter-proposal

After doing more analysis of the Mbed TLS experimental API for interruptible sign-hash operations, and considering additional future use cases for asymmetric signature operations, I would like to propose a different (but similar) interface for these operations.

The background, analysis, and rationale is rather much to put into a comment in this issue, and may be important for future work that addresses some of the use cases. So I've written this up as discussion topic #98. I've replicated the interruptible API definition part of that below.

API design proposal

The API concepts are the same: the PSA_OPERATION_INCOMPLETE status code, the idea of ops, and functions that need to be called repeatedly until the process completes.

The proposed structures and functions for interruptible signature operations, are as follows:

typedef /* impdef */ psa_sign_interruptible_operation_t;
#define PSA_SIGN_INTERRUPTIBLE_OPERATION_INIT /* impdef */
psa_sign_interruptible_operation_t psa_sign_interruptible_operation_init();
psa_status_t psa_sign_interruptible_setup(psa_sign_interruptible_operation_t *op,
                                          psa_key_id_t key, psa_algorithm_t alg);
psa_status_t psa_sign_interruptible_setup_complete(psa_sign_interruptible_operation_t *op);
psa_status_t psa_sign_interruptible_hash(psa_sign_interruptible_operation_t *op,
                                         const uint8_t *hash, size_t hash_len);
psa_status_t psa_sign_interruptible_update(psa_sign_interruptible_operation_t *op,
                                           const uint8_t *buf, size_t buf_len);
psa_status_t psa_sign_interruptible_complete(psa_sign_interruptible_operation_t *op,
                                             uint8_t *sig, size_t sig_size, size_t *sig_len);
psa_status_t psa_sign_interruptible_abort(psa_sign_interruptible_operation_t *op);

typedef /* impdef */ psa_verify_interruptible_operation_t;
#define PSA_VERIFY_INTERRUPTIBLE_OPERATION_INIT /* impdef */
psa_verify_interruptible_operation_t psa_verify_interruptible_operation_init();
psa_status_t psa_verify_interruptible_setup(psa_verify_interruptible_operation_t *op,
                                            psa_key_id_t key, psa_algorithm_t alg,
                                            const uint8_t *sig, size_t sig_len);
psa_status_t psa_verify_interruptible_setup_complete(psa_verify_interruptible_operation_t *op);
psa_status_t psa_verify_interruptible_hash(psa_verify_interruptible_operation_t *op,
                                           const uint8_t *hash, size_t hash_len);
psa_status_t psa_verify_interruptible_update(psa_verify_interruptible_operation_t *op,
                                             const uint8_t *buf, size_t buf_len);
psa_status_t psa_verify_interruptible_complete(psa_verify_interruptible_operation_t *op);
psa_status_t psa_verify_interruptible_abort(psa_verify_interruptible_operation_t *op);

Many signature and verification algorithms involve complex processing of the key and/or signature prior to processing the message data. This is why the setup functions have a matching completion function that enables this step to be interruptible.

The application must either provide a message digest by calling psa_sign_interruptible_hash() or psa_verify_interruptible_hash(), OR, provide message data by calling psa_sign_interruptible_update() or psa_verify_interruptible_update() one or more times. (Note that some algorithms will only support one method).

The structure and naming of this API does permit Mbed TLS to continue to provide its experimental interruptible sign-hash API, implemented as a thin wrapper over this proposal.

Example usage of the interruptible sign operation

This is simplified code, to demonstrate the API flow.

Initialize the operation:

psa_sign_interruptible_operation_top = {0};

Setup the signing algorithm and key:
```
psa_sign_interruptible_setup(&op, key, alg);
while (psa_sign_interruptible_setup_complete(&op) == PSA_OPERATION_INCOMPLETE)
   ;
```
Question: do we want to always require a call to psa_sign_interruptible_setup_complete(), or might simpler algorithms complete within the setup function? - and we instead have the following caller pattern with one less call into the implementation for simple setup:
```
r = psa_sign_interruptible_setup(&op, key, alg);
while (r == PSA_OPERATION_INCOMPLETE)
  r = (psa_sign_interruptible_setup_complete(&op));
```
Then either:
1. Provide the hash:
```
psa_interruptible_sign_hash(&op, &hash, hash_len)
```
2. Or supply a message in one or more calls:
```
psa_interruptible_sign_update(&op, &msg_buf, buf_len)
```
3. Need to decide if we permit neither to be called, and we sign the empty message? - or if that is treated as a programming error (bad-state). In the latter case the empty message can be signed by calling psa_interruptible_sign_update() with a zero-length buffer.

To finish:

uint8_t sig[];
size_t sig_len;
while (psa_interruptible_sign_complete(&op, &sig, sizeof(sig), &sig_len) == PSA_OPERATION_INCOMPLETE)
   ;

ARM-software / psa-api