On the oss-security mailing list, Qualys report that the quicksort implementation in glibc is liable to read and write out of bounds with an intransitive compare function function (which includes the `return a - b` type). https://www.openwall.com/lists/oss-security/2024/01/30/7 With glibc it is bit fiddly to force qsort into using quicksort -- it tries a mergesort first and only resorts to quicksort if an allocation fails[1] -- but in 2006 we adapted the glibc code for lib/ldb/common/qsort.c and that uses the quicksort unconditionally. I haven't checked, but don't I imagine we have non-transitive compares (I think I tried to write one but Jo Sutton stopped me), so this might not be a real problem. Nevertheless, LDB is a semi-public library and there might be other vulnerable users. The mergesort-first behaviour of glibc leads to other bugs we have, where we assume a stable qsort(), which is not common on non-GNU platforms. Indeed, the Qualys article mentions that GNU wanted to change their qsort() to a quicker unstable sort, but it broke too many applications that erroneously relied on the stable behaviour. I think we forked qsort to get qsort_r behaviour for ldb. We now have lib/util/stablesort.c for reliable stable sorts. It includes a qsort_r type function, so we could use that for ldb_qsort().
> We now have lib/util/stablesort.c for reliable stable sorts. It includes a qsort_r type function, so we could use that for ldb_qsort(). Which is not to say we shouldn't do the simple patch first, with involves adding a `tmp_ptr != base_ptr &&` in one place. > I haven't checked, but don't I imagine we have non-transitive compares[...] These ones look dodgy: winsdb_addr_sort_list() in source4/nbt_server/wins/winsdb.c nbtd_wins_randomize1Clist_sort() in source4/nbt_server/wins/winsserver.c I am not completely sure about *all* the others, as some of the code is a bit complex and might introduce non-transitivity in other ways. > Nevertheless, LDB is a semi-public library and there might be other vulnerable users. I can find no use of ldb_qsort() in sssd, so probably that's fine.
In case it’s useful, here’s my old patch to remove ldb_qsort(): https://gitlab.com/samba-team/devel/samba/-/commit/22ba148e2b763ce4644b6a28d9da0a36198026f5
(In reply to Douglas Bagnall from comment #1) > winsdb_addr_sort_list() in source4/nbt_server/wins/winsdb.c This one is probably OK, because the subtracted items are boolean. and > nbtd_wins_randomize1Clist_sort() in source4/nbt_server/wins/winsserver.c here I think the numbers are <= 32, so we're not looking at overflows. Also the nbt server is not often used.
I think we actually found this earlier: https://bugzilla.samba.org/show_bug.cgi?id=14138#c4 and commit defb23732515e3c638d0081f5e4043fbb35d303c > dns_name_compare() had logic to put @ and the top record in the tree being > enumerated first, but if a domain had both then this would break the > older qsort() implementation in ldb_qsort() and cause a read of memory > before the base pointer.
(In reply to Douglas Bagnall from comment #4) > I think we actually found this earlier: also https://bugzilla.samba.org/show_bug.cgi?id=3959
also https://bugzilla.samba.org/show_bug.cgi?id=11503!
This bug was referenced in samba master: 73e4f6026ad04b73074b413bd8c838ca48ffde7f