> On 28 May 2015, at 17:03, William A Rowe Jr <wr...@rowe-clan.net> wrote: > > > On May 26, 2015 10:31 AM, "Dirk-Willem van Gulik" <di...@webweaving.org > <mailto:di...@webweaving.org>> 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. > > > > 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)); > > } > > Giving this some thought for the string version, does it make sense to loop > the underflow string back to offset zero on EOS? There is a certain amount > of cache avoidance that could cause, but it would dodge the optimization of > that phase and ensure the longest-match comparisons are performed (measured > by the untrusted input, presumably). > So I am currently experimenting with
https://gist.github.com/dirkx/37c29dc5a82b6deb0bf0 <https://gist.github.com/dirkx/37c29dc5a82b6deb0bf0> which seems to behave reasonably and does not get optimized out too far. We could perhaps do something where we change the i1/i2 loop indexes by str[i % i1] instead of i1/i2 that ‘stop’; and keep i1 one higher than i until we hit the \0. Dw