fixing a super-linear DoS in the mail gem

The mail gem parses email for a huge slice of the Ruby ecosystem. One method in it turned a tens-of-kilobytes email into tens of seconds of CPU - and, deep enough, a crash. Here is what was wrong and the fix that is now upstream.

what was wrong

Mail::Message#all_parts flattens a MIME tree into a flat list of parts:

def all_parts
  parts.map { |p| [p, p.all_parts] }.flatten
end

Two problems hide in one line:

• it is recursive - one stack frame per level of multipart nesting, so a deeply nested message can exhaust the thread stack and raise SystemStackError;
• it rebuilds an array with flatten at every level, so the total cost is super-linear in the nesting depth.

For a normal two- or three-level email, none of this matters. It matters when someone else chooses the structure - and anything that reads the body of an inbound message does exactly that, because text_part and html_part both route through all_parts.

A deeply nested message is trivial to build (benign benchmark code - it just nests multipart/mixed inside itself):

def build(depth)
  s = "Content-Type: text/plain\r\n\r\nhello\r\n"
  depth.times do |i|
    b = "b#{i}"
    s = "Content-Type: multipart/mixed; boundary=\"#{b}\"\r\n\r\n--#{b}\r\n#{s}--#{b}--\r\n"
  end
  s
end

Timing all_parts alone on a single setup (mail 2.9.1, ruby 3.1.2):

nesting depth	email size	all_parts time
200	13 KB	0.19 s
400	27 KB	0.97 s
600	41 KB	2.46 s
800	54 KB	5.58 s
1000	68 KB	13 s
1500	103 KB	40 s

From depth 200 to 1500 the nesting grows 7.5x and the time grows ~210x - roughly O(depth^2.5), between quadratic and cubic. Past about depth 2000 it stops getting slow and raises SystemStackError instead: the stack runs out first.

So a single ~100 KB email is tens of seconds of CPU on the worker that parses it; a slightly deeper one takes the worker down with a stack overflow. Inbound mail workers run at bounded concurrency, so it does not take many.

the fix

Make all_parts iterative. Same pre-order ordering, same contents, same return type - but linear in the number of parts and no recursion:

def all_parts
  result = []
  stack  = parts.reverse
  until stack.empty?
    part = stack.pop
    result << part
    children = part.parts
    stack.concat(children.reverse) unless children.empty?
  end
  result
end

The super-linear curve disappears (the walk is now linear in the number of parts) and so does the SystemStackError - a thousand-deep message walks fine.

making sure it is safe for everyone

Changing a core method of a gem this widely used, “my new test passes” is not the bar. The bar is the gem’s entire existing suite against the patch:

1839 examples, 0 failures.

And because the bug is algorithmic, not Ruby-version-specific, the same super-linear behaviour shows up on Ruby 3.0 through 3.4 - so the fix helps all of them.

The change is upstream here: mikel/mail#1695.

takeaway

Recursion over attacker-controlled structure, plus an allocation that repeats at every level, is a classic super-linear trap. A tiny input, enormous work. The fix was small; finding where a one-line method quietly costs ~O(depth^2.5) was the whole job.