See https://wiki.php.net/rfc/timing_attack

This has been discussed at length on the mailing list, so a 👎 from me on changing this.

@cjbj I've read it. I couldn't find a mention about leaking if there is a length difference.

@datibbaw
This function has been designed to be improved according to http://marc.info/?l=php-internals&m=139318035405396&w=2.

The actual function's prototype is confusing and the doc is not really explicit (http://php.net/hash_equals says that both arguments must be of the same length but does not explicitly says that the length will leak with the current implementation). Btw it will allow to use hash_equals in Symfony, Joomla, and probably in a lot of other projects (this is one of the goals of this function according to the wiki page and this is not possible yet because of BC breaks introduced in these tools).

As said on the wiki, an implementation in a low level language is better and it will benefit to the whole PHP ecosystem.

A far from perfect benchmark about length leak: https://gist.github.com/dunglas/4b33d449fd1b05469077

The results with this implementation (edit, updated with data from the new CPython inspirited version):

User size: 512  Known size: 1024    Elapsed: 0.001928   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002653   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.005024   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001248   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002343   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.004251   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001335   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002773   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.004718   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001200   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002254   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.004355   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001187   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002453   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.005525   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001492   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002720   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.005281   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001482   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002994   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.005371   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001291   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002275   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.004706   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001392   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002803   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.004515   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.001128   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.002159   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.004199   Iterations: 1000

The "leaked" information seems to be the size of the user submitted data (already known by the attacker).

The results with PHP 5.6.0:

User size: 512  Known size: 1024    Elapsed: 0.000130   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001026   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000139   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000123   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001026   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000139   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000123   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001028   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000139   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000123   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001025   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000139   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000123   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001025   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000138   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000123   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001026   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000139   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000123   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001025   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000139   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000124   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001026   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000138   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000124   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001114   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000193   Iterations: 1000
User size: 512  Known size: 1024    Elapsed: 0.000123   Iterations: 1000
User size: 1024 Known size: 1024    Elapsed: 0.001570   Iterations: 1000
User size: 2048 Known size: 1024    Elapsed: 0.000157   Iterations: 1000

Even if an advanced attacker can discover the length (we can still say in the doc that this function is not robust against length leaking), this is a way harder than with the current implementation for almost no cost.

@dunglas We determined that we don't have any robust mechanism to prevent length leaks and as such preferred to explicitly not support comparison of strings with different length, rather than provide a (wrong) implication that we protect against this, while only providing something that kinda-sorta works. (The docs should be more explicit about this function not being safe with different lengths - right now that isn't clear...)

@nikic isn't it better to have something hard to crack (and documented as not robust to avoid a wrong impression of security) than something easy to crack (think "secure" cookie signature for instance).

If this implementation is still robust for same length strings, of course (if it is not the case, maybe can we introduce a new function or a flag to this one).

@dunglas A signature always has the same known length. A hash always has the same known length. I don't see why the different-lengths case would be relevant in that case.

Python use a similar and probably better implementation (thanks to volatile and no modulo) than this one): https://github.com/python/cpython/blob/c7688b44387d116522ff53c0927169db45969f0e/Modules/_operator.c#L175
If you are interested, I'll update my PR to port their implementation.

They advertise in their doc that length can potentially leak. I think they took the good decision (robuster than classical comparisons and advertised as not secure in some cases).

For a use case, see https://github.com/symfony/symfony/blob/397687f345f4ea83f344a54275f4bc328ac2d4b4/src/Symfony/Component/Security/Csrf/CsrfTokenManager.php#L95

@dunglas Why does that use case require timing safety with different length strings? Is the length of CSRF tokens not constant and known?

@nikic the length can vary. It depends of your configuration and of your CSRF token generator implementation: https://github.com/symfony/symfony/blob/397687f345f4ea83f344a54275f4bc328ac2d4b4/src/Symfony/Component/Security/Csrf/TokenGenerator/UriSafeTokenGenerator.php#L47

@dunglas But within an application? As the client needs to submit the CSRF token, he can inspect a sample value for it - and the length of that value should apply to all tokens across the application.

Anyway, I don't really have a problem with adding this, if we properly document that it's unsafe. Needs to run by the list though, as this was a point of contention at the time the function was implemented.

@nikic you're right if the attacker is able to get a first CSRF token, this is not always the case. A custom generator can also generate not constant length token.
There is other use cases in Symfony https://github.com/symfony/symfony/search?utf8=%E2%9C%93&q=StringUtils (not always secure by design, I think to the plain text password comparison feature).

