On May 26, 2015 10:31 AM, "Dirk-Willem van Gulik" <di...@webweaving.org>
wrote:
>
>
> > 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));
> }
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).
