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

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

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.

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

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.

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.