[RFC] Timing attack safe string comparison function

Andrew Faulds

12 years ago

On 22/12/13 17:08, Rouven Weßling wrote:

> Hi internals,
>
> 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 holidays.
>
> Best regards
> Rouven
>

Hi Rouven, this looks like a great proposal!

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

Unfortunately I can't comment otherwise on your patch as I'm not a
security expert.

[0] https://github.com/php/php-src/blob/master/CODING_STANDARDS

--
Andrea Faulds
http://ajf.me/

Rouven Weßling

12 years ago

Thanks everyone for your feedback, answers inline.

On 22.12.2013, at 18:25, Andrea Faulds <ajf@ajf.me> wrote:

> 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.

On 23.12.2013, at 00:55, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:

> 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 23.12.2013, at 02:26, Tjerk Meesters <tjerk.meesters@gmail.com> wrote:

> 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?

On 23.12.2013, at 10:09, Joe Watkins <pthreads@pthreads.org> wrote:

> 	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

Joe Watkins

12 years ago

On 12/23/2013 09:45 AM, Rouven Weßling wrote:

> Thanks everyone for your feedback, answers inline.
>
> On 22.12.2013, at 18:25, Andrea Faulds <ajf@ajf.me> wrote:
>
>> 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.
>
> On 23.12.2013, at 00:55, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
>
>> 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 23.12.2013, at 02:26, Tjerk Meesters <tjerk.meesters@gmail.com> wrote:
>
>> 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?
>
> On 23.12.2013, at 10:09, Joe Watkins <pthreads@pthreads.org> wrote:
>
>> 	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
>

Morning Rouven,

I was thinking out loud there, I'm glad you read it as you did ...
closing statement was my final conclusion, that it's worth while as a
complimentary tool in the hashing toolbox, and I'd prefer it's name to
reflect that ...

Cheers
Joe

Joe Watkins

12 years ago

On 12/23/2013 09:45 AM, Rouven Weßling wrote:

> Thanks everyone for your feedback, answers inline.
>
> On 22.12.2013, at 18:25, Andrea Faulds <ajf@ajf.me> wrote:
>
>> 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.
>
> On 23.12.2013, at 00:55, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
>
>> 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 23.12.2013, at 02:26, Tjerk Meesters <tjerk.meesters@gmail.com> wrote:
>
>> 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?
>
> On 23.12.2013, at 10:09, Joe Watkins <pthreads@pthreads.org> wrote:
>
>> 	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
>

Morning Rouven,

I'm glad you read it as you did, I was kinda thinking out loud, where I
ended was my final conclusion that it may be worth while as a
complimentary tool in the hashing toolbox, and I'd prefer its name to
reflect that.

Cheers
Joe

Yasuo Ohgaki

12 years ago

Hi all,

On Mon, Dec 23, 2013 at 7:03 PM, Joe Watkins <krakjoe@php.net> wrote:

>         I'm glad you read it as you did, I was kinda thinking out loud,
> where I ended was my final conclusion that it may be worth while as a
> complimentary tool in the hashing toolbox, and I'd prefer its name to
> reflect that.

I agree. It would be better named explicitly.
"strcmp_secure()" or something like this would be good, as it could be
used any security sensitive string comparison.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Jake A. Smith

12 years ago

Hi all,

> "strcmp_secure()" or something like this would be good, as it could be

used any security sensitive string comparison.

I like that. It makes sense for the function to be named for what it does, not how one hopes or expects it will be used. 

JS

—

​Jake A. Smith@jakeasmith | theman@jakeasmith.com

—
Sent from Mailbox for iPhone

On Mon, Dec 23, 2013 at 4:31 PM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:

Thomas Hruska

12 years ago

On 12/23/2013 8:59 PM, Jake A. Smith wrote:

> Hi all,
>
>> "strcmp_secure()" or something like this would be good, as it could be
>
> used any security sensitive string comparison.
>
> I like that. It makes sense for the function to be named for what it does, not how one hopes or expects it will be used.
>
> JS

Perhaps this could be implemented by adding an optional parameter to the
existing str...cmp() series of functions instead of adding more functions.

--
Thomas Hruska
CubicleSoft President

I've got great, time saving software that you might find useful.

http://cubiclesoft.com/

