Re: httpd - side channel attack - timing of digest comparisons

[Dirk-Willem van Gulik]

> On 26 May 2015, at 17:22, Dirk-Willem van Gulik <di...@webweaving.org> wrote:
..
> So I think that what is needed are two (or three) functions
...
> -     A string comparison function; where at least one string is is under 
> control of the attacker.

Now the issue here is that length is every easily revealed. So I can think of 2 
strategies;

-       firmly declare (in the signature of the compare function) one argument 
as potentially hostile.

        And do the comparison largely based on that; which means we only 
marginally reveal the
        actual length of the string compared to. Below is an example; but my 
gut feel it is not
        nearly good enough when you can apply a large chunk of statistics 
against it.

-       treat them both as hostile; and scan for either the shortest or longest 
one and accept
        that you leak something about length.

        Or - if needed - pad this out for strings <1024 (or similar) chars in 
length by doing always
        that many (which will leak less).

Examples are below. Suggestions appreciated. 

Dw.

static int or_bits(int  x) {
  x |= (x >> 4);
  x |= (x >> 2);
  x |= (x >> 1);
  return -(x & 1);
}

/* Quick mickey mouse version to compare the strings. XXX fixme. 
 */
AP_DECLARE(int) ap_timingsafe_strcmp(const char * hostile_string, const char * 
to_protect__string) {
        const unsigned char *p1 = (const unsigned char *)hostile_string;
        const unsigned char *p2 = (const unsigned char *)to_protect__string;
        size_t i = 0, i1 = 0 ,i2 = 0;
        unsigned int res = 0;
        unsigned int d1, d2;

        do {
                res |= or_bits(p1[i1] - p2[i2]);

                d1 = -or_bits(p1[i1]);
                d2 = -or_bits(p2[i2]);

                i1 += d1;
                i2 += d2;
                i += (d1 | d2);

#icase A
        } while (d1 | d2); // longest one will abort
#case B
        } while (d1 & d2); // shortest one will abort
#case C
        } while (i < 1024) } while (d1 | d2); // at least 1024 or longest 
one/shortest one

        // include the length in the coparision; as to avoid foo v.s. foofoofoo 
to match.
        //
        return (int) (res | ( i1 - i2));
}