It's All About Time – Remote timing attacks in PHP

I'm the author of the pull request that prompted the discussion, though, so I'm probably biased. :)

Not really viable against a native code memcmp. Potentially viable against a comparison implemented in PHP or Java.

Here's a video looking at actually implementing such attacks over LAN and internet: http://rdist.root.org/2010/11/09/blackhat-2010-video-on-remo...

> Would a good hosting company block an attack like this at the hardware level? No, there's no generic way to defeat this. The only real limit is how granular your attacker can measure. If you're on shared hosting, you're probably the most vulnerable you can get to this (but also the most screwed already, so you probably don't cate).

That said, while it's not instant game over, you don't really want this vulnerability if you can avoid it. Especially in things like authentication libraries.

http://matasano.com/research/TimeTrial.pdf

https://github.com/dmayer/time_trial

So, there are a few problems with this technique.

1. It ignores the local timing leak

An attacker who can get code running on the server (shared hosts for example), can carefully monitor the CPU usage to see when the process is actually doing work, vs when it sleeps. So really, its not hiding anything.

2. The resolution of the sleep call is WAY too high. We're talking about detecting differences down to 15 nanoseconds. Sleeping for blocks of microseconds or even milliseconds will be far to granular. It will introduce block-like patterns in the requests that should be pretty easy to detect with statistical means.

3. It's basically identical to a random delay. Considering it depends on the system clock, and the original request comes in at a random point, it's functionally identical to calling sleep(random(1, 100)). And over time (many requests), that will average out.

Now, what if we took a different approach. What if we made the operation fixed-time?

    execstart = utime()
    // whatever code
    // clamp to always take 500 microseconds
    sleep( 500 - utime() - execduration)

However, there are two reasons I wouldn't recommend it: It requires guesswork and idle CPU.

You would either need to actively guess every single operation (and remember to clamp it) or clamp the overall application.

If you do it for every operation, that sleep time can become expensive (if you have a lot of them).

If you do it on the application level, and if you do too little, an attacker can use other expensive control (like larger input introducing memory allocation latency) to increase the runtime past the sleep clamp (hence allowing them to attack the vulnerability anyway). If you do too much, the attacker can leverage it to DOS your site (since even a sleeping process is non-trivially expensive).

There are two valid ways of protection IMHO:

1. Make sensitive operations actually constant time.

2. Implement strong IP based protections to prevent the large amount of requests that would be needed to collect enough data to analyze noisy environments. (I need to add this to the post now that I write it).

Personally, you should be doing #2 anyway. But since I also believe in defense-in-depth, I'd do #1 as well.

Your sleep hack is probably less secure. I remember reading somewhere that doing random sleep() calls is flawed and doesn't completely mitigate the attack, but does increase the number of requests needed to get a good statistical analysis.

An approach where you watch the clock will be inherently less portable and actually much harder. Not only will the timing calls be hardware or OS specific, but so will the worst-case time. Imagine having to deal with a chip going into low power mode during your computation. Also you probably don't want to count time that your thread wasn't scheduled to run, so now you're talking about integrating with the scheduler.

The code for the tool (and a presentation pdf) is here if you're interested: https://github.com/aj-code/TimingIntrusionTool5000

However, leaking the length is much less of a problem than allowing the attacker to guess characters one by one.

The problem you'll run into with PHP specifically is that reading an undefined string offset (past the end) will result in a notice: http://3v4l.org/nIkf5

Which means that errors are triggered. So you can increase the length of the user string and note a linear increase in runtime until you increase it past the length of the string, at which point it becomes MUCH slower on a per-character basis (even if you don't do anything with the notice, the error mechanism is still triggered internally, which isn't cheap).

Actually, my original code was more robust as it never read past the end of the string, preventing the notice:

    /**
     * A timing safe equals comparison
     *
     * To prevent leaking length information, it is important
     * that user input is always used as the second parameter.
     *
     * @param string $safe The internal (safe) value to be checked
     * @param string $user The user submitted (unsafe) value
     *
     * @return boolean True if the two strings are identical.
     */
    function timingSafeEquals($safe, $user) {
        // Prevent issues if string length is 0
        $safe .= chr(0);
        $user .= chr(0);

        $safeLen = strlen($safe);
        $userLen = strlen($user);

        // Set the result to the difference between the lengths
        $result = $safeLen - $userLen;

        // Note that we ALWAYS iterate over the user-supplied length
        // This is to prevent leaking length information
        for ($i = 0; $i < $userLen; $i++) {
            // Using % here is a trick to prevent notices
            // It's safe, since if the lengths are different
            // $result is already non-0
            $result |= (ord($safe[$i % $safeLen]) ^ ord($user[$i]));
        }

        // They are only identical strings if $result is exactly 0...
        return $result === 0;
    }

Basically, while it may keep the length %64 safe (since cache lines are 64 bites wide), it doesn't keep the length safe in general. Some length information will be leaked on larger strings. And considering it's impossible to protect the length in the general case, making a function which says it protects length is a lie. Therefore I don't even try and hence save the complexity.

But let me ask this: what cases would you have where are you trying to protect the length? Anything with variable length input (like a password) should likely be one-way hashed anyway. So you'd be comparing fixed-length hashes. So where's the possible leak?