Yasuo Ohgaki

12 years ago

Hi all,

On Tue, Dec 24, 2013 at 1:35 PM, Thomas Hruska <thruska@cubiclesoft.com>wrote:

> On 12/23/2013 8:59 PM, Jake A. Smith wrote:
>
>> Hi all,
>>
>>  "strcmp_secure()" or something like this would be good, as it could be
>>>
>>
>> used any security sensitive string comparison.
>>
>> I like that. It makes sense for the function to be named for what it
>> does, not how one hopes or expects it will be used.
>>
>> JS
>>
>
> Perhaps this could be implemented by adding an optional parameter to the
> existing str...cmp() series of functions instead of adding more functions.

We may do this.
However, strcmp() returns 0 for equal strings while strcmp_secure() will
return TRUE for equal strings. We could make strcmp_secure() returns
FALSE/0 for equal strings, but it does not make much sense.

Perhaps, we need different function name rather than strcmp_secure().

I would like to have dedicated functions for security related features, so
that more users aware of issues.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Thomas Hruska

12 years ago

On 12/23/2013 11:37 PM, Yasuo Ohgaki wrote:

> Hi all,
>
> On Tue, Dec 24, 2013 at 1:35 PM, Thomas Hruska <thruska@cubiclesoft.com>wrote:
>
>> On 12/23/2013 8:59 PM, Jake A. Smith wrote:
>>
>>> Hi all,
>>>
>>>   "strcmp_secure()" or something like this would be good, as it could be
>>>>
>>>
>>> used any security sensitive string comparison.
>>>
>>> I like that. It makes sense for the function to be named for what it
>>> does, not how one hopes or expects it will be used.
>>>
>>> JS
>>>
>>
>> Perhaps this could be implemented by adding an optional parameter to the
>> existing str...cmp() series of functions instead of adding more functions.
>
>
> We may do this.
> However, strcmp() returns 0 for equal strings while strcmp_secure() will
> return TRUE for equal strings. We could make strcmp_secure() returns
> FALSE/0 for equal strings, but it does not make much sense.

Ah, good point.  It was just an idea that crossed my mind and I'll admit
that I had not thought that far ahead.  Having the documentation for the
return value of strcmp() change to "mixed" would indeed be odd if it
returns boolean results for the "secure" version but integer results
otherwise.

--
Thomas Hruska
CubicleSoft President

I've got great, time saving software that you might find useful.

http://cubiclesoft.com/

Sara Golemon

12 years ago

>> Perhaps this could be implemented by adding an optional parameter to the
>> existing str...cmp() series of functions instead of adding more functions.
>
> We may do this.
> However, strcmp() returns 0 for equal strings while strcmp_secure() will
> return TRUE for equal strings. We could make strcmp_secure() returns
> FALSE/0 for equal strings, but it does not make much sense.
>

There's no reason the return value has to be (or even should be)
different from normal strcmp() usage.  The important aspect is that
the timing be (reasonably) constant.

So if I called strcmp($userSupplied, $knownValue,
STRCMP_CONSTANT_TIME) or whatever, I would reasonably (as a user)
expect the return values to still be 0, -1, 1 in line with "normal"
strcmp() usage.  So on that count, I reject your counter-argument.

However, I do worry about using this syntax for a couple reasons of
unintended consequences:

*  Semantics: The first two parameters are no longer interchangeable
(since timing depends on one of them).  Putting it in the wrong spot
negates the usefulness, and that'll be easy with the temptation to
codemod an extra argument in blindly.

* Fat Fingers: A third int/bool field to strcmp() could very easily
get misinterpreted by accidentally using strncmp().  Now that
true/0x01 looks like a length of 1 and your strcmp() only has to match
the first character!

So while I like the elegance of adding an options field to
strcmp/strncmp(), I see it potentially making matters worse.

Lastly, please stay away from names like "strcmp_secure()".  5-10
years from now such a function will inevitably turn out to be insecure
in some way and we'll need to add
strcmp_really_secure_I_mean_it_this_time().  That way lies madness.

-Sara

Adam Harvey

12 years ago

On 27 December 2013 05:57, Sara Golemon <pollita@php.net> wrote:

