[RFC] Timing attack safe string comparison function

Hi Rouven,

On Mon, Dec 23, 2013 at 2:08 AM, Rouven Weßling me@rouvenwessling.dewrote:

I'd like to propose this RFC to introduce a time-constant string
comparison function: https://wiki.php.net/rfc/timing_attack

I will not open the voting before January 7 to account for ho

As you mentioned in code, users should not use when known or user supplied
string
is null.

How about add E_NOTICE error for that case?
If user shouldn't then we are better to warn them.

Comparison is good since it always does the same operation based on user
supplied
string. (Unless compiler does optimizations that I don't expect)

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Hi,

On Mon, Dec 23, 2013 at 1:08 AM, Rouven Weßling me@rouvenwessling.dewrote:

Hi internals,

I'd like to propose this RFC to introduce a time-constant string
comparison function: https://wiki.php.net/rfc/timing_attack

On the whole it looks okay.

The special branch for known_len == 0 && user_len != 0 can be avoided by
doing something like this:

mod_len = max(known_len, 1);

And then use j % mod_len instead of j % known_len to avoid a division
by zero; since x mod 1 always yields 0 you will always be comparing
against the null byte of the known string.

I will not open the voting before January 7 to account for holidays.

Best regards
Rouven

--

Tjerk

Hi!

I'd like to propose this RFC to introduce a time-constant string
comparison function: https://wiki.php.net/rfc/timing_attack

I wonder how practical this would be. There are probably many side
channels in PHP related to how PHP manages memory, copies variables,
processes opcodes, etc. so I wonder if providing such function for PHP
API would practically add anything or if you should be doing crypto that
sensitive in PHP anyway?

--
Stanislav Malyshev, Software Architect
SugarCRM: http://www.sugarcrm.com/
(408)454-6900 ext. 227

On Mon, Dec 23, 2013 at 5:45 PM, Rouven Weßling me@rouvenwessling.dewrote:

Thanks everyone for your feedback, answers inline.

I note your patch uses C++-style (// foobar) comments. However,
according to the coding standards[0], only C-style (/* foobar */) comments
should be used.

Thanks for the hint, I changed the patch accordingly.

As you mentioned in code, users should not use when known or user
supplied string
is null.

How about add E_NOTICE error for that case?
If user shouldn't then we are better to warn them.

That's a fair point, but I expect people would in that case just do their
own check of strlen() === 0 and error out and nothing is gained. Maybe we
can find a way to not need the check at all. (see next response)

Comparison is good since it always does the same operation based on user
supplied
string. (Unless compiler does optimizations that I don't expect)

Thanks for checking that, the people do the better.

On the whole it looks okay.

The special branch for known_len == 0 && user_len != 0 can be avoided
by doing something like this:

mod_len = max(known_len, 1);

And then use j % mod_len instead of j % known_len to avoid a
division by zero; since x mod 1 always yields 0 you will always be
comparing against the null byte of the known string.

This looks like a good approach, but I was under the impression, that PHP
strings aren't guaranteed to have a terminating null byte. Am I mistaken?

Strings are binary safe, but they're still null terminated, as can be seen
from the definitions of ZVAL_STRING() and ZVAL_STRINGL().

http://lxr.php.net/xref/PHP_5_6/Zend/zend_API.h#576

  This does not appear to solve any problems, it appears to add

another function, for that function to solve any problems it must be
deployed.

  So the RFC relies on everyone swapping out every security

sensitive string comparison with the new function, which simply will not
happen.

It's true that adding this function won't magically make any application
safer. The whole point is making it easier for application developers -
especially those not using a huge framework - to use a string comparison
algorithm that - hopefully - many people have reviewed. Also if there's an
issue, this will be fixed by the regular PHP updates (or distributions
backports)

  I'm up for doing something about security, however, this doesn't

actually do that, what it does is add a (generically named) function that
nobody is very likely to deploy, and doesn't fix the vulnerability in
existing code ... which surely has to be the aim of anything targeted at
security - existing code.

  Obviously, we cannot really change all string comparisons to use

security sensitive logic, so this isn't something we can really solve
everywhere from the core, some action must be taken by the user ...

As you mention yourself, we obviously can't force every string comparison
to be time constant. This means there's no "magic bullet" and I think this
is the second best thing to do.

  It might have more traction if the function were named

password_compare or hash_compare or something similar that gives everyone
the idea that it is not simply a string comparison function but the correct
way to verify in particular passwords/hashes or whatever. I'd be much more
inclined to say that's a good idea, providing a full set of tools for
password related foo.

I don't care about the name at all (it's mentioned as an open issue in the
RFC), it's admittedly the second one that came to my mind (after
str_compare_time_constant which is way too long). hash_compare does sound
pretty good though.

Best regards
Rouven

--

Tjerk

Heya,

I was discussing about this RFC with Joe in Room 11 (where we keep him away
from society, for the greater good).

I was wondering why such an API must be implemented in PHP core (which
means C, which means that the usual 15~20 people can fix it if borked,
which is bad) and cannot be just left in userland as it already happens,
for example, with
https://github.com/zendframework/zf2/blob/master/library/Zend/Crypt/Utils.php#L17-L44and
similar libraries that have some decent security policies themselves
(nothing to say about PHP - you guys are doing great!).

Why do we need this in core?
Why can't a user copy-paste those rows (if it's a monkey-patcher) or just
use a library?

