From 58d08ac1badbd17e129b5005ac8d8ce42a3cd40a Mon Sep 17 00:00:00 2001 From: Douglas Bagnall Date: Wed, 3 Mar 2021 19:17:36 +1300 Subject: [PATCH 1/4] ldb_match: trailing chunk must match end of string MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 Reviewed-by: Björn Jacke Reviewed-by: Andrew Bartlett (cherry picked from commit cc098f1cad04b2cfec4ddd6b2511cd5a600f31c6) --- lib/ldb/common/ldb_match.c | 80 +++++++++++++++++--------------------- 1 file 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 */ -- 2.20.2 From 2dad81b3bbba51598b691d11cb3b377bb88666e1 Mon Sep 17 00:00:00 2001 From: Douglas Bagnall Date: Fri, 5 Mar 2021 15:47:56 +1300 Subject: [PATCH 2/4] ldb: add tests for ldb_wildcard_compare MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit BUG: https://bugzilla.samba.org/show_bug.cgi?id=14044 Signed-off-by: Douglas Bagnall Reviewed-by: Björn Jacke Reviewed-by: Andrew Bartlett (cherry picked from commit 33a95a1e75b85e9795c4490b78ead2162e2a1f47) --- lib/ldb/tests/ldb_match_test.c | 134 ++++++++++++++++++++++++++++++--- 1 file changed, 124 insertions(+), 10 deletions(-) diff --git a/lib/ldb/tests/ldb_match_test.c b/lib/ldb/tests/ldb_match_test.c index e09f50c86ba..3028aed072c 100644 --- a/lib/ldb/tests/ldb_match_test.c +++ b/lib/ldb/tests/ldb_match_test.c @@ -91,6 +91,33 @@ static int teardown(void **state) return 0; } +static void escape_string(uint8_t *buf, size_t buflen, + const uint8_t *s, size_t len) +{ + size_t i; + size_t j = 0; + for (i = 0; i < len; i++) { + if (j == buflen - 1) { + goto fin; + } + if (s[i] >= 0x20) { + buf[j] = s[i]; + j++; + } else { + if (j >= buflen - 4) { + goto fin; + } + /* utf-8 control char representation */ + buf[j] = 0xE2; + buf[j + 1] = 0x90; + buf[j + 2] = 0x80 + s[i]; + j+= 3; + } + } +fin: + buf[j] = 0; +} + /* * The wild card pattern "attribute=*" is parsed as an LDB_OP_PRESENT operation @@ -122,23 +149,110 @@ static void test_wildcard_match_star(void **state) * Test basic wild card matching * */ +struct wildcard_test { + uint8_t *val; + size_t val_size; + const char *search; + bool should_match; + bool fold; +}; + +/* + * Q: Why this macro rather than plain struct values? + * A: So we can get the size of the const char[] value while it is still a + * true array, not a pointer. + * + * Q: but why not just use strlen? + * A: so values can contain '\0', which we supposedly allow. + */ + +#define TEST_ENTRY(val, search, should_match, fold) \ + { \ + (uint8_t*)discard_const(val), \ + sizeof(val) - 1, \ + search, \ + should_match, \ + fold \ + } + static void test_wildcard_match(void **state) { struct ldbtest_ctx *ctx = *state; - bool matched = false; - - uint8_t value[] = "The value.......end"; - struct ldb_val val = { - .data = value, - .length = (sizeof(value)) + size_t failed = 0; + size_t i; + struct wildcard_test tests[] = { + TEST_ENTRY("The value.......end", "*end", true, true), + TEST_ENTRY("The value.......end", "*fend", false, true), + TEST_ENTRY("The value.......end", "*eel", false, true), + TEST_ENTRY("The value.......end", "*d", true, true), + TEST_ENTRY("The value.......end", "*D*", true, true), + TEST_ENTRY("The value.......end", "*e*d*", true, true), + TEST_ENTRY("end", "*e*d*", true, true), + TEST_ENTRY("end", " *e*d*", true, true), + TEST_ENTRY("1.0.0.0.0.0.0.0aaaaaaaaaaaa", "*aaaaa", true, true), + TEST_ENTRY("1.0..0.0.0.0.0.0.0aAaaaAAAAAAA", "*a", true, true), + TEST_ENTRY("1.0.0.0.0.0.0.0.0.0.0aaaa", "*aaaaa", false, true), + TEST_ENTRY("1.0.0.0.0.0.0.0.0.0.0", "*0.0", true, true), + TEST_ENTRY("1.0.0.0.0.0.0.0.0.0.0", "*0.0.0", true, true), + TEST_ENTRY("1.0.0.0.0.0.0.0.0.0", "1*0*0*0*0*0*0*0*0*0", true, + true), + TEST_ENTRY("1.0.0.0.0.0.0.0.0", "1*0*0*0*0*0*0*0*0*0", false, + true), + TEST_ENTRY("1.0.0.0.000.0.0.0.0", "1*0*0*0*0*0*0*0*0*0", true, + true), + TEST_ENTRY("1\n0\r0\t000.0.0.0.0", "1*0*0*0*0*0*0*0*0", true, + true), + /* + * We allow NUL bytes in non-casefolding syntaxes. + */ + TEST_ENTRY("1\x00 x", "1*x", true, false), + TEST_ENTRY("1\x00 x", "*x", true, false), + TEST_ENTRY("1\x00 x", "*x*", true, false), + TEST_ENTRY("1\x00 x", "* *", true, false), + TEST_ENTRY("1\x00 x", "1*", true, false), + TEST_ENTRY("1\x00 b* x", "1*b*", true, false), + TEST_ENTRY("1.0..0.0.0.0.0.0.0aAaaaAAAAAAA", "*a", false, false), }; - struct ldb_parse_tree *tree = ldb_parse_tree(ctx, "objectClass=*end"); - assert_non_null(tree); - ldb_wildcard_compare(ctx->ldb, tree, val, &matched); - assert_true(matched); + for (i = 0; i < ARRAY_SIZE(tests); i++) { + bool matched; + int ret; + struct ldb_val val = { + .data = (uint8_t *)tests[i].val, + .length = tests[i].val_size + }; + const char *attr = tests[i].fold ? "objectclass" : "birthLocation"; + const char *s = talloc_asprintf(ctx, "%s=%s", + attr, tests[i].search); + struct ldb_parse_tree *tree = ldb_parse_tree(ctx, s); + assert_non_null(tree); + ret = ldb_wildcard_compare(ctx->ldb, tree, val, &matched); + if (ret != LDB_SUCCESS) { + uint8_t buf[100]; + escape_string(buf, sizeof(buf), + tests[i].val, tests[i].val_size); + print_error("%zu val: «%s», search «%s» FAILED with %d\n", + i, buf, tests[i].search, ret); + failed++; + } + if (matched != tests[i].should_match) { + uint8_t buf[100]; + escape_string(buf, sizeof(buf), + tests[i].val, tests[i].val_size); + print_error("%zu val: «%s», search «%s» should %s\n", + i, buf, tests[i].search, + matched ? "not match" : "match"); + failed++; + } + } + if (failed != 0) { + fail_msg("wrong results for %zu/%zu wildcard searches\n", + failed, ARRAY_SIZE(tests)); + } } +#undef TEST_ENTRY + /* * ldb_handler_copy and ldb_val_dup over allocate by one and add a trailing '\0' -- 2.20.2 From b3ab6fb521fee59a3349353eba4ed546c26e312f Mon Sep 17 00:00:00 2001 From: Douglas Bagnall Date: Wed, 3 Mar 2021 19:54:37 +1300 Subject: [PATCH 3/4] ldb_match: remove redundant check MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit We already ensure the no-trailing-asterisk case ends at the end of the string. BUG: https://bugzilla.samba.org/show_bug.cgi?id=14044 Signed-off-by: Douglas Bagnall Reviewed-by: Björn Jacke Reviewed-by: Andrew Bartlett (cherry picked from commit fa93339978040eab52b2722c1716028b48d8d084) --- lib/ldb/common/ldb_match.c | 2 -- 1 file changed, 2 deletions(-) diff --git a/lib/ldb/common/ldb_match.c b/lib/ldb/common/ldb_match.c index da595615bd9..2f4d41f3441 100644 --- a/lib/ldb/common/ldb_match.c +++ b/lib/ldb/common/ldb_match.c @@ -342,8 +342,6 @@ static int ldb_wildcard_compare(struct ldb_context *ldb, TALLOC_FREE(cnk.data); } - /* last chunk may not have reached end of string */ - if ( (! tree->u.substring.end_with_wildcard) && (val.length != 0) ) goto mismatch; talloc_free(save_p); *matched = true; return LDB_SUCCESS; -- 2.20.2 From dec3269072157d864baca63650b7ed4e48a8bc13 Mon Sep 17 00:00:00 2001 From: Douglas Bagnall Date: Fri, 5 Mar 2021 15:49:56 +1300 Subject: [PATCH 4/4] ldb: dn tests use cmocka print functions MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit BUG: https://bugzilla.samba.org/show_bug.cgi?id=14044 Signed-off-by: Douglas Bagnall Reviewed-by: Björn Jacke Reviewed-by: Andrew Bartlett Autobuild-User(master): Andrew Bartlett Autobuild-Date(master): Wed Mar 10 09:51:25 UTC 2021 on sn-devel-184 (cherry picked from commit bb17b4e1bbd1f03445bb3ef8cfd5f33d5e49bccc) --- lib/ldb/tests/test_ldb_dn.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/lib/ldb/tests/test_ldb_dn.c b/lib/ldb/tests/test_ldb_dn.c index 050c2a66a96..f4b84f9bc04 100644 --- a/lib/ldb/tests/test_ldb_dn.c +++ b/lib/ldb/tests/test_ldb_dn.c @@ -191,7 +191,6 @@ static void test_ldb_dn_explode(void **state) * special, invalid, linear, and ext_linear are set before * explode */ - fprintf(stderr, "%zu «%s»: ", i, tests[i].strdn); linear = ldb_dn_get_linearized(dn); assert_true((linear == NULL) == (tests[i].linearized == NULL)); assert_string_equal(linear, @@ -210,8 +209,8 @@ static void test_ldb_dn_explode(void **state) /* comp nums are set by explode */ result = ldb_dn_validate(dn); - fprintf(stderr, "res %i lin «%s» ext «%s»\n", - result, linear, ext_linear); + print_error("test %zu «%s»: res %i lin «%s» ext «%s»\n", + i, tests[i].strdn, result, linear, ext_linear); assert_true(result == tests[i].explode_result); assert_int_equal(ldb_dn_get_comp_num(dn), -- 2.20.2