ldb: avoid out of bounds read and write in ldb_qsort()
authorDouglas Bagnall <douglas.bagnall@catalyst.net.nz>
Wed, 3 Apr 2024 22:06:00 +0000 (11:06 +1300)
committerAndrew Bartlett <abartlet@samba.org>
Wed, 10 Apr 2024 22:56:33 +0000 (22:56 +0000)
commit73e4f6026ad04b73074b413bd8c838ca48ffde7f
tree9800f68176a269fb4b3b6674e2971130f698b97e
parent60df2a09a4394d2b494224ad3d33314079e73066
ldb: avoid out of bounds read and write in ldb_qsort()

If a compare function is non-transitive (for example, if it evaluates
A > B and B > C, but A < C), this implementation of qsort could access
out-of-bounds memory. This was found in glibc's qsort by Qualys, and
their write-up for OSS-Security explains it very well:

 https://www.openwall.com/lists/oss-security/2024/01/30/7

An example of a non-transitive compare is one in which does this

 int cmp(const void *_a, const void *_b)
 {
        int a = *(int *)_a;
        int b = *(int *)_b;
        return a - b;
 }

which does the right thing when the magnitude of the numbers is small,
but which will go wrong if a is INT_MIN and b is INT_MAX. Likewise, if
a and b are e.g. uint32_t, the value can wrap when cast to int.

We have functions that are non-transitive regardless of subtraction.
For example, here (which is not used with ldb_qsort):

 int codepoint_cmpi(codepoint_t c1, codepoint_t c2)
        if (c1 == c2 ||
            toupper_m(c1) == toupper_m(c2)) {
                return 0;
        }
        return c1 - c2;
 }

The toupper_m() is only called on equality case. Consider {'a', 'A', 'B'}.
     'a' == 'A'
     'a' >  'B'  (lowercase letters come after upper)
     'A' <  'B'

BUG: https://bugzilla.samba.org/show_bug.cgi?id=15569
BUG: https://bugzilla.samba.org/show_bug.cgi?id=15625

Signed-off-by: Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>
lib/ldb/common/qsort.c