httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Yann Ylavic <ylavic....@gmail.com>
Subject Re: Good at assembler ? (Was:httpd - side channel attack - timing of digest comparisons)
Date Mon, 01 Jun 2015 21:39:30 GMT
On Fri, May 29, 2015 at 12:11 PM, Dirk-Willem van Gulik
<dirkx@webweaving.org> wrote:
>
> So if you have the time & can read assembler well - can you compile this at
> a reasonable optimizer setting and look at the assembler to confirm that key
> elements are not somehow optimized away; i.e. the innner loop is running in
> constant time. I am fairly sure about what happens on ARM and x386 — but
> modern x86 is largely voodoo to me.

Does the !! pattern really avoid conditional branches on any compiler?
It does compile to "test %src,%src; setne %dst" on all the gcc I
tested (4.4 => 4.8), but I'm not sure older ones (or other
compilers/archs) would not use a conditional jump instead.

Maybe we could use libressl's pattern instead, something like:

int ap_timingsafe_strcmp_mod(const char * hostile, const char * toProtect)
{
    const unsigned char *p1 = (const unsigned char *)hostile;
    const unsigned char *p2 = (const unsigned char *)toProtect;

    int res = 0, done = 0;
    size_t i = 0, i1 = 1, i2 = 1;
    int d1 = 1, d2 = 1;
    do {
        /* lt is -1 if p1[i] < p2[i]; else 0. */
        int lt = (p1[i % i1] - p2[i % i2]) >> 8;

        /* gt is -1 if p1[i] > p2[i]; else 0. */
        int gt = (p2[i % i2] - p1[i % i1]) >> 8;

        /* cmp is 1 if p1[i] > p2[i]; -1 if p1[i] < p2[i]; else 0. */
        int cmp = lt - gt;

        /* set res = cmp if !done. */
        res |= cmp & ~done;

        /* set done if p1[i] != p2[i]. */
        done |= lt | gt;

        d1 &= ~((p1[i % i1] - 1) >> 8);
        d2 &= ~((p2[i % i2] - 1) >> 8);

        i++;
        i1 += d1;
        i2 += d2;
    } while (d1); // we reveal the length of the hostile string.

    return res;
}

(note that the difference in lengths is handled by comparing the
shortest string's NUL with the char at the same position in the other
string, and that the choosen types avoid casting issues) .

>
> Secondly - when we get to the end of the shorter string; we can either keep
> comparing to the last char or \0; or we go ‘modulo’ to the start of the
> string. Now modulo is perhaps not ideal; and seems to affect the pipeline on
> the XEON cpu (something I confess not to quite understand; and I cannot
> see/replicate on ARM).

Either way, we may leak timing differences because if the protected
string would have been longer, we possibly would have loaded a new
page and/or not reused cached data, and that's probably measurable.

IMHO we can't really have a satisfactory timing safe strcmp, and we
should use a different strategy to protect NUL terminated strings.
For example, we could always allocate a fixed (maximum) size for these
strings (eg. 256 bytes for a password), and compare the hostile
strings up to the minimum of this size and strlen(hostile), using
timing safe memcmp().

Mime
View raw message