Could a random sleep prevent timing attacks?

Question

From Wikipedia

In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms.

Actually, to prevent timing attacks, I'm using the following function taken from this answer:

function timingSafeCompare($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;
}

But I was thinking if is possible prevent this kind of attack using a random sleep like

function timingSafeCompare($a,$b) {
    sleep(rand(0,100));
    if ($a === $b) {
        return true;
    } else {
        return false;
    }
}

Or maybe augmenting the randomness of sleep

sleep(rand(1,10)+rand(1,10)+rand(1,10)+rand(1,10));

This kind of approach can totally prevent timing attacks? Or just make the work harder?

Answer 1

This is fine for a single request if the only side channel observable by the attacker is the response time.

However, if an attacker makes enough requests this random delay could average out as noted in @Scott's answer citing ircmaxell's blog post:

So if we needed to run 49,000 tests to get an accuracy of 15ns [without a random delay], then we would need perhaps 100,000 or 1,000,000 tests for the same accuracy with a random delay. Or perhaps 100,000,000. But the data is still there.

As an example, let's estimate the number of requests a timing attack would need to get a valid 160 bit Session ID like PHP at 6 bits per character which gives a length of 27 characters. Assume, like the linked answer that an attack can only be done on one user at once (as they are storing the user to lookup in the cookie).

Taking the very best case from the blog post, 100,000, the number of permutations would be 100,000 * 2^6 * 27.

On average, the attacker will find the value halfway through the number of permutations.

This gives the number of requests needed to discover the Session ID from a timing attack to be 86,400,000. This is compared to 42,336,000 requests without your proposed timing protection (assuming 15ns accuracy like the blog post).

In the blog post, taking the longest length tested, 14, took 0.01171 seconds on average, which means 86,400,000 would take 1,011,744 seconds which equates to 11 days 17 hours 2 minutes 24 seconds.

Could a random sleep prevent timing attacks?

This depends on the context in which your random sleep is used, and the bit strength of the string that it is protecting. If it is for "keep me logged in" functionality which is the context in the linked question, then it could be worth an attacker spending 11 days to use the timing attack to brute force a value. However, this is assuming perfect conditions (i.e. fairly consistent response times from your application for each string position tested and no resetting or rollover of IDs). Also, these type of activity from an attacker will create a lot of noise and it is likely they will be spotted via IDS and IPS.

It can't entirely prevent them, but it can make them more difficult for an attacker to execute. It would be much easier and better to use something like hash-equals which would prevent timing attacks entirely assuming the string lengths are equal.

Your proposed code

function timingSafeCompare($a,$b) {
    sleep(rand(0,100));
    if ($a === $b) {
        return true;
    } else {
        return false;
    }
}

Note that the PHP rand function is not cryptographically secure:

Caution This function does not generate cryptographically secure values, and should not be used for cryptographic purposes. If you need a cryptographically secure value, consider using openssl_random_pseudo_bytes() instead.

This means that in theory an attacker could predict what rand was going to generate and then use this information to determine whether the response time delay from your application was due to random sleep or not.

The best way to approach security is to assume that the attacker knows your source code - the only things secret from the attacker should be things like keys and passwords - assume that they know the algorithms and function used. If you can still say your system is secure even though an attacker knows exactly how it works, you will be most of the way there. Functions like rand are usually set to seed with the current time of day, so an attacker can just make sure their system clock is set to the same as your server and then make requests to validate that their generator is matching yours.

Due to this, it is best to avoid insecure random functions like rand and change your implementation to use openssl_random_pseudo_bytes which will be unpredictable.

Also, as per ircmaxell's comment, sleep is not granular enough as it only accepts an integer to represent the number of seconds. If you are going to try this approach look into time_nanosleep with a random number of nanoseconds.

These pointers should help secure your implementation against this type of timing attack.

Answer 2

Anthony Ferrara answered this question in his blog post, It's All About Time. I highly recommend this article.

Many people, when they hear about timing attacks, think "Well, I'll just add a random delay! That'll work!". And it doesn't.

Answer 3

This kind of approach can totally prevent timing attacks? Or just make the work harder?

Neither. It doesn't prevent timing attacks, nor does it make them any more difficult at all.

To understand why, look at the docs for sleep. Specifically, the meaning of the first parameter:

Halt time in seconds.

So your app takes 0.3 seconds to respond without sleep. With sleep it takes either 0.3, 1.3, 2.3, etc...

So really, to get the part we care about (the timing difference), we just need to chop off the integer part:

$real_time = $time - floor($time);

But let's go a step further. Let's say that you randomly sleep using usleep. That's a lot more granular. That's sleeping in microseconds.

Well, the measurements are being made in the 15-50 nanosecond scale. So that sleep is still about 100 times less granular than the measurements being made. So we can average off to the single microsecond:

$microseconds = $time * 1000000;
$real_microseconds = $microseconds - floor($microseconds);

And still have meaningful data.

You could go further and use time_nanosleep which can sleep to nanosecond scale precision.

Then you could start fuddling with the numbers.

But the data is still there. The beauty of randomness is that you can just average it out:

$x = 15 + rand(1, 10000);

Run that enough times and you'll get a nice pretty graph. You'll tell that there are about 10000 different numbers, so you can then average away the randomness and deduce the "private" 15.

Because well-behaved randomness is unbiased, it's pretty easy to detect statistically over a large enough sample.

So the question I would ask is:

Why bother with sleep-like hacks when you can fix the problem correctly?