Coordinated Disclosure Timeline
- 2021-07-12: Report sent to maintainers
- 2021-10-12: Maintainers contacted about the expiration of the disclosure window
- 2021-10-22: Maintainers proposed a fix
- 2021-10-29: Maintainers released a fix
Summary
Product
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:
- A suitable prefix. In this case, that means a string taking the same format as Apache access logs.
- A ‘pump’ (in our case, n repetitions of
\x) that sets up 2n possible paths through the NFA. - 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
- CVE-2021-41186
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.