[PATCH] Fix LD_HWCAP_MASK handling

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

Initially reported by Tavis Ormandy as a security problem, but I do not
believe this can be successfully exploited:
- the problematic code (_dl_important_hwcaps) is run when ld.so isn't
  yet fully initialized and only ld.so, the binary, tiny stack and possibly
  vdso are mapped in the address space, so no libc around, calls through
  PLT don't work, etc.
- ld.so's minimal malloc is used (which just incrementally allocates memory,
  first from the end of ld.so's writable segment, then mmap, only last
  allocation can be freed), there is no real heap with sensitive data
  structures in between regions
- _dl_important_hwcaps mallocs (using a single minimal malloc) two
  consecutive chunks of memory, the first is an array of r_strlenpair
  structures, the second part will be a huge string, consisting of the hwcap
  names (hardcoded in ld.so or provided by the kernel, typically only
  lowercase letters and digits) and separated by the directory separator
  - /
  First the code fills the first 2 entries in the array, then sets up
  the string area, using mempcpy calls and last it fills the rest of the
  array in the first area of the allocation.  The first area
  is (1 << cnt) * sizeof (struct r_strlenpair) bytes long, where cnt
  is the number of important hwcaps (LD_HWCAP_MASK bits anded with actual
  AT_HWCAP bits, plus a few hardcoded or kernel provided ones - one
  "tls" hwcap, one with the name of the platform ("i686", etc.) and from
  kernel sometimes "nosegneg".
- no architecture defines more than ~ 35 hwcaps and all hwcaps have ld.so
  or kernel controlled very short names, so on 64-bit architectures
  the computation of total and (1 << cnt) * sizeof (struct r_strlenpair) +
  total won't overflow.  If there isn't enough memory (mmap fails),
  the minimal malloc implementation will either die with an assertion
  failure or (in -DNDEBUG builds) return -1UL.  The code after that will
  store something to -1UL + sizeof (char *) and as nothing is mapped
  at address 0 at that point, will just segfault
- on most 32-bit architectures there aren't enough AT_HWCAP bits set
  or defined in the hwcap strings, only i?86 has all hwcap bits defined
- if cnt is too big (29 and more on 32-bit i?86), (1 << cnt) * sizeof
  (struct r_strlenpair) overflows to 0 and therefore the string
  initialization goes from the beginning of minimal malloc returned area
  upwards, where it surely will hit some unmapped page, either in the
  string initialization or in the subsequent loop initializing the array
  (both go from the bottom upwards)
- the problematic case is cnt smaller than that (28, 27) where malloc
  returns != -1UL, but smaller than the expected size, either because
  of overflow (for cnt == 28), or because ld.so's _end was closer to
  end of virtual address space than the non-overflown size of the region.
  But to successfully exploit this control flow needs to be changed
  so that the string initialization doesn't finish and fall through
  filling the first array (which would segfault) or at least alter
  the internal variables of _dl_hwcap_important so that the loop
  doesn't segfault, but still doesn't modify them too much to break
  the subsequent working of ld.so.  Both mean on i?86 changing the stack
  page (as this is very early in ld.so initialization and no calls with
  deep call stacks were done, most probably no pages below %esp or at
  most one is still mapped).  In order to alter the stack, a lot of
  luck would be needed, such that ld.so's _end is exactly (1 << cnt) * 8
  bytes below the stack page, otherwise it will reach some unmapped page
  before reaching the stack page and segfault.  That's theoretically
  possible, but very unlikely.  While the attacker has some limited
  control over the string array (in addition to number of bits, i.e.
  cnt it can select which hwcaps are considered important, but not
  the order among those important ones - that's always starting with
  smallest one), still it means overwriting the stack just with
  characters from the 0x2f .. 0x39 and 0x61 .. 0x7a ranges.  Non-PIE
  binaries reside at 0x08HHHHHH addresses, non-randomized PIEs
  reside at 0x80000000 or 0x55554000 addresses, randomized at
  various addresses, but usually either around very low addresses
  (0x00HHHHHH for exec-shield), 0x40HHHHHH (TASK_UNMAPPED_BASE),
  0x55554000 (TASK_UNMAPPED_BASE on x86_64 kernels without setarch i386 -3)
  or very high in the address space (0xbHHHHHHH, below stack +
  RLIMIT_STACK).  So if ld.so's _end happend to be very high in the address
  space and exactly (1 << cnt) * 8 below stack page or mmap returned
  similar address (unlikely), it is possible to change the address where
  mempcpy returns to, but it likely won't be to a mapped
  space where code can be executed and if it will, the attacker
  doesn't have much control over where it will land and what will it do
  there.  As ld.so is mostly uninitialized, the chances it successfully
  loads other libraries are very small and there are no sequences in
  ld.so which e.g. let you spawn shell.

2007-07-01  Jakub Jelinek  <jakub@redhat.com>

	* elf/dl-sysdep.c (_dl_important_hwcaps): Add integer overflow check.
	* elf/dl-minimal.c (__libc_memalign): Likewise.  Handle malloc (0).
	Return NULL if mmap failed instead of asserting it does not.
	(calloc): Check for integer overflow.

	* elf/dl-minimal.c (__strtoul_internal): Fix parsing of numbers bigger
	than LONG_MAX / 10.

--- libc/elf/dl-sysdep.c.jj	2006-10-31 23:05:30.000000000 +0100
+++ libc/elf/dl-sysdep.c	2007-07-01 22:30:37.000000000 +0200
@@ -1,5 +1,5 @@
 /* Operating system support for run-time dynamic linker.  Generic Unix version.
-   Copyright (C) 1995-1998, 2000-2005, 2006 Free Software Foundation, Inc.
+   Copyright (C) 1995-1998, 2000-2006, 2007 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
@@ -460,9 +460,21 @@ _dl_important_hwcaps (const char *platfo
     total = temp[0].len + 1;
   else
     {
-      total = (1UL << (cnt - 2)) * (temp[0].len + temp[cnt - 1].len + 2);
-      for (n = 1; n + 1 < cnt; ++n)
-	total += (1UL << (cnt - 3)) * (temp[n].len + 1);
+      total = temp[0].len + temp[cnt - 1].len + 2;
+      if (cnt > 2)
+	{
+	  total <<= 1;
+	  for (n = 1; n + 1 < cnt; ++n)
+	    total += temp[n].len + 1;
+	  if (cnt > 3
+	      && (cnt >= sizeof (size_t) * 8
+		  || total + (sizeof (*result) << 3)
+		     >= (1UL << (sizeof (size_t) * 8 - cnt + 3))))
+	    _dl_signal_error (ENOMEM, NULL, NULL,
+			      N_("Xcannot create capability list"));
+
+	  total <<= cnt - 3;
+	}
     }
 
   /* The result structure: we use a very compressed way to store the
--- libc/elf/dl-minimal.c.jj	2007-02-26 18:13:43.000000000 +0100
+++ libc/elf/dl-minimal.c	2007-07-01 22:12:57.000000000 +0200
@@ -75,14 +75,21 @@ __libc_memalign (size_t align, size_t n)
   alloc_ptr = (void *) 0 + (((alloc_ptr - (void *) 0) + align - 1)
 			    & ~(align - 1));
 
-  if (alloc_ptr + n >= alloc_end)
+  if (alloc_ptr + n >= alloc_end || n >= -(uintptr_t) alloc_ptr)
     {
       /* Insufficient space left; allocate another page.  */
       caddr_t page;
       size_t nup = (n + GLRO(dl_pagesize) - 1) & ~(GLRO(dl_pagesize) - 1);
+      if (__builtin_expect (nup == 0, 0))
+	{
+	  if (n)
+	    return NULL;
+	  nup = GLRO(dl_pagesize);
+	}
       page = __mmap (0, nup, PROT_READ|PROT_WRITE,
 		     MAP_ANON|MAP_PRIVATE, _dl_zerofd, 0);
-      assert (page != MAP_FAILED);
+      if (page == MAP_FAILED)
+	return NULL;
       if (page != alloc_end)
 	alloc_ptr = page;
       alloc_end = page + nup;
@@ -108,7 +115,14 @@ calloc (size_t nmemb, size_t size)
   /* New memory from the trivial malloc above is always already cleared.
      (We make sure that's true in the rare occasion it might not be,
      by clearing memory in free, below.)  */
-  return malloc (nmemb * size);
+  size_t bytes = nmemb * size;
+
+#define HALF_SIZE_T (((size_t) 1) << (8 * sizeof (size_t) / 2))
+  if (__builtin_expect ((nmemb | size) >= HALF_SIZE_T, 0)
+      && size != 0 && bytes / size != nmemb)
+    return NULL;
+
+  return malloc (bytes);
 }
 
 /* This will rarely be called.  */
@@ -264,7 +278,7 @@ __strtoul_internal (const char *nptr, ch
   while (*nptr >= '0' && *nptr <= '9')
     {
       unsigned long int digval = *nptr - '0';
-      if (result > LONG_MAX / 10
+      if (result > ULONG_MAX / 10
 	  || (result == ULONG_MAX / 10 && digval > ULONG_MAX % 10))
 	{
 	  errno = ERANGE;

	Jakub