PSA: implement key derivation for ECC keys

[gilles-peskine-arm]

Implement psa_key_derivation_output_key for elliptic curve keys.

The PSA specification describes exactly how to do this: draw a byte string from the stream, convert it to the target type of private key, and discard the top bits that must be 0 in the result. If it the resulting value is not in the correct range, discard and try again.

(Note that there was a change between versions 1.0.0 and 1.0.1 of the specification. Version 1.0.0 did not have a step of discarding the always-0 top bits, which made it inefficient for key sizes that are not a multiple of 8.)

[mprse]

I read a about elliptic curves and Diffie-Hellman key exchange algorithm to get some background for this task.
Elliptic curves have its public parameters {p, a, b, G, n, h}. G is the generation point (fixed point on the curve that will be used to multiply all of our future points).
Now each side of the transaction in Diffie-Hellman key exchange algorithm generates its public key which is equal to d x G = (Xg, Yg). d is a private key different for each side.

I understand that the algorithm provided in this task is to define d value?

The algorithm is quite simple, but I don't know where N is defined:

These key types require the generation of a private key which is an integer in the range [1, N - 1], where N is the boundary of the private key domain: N is the prime p for Diffie-Hellman, or the order of the curve’s base point for ECC.

Unclear to me is also where the implementation should be added. psa_key_derivation_output_key is mentioned in the task, but it seems to not be a good place as I don't see here any actions performed based on key types. A also don't see where the generated private key could be stored or returned (maybe psa_key_derivation_output_bytes ?).

[gilles-peskine-arm]

So conceptually, key derivation consists of two independent parts:

1. Generate a stream of bytes from the inputs, in a reproducible way.
2. Construct a key of the requested type from the stream of bytes, in a reproducible way.

psa_key_derivation_output_bytes does part 1. psa_key_derivation_output_key calls psa_key_derivation_output_bytes to do part 1 and then has extra code to do part 2. Internally, this happens in psa_generate_derived_key_internal (the code surrounding parts 1 and 2 is to create the key object and recover from errors).

Currently, part 2 in psa_generate_derived_key_internal is not clearly marked. It only implements the simple case where part 2 is simply “take the first n bytes of the stream”:

• Reject key types for which part 2 is not just “take the first n bytes”:

  if( ! key_type_is_raw_bytes( slot->attr.type ) )
      return( PSA_ERROR_INVALID_ARGUMENT );
  if( bits % 8 != 0 )
      return( PSA_ERROR_INVALID_ARGUMENT );
  

• Take the first n bytes (error checking omitted):

  psa_key_derivation_output_bytes( operation, data, bytes );
  psa_driver_wrapper_import_key( &attributes, data, bytes, …);
  

The goal of this task is to implement part 2 for ECC key types, where there's extra work to do on the output from part 1, and the total number of bytes to grab from the stream is not known in advance (which is not a problem: just call psa_key_derivation_output_bytes as many times as needed).

Random key generation works somewhat similarly, but part 1 is a random generator instead of processing from some inputs. In principle, derivation could be implemented by taking the code for random generation and using the derivation byte stream instead of the random generator. However, for derivation, part 2 needs to be reproducible, so it needs to consume the output of the stream in a specific way, whereas for generation it doesn't matter exactly how the output of the RNG is consumed.

For ECC, the private key is indeed d, which needs to be constructed in a specific way (dependent on the curve). The code in mbedtls_ecp_gen_privkey* functions may help, but the method in the PSA specification is not necessarily the same that the code in ecp.c is using for random generation.