Opened 3 years ago

Closed 3 years ago

#20081 closed defect (fixed)

potential memory corruption in or/buffers.c (not exploitable)

Reported by: asn Owned by: nickm
Priority: Medium Milestone: Tor: 0.2.9.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-bug-bounty, review-group-9
Cc: Actual Points: .1
Parent ID: Points: 0.3
Reviewer: Sponsor:

Description

Bug reported by Guido Vranken through hackerone.

We believe it's not an exploitable issue, but it's still a bug worth fixing.

Here follows the report:


In or/buffer.s.c:

/** Return the allocation size we'd like to use to hold <b>target</b>
 * bytes. */
static inline size_t
preferred_chunk_size(size_t target)
{
  size_t sz = MIN_CHUNK_ALLOC;
  while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
    sz <<= 1;
  }
  return sz;
}
#define MIN_CHUNK_ALLOC 256
#define CHUNK_SIZE_WITH_ALLOC(memlen) ((memlen) - CHUNK_HEADER_LEN)

CHUNK_HEADER_LEN is usually around 30 bytes or so.

The problem with preferred_chunk_size is that for a large size_t target, the function will return 0.

If you compile this program with -m32:

#include <stdio.h>
#include <stdint.h>
#define FLEXIBLE_ARRAY_MEMBER /**/
#define DEBUG_CHUNK_ALLOC
/** A single chunk on a buffer. */
typedef struct chunk_t {
  struct chunk_t *next; /**< The next chunk on the buffer. */
  size_t datalen; /**< The number of bytes stored in this chunk */
  size_t memlen; /**< The number of usable bytes of storage in <b>mem</b>. */
#ifdef DEBUG_CHUNK_ALLOC
  size_t DBG_alloc;
#endif
  char *data; /**< A pointer to the first byte of data stored in <b>mem</b>. */
  uint32_t inserted_time; /**< Timestamp in truncated ms since epoch
                           * when this chunk was inserted. */
  char mem[FLEXIBLE_ARRAY_MEMBER]; /**< The actual memory used for storage in
                * this chunk. */
} chunk_t;
#if defined(__GNUC__) && __GNUC__ > 3
#define STRUCT_OFFSET(tp, member) __builtin_offsetof(tp, member)
#else
 #define STRUCT_OFFSET(tp, member) \
   ((off_t) (((char*)&((tp*)0)->member)-(char*)0))
#endif
#define MIN_CHUNK_ALLOC 256
#define CHUNK_HEADER_LEN STRUCT_OFFSET(chunk_t, mem[0])
#define CHUNK_SIZE_WITH_ALLOC(memlen) ((memlen) - CHUNK_HEADER_LEN)
static inline size_t
preferred_chunk_size(size_t target)
{
  size_t sz = MIN_CHUNK_ALLOC;
  while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
    sz <<= 1;
  }
  return sz;
}

int main(void)
{
    size_t i = 1024;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    printf("i is %08X, preferred_chunk_size is %08X\n", i, preferred_chunk_size(i)); i <<= 1;
    return 0;
}

the output is:

i is 00000400, preferred_chunk_size is 00000800
i is 00000800, preferred_chunk_size is 00001000
i is 00001000, preferred_chunk_size is 00002000
i is 00002000, preferred_chunk_size is 00004000
i is 00004000, preferred_chunk_size is 00008000
i is 00008000, preferred_chunk_size is 00010000
i is 00010000, preferred_chunk_size is 00020000
i is 00020000, preferred_chunk_size is 00040000
i is 00040000, preferred_chunk_size is 00080000
i is 00080000, preferred_chunk_size is 00100000
i is 00100000, preferred_chunk_size is 00200000
i is 00200000, preferred_chunk_size is 00400000
i is 00400000, preferred_chunk_size is 00800000
i is 00800000, preferred_chunk_size is 01000000
i is 01000000, preferred_chunk_size is 02000000
i is 02000000, preferred_chunk_size is 04000000
i is 04000000, preferred_chunk_size is 08000000
i is 08000000, preferred_chunk_size is 10000000
i is 10000000, preferred_chunk_size is 20000000
i is 20000000, preferred_chunk_size is 40000000
i is 40000000, preferred_chunk_size is 80000000
i is 80000000, preferred_chunk_size is 00000000

