FFDH 2a: implement Diffie-Hellman key agreement for RFC 7919 groups

[gilles-peskine-arm]

Mbed TLS supports finite-field Diffie-Hellman. The PSA Crypto API specifies key agreement with finite-field Diffie-Hellman for known groups, of which the specification defines one family: the groups from RFC 7919. The PSA API implementation in Mbed TLS only supports ECDH, not FFDH.

Prerequisite (arguably, should be done together): #5911

Goals of this task:

• Add support for FFDH with known groups to psa_key_agreement_raw_internal.
• Translate PSA_DH_GROUP_RFC7919 to the appropriate MBEDTLS_DHM_RFC7919_xxx values.
• Add corresponding tests, with similar coverage as what exists for ECDH. Note that there are two entry points: psa_key_derivation_key_agreement and psa_raw_key_agreement.

Non-goals:

• Declaring other groups that Mbed TLS supports. They're deprecated, so probably not worth the effort and code size at this point.
• Using PSA for FFDH in TLS - this will be handled in separate tasks.

[mpg]

Note: the implementation should probably not use the DHM module (dhm.c), whose API is quite tailored to TLS 1.2 (and earlier), while the PSA API is more generic and modern. In particular, mbedtls_dhm_calc_secret() strips leading zeroes from its output which is what TLS 1.2 requires but is a cryptographic mistake as it leads to the racoon attack - by contrast PSA has fixed size output which is the right thing to do.

So, the implementation should probably just use mbedtls_mpi_exp_mod() and mbedtls_mpi_write_binary() directly. (The optional blinding present in mbedtls_dhm_calc_secret() is only useful for static FFDH, which hopefully nobody still does in 2022, so it can be ignored in the PSA implementation.)

[mprse]

I extended #6010 and added FFDH key agreement. I didn't use dhm.c as requested.
But main problem for me now is with test vectors for FFDH key agreement. @mpg do you maybe know if these are available somewhere? They would need to be consistent with the new rules (leading zeros not stripped, no blinding).

[mpg]

Good news!

Regarding test vectors, I'm surprised and a bit disappointed that RFC 7919 doesn't have any. There are FFDH test vectors in other RFCs but they obviously won't work here as they are for different groups. I searched a bit and couldn't find any test vectors for those groups. I say we should generate some ourselves, should be easily done using Python as it has built-in multi-precision integers and modular exponentiation.

Regarding leading zeroes, I was going to say there's a good chance (nearly 255 out of 256) that there are none for random test vectors. But then I thought, well, since we're generating our own test vectors we may as well make sure we do hit that corner case, to make sure things work as expected. This should easy to achieve:

1. generate a key pair, keep only the public key
2. generate a private key (just an integer in the range [2, p-2])
3. compute the shared secret - if it has a leading 0 byte, done, otherwise go back to 2 until it does
   We should get a success after a few hundred iterations.

I'd say ideally for each group we want two test vectors: one where the shared secret is full-length, plus one where it has a leading 0 byte.

Regarding blinding, it doesn't change the result, so its presence or absence doesn't affect the selection of test vectors.

[mprse]

Yes, I also couldn't find anything useful on the internet. Predefined test vectors are better than python script because it will do the same what our C implementation does. But if there is no other way I will continue with python.

Thanks for clarification and hints.

[mpg]

Yes, generating test vectors ourselves is far from ideal. When we get to integration in TLS 1.3, we can also add interop tests with other implementations for some extra validation - I've just added an item about that in #5979 (last checkbox).

[mprse]

I got script for generating test vectors for FFDH and added tests for psa_raw_key_agreement and everything works except tests for 1024 bytes keys. In this case I'm getting parsing error (looks like some kind of length limitation):

PSA raw key agreement: FFDH 8192 bits ............................. Expected string (with "") for parameter and got: "ede0361026e81a9ad960f674de49449f12ee33c2dda7028c6b7fad7f8f8a7edc495621a6d13e47847873a954adfe7bb6a2ed7c9bc21f3b57458d9116ff4ed06cfca40e2002a70bca91a9a9e0475dd74be7d58453d3cc155ee0b0be20197e14674a7a6f8d903e211cbdbdad1e3383d0d1ae6b4d56837671589d8f151acb34bb4d1cdda55a0f9d1f70e80c61553fd0152bc871e930054efe763fdcd1f8fd1702afa61b3471e7a504612c58ab05ed581b34e2a884c5dd8d2aa919855351719e2cb290d00f0b161c104415f5579731072c1382508421c8d674113b2fe25a0e979455c8f145285ed3d32b744153d3ffab7625a3173440f026ecc62d9dd1bbdff6136f5d9d5245ff307eabfa91f6a10e7cf62a889975c0afd2f707eb8a43c2499c05029ca613edae2741f8e56b186a6390fbb0962323ed6c492620c1c8a24f9a89f15c00bd7263423e714db0fe0381556a15a8e4d1b7383d52fd524425e0200f9d410833330253306b1c23c15c08310bfc12b48131c120db8444d34dd951c5fd6df44e0eecbe92ad5f13641600db68d1d2c7d8ff460058c09d89d4febf2fcaacb40c900e19e4dc868a24ec61361c452541a0fb13da53d61b59806e0598985031e161a2e887420e4c6ce217587c72cd3a7b3085d2383112e1066277ed63e82ec16ac6dc7ce0ade255f30275b9798d4476f31d8d237c4d79b13da9dc6ceed7fe626e4da6eb6cfd234b8fdec4fd4520898b13a77aa034361c0d63edef55595e3e638b48c1c00e8c683c8cffd9fac2a33f73e04aff1f4624669057c7faf51f996e3d64bea3097b4810f99c8f078887be2440f67b249467eb26a03210b4d2baeaa8dc9746a14a6cfb45297e121eef8540eb438270403105c11ef4fed87127545b81e37ee1f942605a5a46253752351dee91d0a171031defa9dd20cbb942e3940fa43542f6fbcb0980f6ef2b36297527f7c0d47e36ea203

Now I wanted to add test psa_key_derivation_key_agreement(), but in this case I need to use PSA_ALG_KEY_AGREEMENT(PSA_ALG_FFDH, ??? ) algorithm but got problem with second parameter. What key derivation algorithm should be used here?

[mpg]

Hmm, good question. Any key derivation algorithm would make sense I think. Perhaps test with HKDF as that's a fairly standard one, that's neither outdated not specific-purpose? I'm afraid again we'll have to generate test vectors ourselves...

I looked at RFC 8448 (example traces for TLS 1.3) but it doesn't have any FFDH example, and neither does the illustrated TLS 1.3 handshake. Again, validation will mostly be interop testing with OpenSSL and GnuTLS when we've used it in TLS 1.3, which is not ideal but will have to do.