> However, I do worry about using this syntax for a couple reasons of
> unintended consequences:
>
> * Fat Fingers: A third int/bool field to strcmp() could very easily
> get misinterpreted by accidentally using strncmp().  Now that
> true/0x01 looks like a length of 1 and your strcmp() only has to match
> the first character!

This does worry me a little too.

Another reason I'm not thrilled with the idea of adding a parameter is
that I think it's clearer what's going on if the function name itself
is descriptive (provided a good name can be found) — fundamentally,
they're actually different operations, even if they're in the class of
"string comparison functions", and if you're switching out the entire
implementation based on a mode parameter, that suggests to me they
should be different functions.

> Lastly, please stay away from names like "strcmp_secure()".  5-10
> years from now such a function will inevitably turn out to be insecure
> in some way and we'll need to add
> strcmp_really_secure_I_mean_it_this_time().  That way lies madness.

+1. I don't know what a good name is, but anything with the word
"secure" isn't it. str_compare_constant_time()?

Adam

Stas Malyshev

12 years ago

Hi!

> There's no reason the return value has to be (or even should be)
> different from normal strcmp() usage.  The important aspect is that
> the timing be (reasonably) constant.

From what I have seen, proposed solution (with XORs) can not deliver the
same return value as strcmp, namely:

Returns < 0 if str1 is less than str2; > 0 if str1 is greater than str2,
and 0 if they are equal.

So if we want even minimal compatibility with what strcmp does, it would
be more complex algorithm - and I'm not sure it'd really be that useful
since time-safe comparison would usually be performed for equality.

> So while I like the elegance of adding an options field to
> strcmp/strncmp(), I see it potentially making matters worse.

We have more than two string comparison functions. Of course, keeping
with long-standing traditions of PHP function design, we could just
ignore them and say "so what, this one has two parameters, this one has
three, big deal, it serves my use case" - but I think it's not a very
good idea. Also, it general, it is not a very good idea to add options
to a function that make it take completely different code branch with
different logic, different return params, etc. Sometimes it's
inevitable, but usually it's much better to make it a different function.

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

Mateusz Kocielski

12 years ago

On Mon, Dec 23, 2013 at 07:59:57PM -0800, Jake A. Smith wrote:

> > "strcmp_secure()" or something like this would be good, as it could be
>
> used any security sensitive string comparison.
>
> I like that. It makes sense for the function to be named for what it does, not how one hopes or expects it will be used.??
>

I think that "secure" suffix may be confusing (what does it mean that
this function is "secure"?), "timingsafe_strcmp" or something in that
manner would be better. It simply describes what the function does.

Pierre Joye

12 years ago

On Dec 27, 2013 4:04 PM, "Mateusz Kocielski" <shm@digitalsun.pl> wrote:

> I think that "secure" suffix may be confusing (what does it mean that
> this function is "secure"?),

Agreed.

> "timingsafe_strcmp" or something in that
> manner would be better. It simply describes what the function does.

Can we not simply use an extra argument?

Cheers,
Pierre

Rouven Weßling

12 years ago

On 23.12.2013, at 20:45, Joe Watkins <krakjoe@php.net> wrote:

> It might belong in ext/hash, not sure ...

Since the function has no dependencies I'd like it to be available without extensions. However that's not a battle I'm willing to die for.

> It's not a great idea to have it with the password stuff, as I first suggested, but I do think the two should share code, there's no reason to have two internal implementations of this, can you not make the code from password into a ZEND_API function and share it with this wherever you put it ??

Yes, that should be possible. password_verify is able to do some assumptions on the length of string, but that can just be removed.

On 27.12.2013, at 10:07, Pierre Joye <pierre.php@gmail.com> wrote:

>> "timingsafe_strcmp" or something in that
>> manner would be better. It simply describes what the function does.
>
> Can we not simply use an extra argument?

I'd be against adding a parameter to strcmp for this, as that would completely change the function's semantic. Currently it returns an integer with different meaning for a negative, positive or zero value. However the "hash_compare" function only returns a boolean.

Best regards
Rouven

Sara Golemon

12 years ago

>> It might belong in ext/hash, not sure ...
>
> Since the function has no dependencies I'd like it to be available without extensions. However that's not a battle I'm willing to die for.
>

