Good at assembler ? (Was:httpd - side channel attack - timing of digest comparisons)

[Dirk-Willem van Gulik]

>>> On 28 May 2015, at 17:03, William A Rowe Jr <wr...@rowe-clan.net 
>>> <mailto:wr...@rowe-clan.net>> wrote:
….
>>> > > On 26 May 2015, at 17:22, Dirk-Willem van Gulik <di...@webweaving.org 
>>> > > <mailto: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.
>>> 
Thanks for all the feedback. With a bit of help from Martijn Boekhorst and Andy 
Armstrong I got as far as:

        https://gist.github.com/dirkx/37c29dc5a82b6deb0bf0 
<https://gist.github.com/dirkx/37c29dc5a82b6deb0bf0>

which I am now testing against a wide range of settings & compilers (in essence 
running a side channel attack on it and see how far I get with the various 
variations).

However I could use some help & manual inspection ?

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.

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).

So I would also love to have feedback on the two strategies in the code w.r.t. 
to that - and not getting hit by pipeline length; L3 caches or odd things like 
page boundaries.

Above GIST has the full code - the simpliefied version below (which does not 
have the 1024 min length).

Dw.



// MODULO version

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

        size_t i1 = 1 ,i2 = 1;
        unsigned int d1 = 1, d2 = 1, res = 0;
        do {
                res |= (p1[i % i1] - p2[i % i2]);
 
                d1 &= !!p1[i % i1];
                d2 &= !!p2[i % i2];

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

        res |= (i1 - i2);
 
        return (int) res;
}
 

// Cycle at last char version

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

        size_t i1 = 0 ,i2 = 0;
        unsigned int d1 = 1, d2 = 1, res = 0;
 
        do {
                res |= (p1[i1] - p2[i2]);

                d1 &= !!p1[i1];
                d2 &= !!p2[i2];

                i1 += d1;
                i2 += d2;
                i++;
        } while (d1); // we reveal the length of the hostile string. Use 
(d1|d2) and a min run-length to hide both.

        res |= (i1 - i2);
 
        return (int) res;
}