Date: Mon, 22 Jan 2007 05:14:49 +0100
From: "Michele Cicciotti" <mc@...msa.net>
To: <full-disclosure@...ts.grok.org.uk>
Subject: Re: Major gcc 4.1.1 and up security issue

> I guess something like this, but with substraction instead of division
> can be implemented for checking for overflows on addition?

Personally I was very surprised that most people thought of "a + 100 > a" first. I never used that, however tempting it could be, because it felt like cheating. For e.g. additions I always followed this line of thought:

   (a + b <= MAX) => but a + b could overflow...
=> (a <= MAX - b) => but if MAX < INT_MAX, MAX - b could underflow...
=> (b <= MAX && a <= MAX - b) and let the compiler optimize out the case in which MAX == INT_MAX

> Are there other, possibly more terse ways to do this check? Maybe
> something like a "best practice" to do this kind of thing?

In Windows the best practice is to use the routines defined in <intsafe.h> (part of PSDK). Said routines sidestep the issue completely by only operating on unsigned values. Conversion routines are provided to extract signed values. Examples:

//
// UINT addition
//
__inline
HRESULT
UIntAdd(
    __in UINT uAugend,
    __in UINT uAddend,
    __out __deref_out_range(==,uAugend + uAddend) UINT* puResult)
{
    HRESULT hr;

    if ((uAugend + uAddend) >= uAugend)
    {
        *puResult = (uAugend + uAddend);
        hr = S_OK;
    }
    else
    {
        *puResult = UINT_ERROR;
        hr = INTSAFE_E_ARITHMETIC_OVERFLOW;
    }
    
    return hr;
}

__inline
HRESULT
UIntToInt(
    __in UINT uOperand,
    __out __deref_out_range(==,uOperand) INT* piResult)
{
    HRESULT hr;

    if (uOperand <= INT_MAX)
    {
        *piResult = (INT)uOperand;
        hr = S_OK;
    }
    else
    {
        *piResult = INT_ERROR;
        hr = INTSAFE_E_ARITHMETIC_OVERFLOW;
    }

    return hr;
}

Note how the sum itself is used in the overflow check for the addition. Multiplication is performed in double precision and the result is converted back, I suppose to avoid divisions (divisions are teh eeevil). Examples:

__inline
HRESULT
UShortMult(
    __in USHORT usMultiplicand,
    __in USHORT usMultiplier,
    __out USHORT* pusResult)
{
    ULONG ulResult = ((ULONG)usMultiplicand) * ((ULONG)usMultiplier);
    
    return ULongToUShort(ulResult, pusResult);
}

__inline
HRESULT
UIntMult(
    __in UINT uMultiplicand,
    __in UINT uMultiplier,
    __out UINT* puResult)
{
    ULONGLONG ull64Result = UInt32x32To64(uMultiplicand, uMultiplier);

    return ULongLongToUInt(ull64Result, puResult);
}

Oh yes, 64 x 64 is implemented in this way as well. x64 has 64x64->128 opcode, so the code is not dissimilar to the generic cases seen above, for other architectures an ugly piece of inline code is used, which I won't paste, but here's its rationale:

    // 64x64 into 128 is like 32.32 x 32.32.
    //
    // a.b * c.d = a*(c.d) + .b*(c.d) = a*c + a*.d + .b*c + .b*.d
    // back in non-decimal notation where A=a*2^32 and C=c*2^32:  
    // A*C + A*d + b*C + b*d
    // So there are four components to add together.
    //   result = (a*c*2^64) + (a*d*2^32) + (b*c*2^32) + (b*d)
    //
    // a * c must be 0 or there would be bits in the high 64-bits
    // a * d must be less than 2^32 or there would be bits in the high 64-bits
    // b * c must be less than 2^32 or there would be bits in the high 64-bits
    // then there must be no overflow of the resulting values summed up.

> I also think that CPUs can detect internally when an overflow happens -
> is there a way to use that feature in C somehow, in a portable way?
> (Somehow I feel that the answer is that not all CPUs do that, so - no.)

x86 has the INTO opcode for this. It performs an INT 4 if the overflow flag is set. I don't know about other architectures, but I'd guess it's not terribly portable nor terribly lightweight if Microsoft didn't do that in intsafe.h

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/

Powered by blists - more mailing lists