There's an easy fix for that.  Don't make hash optional.  It's got no
external dependencies, and despite appearances (covering many files),
is actually pretty lightweight.

When the extension was first bundled (years ago) a lot of the
algorithm implementations were new, and all the code in the wild was
using standard's md5()/sha1(), but that's shifted.

-Sara

Tjerk Meesters

12 years ago

On Mon, Dec 23, 2013 at 5:45 PM, Rouven Weßling <me@rouvenwessling.de>wrote:

> Thanks everyone for your feedback, answers inline.
>
> On 22.12.2013, at 18:25, Andrea Faulds <ajf@ajf.me> wrote:
>
> > 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.
>
> On 23.12.2013, at 00:55, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
>
> > 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 23.12.2013, at 02:26, Tjerk Meesters <tjerk.meesters@gmail.com> wrote:
>
> > 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

>
> On 23.12.2013, at 10:09, Joe Watkins <pthreads@pthreads.org> wrote:
>
> >       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

Yasuo Ohgaki

12 years ago

Hi Rouven,

On Mon, Dec 23, 2013 at 2:08 AM, Rouven Weßling <me@rouvenwessling.de>wrote:

> 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

Tjerk Meesters

12 years ago

Hi,

On Mon, Dec 23, 2013 at 1:08 AM, Rouven Weßling <me@rouvenwessling.de>wrote:

> 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
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

--
--
Tjerk

Joe Watkins

12 years ago

On 12/22/2013 05:08 PM, Rouven Weßling wrote:

> Hi internals,
>
> 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 holidays.
>
> Best regards
> Rouven
>

Morning,

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.

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 ...

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.

Cheers
Joe

Yasuo Ohgaki

12 years ago

Hi Joe,

On Mon, Dec 23, 2013 at 6:09 PM, Joe Watkins <krakjoe@php.net> wrote:

>         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.

Good name would help for sure.
+1

Since this is new function independent from any other feature and could use
fix
vulnerability in user code, it would be better if we add this to 5.5.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Stas Malyshev

12 years ago

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

Joe Watkins

12 years ago

On 12/23/2013 10:11 AM, Stas Malyshev wrote:

> 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?
>

One of the chaps on SO done a bit of testing, it appears that without
usleep in php land you cannot avoid cpu spikes, and so cannot get a
reliable vector of attack unless the server side code has been prepared
to be attacked. But this is only testing.

I see the things you see, however, probably better to do something than
nothing I think, this is technically the correct thing to do, and is
simple enough, so I say do it ...

Cheers
Joe

Rouven Weßling

12 years ago

Hi Stas.

On 23.12.2013, at 11:11, Stas Malyshev <smalyshev@sugarcrm.com> wrote:

>> 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?

Indeed, a managed language like PHP will never be able to guarantee safety in this regard. However while you may be able to gain information about the length of the known string, I doubt it will be possible to exploit the string comparison itself (getting byte for byte closer to the hash).

As for your last point, you don't need to do terribly sensitive crypo for this to make sense. Any password hash comparison will do.

That there's a need for this sort of thing is probably demonstrated by the fact, that this is already used by major framework like Joomla! and Symfony2, but implemented in pure PHP which suffers even more from the issues you describe. Also PHP core does something like this already, but only in the narrow use case of password_verify.

On 23.12.2013, at 11:20, Joe Watkins <krakjoe@php.net> wrote:

> One of the chaps on SO done a bit of testing, it appears that without usleep in php land you cannot avoid cpu spikes, and so cannot get a reliable vector of attack unless the server side code has been prepared to be attacked. But this is only testing.

Do you have a link to that discussion? It'd probably be interesting to read in the context of this discussion.

Best regards
Rouven

Joe Watkins

12 years ago

On 12/23/2013 10:26 AM, Rouven Weßling wrote:

