ECC key size for secp224k1 is not consistent with key size specification

[Emill]

The key size for secp224k1 is specified to be 225 bits:

psa-api/doc/crypto/api/keys/types.rst

Line 956 in 8fab2a2

* secp224k1 : ``key_bits = 225``

This does not follow the specification of the key size:

psa-api/doc/crypto/api/keys/types.rst

Line 758 in 8fab2a2

The size of an elliptic curve key is the bit size associated with the curve, that is, the bit size of :math:`q`` for a curve over a field :math:`\mathbb{F}_q`.

As seen at https://neuromancer.sk/std/secg/secp224k1, the bit size of the prime for this curve is 224. However, the bit size of the curve order is 225 and this is why the key size needs to be one bit bigger for private keys, since a private key for ECDH and ECDSA is a number between 1 and n-1, where n is the curve order. However for corresponding public keys, each coordinate is at most p and hence fits in 224 bits for secp224k1.

Note that the public key size is specified to the same as the private key:

psa-api/doc/crypto/api/keys/types.rst

Line 877 in 8fab2a2

The size of an elliptic curve public key is the same as the corresponding private key. See `PSA_KEY_TYPE_ECC_KEY_PAIR()` and the documentation of each elliptic curve family for details.

Not sure what the intention here is regarding secp224k1 if public key size should be 225 (with always one msb zero bit) or 224.

As a side note, it's even worse for Ed25519, where the private key is not a number between 1 and n-1 but is a 256 bit random bit string that is internally to be fed into a KDF per RFC 8032. Currently Edwards25519 keys are specified to have 255 key bits, which technically corresponds to the description for key size above since the bit size of the prime of the curve is 255, but does not match with what is used as private key for the EdDSA scheme (256 bits). And public keys are also 256 bits (not 255).

I'm not sure what the exact purpose of the "key size" attribute is. If it is to describe the actual size of a key (used when allocating buffer sizes etc.), it is apparently wrong, as seen above. If the intention is to rather specify the strength of the curve/algorithm (e.g. the size of the prime field of the curve, which can differ slightly from key sizes), then make that clear in the description and change secp224k1's "size" to 224. But in that case I'm not sure what the purpose of "public key size" would be. It anyway confuses me that the public key size is the size of only one coordinate, while typically the public key needs both coordinates.

[gilles-peskine-arm]

The key bit-size attribute has several complementary purposes:

1. It's intended to be the number N used in the established expression “this is an N-bit key”, in cases where N is consensual. This works out fine for AES, RSA, finite-field DH, most elliptic curves, etc. It isn't precise enough for some key types such as finite-field DSA (which we've fortunately outlived) or for a few elliptic curves.
2. It's intended to be a way to pinpoint the strength and interoperability when generating or deriving a key. For example, it allows distinguishing between AES-128/AES-192/AES-256, it drives the strength-vs-performance compromise for RSA, etc.
3. In cases where there are several closely related key types, it allows specifying one of them. That is why we've grouped elliptic curves into families such that each family only has one curve of a given “size”.
4. It's intended to follow general rules, as much as possible, so that you should mostly be able to guess right in any given case. For example, if the key is part of a family and has one bit-string or integer whose size characterizes the strength of the key, then the length of that bit-string or integer should be the bit-size.

This is not directly related to the buffer size needed to represent a key, since that depends on the chosen representation format and possibly on the key itself. For example, it wouldn't be meaningful to classify RSA key pairs according to their RFC 8017 DER encoding. However, it is possible to calculate a sensible buffer size for a given key type and bit-size.

For elliptic curves, we meant to pick one, between the curve order and the prime. (Private discussions: 1 2.) They are usually the same but differ by one bit for a few curves such as secp224k1. Going by rule 4 above, we reasoned that for Weierstrass curves, we would always pick the size of the private key (as a number). But going by rule 4, we could also have declared that since it has 224 in the name, secp224k1 would be considered a 224-bit key. Picking the larger number did have an advantage: if you use a uniform rule to calculate buffer sizes, they'll always be large enough, whereas if you use the smaller size, you have to add 1 when the buffer needs to contain the larger number.

For Curve25519/Ed25519 and Curve448/Ed448, it wasn't clear which number to pick (Do we count the number of non-forced bits in the private key? Do we take a number and divide by the cofactor to get the strength?). So we ended up picking the number in the curve name: that time we followed the second part of rule 4 and not the first.

For backward compatibility, I think the bit-size of secp224k1 needs to remain 225. Note that an implementation is allowed to accept 224 as equivalent as an input to a key creation function, but it is supposed to output 225 when querying the key attributes (although technically outputting 224 would be correct if 224 was explicitly specified when creating the key, since the application would be relying on nonstandard behavior). Note also that I wouldn't be surprised if nobody ever provided a PSA Crypto API that supports secp224k1; we won't add it to Mbed TLS.