[tor-bugs] #18162 [- Select a component]: Potential heap corruption in smartlist_add(), smartlist_insert()
Tor Bug Tracker & Wiki
blackhole at torproject.org
Wed Jan 27 15:15:57 UTC 2016
#18162: Potential heap corruption in smartlist_add(), smartlist_insert()
----------------------------------+---------------------
Reporter: asn | Owner:
Type: defect | Status: new
Priority: Medium | Milestone:
Component: - Select a component | Version:
Severity: Normal | Resolution:
Keywords: | Actual Points:
Parent ID: | Points:
Sponsor: |
----------------------------------+---------------------
Description changed by asn:
Old 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`.
New description:
Here follows vulnerability report by `Guido Vranken` reported through the
Tor bug bounty program.
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`.
--
--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/18162#comment:1>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online
More information about the tor-bugs
mailing list