> Hi Stas.
>
> On 23.12.2013, at 11:11, Stas Malyshev <smalyshev@sugarcrm.com> wrote:
>
>>> 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?
>
> Indeed, a managed language like PHP will never be able to guarantee safety in this regard. However while you may be able to gain information about the length of the known string, I doubt it will be possible to exploit the string comparison itself (getting byte for byte closer to the hash).
>
> As for your last point, you don't need to do terribly sensitive crypo for this to make sense. Any password hash comparison will do.
>
> That there's a need for this sort of thing is probably demonstrated by the fact, that this is already used by major framework like Joomla! and Symfony2, but implemented in pure PHP which suffers even more from the issues you describe. Also PHP core does something like this already, but only in the narrow use case of password_verify.
>
> On 23.12.2013, at 11:20, Joe Watkins <krakjoe@php.net> wrote:
>
>> One of the chaps on SO done a bit of testing, it appears that without usleep in php land you cannot avoid cpu spikes, and so cannot get a reliable vector of attack unless the server side code has been prepared to be attacked. But this is only testing.
>
> Do you have a link to that discussion? It'd probably be interesting to read in the context of this discussion.
>
> Best regards
> Rouven
>

Morning Rouven

Room 11 on stackoverflow (where all the cool kids hang out)

Cheers
Joe

Joe Watkins

12 years ago

On 12/23/2013 10:26 AM, Rouven Weßling wrote:

> Hi Stas.
>
> On 23.12.2013, at 11:11, Stas Malyshev <smalyshev@sugarcrm.com> wrote:
>
>>> 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?
>
> Indeed, a managed language like PHP will never be able to guarantee safety in this regard. However while you may be able to gain information about the length of the known string, I doubt it will be possible to exploit the string comparison itself (getting byte for byte closer to the hash).
>
> As for your last point, you don't need to do terribly sensitive crypo for this to make sense. Any password hash comparison will do.
>
> That there's a need for this sort of thing is probably demonstrated by the fact, that this is already used by major framework like Joomla! and Symfony2, but implemented in pure PHP which suffers even more from the issues you describe. Also PHP core does something like this already, but only in the narrow use case of password_verify.
>
> On 23.12.2013, at 11:20, Joe Watkins <krakjoe@php.net> wrote:
>
>> One of the chaps on SO done a bit of testing, it appears that without usleep in php land you cannot avoid cpu spikes, and so cannot get a reliable vector of attack unless the server side code has been prepared to be attacked. But this is only testing.
>
> Do you have a link to that discussion? It'd probably be interesting to read in the context of this discussion.
>
> Best regards
> Rouven
>

Right so,

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. */

We already do this, it is a completion of the API, there should be no
argument at all, I'd come at it from this angle, name it as a completion
of this API (password_match) and document it as such.

Cheers
Joe

Marco Pivetta

12 years ago

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/

Joe Watkins

12 years ago

On 12/23/2013 11:04 AM, Marco Pivetta wrote:

> 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

Joe Watkins

12 years ago

On 12/23/2013 11:16 AM, Joe Watkins wrote:

> On 12/23/2013 11:04 AM, Marco Pivetta wrote:
>> 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

Woops, I am not demoting you to a mere macro, you are of course Marco :)

Marco Pivetta

12 years ago

On 23 December 2013 12:16, Joe Watkins <krakjoe@php.net> wrote:

>
> 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".

> 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",

That's admirable, but the userland implementation seems ok for me as well.

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

I'm always barking mad :-)

Cheers,

Marco Pivetta

http://twitter.com/Ocramius

http://ocramius.github.com/

Rouven Weßling

12 years ago

Hi Marco.

On 23.12.2013, at 12:04, Marco Pivetta <ocramius@gmail.com> wrote:

> 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.

On 23.12.2013, at 12:25, Marco Pivetta <ocramius@gmail.com> wrote:

> On 23 December 2013 12:16, Joe Watkins <krakjoe@php.net> wrote:
>
>> 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

Joe Watkins

12 years ago

On 12/23/2013 04:46 PM, Rouven Weßling wrote:

> Hi Marco.
>
> On 23.12.2013, at 12:04, Marco Pivetta <ocramius@gmail.com> wrote:
>
>> 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.
>
> On 23.12.2013, at 12:25, Marco Pivetta <ocramius@gmail.com> wrote:
>
>> On 23 December 2013 12:16, Joe Watkins <krakjoe@php.net> wrote:
>>
>>> 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
>

It might belong in ext/hash, not sure ...

It's not a great idea to have it with the password stuff, as I first
suggested, but I do think the two should share code, there's no reason
to have two internal implementations of this, can you not make the code
from password into a ZEND_API function and share it with this wherever
you put it ??

Cheers
Joe