I don't trust PHP coders in general, so I'm pretty sure that the example
I've posted before @ https://gist.github.com/Ocramius/8094168 is quite
obscure to the 99.9% of PHP developers.

Who has been doing it wrong will continue going on and not caring.

Those who are aware of the dangers and do care are most probably already
using these kinds of checks vie an imported library.

So what is pushing towards yet another function in here?

Don't get me wrong: I am all for security, but I don't see a difference
between a php-core implementation and a userland implementation.

Cheers,

Marco Pivetta

http://twitter.com/Ocramius

http://ocramius.github.com/

Ok, good wanderings dear Macro ...

We already have it in core, here it is:

291 /* We're using this method instead of == in order to provide
292 * resistence towards timing attacks. This is a constant time
293 * equality check that will always check every byte of both
294 * values. */
295 for (i = 0; i < hash_len; i++) {
296 status |= (ret[i] ^ hash[i]);
297 }

So that puts in perspective the what if it borks argument, and the
complication argument too, since the new function and old can share a
static inline implementation of the same logic ... do you really want me
to explain why static inline c is better than PHP, or is that obvious at
this point ??

I would love it if at some point in the future you could point at bits
of PHP and say "that's a good implementation", right now the most you
can say is "here's some functions implemented to help in this area, and
here's all the code and knowledge of PHP you require to make good, sane
use of it".

Anyone who doesn't see that, is barking mad, barking, mad ...

Cheers
Joe

Hi Marco.

I was wondering why such an API must be implemented in PHP core (which means C, which means that the usual 15~20 people can fix it if borked, which is bad) and cannot be just left in userland as it already happens, for example, with https://github.com/zendframework/zf2/blob/master/library/Zend/Crypt/Utils.php#L17-L44 and similar libraries that have some decent security policies themselves (nothing to say about PHP - you guys are doing great!).

Why do we need this in core?
Why can't a user copy-paste those rows (if it's a monkey-patcher) or just use a library?

Obviously this doesn't have to be in core, but there are a number of advantages:

• Increased awareness
• Robuster implementation since it's in a lower level language (see Stas' E-Mail earlier)
• Wider security review

For example the linked Zend example has a small issue because it actually leaks length information. That's unimportant if one is comparing a hash (they usually have a constant length) but for other applications it might be an issue.

Also the simple fact that basically everyone (Joomla, Zend, Symfony2) ships some function for this, shows that there's a high demand for this functionality. Why not provide it out of the box?

Don't get me wrong: I am all for security, but I don't see a difference between a php-core implementation and a userland implementation.

The hope is, like with the password hashing function, that by making it easier to use best practices, coders will follow them.

291 /* We're using this method instead of == in order to provide
292 * resistence towards timing attacks. This is a constant time
293 * equality check that will always check every byte of both
294 * values. */
295 for (i = 0; i < hash_len; i++) {
296 status |= (ret[i] ^ hash[i]);
297 }

So that puts in perspective the what if it borks argument, and the
complication argument too, since the new function and old can share a
static inline implementation of the same logic ... do you really want me to
explain why static inline c is better than PHP, or is that obvious at this
point ??

The performance question is irrelevant to me - I don't think I'd ever code
a performance-sensitive API with this sort of function, but maybe someone
has a real world example for that. Slower is probably even better here :P

Let me re-state: "performance is not a problem here".

Indeed, this is not a function where performance is critical and it will likely be so rarely called even by its heaviest users that the difference of C vs PHP won't even make a dent in resource usage.

I've updated the patch with Tjerk's suggestion and renamed the function to hash_compare. I've also updated the RFC accordingly.

Best regards
Rouven