Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72306
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain rouvenwessling.de designates 5.35.242.46 as permitted sender)
Content-Type: text/plain; charset=iso-8859-1
Mime-Version: 1.0 (Mac OS X Mail 7.0 \(1822\))
In-Reply-To: <CAGa2bXYab=2DeJu+ESWP_9Vte2FY37L2+kJFnuN4JwUj9Num1w@mail.gmail.com>
Date: Thu, 6 Feb 2014 00:36:44 +0100
Cc: Stas Malyshev <smalyshev@sugarcrm.com>,
 Nikita Popov <nikita.ppv@gmail.com>,
 PHP internals <internals@lists.php.net>
Content-Transfer-Encoding: quoted-printable
Message-ID: <AC16ADC6-801E-4D0D-9FD4-0BEE2D017E16@rouvenwessling.de>
References: <9E3AA302-1EC1-4497-996F-716555CAAB64@rouvenwessling.de> <CAF+90c-32u=vVy4L4pB_OWGu2VmeUckxq8UW_AVJNC8iDtiWMQ@mail.gmail.com> <52F0139C.2060102@sugarcrm.com> <CAGa2bXZhT_8-BEjLuA4EPkZmxtpO1onz7AGTjCE-w85XC5pwdQ@mail.gmail.com> <CAGa2bXYab=2DeJu+ESWP_9Vte2FY37L2+kJFnuN4JwUj9Num1w@mail.gmail.com>
To: Yasuo Ohgaki <yohgaki@ohgaki.net>
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: me@rouvenwessling.de (=?iso-8859-1?Q?Rouven_We=DFling?=)

Hi everyone,

sorry for not getting back earlier, real life taking it's toll. I'll try =
to answer things in just a couple of E-Mail to not cause too much =
traffic (there seems to be a lot lately!)

On 03.02.2014, at 13:23, Andrea Faulds <ajf@ajf.me> wrote:

> On 02/02/14 22:50, Rouven We=DFling wrote:
>> as I've received no further feedback I've opened the voting on =
"Timing attack safe string comparison function":
>=20
> I've voted yes. However, at the risk of opening more bikeshedding =
again, I should say that I don't think hash_compare is an appropriate =
name. It's a timing attack-safe string comparison function, so I think =
something like str_equals_time_constant might be better as it is not so =
much a hash comparison function as a string comparison function.

I'd rather not discuss this anymore. The discussion was open since =
mid-december. By my reading, there was no universally agreed name. Since =
it was suggested this goes into ext/hash starting with hash_ also seemed =
important to me.

On 03.02.2014, at 17:18, Sara Golemon <pollita@php.net> wrote:

> Voted yes, but IMO the comparison function should behave a little more
> like =3D=3D=3D.  That is: something like hash_compare(null,"") should =
return
> false.  Possibly be even more strict and require both input parameters
> to be string (e.g. hash_compare(123,123) would return false as well).
>=20
> But there's some "non-PHP"ish about that idea so I'm not horribly =
fussed by it.


That sounds like a good idea to me. I'd wager we can change this post =
RFC too? Or is the process more strict than I think it is?

I like the suggestion of an E_WARNING for that case too.

On 03.02.2014, at 18:10, Nikita Popov <nikita.ppv@gmail.com> wrote:

> Did your code already get reviewed by someone with understanding of =
the issue? =46rom a quick glance, two potential issues:

Anthony Ferra reviewed (and improved) my original patch, however it has =
been changed since. Notably the MAX change wasn't included originally.

>  * 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 =3D =
known_len+1 or known_len&1.

This problem should be limited by that fact, that except for the case =
where known_len =3D=3D 0, always the same branch is hit.

>  * 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.
> 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.


I agree leaking length may happen. I'm wondering if my first patch =
wasn't safer in this regard. If no better implementation can be found =
I'd suggest to just document, that length may leak. However to me that's =
acceptable as long as this doesn't allow approximating the known string =
by changing the input byte by byte.

On 04.02.2014, at 07:20, Tjerk Meesters <tjerk.meesters@gmail.com> =
wrote:

> 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 :)

While I like the idea, of foregoing this entire discussion I think it is =
a good idea to get something better than =3D=3D=3D out to people who =
compare mixed length strings.=20

On 05.02.2014, at 03:58, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:

> It could be optimized a little since 256 is too much for now.
> How about make MAX returns max of 3 values?
>=20
> len =3D MAX(known_len, user_len, 64);


What would this buy us? We still get branch on MAX and the memory access =
would still go the same memory if the string is shorter than 64 bytes.

Best regards
Rouven