Affected: rack

Rack is a modular Ruby web server interface. Prior to versions 2.2.23, 3.1.21, and 3.2.6, Rack::Utils.select_best_encoding processes Accept-Encoding values with quadratic time complexity when the header contains many wildcard (*) entries. Because this method is used by Rack::Deflater to choose a response encoding, an unauthenticated attacker can send a single request with a crafted Accept-Encoding header and cause disproportionate CPU consumption on the compression middleware path. This results in a denial of service condition for applications using Rack::Deflater. This issue has been patched in versions 2.2.23, 3.1.21, and 3.2.6.

Affected: RubyGems: rack

## Summary

`Rack::Utils.select_best_encoding` processes `Accept-Encoding` values with quadratic time complexity when the header contains many wildcard (`*`) entries. Because this method is used by `Rack::Deflater` to choose a response encoding, an unauthenticated attacker can send a single request with a crafted `Accept-Encoding` header and cause disproportionate CPU consumption on the compression middleware path.

This results in a denial of service condition for applications using `Rack::Deflater`.

## Details

`Rack::Utils.select_best_encoding` expands parsed `Accept-Encoding` values into a list of candidate encodings. When an entry is `*`, the method computes the set of concrete encodings by subtracting the encodings already present in the request:

```ruby if m == "*" (available_encodings - accept_encoding.map(&:first)).each do |m2| expanded_accept_encoding << [m2, q, preference] end else expanded_accept_encoding << [m, q, preference] end ```

Because `accept_encoding.map(&:first)` is evaluated inside the loop, it is recomputed for each wildcard entry. If the request contains `N` wildcard entries, this produces repeated scans over the full parsed header and causes quadratic behavior.

After expansion, the method also performs additional work over `expanded_accept_encoding`, including per-entry deletion, which further increases the cost for large inputs.

`Rack::Deflater` invokes this method for each request when the middleware is enabled:

```ruby Utils.selec…