> On 28 May 2015, at 17:24, Dirk-Willem van Gulik <[email protected]> wrote:
>
>
>> On 28 May 2015, at 17:03, William A Rowe Jr <[email protected]
>> <mailto:[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.
Updated the above gist with your idea (also shown below).
Dw.
/* Quick mickey mouse version to compare the strings. XXX fixme.
*/
typedef enum ap_compareflag_t {
AP_HOSTILE_STR1 = 1, // if a string is ‘hostile’ - we’re fine to abort
on it early.
AP_HOSTILE_STR2 = 2, // otherwise we hide its length by checking it for
the length of the other (or both).
AP_MIN1024 = 4 // pretend that they are at least 1024 chars in
size.
} ap_compareflag_t;
AP_DECLARE(int) ap_timingsafe_strcmp(const char * str1, const char * str2,
ap_compareflag_t flags) {
const unsigned char *p1 = (const unsigned char *)str1;
const unsigned char *p2 = (const unsigned char *)str2;
size_t i = 0, i1 = 1 ,i2 = 1;
unsigned int res = 0;
unsigned int d1, d2;
if (flags == 0)
flags = AP_HOSTILE_STR1 | AP_HOSTILE_STR2 | AP_MIN1024;
// printf("\n%s=%s\n\t",str1,str2);
do {
do {
res |= or_bits(p1[i % i1] - p2[i % i2]);
d1 = -or_bits(p1[i1]);
d2 = -or_bits(p2[i2]);
i1 += d1;
i2 += d2;
i++;
// printf("%c", ((d1 & d2) ? '=' : (d1 ? '1' : (d2 ? '2' :
'.'))));
} while(i < (flags & AP_MIN1024) * 256);
} while (
((flags & AP_HOSTILE_STR1) && d1) |
((flags & AP_HOSTILE_STR2) && d2)
);
res |= (i1 - i2);
// printf(" = %d\n", res);
// include the length in the coparision; as to avoid foo v.s. foofoofoo
to match.
//
return (int) res;
}
