skip to content
Back to GitHub.com
Home Bounties Research Advisories Get Involved Events
November 3, 2021

GHSL-2021-102: ReDoS (Regular Expression Denial of Service) in Fluentd - CVE-2021-41186

GitHub Security Lab

Coordinated Disclosure Timeline

Summary

Product

fluent/fluentd

Tested Version

v1.13.1

Details

Fluentd uses a regular expression that is vulnerable to catastrophic backtracking to parse logs from the Apache 2 web server:

/^(?<host>[^ ]*) [^ ]* (?<user>[^ ]*) \[(?<time>[^\]]*)\] "(?<method>\S+)(?: +(?<path>(?:[^\"]|\\.)*?)(?: +\S*)?)?" (?<code>[^ ]*) (?<size>[^ ]*)(?: "(?<referer>(?:[^\"]|\\.)*)" "(?<agent>(?:[^\"]|\\.)*)")?$/

The problematic parts of the regex are the capture groups path, referer, and agent, which have the form (?<...>(?:[^\"]|\\.)*?. The string \x, for example, will match both branches of the alternation (|), so the regex engine has two possible paths in the NFA to try.

A successful ReDoS exploit requires 3 things:

  1. A suitable prefix. In this case, that means a string taking the same format as Apache access logs.
  2. A ‘pump’ (in our case, n repetitions of \x) that sets up 2n possible paths through the NFA.
  3. A suffix that fails to match (in our case, an extra, unescaped " would do it), triggering backtracking.

For example, with 28 repetitions of \x and a "suffix for the user-agent, it takes approximately 30 seconds to test the string:

irb(main):025:0> agent = '\\x' * 28 + '"'
=> "\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\\x\""
irb(main):026:0> REGEXP.match '127.0.0.1 - username [29/Jun/2021:12:23:16 +0100] "GET /foo.html HTTP/1.0" 200 1234 "https://example.com/referer" "' + agent + '"'
processing time: 30.385724s
=> nil

Every additional \x doubles the time it takes.

Impact

Denial of Service

CVE

Resources

Credit

This issue was discovered by @nickrolfe (Nick Rolfe) from the GitHub CodeQL team.

Contact

You can contact the GHSL team at securitylab@github.com, please include GHSL-2021-102 in any communication regarding this issue.