Hi,

There is an issue in version 1.0.0 of the PSA Crypto API, that can result in severe inefficiency in key generation in some circumstances. It is also possible that the definition could be interpreted differently in different implementations, which is a major interoperability issue for key derivation algorithms.

As a result, Arm would like to clarify this operation, ideally in a way that eliminates the inefficiency. Please let me know if you have an implementation of the PSA Crypto API, and whether this proposed change would affect it.

In section 10.5.3, the definition of psa_key_derivation_output_key() for several key types is inefficient for Weierstrass elliptic curves and Diffie-Hellman groups whose size is not a multiple of 8. The definition does not follow the cited NIST specifications (although this is not a compliance issue since these NIST specifications apply to random generation, not to deterministic derivation).

The current specification states:

this function draws a byte string of length ceiling(bits/8) bytes. If the resulting byte string is acceptable, it becomes the key, otherwise the drawn bytes are discarded. This process is repeated until an acceptable byte string is drawn.

This is secure, but it is inefficient if some bits are always 0 (or always 1) in acceptable results. In practice, for L-bit curves where L is not a multiple of 8 (for example sec521r1), this leads to rejecting many candidates because their most significant bits are not 0.

The NIST process (e.g. https://doi.org/10.6028/NIST.SP.800-56Ar3 §5.6.1.2.2 step 4) is similar, but involves drawing L bits from the RNG, not ceiling(L/8).

The input to this function is a byte stream generator. It wouldn't make sense to consume a number of bits that isn't a whole number of bytes. However, forcing top bits to 0 would make sense, and would be more efficient and closer to the NIST process.

Arm proposes to modify the definition to require that the tops bits (ceiling(bits/8)*8 - bits) are set to zero when drawing bytes from the generated stream, prior to the byte string being tested for acceptability. This would be an incompatible change for any implementation that had support for deriving affected keys, which discarded byte strings that had any of the top bits set to one.

Regards,

Andrew Thoelke Software Systems Architect | Arm . . . . . . . . . . . . . . . . . . . . . . . . . . . m. +44 7766 990101 Arm.com