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 <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Björn Jacke <bjacke@samba.org>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>
(cherry picked from commit cc098f1cad04b2cfec4ddd6b2511cd5a600f31c6)

1 files changed, 35 insertions, 45 deletions

diff --git a/lib/ldb/common/ldb_match.c b/lib/ldb/common/ldb_match.c
index 829afa77e71..da595615bd9 100644
--- a/lib/ldb/common/ldb_match.c
+++ b/lib/ldb/common/ldb_match.c
@@ -295,8 +295,9 @@ static int ldb_wildcard_compare(struct ldb_context *ldb,
 		uint8_t *p;
 
 		chunk = tree->u.substring.chunks[c];
-		if(a->syntax->canonicalise_fn(ldb, ldb, chunk, &cnk) != 0) goto mismatch;
-
+		if(a->syntax->canonicalise_fn(ldb, ldb, chunk, &cnk) != 0) {
+			goto mismatch;
+		}
 		/*
 		 * Empty strings are returned as length 0. Ensure
 		 * we can cope with this.
@@ -304,52 +305,41 @@ 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 (cnk.length > val.length) {
+			goto mismatch;
+		}
 
-		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;
+			p = val.data + val.length - cnk.length;
+			cmp = memcmp(p,
+				     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;
+			}
+			/* move val to the end of the match */
+			p += cnk.length;
+			val.length -= (p - val.data);
+			val.data = p;
 		}
-		val.length = val.length - (p - (uint8_t *)(val.data)) - cnk.length;
-		val.data = (uint8_t *)(p + cnk.length);
 		c++;
-		talloc_free(cnk.data);
-		cnk.data = NULL;
+		TALLOC_FREE(cnk.data);
 	}
 
 	/* last chunk may not have reached end of string */