Opened 4 years ago

Last modified 4 years ago

#18162 closed defect

Potential heap corruption in smartlist_add(), smartlist_insert() — at Initial Version

Reported by: asn Owned by:
Priority: High Milestone: Tor: 0.2.8.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-bug-bounty, security, 025-backport, 026-backport, 027-backport, 024-backport, 2016-bug-retrospective
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

Here follows vulnerability report by Guido Vranken.
The attack requires minimum 16GB of available memory on the victim's host, so it's quite hard to be exploited.

Walkthrough of the vulnerability

smartlist_add and smartlist_insert both invoke smartlist_ensure_capacity prior adding an element to the list in order to ensure that sufficient memory is available, to exit() if not enough memory is available and to detect requests for an invalid size:

static INLINE void
smartlist_ensure_capacity(smartlist_t *sl, int size)
{
#if SIZEOF_SIZE_T > SIZEOF_INT
#define MAX_CAPACITY (INT_MAX)
#else
#define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*))))
#define ASSERT_CAPACITY
#endif
  if (size > sl->capacity) {
    int higher = sl->capacity;
    if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) {
#ifdef ASSERT_CAPACITY
      /* We don't include this assertion when MAX_CAPACITY == INT_MAX,
       * since int size; (size <= INT_MAX) makes analysis tools think we're
       * doing something stupid. */
      tor_assert(size <= MAX_CAPACITY);
#endif
      higher = MAX_CAPACITY;
    } else {
      while (size > higher)
        higher *= 2;
    }
    sl->capacity = higher;
    sl->list = tor_reallocarray(sl->list, sizeof(void*),
                                ((size_t)sl->capacity));
  }
#undef ASSERT_CAPACITY
#undef MAX_CAPACITY
}

On a typical 64-bit system, SIZEOF_INT is 4 and SIZEOF_SIZE_T is 8. Consequently, MAX_CAPACITY is INT_MAX, which is 0x7FFFFFFF as can be seen in torint.h:

#ifndef INT_MAX
#if (SIZEOF_INT == 4)
#define INT_MAX 0x7fffffffL
#elif (SIZEOF_INT == 8)
#define INT_MAX 0x7fffffffffffffffL
#else
#error "Can't define INT_MAX"
#endif
#endif

So MAX_CAPACITY is 0x7FFFFFFF. Now assume that that many (0x7FFFFFFF) items have already been added to a smartlist via smartlist_add(sl, value).

smartlist_add() is:

void
smartlist_add(smartlist_t *sl, void *element)
{
  smartlist_ensure_capacity(sl, sl->num_used+1);
  sl->list[sl->num_used++] = element;
}

If sl->num_used is 0x7FFFFFFF prior to invoking smartlist_add, then the next smartlist_add is effectively:

void
smartlist_add(smartlist_t *sl, void *element)
{
  smartlist_ensure_capacity(sl, -2147483648);
  sl->list[2147483647] = element;
  sl->num_used = -2147483648
}

This is the case since we are dealing with a signed 32 bit integer, and 2147483647 + 1 equals -2147483647.

All of the code in smartlist_ensure_capacity is wrapped inside the following if block:

  if (size > sl->capacity) {
  }

The expression -2147483648 > 2147483647 equals false, thus the code inside the block is not executed.

What actually causes the segmentation fault is that a negative 32 bit integer is used to compute a the location of array index on a 64 bit memory layout, ie., the next call to smartlist_add is effectively:

void
smartlist_add(smartlist_t *sl, void *element)
{
  smartlist_ensure_capacity(sl, -2147483647); // Note that this is effective do-nothing code, as explained above
  sl->list[-2147483648] = element;
  sl->num_used = -2147483647
}

Discussion

The requirement for 16 gigabytes of memory is considerable.

Triggering the vulnerability obviously also requires some code path which will invoke smartlist_add or smartlist_insert upon the same smartlist at the attacker's behest. Moreover, such a code path may have the side effect that it requires a separate allocation for each object that is added to the list; smartlist_add takes a pointer argument after all -- usually, but not always, this pointer refers to freshly allocated memory. Exceptions to this rule are static strings and pointers to a place in a large string or buffer that was already extant.
Once a vulnerable code path has been discovered, then it ultimately boils down to how much memory a user's machine is able to allocate in order to corrupt the heap.

Despite these constraints, smartlists form a considerable portion of the infrastructure of your code (I count some 380+ occurrences of smartlist_add/smartlist_insert in the .c files using grep, that is excluding the test/ directory) and as such it's probably wise to revise the checks in smartlist_ensure_capacity.

Child Tickets

Change History (0)

Note: See TracTickets for help on using tickets.