Bug 14547 (CVE-2012-4412) - strcoll integer / buffer overflow (CVE-2012-4412, CVE-2012-4424)
Summary: strcoll integer / buffer overflow (CVE-2012-4412, CVE-2012-4424)
Status: RESOLVED FIXED
Alias: CVE-2012-4412
Product: glibc
Classification: Unclassified
Component: libc (show other bugs)
Version: 2.16
: P2 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
: CVE-2012-4424 (view as bug list)
Depends on:
Blocks:
 
Reported: 2012-09-05 20:59 UTC by Joseph Myers
Modified: 2015-02-24 11:36 UTC (History)
8 users (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:
fweimer: security+


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Joseph Myers 2012-09-05 20:59:31 UTC
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;
}
Comment 1 Joseph Myers 2012-09-05 21:12:50 UTC
It looks like the same issue is also present in strxfrm (not tested).
Comment 2 Joseph Myers 2012-09-06 16:54:00 UTC
*** Bug 14552 has been marked as a duplicate of this bug. ***
Comment 3 Rich Felker 2012-09-08 03:38:25 UTC
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.
Comment 4 Shaun Colley 2012-09-11 09:53:33 UTC
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
Comment 5 Shaun Colley 2012-09-11 15:51:47 UTC
The unbounded alloca issue also appears to be present in strxfrm.
Comment 7 Siddhesh Poyarekar 2013-09-23 06:00:27 UTC
Fixed in master:

commit 303e567a8062200dc06acde7c76fc34679f08d8f
Author: Siddhesh Poyarekar <siddhesh@redhat.com>
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 <siddhesh@redhat.com>
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.
Comment 8 mancha 2013-10-25 13:09:56 UTC
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!
Comment 9 mancha 2013-10-25 13:17:48 UTC
(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.
Comment 10 Siddhesh Poyarekar 2013-10-25 13:30:01 UTC
(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.
Comment 11 mancha 2013-10-25 15:03:25 UTC
(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.
Comment 12 Jackie Rosen 2014-02-16 19:41:09 UTC Comment hidden (spam)