The danger is that the return value of preferred_chunk_size is always used as a parameter to tor_malloc or tor_realloc. It is called at these places:

In buf_pullup:

 210     newsize = CHUNK_SIZE_WITH_ALLOC(preferred_chunk_size(capacity));
 211     newhead = chunk_grow(buf->head, newsize);

In buf_new_with_capacity:

 283 /** Create and return a new buf with default chunk capacity <b>size</b>.
 284  */
 285 buf_t *
 286 buf_new_with_capacity(size_t size)
 287 {
 288   buf_t *b = buf_new();
 289   b->default_chunk_size = preferred_chunk_size(size);
 290   return b;
 291 }

In buf_add_chunk_with_capacity:

 401 /** Append a new chunk with enough capacity to hold <b>capacity</b> bytes to
 402  * the tail of <b>buf</b>.  If <b>capped</b>, don't allocate a chunk bigger
 403  * than MAX_CHUNK_ALLOC. */
 404 static chunk_t *
 405 buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
 406 {
 407   chunk_t *chunk;
 408 
 409   if (CHUNK_ALLOC_SIZE(capacity) < buf->default_chunk_size) {
 410     chunk = chunk_new_with_alloc_size(buf->default_chunk_size);
 411   } else if (capped && CHUNK_ALLOC_SIZE(capacity) > MAX_CHUNK_ALLOC) {
 412     chunk = chunk_new_with_alloc_size(MAX_CHUNK_ALLOC);
 413   } else {
 414     chunk = chunk_new_with_alloc_size(preferred_chunk_size(capacity));
 415   }

buf_new_with_capacity is currently called nowhere except for tests.
buf_add_chunk_with_capacity is called at various places but currently not with the apped parameter set to 0.

However, buf_pullup is called at various places and the call to preferred_chunk_size is reachable. Whether it is reachable with a parameter large enough that it will return 0 I'm not sure about.

int
tor_main(int argc, char *argv[])
{
    buf_t* buf;
    char* string;
    size_t string_len;
    size_t i;

    buf = buf_new();
    string_len = 0x00001000;
    string = tor_malloc(string_len);
    for (i = 0; i < 507904; i++)
    {
        write_to_buf(string, string_len, buf);
    }
    write_to_buf(string, 0x3FFFFFA, buf);
    free(string);
    buf_pullup(buf, 0x90000000); 
}

What will happen is that buf_pullup will call hunk_grow

 140 static inline chunk_t *
 141 chunk_grow(chunk_t *chunk, size_t sz)
 142 {
 143   off_t offset;
 144   size_t memlen_orig = chunk->memlen;
 145   tor_assert(sz > chunk->memlen);
 146   offset = chunk->data - chunk->mem;
 147   chunk = tor_realloc(chunk, CHUNK_ALLOC_SIZE(sz));
 148   chunk->memlen = sz;
 149   chunk->data = chunk->mem + offset;

tor_realloc will in effect be called with a size parameter of 0. Whether and how much legitimate heap memory realloc will allocate might be implementation-dependent. The point is that the
following lines might overwrite heap memory:

 148   chunk->memlen = sz;
 149   chunk->data = chunk->mem + offset;

since hunk is a memory area that has just been allocated to 0 (or 1, after correction) bytes.

The whole scenario is not very likely considering Tor's frugal memory consumption but it is nonetheless a programming fault in the buffers "API" that could lead to stability issues. Especially if you ever
expand the use of buf_pullup, buf_new_with_capacity, and/or uncapped buf_add_chunk_with_capacity, it'll be wise to hard-limit the amounts of right-shifts in preferred_chunk_size (a
single unintended negative integer -> size_t can be conducive in establishing an exploitation path).

Child Tickets

Change History (14)

comment:1 Changed 3 years ago by nickm

Milestone: Tor: 0.2.???Tor: 0.2.9.x-final

Thanks for the writeup. Putting into 0.2.9 because best not let this stuff sit.

comment:2 Changed 3 years ago by asn

Status: newneeds_review

Suggested patch by Guido accompannied by rationale:


diff --git a/d.c b/d.c
index 045a678..1a50261 100644
--- a/d.c
+++ b/d.c
@@ -29,8 +29,11 @@ static inline size_t
 preferred_chunk_size(size_t target)
 {
   size_t sz = MIN_CHUNK_ALLOC;
+  size_t prev = 0;
   while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
     sz <<= 1;
+    tor_assert(sz > prev);
+    prev = sz;
   }
   return sz;
 }

