From 007425381dab130e2e30af3ce6c44e5253bf1a2c Mon Sep 17 00:00:00 2001 From: Douglas Bagnall Date: Wed, 3 Mar 2021 19:17:36 +1300 Subject: [PATCH] ldb_match: trailing chunk must match end of string A wildcard search is divided into chunks by the asterisks. While most chunks match the first suitable string, the last chunk matches the last possible string (unless there is a trailing asterisk, in which case this distinction is moot). We always knew this in our hearts, but we tried to do it in a funny complicated way that stepped through the string, comparing here and there, leading to CVE-2019-3824 and missed matches (bug 14044). With this patch, we just jump to the end of the string and compare it. As well as being correct, this should also improve performance, as the previous algorithm involved a quadratic loop of erroneous memmem()s. See https://tools.ietf.org/html/rfc4517 BUG: https://bugzilla.samba.org/show_bug.cgi?id=14044 Signed-off-by: Douglas Bagnall --- lib/ldb/common/ldb_match.c | 69 +++++++++++++++++--------------------- 1 file changed, 30 insertions(+), 39 deletions(-) diff --git a/lib/ldb/common/ldb_match.c b/lib/ldb/common/ldb_match.c index 829afa77e71..2b21b607ec9 100644 --- a/lib/ldb/common/ldb_match.c +++ b/lib/ldb/common/ldb_match.c @@ -304,47 +304,38 @@ static int ldb_wildcard_compare(struct ldb_context *ldb, if (cnk.length == 0) { goto mismatch; } - /* - * Values might be binary blobs. Don't use string - * search, but memory search instead. - */ - p = memmem((const void *)val.data,val.length, - (const void *)cnk.data, cnk.length); - if (p == NULL) goto mismatch; - - /* - * At this point we know cnk.length <= val.length as - * otherwise there could be no match - */ - if ( (! tree->u.substring.chunks[c + 1]) && (! tree->u.substring.end_with_wildcard) ) { - uint8_t *g; - uint8_t *end = val.data + val.length; - do { /* greedy */ - - /* - * haystack is a valid pointer in val - * because the memmem() can only - * succeed if the needle (cnk.length) - * is <= haystacklen - * - * p will be a pointer at least - * cnk.length from the end of haystack - */ - uint8_t *haystack - = p + cnk.length; - size_t haystacklen - = end - (haystack); - - g = memmem(haystack, - haystacklen, - (const uint8_t *)cnk.data, - cnk.length); - if (g) { - p = g; - } - } while(g); + if ( (tree->u.substring.chunks[c + 1]) == NULL && + (! tree->u.substring.end_with_wildcard) ) { + /* + * The last bit, after all the asterisks, must match + * exactly the last bit of the string. + */ + int cmp; + uint8_t *end = NULL; + uint8_t *candidate = NULL; + if (chk.length > val.length) { + goto mismatch; + } + end = val.data + val.length; + candidate = end - cnk.length; + cmp = memcmp(candidate, + cnk.data, + cnk.length); + if (cmp != 0) { + goto mismatch; + } + } else { + /* + * Values might be binary blobs. Don't use string + * search, but memory search instead. + */ + p = memmem((const void *)val.data,val.length, + (const void *)cnk.data, cnk.length); + if (p == NULL) goto mismatch; } + + val.length = val.length - (p - (uint8_t *)(val.data)) - cnk.length; val.data = (uint8_t *)(p + cnk.length); c++; -- 2.20.1