safety – Out-of-bounds learn & write within the glibc’s qsort()

2024-02-05 12:04:06
oss-security – Out-of-bounds learn & write within the glibc’s qsort()
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Tue, 30 Jan 2024 18:39:37 +0000
From: Qualys Safety Advisory <qsa@...lys.com>
To: "oss-security@...ts.openwall.com" <oss-security@...ts.openwall.com>
Topic: Out-of-bounds learn & write within the glibc's qsort()


Qualys Safety Advisory

For the algorithm lovers: Nontransitive comparability features result in
out-of-bounds learn & write in glibc's qsort()


========================================================================
Contents
========================================================================

Abstract
Background
Experiments
Evaluation
Patch
Dialogue
Acknowledgments
Timeline

    CUT MY LIST IN TWO PIECES
    THAT'S HOW YOU START QUICK SORT
        -- https://twitter.com/QuinnyPig/status/1710447650112438710


========================================================================
Abstract
========================================================================

We found a reminiscence corruption within the glibc's qsort() perform, due
to a lacking bounds examine. To be susceptible, a program should name qsort()
with a nontransitive comparability perform (a perform cmp(int a, int b)
that returns (a - b), for instance) and with a lot of attacker-
managed components (to trigger a malloc() failure inside qsort()). We
haven't tried to seek out such a susceptible program in the actual world.

