5.3 KiB
mbedTLS — CWE-407 Disclosure Brief
Project: mbedTLS Disclosure date: 2026-03-27 Severity: HIGH Speedup: varies; up to 11.5M ops/handshake eliminated Status: PATCHED
Finding
mbedTLS contains two independent multi-dimensional complexity defects in its TLS handshake code. The first is an O(S×C×L) ALPN protocol negotiation scan in TLS extension parsing. The second is an O(S×C×D) cipher suite selection in the TLS 1.2 server, where D is the length of the global ciphersuite definitions array. Together these cause handshake processing time to scale with the product of configuration dimensions rather than their sum.
The Defect(s)
| ID | Location | Pattern | Complexity |
|---|---|---|---|
| mbedtls-0001 | library/ssl_tls.c |
mbedtls_ssl_parse_alpn_ext() outer for over S server ALPN names × inner while memcmp over C client names × string length L |
O(S×C×L) |
| mbedtls-0002 | library/ssl_tls12_server.c |
TLS 1.2 cipher selection: S server suites × C client suites × D ciphersuite_definitions[] scan |
O(S×C×D) ≈ 11.5M ops/handshake |
Complexity Proof
mbedtls-0001 — Let S = number of server ALPN protocol names, C = number of client ALPN protocol names, L = average protocol name length.
mbedtls_ssl_parse_alpn_ext() iterates over S server names in an outer for loop. For each server name, it iterates over C client names in an inner while loop, calling memcmp (O(L)) for each comparison:
Total: S × C × L byte comparisons per ALPN extension parse
A 64-slot FNV-1a hash set of server ALPN names (built once at config time) reduces the inner scan to a single hash lookup per client name:
Fixed: C × (hash(name) + possible 1 collision check) = O(C×L)
Savings factor: S×
For S = 8, C = 10, L = 20: defective path = 1,600 byte comparisons; fixed = 200.
mbedtls-0002 — Let S = number of server-configured cipher suites, C = number of client-offered cipher suites, D = number of entries in ciphersuite_definitions[] (typically ~60–80).
For each of the S server suites, the code scans all C client suites. For each matching pair, it then scans the ciphersuite_definitions[] array of D entries to look up the suite descriptor:
Total: S × C × D comparisons per TLS 1.2 handshake
With S = 15, C = 20, D = 38 (common mbedTLS configuration): 15 × 20 × 38 = 11,400 comparisons per handshake. Pre-building a HashSet of client suite IDs and a HashMap<suite_id, definition> reduces this to O(S + C + D) initialization plus O(S) matching.
Impact
mbedtls-0001 affects all TLS connections that negotiate ALPN — HTTPS/2 servers, gRPC, any TLS service that advertises multiple protocols. Embedded devices and IoT gateways running mbedTLS are particularly sensitive, as they have constrained CPU budgets and process many simultaneous connections.
mbedtls-0002 is in the TLS 1.2 handshake hot path. At ~11.5M comparisons per handshake in the worst case (dense cipher configs), high-connection-rate servers and embedded TLS endpoints handling many simultaneous clients accumulate significant CPU overhead. mbedTLS is deployed in constrained environments (Arm Cortex-M, RTOS) where every cycle counts.
The Fix
mbedtls-0001: Build a 64-slot FNV-1a hash set of server ALPN name strings once during ssl_conf_alpn_protocols(). Use it in mbedtls_ssl_parse_alpn_ext() to replace the inner client-name scan with O(1) lookups.
mbedtls-0002: Pre-build two structures at handshake init: (1) a HashSet of client-offered suite IDs for O(1) client-suite membership; (2) a HashMap<suite_id, definition*> from ciphersuite_definitions[] for O(1) descriptor lookup. Replace the triple-nested loop with two linear passes.
Patch
# mbedtls-0001: library/ssl_tls.c
- for (p = ssl->conf->alpn_list; *p != NULL; p++) {
- theirs = buf;
- while (theirs < end) {
- if (memcmp(*p, theirs + 1, name_len) == 0) { match = 1; }
- theirs += 1 + theirs[0];
- }
- }
+ /* build FNV-1a hash set of server names at config time */
+ alpn_hash_set_t srv_alpn_set;
+ alpn_hash_init(&srv_alpn_set, ssl->conf->alpn_list);
+ theirs = buf;
+ while (theirs < end) {
+ if (alpn_hash_contains(&srv_alpn_set, theirs + 1, theirs[0]))
+ { match = 1; break; }
+ theirs += 1 + theirs[0];
+ }
# mbedtls-0002: library/ssl_tls12_server.c
- for (i = 0; i < server_suite_count; i++) {
- for (j = 0; j < client_suite_count; j++) {
- if (server_suites[i] == client_suites[j]) {
- suite_info = mbedtls_ssl_ciphersuite_from_id(server_suites[i]);
- /* linear scan of ciphersuite_definitions[] */
- }
- }
- }
+ /* pre-build client set and definition map */
+ uint16_set_t client_set; uint16_set_init(&client_set, client_suites, n);
+ suite_map_t def_map; suite_map_init(&def_map);
+ for (i = 0; i < server_suite_count; i++) {
+ if (uint16_set_contains(&client_set, server_suites[i])) {
+ suite_info = suite_map_lookup(&def_map, server_suites[i]);
+ }
+ }
What We Ask
Please review, apply, and coordinate a 90-day disclosure window before public release. Reply to security@undefect.com.
This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com