The helpdesk software Kayako uses an insecure method of generating tokens used for sessions and CSRF protection. It is possible to seed the random number generator with the current time and then crack that seed, making it possible to predict a large part of any following tokens generated by Kayako.

BuildHash

Kayako has a BuildHash function, that is used to create 32 character tokens. This function is used on multiple places, wherever a token or random string is needed:

  • Session tokens
  • CSRF protection tokens
  • Reset password token
  • Captcha generation
  • Password generation

The function looks like this:

function BuildHash()
{
    return BuildHashBlock() . BuildHashBlock() . BuildHashBlock() . BuildHashBlock();
}

function BuildHashBlock()
{
    $Ch1to3 = mt_rand(0, 36 * 36 * 36) - 1;
    $Ch4to5 = mt_rand(0, 36 * 36) - 1;
    $Ch6to8 = hexdec(substr(uniqid(), -6)) % (36 * 36 * 36);

    return str_pad(base_convert($Ch1to3, 10, 36), 3, '0', STR_PAD_LEFT) . str_pad(base_convert($Ch4to5, 10, 36), 2, '0', STR_PAD_LEFT) . str_pad(base_convert($Ch6to8, 10, 36), 3, '0', STR_PAD_LEFT);
}

It does some complicated things to convert numbers to strings and back, but basically it calls mt_rand twice and uniqid once for each block, and concatenates four of such blocks. This makes a 32 character token.

As we have previously seen, the uniqid function simply returns the current time, and the output of random number generators can not be regarded as secure.

Just looking at this it is not a very secure token, but it gets even worse.

Reseeding the random number generator

Kayako contains another function to create a random number:

function BuildRandom($_min, $_max)
{
    list($_usec, $_sec) = explode(' ', microtime());

    // Seed
    mt_srand((float) $_sec + ((float) $_usec * 100000));

    return mt_rand($_min, $_max);
}

As you see it seeds the random number generator by calling mt_srand with the current time. We can call this function by requesting a specific URL, which means that we can seed the random number generator with the current time whenever we want. This makes it even easier to crack the state of mt_rand.

Attack

An attack would work as follows:

  • Call BuildRandom by requesting a URL that uses this function, and remember when we did this. This seeds the random number generator with the current time, which we know approximately.
  • Request a token. A good candidate is a CSRF token or session token, which are both returned on a request to the home page.
  • Loop through many seeds corresponding to the time of the first request, until we generate the same token as in the second request.

We can now predict any future mt_rand output, so we know a great part of each hash generated on the server. The only parts left unknown are the uniqid parts.

The above process takes less than a second. I made a proof of concept that cracks the token used for the password reset. When it requests a password reset, a validation link with a token is mailed to the user. This token is made with BuildHash, so if we crack the random number generator and reset the password, we know a big part of this token.

$ php -f resetpassword_simple.php 
Working from 1466675441.546206 to 1466675441.502969
The hash looks like this: rk29o...v56qb...a0eut...17eyn...

This indeed corresponds to the token in the e-mail:

To reset your password, click the link below or copy and paste the link into your browser location bar:

.../UserLostPassword/Validate/rk29oxb1v56qbxdya0eutxgn17eynxjb

Although we did not retrieve the whole token, we reduced the search space from 32 characters to 12 characters. By measuring the time taken for requests we could further narrow down the return value for uniqid, after which a brute-force attack on the token could be feasible. Once we have the token we can reset the password of the user.

Kayako’s fix

Kayako published a patch on their website to fix this issue. The patch introduces a new function, GenerateID, which uses openssl_random_pseudo_bytes to generate a secure random token. This new function is used to create the session token for administrators and staff.

Conclusion

Because the Kayako tokens are partially made from mt_rand, and we can reseed it with the current time by requesting a web page, we can easily crack the state of the random number generator and predict a large part of future tokens.

Timeline

  • Jun 3 - mailed Kayako about insecure BuildHash function.
  • Jun 9 - received response that Kayako believed the impact to be reduced to unauthenticated sessions.
  • Jun 10 - mailed Kayako that the same tokens are used as session tokens for staff and admins.
  • Jun 15 - Kayako releases a security advisory.