All glibc variations from not less than September 1992 (glibc 1.04) to the
present launch (glibc 2.38) are affected, however the glibc's builders
have independently found and patched this reminiscence corruption within the
grasp department (commit b9390ba, "stdlib: Repair array bounds safety in
insertion kind part of qsort") throughout a current refactoring of qsort().

About our advisory, the glibc safety staff points the next
assertion:

------------------------------------------------------------------------
This reminiscence corruption within the GNU C Library by the qsort perform is
invoked by an software passing a non-transitive comparability perform, which
is undefined in response to POSIX and ISO C requirements.  In consequence, we're of
the opinion that the ensuing CVE, if any, ought to be assigned to any such
calling purposes and subsequently fastened by passing a legitimate comparability
perform to qsort and to not glibc.  We nonetheless acknowledge that it is a
high quality of implementation challenge and we fastened this in a current refactor of
qsort.  We wish to thank Qualys for sharing their findings and serving to
us validate our current adjustments to qsort.
------------------------------------------------------------------------


========================================================================
Background
========================================================================

Whereas looking by Postfix's HISTORY file, we stumbled throughout a
puzzling entry from February 2002:

------------------------------------------------------------------------
        Bugfix: make all recipient comparisons transitive, as a result of
        Solaris qsort() causes SIGSEGV errors in any other case. Victor
        Duchovni, Morgan Stanley. File: *qmgr/qmgr_message.c.
------------------------------------------------------------------------

Segmentation faults in qsort()? Transitive comparability features?

As defined within the guide web page for qsort(), "The comparability perform
should return an integer lower than, equal to, or larger than zero if the
first argument is taken into account to be respectively lower than, equal to, or
larger than the second." In fact, such a comparability perform cmp()
have to be transitive:

- if a < b (i.e., if cmp(pointer_to(a), pointer_to(b)) < 0);

- and if b < c (i.e., if cmp(pointer_to(b), pointer_to(c)) < 0);

- then essentially a < c (i.e., cmp(pointer_to(a), pointer_to(c)) < 0).

For instance, the next comparability perform (which compares integers)
is transitive (and completely appropriate):

------------------------------------------------------------------------
int
cmp(const void * const pa, const void * const pb)
{
    const int a = *(const int *)pa;
    const int b = *(const int *)pb;
    if (a > b) return +1;
    if (a < b) return -1;
    return 0;
}
------------------------------------------------------------------------

A shorter and extra environment friendly model of this comparability perform may
merely "return (a > b) - (a < b);" and nonetheless be transitive and completely
appropriate:

- if a > b, it returns 1 - 0 = +1;

- if a < b, it returns 0 - 1 = -1;

- if a = b, it returns 0 - 0 = 0.

The query, then, is: how can a comparability perform be nontransitive?
A comparability perform cmp() is nontransitive if there exist a, b, and c
such that:

- a < b (as a result of cmp(pointer_to(a), pointer_to(b)) < 0);

- b < c (as a result of cmp(pointer_to(b), pointer_to(c)) < 0);

- however a >= c (as a result of cmp(pointer_to(a), pointer_to(c)) >= 0 by
  mistake).

Though the next comparability perform appears appropriate at first, it's
in actual fact nontransitive, as a result of the subtraction in "return (a - b);" is
liable to integer overflows:

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

For instance, if a = INT_MIN, b = 0, and c = INT_MAX, then:

- a < b (as a result of cmp(pointer_to(a), pointer_to(b)) returns INT_MIN - 0,
  which is accurately unfavourable);

- b < c (as a result of cmp(pointer_to(b), pointer_to(c)) returns 0 - INT_MAX,
  which can also be accurately unfavourable);

- however a > c by mistake (as a result of cmp(pointer_to(a), pointer_to(c))
  returns INT_MIN - INT_MAX = +1, which is incorrectly optimistic as a result of
  this subtraction overflows).

Sadly, such nontransitive comparability features are extraordinarily
frequent, as mentioned on this glorious weblog submit from Ted Unangst:

  https://flak.tedunangst.com/post/subtraction-is-not-comparison

and as hinted at in OpenBSD's guide web page for qsort(): "It's virtually
at all times an error to make use of subtraction to compute the return worth of the
comparability perform."

Happily, when handed to a strong qsort() implementation, these
nontransitive comparability features ought to (on the worst) lead to an
incorrectly sorted array; actually not in a reminiscence corruption. Nevertheless,
the aforementioned entry from Postfix's HISTORY file means that not
all qsort() implementations are sturdy.


========================================================================
Experiments
========================================================================

We subsequently determined to evaluate the robustness of the glibc's qsort()
implementation, by calling it with a nontransitive comparability perform:

------------------------------------------------------------------------
  1 #embody <limits.h>
  2 #embody <stdlib.h>
  3 #embody <sys/time.h>
  4 
  5 static int
  6 cmp(const void * const pa, const void * const pb)
  7 {
  8     const int a = *(const int *)pa;
  9     const int b = *(const int *)pb;
 10     return (a - b);
 11 }
 12 
 13 int
 14 most important(const int argc, const char * const argv[])
 15 
------------------------------------------------------------------------

- at traces 5-11, cmp() is the nontransitive comparability perform
  launched within the earlier "Background" part;

- at traces 16-18, the variety of components to be sorted (easy integers)
  is learn from the command line;

- at traces 20-23, the array of components to be sorted is calloc()ated,
  together with a canary ingredient beneath this array, and a canary ingredient
  above this array;

- at traces 29-30, these two canary components are randomized, and copied
  to the stack for later comparability;

- at line 31, one random ingredient of the array is initialized to INT_MIN
  (all different components are initialized to 0 by calloc());

- at line 33, the weather of this array are sorted by qsort();

- at traces 34-35, the 2 canary components (beneath and above the sorted
  array) are checked towards their stack copies, and in the event that they differ (an
  out-of-bounds write in qsort()), abort() is known as.

We selected the array components a = INT_MIN and b = 0 as a result of they straight
exhibit the problematic habits of this cmp() perform:

- a < b, as a result of cmp(pointer_to(a), pointer_to(b)) returns INT_MIN - 0,
  which is accurately unfavourable;

- however b < a by mistake, as a result of cmp(pointer_to(b), pointer_to(a))
  returns 0 - INT_MIN = INT_MIN (the "Leblancian Paradox"), which is
  incorrectly unfavourable (as a result of this subtraction overflows).

We then executed our take a look at program in a loop, on Fedora 39 (which makes use of
the most recent glibc model, 2.38):

------------------------------------------------------------------------
$ whereas true; do n=$((RANDOM*64+RANDOM+1)); ./qsort $n; carried out
------------------------------------------------------------------------

Unsurprisingly, nothing occurred: our program didn't crash or abort().
Whereas this loop was nonetheless operating (and never crashing), we began to learn
the glibc's qsort() implementation; to our nice shock, we found
that the glibc's qsort() isn't, in actual fact, a fast kind by default, however a
merge kind (in stdlib/msort.c).

Almost definitely, merge kind was chosen over fast kind to keep away from fast kind's
worst-case efficiency, which is O(n^2); alternatively, merge kind's
worst-case efficiency is O(n*log(n)). However merge kind suffers from one
main downside: it doesn't kind in-place -- it malloc()ates a duplicate of
the array of components to be sorted. In consequence, if this array may be very
giant (traces 212-217), or if this malloc() fails (traces 219-229), then
the glibc's qsort() falls again to a fast kind (in stdlib/qsort.c),
as a result of fast kind does kind in-place:

------------------------------------------------------------------------
163 void
164 __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
165 {
166   size_t dimension = n * s;
...
170   /* For big object sizes use oblique sorting.  */
171   if (s > 32)
172     dimension = 2 * n * sizeof (void *) + s;
173 
174   if (dimension < 1024)
175     /* The non permanent array is small, so put it on the stack.  */
176     p.t = __alloca (dimension);
177   else
178     {
...
212       /* If the reminiscence necessities are too excessive do not allocate reminiscence.  */
213       if (dimension / pagesize > (size_t) phys_pages)
214         {
215           _quicksort (b, n, s, cmp, arg);
216           return;
217         }
218 
219       /* It is considerably giant, so malloc it.  */
220       int save = errno;
221       tmp = malloc (dimension);
222       __set_errno (save);
223       if (tmp == NULL)
224         {
225           /* Could not get area, so use the slower algorithm
226              that does not want a brief array.  */
227           _quicksort (b, n, s, cmp, arg);
228           return;
229         }
230       p.t = tmp;
231     }
...
299 }
------------------------------------------------------------------------

We subsequently determined to evaluate the robustness of the glibc's fast kind
(as an alternative of its merge kind, which was clearly not crashing), by forcing
qsort() to name _quicksort(). Domestically, forcing the malloc() at line 221
to fail may be very straightforward: we merely execute our program with a low RLIMIT_AS
("The utmost dimension of the method's digital reminiscence", man setrlimit); and
this works even when executing a SUID-root program. So we executed our
program within the following loop as an alternative:

------------------------------------------------------------------------
$ whereas true; do n=$((RANDOM*64+RANDOM+1)); prlimit --as=$((n*4/2*3)) ./qsort $n; carried out
Aborted (core dumped)
Aborted (core dumped)
Aborted (core dumped)
...
------------------------------------------------------------------------

Extremely, we virtually instantly noticed crashes of our take a look at program:
calls to abort(), as a result of one among our canary components (beneath or above the
sorted array) was overwritten (i.e., an out-of-bounds write in qsort()).
To grasp these crashes, we examined one among them in gdb:

------------------------------------------------------------------------
$ gdb prlimit
(gdb) run --as=8104854 ./qsort 1350809
Beginning program: /usr/bin/prlimit --as=8104854 ./qsort 1350809
...
Program obtained sign SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@...ry=6, no_tid=no_tid@...ry=0) at pthread_kill.c:44
44            return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;

