Improve ECC defaults to decrease RAM usage (for the same speed) #4127
Comments
I agree, and I think we should prioritize P-384 over P-521. P-521's slightly-larger-than-a-machine-word size leads to some practical side channel attacks by detecting when the top word is 0, which happens with macroscopic probability. Mbed TLS is protected under all known such attacks, but I wouldn't be surprised if there were more subtle ones that are still (publicly) undiscovered. |
|
I think these changes would be acceptable in a minor release. But 3.0 is a good opportunity to make them too. |
gilles-peskine-arm
added
component-crypto
Support for using Curve25519 in TLS has been merged in the meantime, so my recommendation would now be to use Curve25519 as the first choice and the P-256 as the second choice. Note: the impact on peak RAM for and ECDHE-ECDSA handshake would be zero, as the peak is reached in the ECDSA part, using Curve25519 would nicely reduce peak RAM usage of ECDHE-PSK handshakes (compared to P-256). |
|
Change 1 is related to #4604. I've made the documentation of the curve selection order in TLS more precise so this change would be considered an API break. I don't feel strongly about it though; we could instead document that the priority order may change. |
MBEDTLS_ECP_WINDOW_SIZE is a compromise between memory usage (growing based on the value) and performance (faster with larger values). There are disminishing returns as the value grows larger. Based on Manuel's benchmarks recorded in Mbed-TLS#4127, 4 is a good compromise point, with larger values bringing little advantage. So reduce the default from 6 to 4. Document the default value as in optimized for performance mostly, but don't document the specific value, so we may change it later or make it platform-dependent. Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>
MBEDTLS_ECP_WINDOW_SIZE is a compromise between memory usage (growing based on the value) and performance (faster with larger values). There are disminishing returns as the value grows larger. Based on Manuel's benchmarks recorded in Mbed-TLS#4127, 4 is a good compromise point, with larger values bringing little advantage. So reduce the default from 6 to 4. Document the default value as in optimized for performance mostly, but don't document the specific value, so we may change it later or make it platform-dependent. Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>
MBEDTLS_ECP_WINDOW_SIZE is a compromise between memory usage (growing based on the value) and performance (faster with larger values). There are disminishing returns as the value grows larger. Based on Manuel's benchmarks recorded in Mbed-TLS#4127, 4 is a good compromise point, with larger values bringing little advantage. So reduce the default from 6 to 4. Document the default value as in optimized for performance mostly, but don't document the specific value, so we may change it later or make it platform-dependent. Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>
MBEDTLS_ECP_WINDOW_SIZE is a compromise between memory usage (growing based on the value) and performance (faster with larger values). There are disminishing returns as the value grows larger. Based on Manuel's benchmarks recorded in Mbed-TLS#4127, 4 is a good compromise point, with larger values bringing little advantage. So reduce the default from 6 to 4. Document the default value as in optimized for performance mostly, but don't document the specific value, so we may change it later or make it platform-dependent. Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>
MBEDTLS_ECP_WINDOW_SIZE is a compromise between memory usage (growing based on the value) and performance (faster with larger values). There are disminishing returns as the value grows larger. Based on Manuel's benchmarks recorded in Mbed-TLS#4127, 4 is a good compromise point, with larger values bringing little advantage. So reduce the default from 6 to 4. Document the default value as in optimized for performance mostly, but don't document the specific value, so we may change it later or make it platform-dependent. Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>
Description
Note: was previously raised internally as IOTSSL-1864 in Nov. 2017.
Several default values are sub-optimal regarding ECC performance (RAM usage and execution time) and should be adjusted. Three changes are suggested, all of them are simple changes of default values (and documentation).
Note: all RAM figures were measured on x86-64 for convenience, but the proportions should be similar on other platforms. Some were extrapolated and might need experimental confirmation.
Change 1: preferred curve (TLS). In the SSL module, by default the largest curve is preferred. In the standalone configuration, this means P-521 (in the mbed OS configuration, that might be P-384). Those curves use respectively 18.5 and 16.5 KB or heap for an ECDHE handshake, while P-256 uses only 7.2KB and much less computational power, and provides sufficient security. We should make that the preferred curve in the defaults. (And make it Curve25519 once we support it with TLS, as it only uses 1.4KB heap for ECDHE.)
Change 2: window size (ECP module). The default value of
MBEDTLS_ECP_WINDOW_SIZEis 6 which is probably not the best trade-off between RAM usage and performance, and should probably be changed to 4 (or even a lower value). For example for P-521 (assuming a workflow that doesn't benefit from the current implementation ofFIXED_POINT_OPTIM, see below), changing that value from 6 to 4 would divide heap usage by about 2, while modifying performance by an amount that's below the benchmark program's sensitivity on my laptop. For P-256 it decreases heap usage by 25% while also not impacting performance in a way that's easy to measure. (Values below 4 do decrease performance in a measurable way.)(Note that for workflows that benefit from
FIXED_POINT_OPTIM, or if it gets fixed, thenWINDOW_SIZEvalues above 4 would actually speed up some operations (by about 10% moving from 4 to 6).)Change 3: fixed point optimisation (ECP module).(Edit: this is irrelevant now that #4128 has been implemented.) The current implementation ofMBEDTLS_FIXED_POINT_OPTIMis supposed to be a RAM-performance trade-off but actually doesn't improve performance (while consuming RAM) in common workflows, most notably not in TLS. The only workflow where it actually improves performance is when you perform repeated ECDSA operations with the same context, but not through the PK layer. It should be disabled by default (and then maybe re-introduced in an improved version). Doing so would bring heap usage of ECDHE with P-256 withWINDOW_SIZE == 4(see above) from 5.4KB to 3.7KB.The current implementation of fixed point optim also has the problem that the longer the cert chain is, the more memory is used by ECC while verifying it. (Exactly how much is not easy to express without going into gory details.)
Note: as an alternative to disabling fixed point optimization, #4128 would bring the same RAM benefits while improving performance in addition.
All changes together
Overall, assuming the preferred curve is chosen, those three changes would bring the heap usage of the ECDHE part of the TLS handshake in the default standalone configuration from 18.5KB to 3.7KB while improving its execution time by 300%.
For certificate chain verification, as many ECC CAs use P-384 for they root certificate, changes 2 and 3 should reduce heap usage by at least 12KB (more depending on chain length), with little to no impact on speed.
Executive summary: Overall (ECHDE + cert verification, with a chain of length 1), those 3 changes amount to saving 12KB of RAM with no significant change in speed. This represents almost half the total RAM used for a handshake (excluding I/O buffers).
The text was updated successfully, but these errors were encountered: