> On 28 May 2015, at 17:03, William A Rowe Jr <[email protected]> wrote:
>
>
> On May 26, 2015 10:31 AM, "Dirk-Willem van Gulik" <[email protected]
> <mailto:[email protected]>> wrote:
> >
> >
> > > On 26 May 2015, at 17:22, Dirk-Willem van Gulik <[email protected]
> > > <mailto:[email protected]>> 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
