Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72175
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.128.176 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <CAF+90c-32u=vVy4L4pB_OWGu2VmeUckxq8UW_AVJNC8iDtiWMQ@mail.gmail.com>
References: <9E3AA302-1EC1-4497-996F-716555CAAB64@rouvenwessling.de>
	<CAF+90c-32u=vVy4L4pB_OWGu2VmeUckxq8UW_AVJNC8iDtiWMQ@mail.gmail.com>
Date: Tue, 4 Feb 2014 14:20:37 +0800
Message-ID: <CAHMUw2FM78xLxYt3YmZVE4G9jbuJbc+J-A4T21amhbuCbnLYWg@mail.gmail.com>
To: Nikita Popov <nikita.ppv@gmail.com>
Cc: =?ISO-8859-1?Q?Rouven_We=DFling?= <me@rouvenwessling.de>, 
	PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=bcaec548a15b7f0f7404f18ea3b6
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: tjerk.meesters@gmail.com (Tjerk Meesters)

--bcaec548a15b7f0f7404f18ea3b6
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On Tue, Feb 4, 2014 at 1:10 AM, Nikita Popov <nikita.ppv@gmail.com> wrote:

> On Sun, Feb 2, 2014 at 11:50 PM, Rouven We=DFling <me@rouvenwessling.de
> >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 t=
he
> if and else branches will have different instruction counts in that case.
> Simple alternative would be something fixed like mod_len =3D 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 thi=
s
> 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
>



--=20
--
Tjerk

--bcaec548a15b7f0f7404f18ea3b6--