Multiplication Considered Harmful

Today we’ll be talking about the dangers of multiplication integer
overflows in C, the type of bug responsible for the
OpenSSH hole of 2002.

Integer overflows occur when an operation causes a number to
grow or shrink out of bounds,
resulting in a much smaller or much larger number than expected.
For example, a char can only hold 256 values.
If two chars are multiplied together,
there is a possibility of overflow:

    char a, b;
    a = b = 127;
    a = a * b;  /* overflow */

Because arithmetic is done in code all over the place,
adding checks can be very tedious and is often ignored.
A common idiom to allocate memory is:

    size_t num, size;
    char *ptr;
    …
    if ((ptr = malloc(num * size)) == NULL) /* overflow */
        return (NULL);

The multiplication can create a number larger than a size_t can hold,
causing an integer overflow.
The integer overflow in this case causes less memory to be allocated
than the program expects.
The program could then take user input and write past the actual small
allocation into memory it thinks it owns,
causing problems like a generic buffer overflow.
This was the idiom used in the OpenSSH hole of 2002,
demonstrating the severity of these bugs.

We recommend using calloc(3) whenever allocating multiple objects
of the same size.
The above code would be written as:

    size_t num, size;
    char *ptr;
    …
    if ((ptr = calloc(num, size)) == NULL)
        return (NULL);

calloc(3) has checks to make sure the multiplication does not overflow.

Unfortunately there is no safe replacement for realloc(3).
To prevent multiplication overflow, a check must be added:

    size_t newsize, num, size;
    char *newptr, *ptr;
    …
    if (num && size && SIZE_MAX / num < size) {
        errno = ENOMEM;
        return (NULL);
    }
    newsize = num * size;
    if ((newptr = realloc(ptr, newsize)) == NULL)
        return (NULL);
    ptr = newptr;

This is a hassle, but it is important to add these safeguards,
especially when doing multiplication, which can quickly overflow.

To lessen developer work and simplify code,
an xrealloc() function was added to ssh.
xrealloc() has a similar API to calloc(3),
taking both a num parameter and a size parameter.
The above example can be written using xrealloc() as:

    size_t num, size;
    char *newptr, *ptr;
    …
    if ((newptr = xrealloc(ptr, num, size)) == NULL)
        return (NULL);
    ptr = newptr;

Due to its elegance, this API was also imported for OpenCVS.

For more information, please read a -current malloc(3) man page,
which was recently updated with better usage examples.