[Bug libc/14547] New: strcoll integer / buffer overflow

[Bug libc/14547] New: strcoll integer / buffer overflow

[jsm28 at gcc dot gnu.org]

http://sourceware.org/bugzilla/show_bug.cgi?id=14547

             Bug #: 14547
           Summary: strcoll integer / buffer overflow
           Product: glibc
           Version: 2.16
            Status: NEW
          Severity: normal
          Priority: P2
         Component: libc
        AssignedTo: unassigned@sourceware.org
        ReportedBy: jsm28@gcc.gnu.org
                CC: drepper.fsp@gmail.com
    Classification: Unclassified


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;
}

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[jsm28 at gcc dot gnu.org]

http://sourceware.org/bugzilla/show_bug.cgi?id=14547

--- Comment #1 from Joseph Myers <jsm28 at gcc dot gnu.org> 2012-09-05 21:12:50 UTC ---
It looks like the same issue is also present in strxfrm (not tested).

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[jsm28 at gcc dot gnu.org]

http://sourceware.org/bugzilla/show_bug.cgi?id=14547

Joseph Myers <jsm28 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |shaun.colley at ioactive
                   |                            |dot com

--- Comment #2 from Joseph Myers <jsm28 at gcc dot gnu.org> 2012-09-06 16:54:00 UTC ---
*** Bug 14552 has been marked as a duplicate of this bug. ***

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[ppluzhnikov at google dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=14547

Paul Pluzhnikov <ppluzhnikov at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppluzhnikov at google dot
                   |                            |com

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[bugdal at aerifal dot cx]

http://sourceware.org/bugzilla/show_bug.cgi?id=14547

Rich Felker <bugdal at aerifal dot cx> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugdal at aerifal dot cx

--- Comment #3 from Rich Felker <bugdal at aerifal dot cx> 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.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[shaun.colley at ioactive dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=14547

--- Comment #4 from Shaun Colley <shaun.colley at ioactive dot com> 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

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[shaun.colley at ioactive dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=14547

--- Comment #5 from Shaun Colley <shaun.colley at ioactive dot com> 2012-09-11 15:51:47 UTC ---
The unbounded alloca issue also appears to be present in strxfrm.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[siddhesh at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

Siddhesh Poyarekar <siddhesh at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |siddhesh at redhat dot com
         Resolution|---                         |FIXED

--- Comment #7 from Siddhesh Poyarekar <siddhesh at redhat dot com> ---
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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[mancha1 at hush dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

mancha <mancha1 at hush dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mancha1 at hush dot com

--- Comment #8 from mancha <mancha1 at hush dot com> ---
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!

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[mancha1 at hush dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

--- Comment #9 from mancha <mancha1 at hush dot com> ---
(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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[siddhesh at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

--- Comment #10 from Siddhesh Poyarekar <siddhesh at redhat dot com> ---
(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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[mancha1 at hush dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

--- Comment #11 from mancha <mancha1 at hush dot com> ---
(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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[jackie.rosen at hushmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

Jackie Rosen <jackie.rosen at hushmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jackie.rosen at hushmail dot com

--- Comment #12 from Jackie Rosen <jackie.rosen at hushmail dot com> ---
*** Bug 260998 has been marked as a duplicate of this bug. ***
Seen from the domain http://volichat.com
Page where seen: http://volichat.com/adult-chat-rooms
Marked for reference. Resolved as fixed @bugzilla.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[schwab at sourceware dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

Andreas Schwab <schwab at sourceware dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|jackie.rosen at hushmail dot com   |

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fweimer at redhat dot com
              Alias|                            |CVE-2012-4412
              Flags|                            |security+

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow (CVE-2012-4412, CVE-2012-4424)

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|strcoll integer / buffer    |strcoll integer / buffer
                   |overflow                    |overflow (CVE-2012-4412,
                   |                            |CVE-2012-4424)
              Alias|CVE-2012-4412               |

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/14547] strcoll integer / buffer overflow (CVE-2012-4412, CVE-2012-4424)

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14547

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
              Alias|                            |CVE-2012-4412

-- 
You are receiving this mail because:
You are on the CC list for the bug.