Potential hash-collision CPU amplification in request-field maps

[K-ANOY]

Crow stores client-controlled request-field names in maps using fixed-seed crow::ci_hash or default string hashing. Inputs that collide under the target build may increase map-operation costs. The relevant paths have different limits and activation requirements.

Affected code

Paths below are relative to include/crow/.

• Multipart part names: multipart_view.h:118,126 defines message_view::part_map. Constructing message_view(req) parses the body (185-189) and inserts each part's Content-Disposition name value as the key (232-234). This requires application use of the multipart parser; examples/example_file_upload.cpp:9 shows that integration.
• Request header names: http_request.h:52 declares request::headers; parser.h:49,80 inserts parsed wire names. This runs during normal HTTP header parsing.
• Multipart section-header names: multipart_view.h:43 defines mph_view_map; parse_section_head creates result at 256, extracts names at 276-279, and inserts them at 298. This shares the multipart activation requirement above.
• Cookie names: middlewares/cookie_parser.h:204 declares the context's jar; before_handle trims and inserts cookie names at 254-255,285. The application must enable CookieParser middleware. Multiple Cookie headers are rejected at 234-241; one header can contain multiple cookie entries.
• Query dictionary subkeys: query_string::get_dict creates a default-hashed map at query_string.h:481-489. For example, get_dict("filter") extracts client-controlled subkeys from filter[color]=blue. This map is built only when the application calls get_dict or pop_dict (497-500).

The first three stores are unordered_multimap containers using ci_hash and ci_key_eq: hashing starts at zero and mixes uppercased characters (ci_map.h:12-40). They preserve duplicate entries, including case-equivalent names. Cookie and query-dictionary results are unique-key maps using default string hashing. A probe must preserve these container and equality differences.

Relevant insertion statements:

// Multipart part name -> part.
part_map.emplace(
    get_header_object(parsed_section.headers, "Content-Disposition")
        .params.find("name")->second, parsed_section);

// HTTP and multipart section headers.
self->req.headers.emplace(std::move(self->header_field),
                          std::move(self->header_value));
result.emplace(key, to_add);

// Cookie name and query dictionary subkey.
ctx.jar.emplace(std::string(name_sv), std::string(value_sv));
ret.insert(*element);

Input limits and impact

• HTTP request line and headers: the parser enforces a default combined 80 KiB limit (http_parser_merged.h:50-52,292-299,753-754). This constrains URL queries and Cookie input. It does not cap multipart section headers, which are inside the body.
• Query dictionary: MAX_KEY_VALUE_PAIRS_COUNT = 256 (query_string.h:333) limits the pairs retained during construction (376-379; qs_parse loop at 125-133). The dictionary cannot grow beyond those retained pairs. Its helper also rescans the parameter list for successive entries (215-225,488), so dictionary-building time must distinguish scanning cost from hash-collision cost.
• Multipart: no explicit part-count or section-header-count cap appears in the cited loops. parser.h:88-92 appends body data without a body-size check in that callback; deployment-level body limits and checks before constructing message_view remain relevant.

These are request/message-scoped entries, not persistent session-table populations. Practical impact depends on accepted input, the selected container implementation, and its collision and rehash behavior.

Suggested fix

Use a keyed hash designed to resist hash flooding, preserving the existing case-insensitive header behavior. Keep the HTTP header and query-count limits; add practical body, multipart part/section-header, and cookie-count limits where appropriate.

[gittiver]

a keyed hash increase in all cases the map operations cost, could you elaborate how this shall be compensated.?

[K-ANOY]

Thanks, that's a fair concern. My local benchmarks suggest that a keyed hash combined with cheaper case folding can outperform Crow's current implementation.

The current ci_hash constructs a std::locale on every call and uses locale-aware std::toupper for every character. I benchmarked commit e91d0e7 with g++ 11.4 at -O2, using 20 common request header names. These are medians from five runs:

Hasher	ns/hash	ns/map build + lookup + destruction
Current ci_hash	79.24	2458
Same algorithm, ASCII folding	12.99	1486
SipHash-1-3, random key, ASCII folding	16.13	1527
SipHash-2-4, random key, ASCII folding	19.86	1585

For this workload, the savings from replacing locale-based case conversion more than offset the additional hashing cost. These are microbenchmarks, not end-to-end server measurements.

HTTP field names are ASCII tokens, so ASCII folding is appropriate there. A broader change to ci_hash would also need to preserve compatible equality semantics and account for its use with multipart part names.

Separately, configurable parsing limits would help. In the reviewed version, I found no explicit HTTP body-size cap in the receive path, or count limits for multipart parts, headers per part, and parameters per header. Deployment-level limits may still apply. header_view::params and its owning counterpart are also default-hashed maps populated from client-supplied parameter names.

[gittiver]

Thanks for the detailed writeup. The code reading is accurate, but I don't see a practical exposure here, so I'm closing this as won't-fix.
Worst case is that all headers have the same name, therefore also the same hash. a keyed hash does not help in this case.

Nevertheless the ci_map specific hashes are slow, thank you for hinting me to this.