@Joey3000 opened this Issue on December 31st 2015 Contributor

Background

See http://codahale.com/a-lesson-in-timing-attacks/. Also, Github advises using constant-time string comparison with its authentication token.

Issue

The authenticateWithToken() and authenticateWithTokenOrHashToken() functions of the Login plugin (see https://github.com/piwik/piwik/blob/2.16.0-b1/plugins/Login/Auth.php#L72-L96) currently don't use a constant-time string comparison when checking validity of token_auth.

Specifically:

  1. authenticateWithTokenOrHashToken(): Following comparisons are not constant-time:
    • SessionInitializer::getHashTokenAuth($login, $user['token_auth']) === $token
    • $user['token_auth'] === $token
  2. authenticateWithToken(): I'm not familiar with DB access, but it seems possible that $user = $this->userModel->getUserByTokenAuth($token) is not constant-time, referring to the comparison by MySQL of $token to table entries on value search (requested in https://github.com/piwik/piwik/blob/2.16.0-b1/plugins/UsersManager/Model.php#L175).

Note: authenticateWithPassword() does not seem to be affected, because it compares hashes of the password. Which should make such character-by-character recovery impossible, given that a hash changes entirely with a slightest change of the password.(See next comment.)

Possible Solutions:

  1. authenticateWithTokenOrHashToken(): See, e.g., https://github.com/phpseclib/phpseclib/blob/2.0.0/phpseclib/Crypt/RSA.php#L2201-L2213 for an example on constant-time string comparison. (Its length check should not be an issue with token_auth in Piwik, since it's a (MD5) hash, whose length is constant and thus does not contain any information useful to an attacker.) Alternatively, see next point.

    Another secure string comparison example can be found here: https://github.com/defuse/php-encryption/blob/399fc4c4798b301681888c2608b0ddd060d477da/src/Crypto.php#L409.

2. authenticateWithToken(): A solution could be storing the token_auth in hashed form, similarly to the password. And similarly, hashing the received value before searching for it in the DB.(See next comment.)

Additional Notes

It seems to be very hard to exploit this with a web application (especially over the internet). So that this is rather an "enhancement". E.g., following test:

$time_start = microtime(true);

for ( $i = 0; $i < 1000000; ++$i )
{
   $results = strcmp('stringstring', 'stringstring');
}

$time_end = microtime(true);
printf("strcmp with matching strings took %f seconds\n", $time_end - $time_start);

$time_start = microtime(true);

for ( $i = 0; $i < 1000000; ++$i )
{
   $results = strcmp('stringstring', 'weoisdfd');
}

$time_end = microtime(true);
printf("strcmp with non-matching strings took %f seconds\n", $time_end - $time_start);

$time_start = microtime(true);

for ( $i = 0; $i < 1000000; ++$i )
{
   $results = 'stringstring' === 'stringstring';
}

$time_end = microtime(true);
printf("=== with matching strings took %f seconds\n", $time_end - $time_start);

$time_start = microtime(true);

for ( $i = 0; $i < 1000000; ++$i )
{
   $results = 'stringstring' === 'weoisdfd';
}

$time_end = microtime(true);
printf("=== with non-matching strings took %f seconds\n", $time_end - $time_start);

on http://sandbox.onlinephpfunctions.com/ outputs, e.g., following with PHP 5.0.5:

strcmp with matching strings took 0.411142 seconds
strcmp with non-matching strings took 0.393982 seconds
=== with matching strings took 0.192044 seconds
=== with non-matching strings took 0.172884 seconds

I.e., a difference of ca. 20ms per 1000000 comparisons, or ca. 20ns per comparison with ===.(See next comment.)

With PHP 5.6.2 it's faster, but the difference is similar, e.g.:

strcmp with matching strings took 0.246002 seconds
strcmp with non-matching strings took 0.236303 seconds
=== with matching strings took 0.047865 seconds
=== with non-matching strings took 0.023867 seconds

P.S.: I'm not an expert with any of the above, in any way shape or form :)

@Joey3000 commented on January 2nd 2016 Contributor

Having thought about this issue a bit more, here is an extension/update to the original post:

Issue

Here are additional points. (Points 1 and 2 of the original post are still valid.)

3. Unlike stated above, the authenticateWithPassword() function (see https://github.com/piwik/piwik/blob/2.16.0-b1/plugins/Login/Auth.php#L61-L70) is also affected on its check of $user['password'] === $passwordHash.
The reason is that the currently used MD5 hash function is very broken, as can be any hash function in future. To "break in", an attacker would need:

  • Try any string as password, making sure that the string's hash value does not change in the already recovered characters.
  • Make sure that the tried string's length stays the same between the tries, so that its hash calculation time stays constant.

    Now, that last point makes the attack much more difficult (if not almost impossible), because it's one thing to find a collision with strings of any length, and a completely different one to do so with strings of equal length. Still, there is a theoretical possibility (the longer the strings, the easier), and hash functions only get more broken over time.

    Please note that:

  • The attacker would not need to recover the actual password, but just a string whose hash value equals (i.e. collides with) the hash value of the password.
  • Addition of a salt to the password would make no difference for a timing attack. Because a salt just changes the hash value compared against.

4. isTokenValid() on password reset token (https://github.com/piwik/piwik/blob/2.16.0-b1/plugins/Login/PasswordResetter.php#L234) is not constant-time on its check of $generatedToken === $token.

5. verifyNonce() on nonce (https://github.com/piwik/piwik/blob/2.16.0-b1/core/Nonce.php#L76) is not constant-time on its check of $cnonce !== $nonce.

6. validatePhoneNumber() on phone number verification (https://github.com/piwik/piwik/blob/2.16.0-b1/plugins/MobileMessaging/API.php#L273) is not constant-time on its check of $verificationCode == $phoneNumbers[$phoneNumber].

7. setIgnoreCookie() on ignore cookie setting (https://github.com/piwik/piwik/blob/2.16.0-b1/plugins/UsersManager/Controller.php#L302) is not constant-time on its check of $salt !== $this->getIgnoreCookieSalt().

Possible Solutions

  1. authenticateWithTokenOrHashToken():
    1. Either: Same as in the original post.
    2. Or: https://github.com/piwik/piwik/issues/9457 (which is similar to point 3.ii. below).
  2. authenticateWithToken(): This point in the original post is wrong. An additional hash round would not make a difference (assuming that hashing is a constant-time operation) - it would just change the hash value compared against. Instead, a solution could be:
    1. Either: An addition of an artificial random time jitter, to overlay the DB search time. One with a resolution in the area of the DB search time difference due to the non-constant comparison. (See next comment.)
    2. Or: Same as 1.ii. above.
  3. authenticateWithPassword():
    1. Either: Same as in point 1.i. above.
    2. Or: https://github.com/piwik/piwik/issues/5728#issuecomment-162944909.
      It uses password_verify() which is safe against timing attacks. It requires PHP 5 >= 5.5.0, which should be fine for Piwik 3.0 (https://github.com/piwik/piwik/issues/8156).
  4. isTokenValid(): Same as in point 1.i. above.
  5. verifyNonce(): Same as in point 1.i. above.
  6. validatePhoneNumber(): Same as in point 1.i. above.
  7. setIgnoreCookie(): Same as in point 1.i. above.

Additional Notes

The test in the original post was not correct, in that the comparison time difference of only one character should be tested:

$time_start = microtime(true);

for ( $i = 0; $i < 1000000; ++$i )
{
   $results = 'aa' === 'ab';
}

$time_end = microtime(true);
printf("=== with matching strings took %f seconds\n", $time_end - $time_start);

$time_start = microtime(true);

for ( $i = 0; $i < 1000000; ++$i )
{
   $results = 'aa' === 'bb';
}

$time_end = microtime(true);
printf("=== with non-matching strings took %f seconds\n", $time_end - $time_start);

Which outputs following with PHP 5.0.5:

=== with matching strings took 0.188403 seconds
=== with non-matching strings took 0.183385 seconds

I.e., a difference of ca. 5ms per 1000000 comparisons, or ca. 5ns per comparison. And about half of that with PHP 5.6.2.

Which makes this even more theoretical in the realm of web applications (especially over the Internet).

@Joey3000 commented on January 4th 2016 Contributor

The above solution 2.i. (time jitter "padding" of the comparison time) would not work. It would make an attack slower, but not prevent it. Because of a possibility of a statistical analysis attack. Paraphrasing https://www.reddit.com/r/netsec/comments/3zc5qu/https_bicycle_attack/cylek82:

If you were to observe enough samples, you'd eventually identify a case where the random time padding length reached its minimum, which would give you a close estimate of the actual comparison time.

For example, if you say "padding time is randomly selected between 5 and 50 ns, with a resolution of 5ns", after 10 observations you can assume that the actual comparison time is probably 5ns shorter than the smallest comparison time you observed. Your confidence factor only goes up with the number of observations.

@Joey3000 commented on January 5th 2016 Contributor

From another discussion, from 2010, Nanosecond Scale Remote Timing Attacks On PHP Applications: Time To Take Them Seriously?:

Throw in possible situation improvements (for an attacker) due to CPU/RAM constraints, increased sampling and analysis, and we now have something a heck of a lot more worrying. The real possibility [is] that our network jitter defence is dead in the water – the gulf between a 1ns memcmp() comparison and a 15ns detection resolution no longer looks insurmountable.

It even advocates for timing attack prevention on user name ("login") (which is, similarly to the issue point 2 above, also vulnerable on its DB look-up in https://github.com/piwik/piwik/blob/2.16.0-b1/plugins/Login/Auth.php#L63):

It has long been noted by programmers that, where usernames are not explicitly public by design, disclosing usernames indirectly is a problem. If nothing else it increases the risk of cross referencing username/password combinations from other more seriously compromised websites. We all use a different password for every single site, don’t we?

But, in my opinion (given its implementation complexity), that would not be needed with a timing attack-secure password handling.

@mattab commented on December 4th 2020 Member

A method was added in https://github.com/matomo-org/matomo/pull/16696 and documented it in the checklist and security guide plus it's a public API. we'll only need to use it in the codebase eventually

Powered by GitHub Issue Mirror