(gdb) backtrace
#0  __pthread_kill_implementation (threadid=<optimized out>, signo=signo@...ry=6, no_tid=no_tid@...ry=0) at pthread_kill.c:44
#1  0x00007ffff7e698a3 in __pthread_kill_internal (signo=6, threadid=<optimized out>) at pthread_kill.c:78
#2  0x00007ffff7e178ee in __GI_raise (sig=sig@...ry=6) at ../sysdeps/posix/elevate.c:26
#3  0x00007ffff7dff8ff in __GI_abort () at abort.c:79
#4  0x0000555555555334 in most important (argc=2, argv=0x7fffffffe338) at qsort.c:34

(gdb) select-frame 4
(gdb) p/x canary1
$1 = 0xc6109e4c
(gdb) p/x *pcanary1
$2 = 0x0

(gdb) x/xw pcanary1 - 2
0x7ffff78af008: 0x00528002
0x7ffff78af00c: 0x80000000
0x7ffff78af010: 0x00000000
0x7ffff78af014: 0xc6109e4c
0x7ffff78af018: 0x00000000
------------------------------------------------------------------------

- at tackle 0x7ffff78af010 (pcanary1), the unique worth of the canary
  (0xc6109e4c) was overwritten with 0x0 -- an out-of-bounds write;

- at tackle 0x7ffff78af00c (beneath pcanary1), probably the most vital phrase
  of an mchunk_size (heap metadata) was overwritten with 0x80000000
  (INT_MIN) -- one other out-of-bounds write;

- at tackle 0x7ffff78af014 (above pcanary1), the primary ingredient of the
  array was overwritten with 0xc6109e4c (the unique worth of the
  canary), which was subsequently learn out-of-bounds beforehand (from
  pcanary1).


========================================================================
Evaluation
========================================================================

To determine the foundation trigger of those out-of-bounds reminiscence accesses, we
should analyze the implementation of the glibc's fast kind:

------------------------------------------------------------------------
 87 void
 88 _quicksort (void *const pbase, size_t total_elems, size_t dimension,
 89             __compar_d_fn_t cmp, void *arg)
 90 {
 91   char *base_ptr = (char *) pbase;
...
108       whereas (STACK_NOT_EMPTY)
109         {
...
193         }
...
206     char *tmp_ptr = base_ptr;
...
214     for (run_ptr = tmp_ptr + dimension; run_ptr <= thresh; run_ptr += dimension)
215       if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
216         tmp_ptr = run_ptr;
217 
218     if (tmp_ptr != base_ptr)
219       SWAP (tmp_ptr, base_ptr, dimension);
...
223     run_ptr = base_ptr + dimension;
224     whereas ((run_ptr += dimension) <= end_ptr)
225       {
226         tmp_ptr = run_ptr - dimension;
227         whereas ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
228           tmp_ptr -= dimension;
...
246       }
...
248 }
------------------------------------------------------------------------

