GHSL-2022-128: Quadratic complexity algorithm in cmark - CVE-2023-22486

Coordinated Disclosure Timeline

• 2022-12-13 Emailed report to John MacFarlane (@jgm).
• 2022-12-15: Acknowledged by John MacFarlane.
• 2023-01-05: Fix implemented by John MacFarlane.
• 2023-01-23: Assigned CVE-2023-22486 and fixed in cmark-gfm (GitHub’s fork of cmark).
• 2023-01-23: Fixed in cmark
• 2023-01-23: Fixed in cmark-gfm

Summary

A crafted markdown document can trigger a quadratic complexity algorithm in cmark.

Product

cmark

Tested Version

Latest master: cd5b2f6

Details

Issue: Quadratic behavior in handle_close_bracket (is_image logic) (GHSL-2022-128)

A markdown document containing a large number of repetitions of the characters ![[]() can trigger quadratic behavior.

Proof of concept:

python3 -c 'print("![[]()" * 20000)' | cmark

Increasing the number 20000 in the above command causes the running time to increase quadratically.

This is a sample stack trace from the quadratic algorithm:

1. handle_close_bracket (subj=0x7fffffffbda0) at src/inlines.c:1230
2. 0x000055555556adcb in parse_inline (subj=0x7fffffffbda0, parent=0x5555555ab790, options=1024) at src/inlines.c:1356
3. 0x000055555556b09e in cmark_parse_inlines (mem=0x5555555a90e0 <DEFAULT_MEM_ALLOCATOR>, parent=0x5555555ab790, refmap=0x5555555aa570, options=1024) at src/inlines.c:1398
4. 0x000055555556545d in process_inlines (mem=0x5555555a90e0 <DEFAULT_MEM_ALLOCATOR>, root=0x5555555aa370, refmap=0x5555555aa570, options=1024) at src/blocks.c:408
5. 0x00005555555658ab in finalize_document (parser=0x5555555aa2c0) at src/blocks.c:530
6. 0x0000555555567626 in cmark_parser_finish (parser=0x5555555aa2c0) at src/blocks.c:1303
7. 0x0000555555562fa2 in main (argc=3, argv=0x7fffffffdfc8) at src/main.c:203

The quadratic behavior is caused by the loop at src/inlines.c:1229:

while (opener != NULL) {
  if (!opener->image) {
    if (!opener->active) {
      break;
    } else {
      opener->active = false;
    }
  }
  opener = opener->previous;
}

The malicious input (see above) causes this loop to repeatedly iterate all the way back to the beginning of the list.

Impact

This issue could be used in a denial-of-service attack on websites that use cmark to render markdown documents.

CVE

• CVE-2023-22486

Credit

This issue was discovered and reported by GHSL team member @kevinbackhouse (Kevin Backhouse).

Contact

You can contact the GHSL team at securitylab@github.com, please include a reference to GHSL-2022-128 in any communication regarding this issue.