Various Integer Overflows in dlmalloc

[Richard Weinberger <richard@sigma-star.at>]

Hi!

While inspecting various security aspects of U-Boot I noticed some
issues around dlmalloc and asking for your feedback, especially for the
first issue.
I'm CC'ing Barebox folks since Barebox seems to be based on the same
dlmalloc-implementation as U-Boot does.

1. Integer Overflow While Computing Allocation Size

malloc/realloc/memalign take an arbitrary request size and apply
padding.

First, the length is (imperfectly) checked and the the conversion happens:

  if ((long)bytes < 0) return NULL;

  nb = request2size(bytes);  /* padded request size; */

The problem is that the request2size() macro is casting the requested
size to an signed long and adds SIZE_SZ + MALLOC_ALIGN_MASK:

#define request2size(req) \
 (((long)((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) < \
  (long)(MINSIZE + MALLOC_ALIGN_MASK)) ? MINSIZE : \
   (((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK)))

So, any allocation request between LONG_MAX - (SIZE_SZ + MALLOC_ALIGN_MASK) - 1 and LONG_MAX
will cause an overflow and as a consequence the caller will get
less memory than requested.

e.g. on an 32bits system malloc(2147483647) will succeed but allocates
only 16 bytes (MINSIZE). I've tested this with U-Boot on i386 and ARM.

This is a beefy vulnerability for exploit writers since unbound allocations
do happen. Like in the ext4 and squashfs symlink code, I'm sure there are more.
If you don't care about verified boot, it's less of an issue, though.

I'm not so sure what the best fix is.
Mostly because I'm not sure why request2size() is anyway casting to long.
The original dlmalloc.c implementation doesn't do so. It has also a more
sophisticated overflow check, which is also missing in both U-Boot and Barebox.
See https://research.cs.wisc.edu/sonar/projects/mnemosyne/resources/doc/html/malloc-original_2src_2dlmalloc_8c-source.html
Lines 01938 to 01962.

I tracked down the bug to ppcboot, it's there since day 0.
So I don't know what's the intention behind casting.

On the other hand, since over commit is not supported, we could also just fail
if the requested size is larger then the total amount of system memory.
I'm a little in fear that more overflows are lurking in the code.

2. Integer overflow in sbrk() (U-Boot only)

sbrk() does:
        ulong new = old + increment;

        /*
         * if we are giving memory back make sure we clear it out since
         * we set MORECORE_CLEARS to 1
         */
        if (increment < 0)
                memset((void *)new, 0, -increment);

        if ((new < mem_malloc_start) || (new > mem_malloc_end))
                return (void *)MORECORE_FAILURE;


If old + increment overflows (increment is a ptrdiff_t) then
sbrk() wrongly thinks we're shrinking the heap and memsets an invalid
range.

I propose as solution, applying memset() after the range check.

3. Wrong ptrdiff_t type (U-Boot only)

U-Boot defines __kernel_ptrdiff_t to int for both i386 and x86_64.
As a consequence, large allocations on x86_64 will overflow the increment
parameter of sbrk() and less than requested is allocated.
I suggest defining __kernel_ptrdiff_t on x86_64 to long.

Thanks,
//richard
-- 
​​​​​sigma star gmbh | Eduard-Bodem-Gasse 6, 6020 Innsbruck, AUT
UID/VAT Nr: ATU 66964118 | FN: 374287y