- at traces 108-193, when fast kind's partitions turn into smaller than
  MAX_THRESH (4 components), _quicksort() switches to a remaining insertion
  kind (at traces 206-246), which is quicker than fast kind for small or
  principally sorted arrays;

- at traces 206-219, this insertion kind makes certain that the very first
  ingredient of the array (base_ptr) is the smallest ingredient of the array;

- at traces 226-228, this primary ingredient acts as a pure barrier that
  prevents tmp_ptr from being decremented beneath the array (as a result of if
  tmp_ptr reaches base_ptr, then essentially cmp(run_ptr, tmp_ptr) >= 0
  as a result of tmp_ptr is base_ptr, the smallest ingredient of the array);

- sadly this doesn't maintain true if cmp() is nontransitive, in
  which case cmp(run_ptr, tmp_ptr) may be < 0 even when tmp_ptr is
  base_ptr, so tmp_ptr may be decremented beneath the array, the place
  out-of-bounds components are learn and overwritten.


========================================================================
Patch
========================================================================

To patch these out-of-bounds reminiscence accesses in _quicksort(), a easy
examine "tmp_ptr > base_ptr &&" may be added in entrance of the cmp() name at
line 227 (in fact this doesn't magically lead to a accurately sorted
array if cmp() is nontransitive, however not less than it doesn't lead to a
reminiscence corruption anymore).

Actually, whereas drafting this advisory, we found that such a examine
("tmp_ptr != base_ptr &&") has already been added to the glibc's grasp
department (which can turn into glibc 2.39 in February 2024), by the next
commit ("stdlib: Repair array bounds safety in insertion kind part of
qsort"):

  https://sourceware.org/git?p=glibc.git;a=commit;h=b9390ba93676c4b1e87e218af5e7e4bb596312ac

Certainly, the glibc builders have not too long ago refactored qsort() and
changed the merge kind (and its fallback to fast kind) with an
introspective kind (a mix of fast kind, heap kind, and
insertion kind):

  https://en.wikipedia.org/wiki/Introsort
  https://sourceware.org/pipermail/libc-alpha/2023-October/151907.html

Throughout this refactoring, the glibc builders have proactively
found (and patched) the out-of-bounds reminiscence accesses within the
insertion kind (most likely as a result of these out-of-bounds reminiscence accesses
turned straight uncovered to the misbehavior of nontransitive comparability
features, as an alternative of being safely hidden behind a malloc() failure in
the merge kind).

Final-minute observe: in January 2024, the glibc builders have reverted
this refactoring of qsort(), again to the unique merge kind, plus a
fallback to heap kind as an alternative of fast kind; for extra info:

  https://sourceware.org/pipermail/libc-alpha/2024-January/154051.html


========================================================================
Dialogue
========================================================================

We have now not tried to discover a susceptible program (i.e., a program that
makes use of a nontransitive comparability perform to qsort() attacker-controlled
components); nonetheless, susceptible packages are sure to exist in the actual
world:

- calls to qsort() are extraordinarily frequent;

- nontransitive comparability features are additionally frequent;

- all glibc variations from not less than September 1992 (glibc 1.04, the primary
  model that we may discover on-line) to the present launch (glibc 2.38)
  are affected by this reminiscence corruption.

Domestically, forcing a malloc() failure in qsort() (which is critical to
attain the reminiscence corruption) is simple: both execute the goal program
(e.g., a SUID-root program) with a low RLIMIT_AS, or allocate a big
quantity of reminiscence with one other program on the identical machine.

Remotely, forcing this malloc() failure is more durable: both allocate a
great amount of reminiscence (e.g., a reminiscence leak) within the community service that
is being focused, or in one other community service on the identical machine.


========================================================================
Acknowledgments
========================================================================

We thank the glibc safety staff and the linux-distros@...nwall.


========================================================================
Timeline
========================================================================

2023-12-12: We despatched a draft of our advisory to the glibc safety staff.
They instantly acknowledged receipt of our electronic mail.

2023-12-19: The glibc safety staff determined to not deal with this reminiscence
corruption in qsort() as a vulnerability within the glibc itself, as
defined within the "Abstract" of our advisory.

2024-01-16: We backported commit b9390ba to all present and previous steady
variations of the glibc, and despatched this patch and a draft of our advisory
to the linux-distros@...nwall (to piggyback on the glibc embargo for
CVE-2023-6246). They instantly acknowledged receipt of our electronic mail.

2024-01-30: Coordinated Launch Date (18:00 UTC).
Please take a look at the

Open Source Software Security Wiki, which is counterpart to this
mailing list.