As a side note, Zend Framework also try to hide length of compared strings and this function is not usable to replace the PHP implementation: https://github.com/zendframework/zf2/blob/master/library/Zend/Crypt/Utils.php#L41

Hmm... I'm no security expert, but I wonder if this isn't solving the wrong problem. Your function itself won't leak on length, but wouldn't all the memory allocations and so on surrounding it leak instead?

In Java, the leak on lengths (almost the same algorithm than in PHP 5.6.0) was considered as a security vulnerability and has been fixed: http://codahale.com/a-lesson-in-timing-attacks/

@TazeTSchnitzel I'm not an expert too. What I want to do is not be 100% sure that the function leak anything but make it harder for an attacker to compute useful data. And, btw, increase the security of the whole PHP ecosystem by allowing Sf, Zf, Joomla... to switch to the (better) C version.
By porting the CPython version, the leak must be really limited, especially for network applications.

Alright, let's go through this.

First off, it's very hard not to leak length information. Very hard. In the general case, it may not even be possible.

In the case of Python, there are data-length dependent branches:

/* don't use else here to keep the amount of CPU instructions constant,
 * volatile forces re-evaluation
 *  */
if (len_a == length) {
    left = *((volatile const unsigned char**)&a);
    result = 0;
}
if (len_a != length) {
    left = b;
    result = 1;
}

for (i=0; i < length; i++) {
    result |= *left++ ^ *right++;
}

In that case, the first two branches will depend on the length difference between the two strings. This is a source of timing information about the two lengths. This is because x86 processors make heavy use of branch prediction. This is able to be leveraged by an attacker. So leveraging the difference between branch prediction misses (which are extremely expensive) and hits, it leaks information that the lengths are not the same.

To prove that this difference exists, let's analyze your benchmark results. If we average all of the timings on a per-byte basis, we get the following results:

Hmmm... They are all different? Yes. Well, but the smallest value is the most expensive one. Weird. Well, not so, if we think about it. There's overhead to calling the function, and setting up (the two if statements). And those costs get averaged in and are constant for each size (well, one of them is different for our known length of 1024).

