On Tue, Feb 4, 2014 at 1:10 AM, Nikita Popov <[email protected]> wrote:
> On Sun, Feb 2, 2014 at 11:50 PM, Rouven Weßling <[email protected]
> >wrote:
>
> > Hi internals,
> >
> > as I've received no further feedback I've opened the voting on "Timing
> > attack safe string comparison function":
> >
> > - https://wiki.php.net/rfc/timing_attack
> >
> > Voting ends on 2014/02/09 11:00PM UTC
> >
> > Best regards
> > Rouven
> >
>
> Did your code already get reviewed by someone with understanding of the
> issue? From a quick glance, two potential issues:
> * You are using MAX, i.e. an if-then-else branch. I'm pretty sure that the
> if and else branches will have different instruction counts in that case.
> Simple alternative would be something fixed like mod_len = known_len+1 or
> known_len&1.
>
I can't speak for other compilers, but gcc compiles the ternary to this:
cmpl $0, -8(%rbp)
cmovg -8(%rbp), %eax
So it comes down to whether cmovg takes a variable amount of time; that
said, the move operation is only required if the known length is zero, i.e.
you're comparing user input against an empty string which is quite unlikely..
> * You leak information on mod_len / known_len, because you will have
> different cache access patterns for comparing always the same 10 memory
> positions and 10000 different ones, at least I'd assume so.
>
There's one particular scenario that comes to mind: if the string data
spans at least two memory pages; assuming memory allocation is optimized to
fit allocated memory inside one page whenever possible, we're talking about
string lengths bigger than the page itself, i.e. 4kB / 8kB.
Given that the known string is relatively small, the leaked information may
reveal that the given string is bigger than the known string.
The above is my own logical deduction, I'm not an expert in this area :)
I don't know how you can prevent the latter issue, and if it is possible at
> all. Personally I'd just drop the length magic and explicitly document it
> to be safe for equal-length strings only. In any case you should have this
> reviewed by someone with more than just a cursory understanding of the
> matter.
>
Given the name hash_compare() it makes a good case to add a bail-out
branch based on string length, in which case you don't have to remember
which argument should come first ... still, it may be nice to have a
generic comparison function :)
> Nikita
>
--
--
Tjerk