"It's agnostic as to whether the system is 32 or 64 bit, deals with the core problem (preventing the actual overflow), and lets other functions (such as tor_malloc) deal with outrageous allocatiion
sizes if applicable. If you want proper error handling instead of a hard abort through tor_assert() then more changes are necessarily, but I'd say that since Tor's general memory consumption is at
present relatively frugal, attempts to allocate 2+ GB's of memory are an indication that something is already amiss so an abort is the way to go."

comment:3 Changed 3 years ago by nickm

I don't love the use of tor_assert here; if we're going to assert, let's assert something about target as we enter the function.

comment:4 Changed 3 years ago by nickm

Like, how about this:

diff --git a/src/or/buffers.c b/src/or/buffers.c
index 31985723929a11..631c3b863a1b87 100644
--- a/src/or/buffers.c
+++ b/src/or/buffers.c
@@ -169,6 +169,9 @@ chunk_grow(chunk_t *chunk, size_t sz)
 static inline size_t
 preferred_chunk_size(size_t target)
 {
+  tor_assert(target <= SIZE_T_CEILING - CHUNK_HEADER_LEN);
+  if (target > MAX_CHUNK_ALLOC)
+    return target;
   size_t sz = MIN_CHUNK_ALLOC;
   while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
     sz <<= 1;

comment:5 Changed 3 years ago by nickm

Keywords: review-group-9 added

comment:6 Changed 3 years ago by teor

I am happier with the second patch, but somewhat counter-intuitively, it limits the returned sz to MAX_CHUNK_ALLOC << 1, not MAX_CHUNK_ALLOC.

preferred_chunk_size(MAX_CHUNK_ALLOC):

  • passes both initial checks, and
  • passes while (CHUNK_SIZE_WITH_ALLOC(sz) < target) even when sz is MAX_CHUNK_ALLOC, because CHUNK_SIZE_WITH_ALLOC(sz) subtracts the chunk header offset.

preferred_chunk_size(CHUNK_SIZE_WITH_ALLOC(MAX_CHUNK_ALLOC)):

  • actually produces a result of MAX_CHUNK_ALLOC, and is the highest value that does so.

If we want to keep this behaviour, we should document it, but I'd prefer we fix it so that MAX_CHUNK_ALLOC really is the maximum allocated chunk size (or, perhaps, to avoid changing behaviour, make MAX_CHUNK_ALLOC equal to 65536 << 1?). But either way, this is not a security issue.

The first patch is not ideal: it would let the overflow happen, then abort, which is not undefined behaviour for unsigned types, but it's not best practice. (And it might cause various static analysis tools to complain, and also likely crash on -fsanitize=unsigned-integer, which is somewhat immaterial given we crash straight after anyway...)

comment:7 Changed 3 years ago by teor

Status: needs_reviewneeds_revision

comment:8 Changed 3 years ago by nickm

Status: needs_revisionneeds_review

I've updated it, per your comments. Now it's a branch, with unit tests. How do you like bug20081 in my public repository?

comment:9 Changed 3 years ago by nickm

Owner: set to nickm
Status: needs_reviewaccepted

comment:10 Changed 3 years ago by nickm

Status: acceptedneeds_review

comment:11 Changed 3 years ago by nickm

Keywords: 029-proposed removed

That which is already in 0.2.9 cannot be 029-proposed.

comment:12 Changed 3 years ago by teor

Status: needs_reviewmerge_ready

Looks great!
Tests work for me, and I'm happy that MAX is a true maximum.

comment:13 Changed 3 years ago by nickm

Merged. Thanks to teor for the review and to guido for the report and to asn for the hackerone wrangling!

comment:14 Changed 3 years ago by nickm

Actual Points: .1
Resolution: fixed
Status: merge_readyclosed
Note: See TracTickets for help on using tickets.