But let's look at the difference between the average times. But we need to normalize that difference, because it's spread out over different numbers of bits. So we wind up needing an equation to figure out the overhead (these numbers are simply the average time for a full run:

0.015165 = $overhead + 512 * $bytecost
0.028147 = $overhead + 1024 * $bytecost
0.053206 = $overhead + 2048 * $bytecost

And since we have 2 unknowns and 3 functions, we can solve. Let's solve for $overhead:

$bytecost = (0.015165 - $overhead) / 512
$overhead = 0.028147 - 1024 * $bytecost

Then

$overhead = 0.028147 - 1024 * (0.015165 - $overhead) / 512
$overhead = 0.028147 - 2 * (0.015165 - $overhead)
$overhead = 0.028147 - 0.03033 + 2 * $overhead
-$overhead = -0.002183
$overhead = 0.002183

But wait, that only accounts for the two, so we need to take into account the 2048 run. So let's compute the three permutations of overhead and average them (between 512 and 1024, 512 and 2048, and 1024 and 2048:

Average: 0.002574

So when we subtract that number from our original table, we get:

Notice how the most expensive per byte is 1024... And that's the one which has our user defined string!

If you want to try this yourself, rather than trying 512 vs 1024 vs 2048, try it on 1027 vs 1028 vs 1029 (all three not the same as 1024 known). And try it on 1023 vs 1024 vs 1025 (where 1024 is known). And use a lot more than 4 significant digits of timing. And you should be able to see without even all this math, that 1024 is the value.

In fact, in general (for arbitrary strings) it's not really possible to prevent leaking the length of the source string.

We could hash each string with a secret random key, and verify the hashes match. This is called Double HMAC Verification. This seems like it hides length differences. Right?

Well, no. Because all hash functions pad input to a multiple of its block size. So there is branch conditional logic around exact string size. And you can trivially detect how many blocks there are, so you know the scale of the string.

Additionally, the link that @dunglas posted about Java's timing attack was because it leaked timing information. The fixed Java implementation is basically identical to PHP's for all practical purposes.

However

I must question the use-case for protecting arbitrary length strings.

The typical use-case for timing safe comparison is validating MACs (Message Authentication Codes. MACs should always have the same length. If it has a different length, something is very wrong. So leaking the length isn't an issue. Especially since you're giving the attacker the original length via the MAC when you append/prepend it to the ciphertext.

What are you comparing with a timing safe comparison where lengths could be different?

And if it's that critical, you should pre-hash the value in the database (not the same as hashing it before comparison), so that it's reduced to a fixed length by the time the attacker can guess it. That way, even though timing information may be leaked, it's useless as it's not timing information about the data, but about its hash.

So in general, I think that PHP's implementation is good enough. Yes, we can try to defend against length leak. But it won't work. So we can either pretend to, or we can simply acknowledge that it won't work, and document it. And tell users that they should design their systems so length isn't a secret. And that will improve security.

@ircmaxell thanks for the explanation. Here what we want is not to leak nothing, but to leak less, and the Python implementation leak less than the PHP one.

If we consider that the PHP implementation is good enough, what about throwing an error (or a warning) when lengths are not equals instead of returning false. It will be more explicit for the end developer.

@dunglas I'll let Anthony (ircmaxell) say if that's a good idea or not, but if it is, you should use E_NOTICE or E_STRICT to avoid it popping up in production.

EDIT: Wait, no, that's a terrible idea, silly me.

I am strongly against adding an error (warning, notice, strict, whatever you want to call it).

If one of the inputs is user-controlled, that means that the user can cause you to raise an error? That's not good. And your only defense of that is having the developer add a check for the length (which is adding a timing difference anyway).

Point being that it's impossible to defend against length differences in the general case. Raising errors would just make that worse. Or at best lead people to thinking:

if (strlen($a) == strlen($b)) {
    return hash_compare($a, $b);
}
return false;

Is somehow safer than just using hash_compare directly. Because it doesn't throw warnings/errors!!! So it must be better!

No, different length strings are a valid case. And in the case where you don't want to leak length information, you need to do things like pre-hashing (in a different request/process).

But even at that point, it should be extremely rare when you do actually need to protect length as more than just obscurity...

@ircmaxell, if, by design, hash_equals must not be used to compare strings of different lengths, throwing a strict warning will allow the developer to catch the design problem at development time isn't it? If it can be used to compare strings of different length, why not try to leak less (even if it's impossible to not leak, a smaller difference will be harder/longer to catch, especially over a network). I'm just asking by curiosity, I'll close this PR if everyone agree with @ircmaxell.

@dunglas Comparing strings of different lengths is a completely valid and even normal thing, you're just not safe from it leaking the length difference.

Other way around. hash_equals can compare strings of different lengths. And should be used whereever you don't want to leak contents. It won't leak timing information about the contents. It will leak the length, but as we showed that's unavoidable.

And it's not up to the developer to determine if the strings are different lengths. It's the attacker/user that does. They are the one who is submitting the data that's being compared.

Normal comparison functions (== and ===) are not timing safe. Meaning that

aaaa === bbbb

Will take measurably less time than

aaaa === aaab

So information is leaked. And if an attacker can knowingly control one of the pieces of data, then they can deduce the entire string, by measuring the timing differences at play.

With hash_equals, if the strings are different lengths, then no comparisons are made at all. So the contents are still protected. This is desirable. Because the contents are protected. Which is what we're trying to protect.

So yes, hash_equals should be used to compare strings of different lengths. That is by design. It's just not designed to protect the leaking of length information (because that's not possible in the general case).

And yes, while we could make it harder to spot the difference of length (like python did with its implementation), that will lead to a situation where many think that it's safe, when its not. And lead to developers not designing systems where length is a secret, which reduces overall security.

I'd rather not make false promises ("This is mostly resistant to length leaks"). Instead, I'd rather make security where we can, and document and educate where we can't.

@ircmaxell my proposal here is making harder to spot the difference of length and documenting the function on php.net has leaking the length (without even mentioning a mitigation). It will not give a wrong impression of security.

It will also allow using the C implementation (more robust because lower level) in Symfony (they want to keep the mitigation, see symfony/symfony#11797) and other frameworks implementing a mitigation strategy. Many projects will benefit of an increased security (even if far from perfect and badly designed) by this change.

I commented on that PR. this needs to be fixed with education, not with applying changes that don't work because it makes someone feel safer without actually protecting them.

For information, the HHVM implementation try to hide the length too: https://github.com/facebook/hhvm/blob/89ede71cd24a8ba901ae7a89142b08feaaf8e8ab/hphp/runtime/ext/ext_hash.cpp#L366

The commit introducing this feature: facebook/hhvm@2ff6f85 cc @sgolemon @apage43

@dunglas Facebook doing something silly doesn't mean we should.

@TazeTSchnitzel I don't want to troll. I think there is a consensus to document the function has leaking length information. But having a similar behavior for security functions in both implementations benefits to all PHP apps (regardless if the behavior is to return early or not).

@dunglas There's no point given it's not in our docs, and might even be unhelpful as people will gain the impression that length isn't leaked.

The warning in the Python doc (https://docs.python.org/3.5/library/hmac.html#hmac.compare_digest):

Note If a and b are of different lengths, or if an error occurs, a timing attack could theoretically reveal information about the types and lengths of a and b–but not their values.

Regardless if we keep the current implementation or not, I propose to improve http://php.net/hash_equals by making clear that the length can leak:

Both arguments must be of the same length to be compared successfully. If they are not, or if an error occurs, a timing attack could reveal information about the length of $known_string but not its value.
When arguments of differing length are supplied, FALSE is returned.

@dunglas Yeah, it's bad the docs don't make clear the length can leak. Your function removes this warning from the PHP source, though.

@Tyrael you're right. Fixed and updated the PR body reflecting the current state of this proposal.

@dunglas I agree 100% that the docs should explain the leak. I think we need to be careful though, as the wording should be thought through as to indicate that the function is still safe and should be used. A warning may scare people off and make the overall situation worse.

So while it definitely should say that lengths are leaked. Perhaps it should also say that this is expected (and impossible to defend against anyway), with suggestions for how to secure it if necessary...

Additionally, looking at the HHVM implementation, it most definitely leaks length information (worse than the python implementation). Because it has data-dependent branching, which will leak the length to a side channel attacker. And rather than being a single branch like cpython's version, it's a branch within a loop.

And keep in mind that there aren't gradations of leakages. Either it leaks information, or it doesn't. If it leaks information, the difference between a gardenhose and a water main is irrelevant when all you need is a drop.

So while I don't think it's worth changing any of the implementations. i think it's worth while documenting the limitations, but the limitations that apply to all of them. Not just one. So HHVM and PHP should both document the leaked length information. And should avoid saying things like "leaks less" or "is not as leaky as", etc.

@ircmaxell can you write something to add to the doc about how to secure apps with pre-hashing or other applicable strategies? I strongly agree that both PHP.net, HHVM and frameworks docs must make it clear that the length will leak. I tried for Symfony (symfony/symfony#11822).

Concerning the Python-like implementation, I don't understand why you introduced a similar mitigation in Symfony and don't want it in PHP (documented as leaking the length anyway).

Correct me if I'm wrong: an attacker will take more time / need more ressources and maybe fail to crack a poorly designed "typical" web application (doing only one call to hash_equals, with network noise, DOS protections...) with the mitigation than without. And it doesn't decrease security for new / well designed applications because the function will be documented as leaking length.

Here is a use case:
According to the discussion on the Symfony PR, those frameworks are switching (or will switch) to hash_equals. Even old branches (Symfony 2.3 LTS will switch to hash_equals too, so old applications getting framework security updates will blindly switch to hash_equals).
Now think about an "old" application relying on the (wrongly - and soon corrected) documented fact that the Symfony (or ZF or Joomla) PHP implementation of constant time string comparison don't leak length. After an upgrade of the server to PHP 5.6, this app will be easier to crack.
In all cases, the application is vulnerable, but now, it can be cracked by a less skilled / powerful attacker. If the mitigation is merged, the application is still vulnerable (because it is by design), but no more no less than before (in fact maybe a bit less thanks to the C implementation replacing the PHP one).

Shorter: why not merge it if it makes it harder in some cases for an attacker while documented as leaking the length.

Can you provide an example where leaking the length results in a breach? In what specific cases is the length a protected secret?

Additionally, even if the Symfony version was documented to not leak length information, it did. So the issue isn't that PHP's leaks it, it's that Symfony's pretended not to.

Shorter: why not merge it if it makes it harder in some cases for an attacker while documented as leaking the length.

Does it? Can you prove that? What edge does knowing the length give an attacker in a real world app?

I am swayed by the arguments put forward in opposition that changing the implementation achieves nothing of any value.

Closing PR.