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?

Artimas

Just use hash_equals() and call it a day. – Connelley

Answer 1

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?

Lugsail

I love how I'm the author of the post cited in both other answers, and they are higher voted than me :-P... (Just playing, it's actually quite an honor) – Lugsail

Nice blog post. Maybe there is some sort of timing attack you can use to hack the question and make it accept your answer. – Sententious

Are you sure they "do not make them any more difficult at all" ? At all? If one response time is 1ms average and you add about 1 second of random sleep, at least now the attacker must wait a thousand times more (or use way more threads), making the attacks not harder, but longer at least. If my webapp has insane traffic for 1 week, thats easier to spot than a short burst of traffic at 3AM. – Miraculous

I'm no statistician, but isn't the point that the "15" in your above example isn't always consistent depending on external factors (e.g. server load)? So if you've got some operation that usually takes between 12 and 18 microseconds, and you introduce between 0 and 6 microseconds of sleep, it's impossible to detect it. Another option is to have all operations take a fixed amount of time, i.e. sleep for the difference of actual time taken and some arbitrary length of time? – Cavite

do you think this sleep-based hack prevents timing attacks? – Damnation

Answer 2

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.

Indignant

Also: sleep() accepts seconds as a parameter. Which has way too low of granularity to hide anything... – Lugsail

In my point of view a random sleep is not a good choice. Even a with openssl_random_pseudo_bytes, beacause good random numbers are even distributed. This means you always add a avg sleep, when you make enough requests. – Usurpation

Answer 3

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.

Connelley

Lots of pretty graphs and I'm sure the actual lecture explains it, but i personally can't see how adding a truely random sleep is not enough to mitigate a timing attack. – Sententious

@Phil_1984_ 1) granularity. Most "random" sleeps are at the millisecond level where the difference's we're measuring are at the 10's of nanosecond level. 2) Locality. A agent on the hardware can watch CPU load and tell sleep from activity (in VMs, etc). 3) Statistically those random sleeps can be averaged away. 4) It's a bandaid. It's not mitigating, it's not plugging the underlying wound, it's just making it so you can't see it. It's obscurity. – Lugsail

Ah I only read the 2nd link. 1st link explains it all and is very interesting, thanks. You just have to do a lot of requests to average out the randomness. There is also randomness in load (as you said) and at every network hop too which theoretically could get averaged out in the same way. For the OPs string comparison problem, is there anything wrong with simply hashing first then comparing the results? – Sententious

@Phil_1984_ just hashing isn't enough (since hashing is predictable). You'd need to hash with a random string (preferably in HMAC): isecpartners.com/blog/2011/february/… (note that uses a static key, but many of us recommend using a random one). – Lugsail

Yeah, double HMAC with a nonce does make timing attacks impractical if you have an allergy for the correct solution. – Connelley

Good article. It does say that "clamping" the time to a minimum would work. I suspect at least some people who ask about adding a random amount of time are actually thinking about this so-called "clamping" but do not explain themselves well. – Birecree

Answer 4

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

ircmaxell have already answered why this only makes the work harder,

but a solution to prevent timing attacks in PHP in general would be

/**
 * execute callback function in constant-time,
 * or throw an exception if callback was too slow
 *
 * @param callable $cb
 * @param float $target_time_seconds
 * @throws \LogicException if the callback was too slow
 * @return whatever $cb returns.
 */
function execute_in_constant_time(callable $cb, float $target_time_seconds = 0.01)
{
    $start_time = microtime(true);
    $ret = ($cb)();
    $success = time_sleep_until($start_time + $target_time_seconds);
    if ($success) {
        return $ret;
    }
    // dammit!
    $time_used = microtime(true) - $start_time;
    throw new \LogicException("callback function was too slow! time expired! target_time_seconds: {$target_time_seconds} actual time used: {$time_used}");
}

using that approach, your code could be

function timingSafeCompare($a,$b, float $target_time_seconds = 0.01) {
    return execute_in_constant_time(fn() => $a === $b, $target_time_seconds);
}

downside is that you should pick a number with a large margin, meaning relatively much time is lost sleeping.. fwiw on my laptop i had to use 0.2 (200 milliseconds) to compare 2x exactly-1-GiB strings, with a Core i7-8565U (a weird 2018 mid-range laptop cpu i've never heard of)

and this loop:

ini_set("memory_limit", "-1");
$s1 = "a";
$s2 = "a";
$append = str_repeat("a",100*1024);
try {
    for (;;) {
        $res = timingSafeCompare($s1, $s2, 0.01);
        $s1 .= $append;
        $s2 .= $append;
    }
} catch (\Throwable $e) {
    var_dump(strlen($s1));
}

craps out at about 65 megabytes/int(65126401)

(but how often do you need to constant-time-compare strings above 65MB? i imagine it's not often)

• you might think "then the attacker could send a HUGE string to compare, and check how long it takes for the exception to be thrown" but i don't think that would work, === starts by checking if both strings have the same length, and short-circuits if they have different lengths, such an attack should only work if the attacker can set the length for both strings to be large enough to timeout

• today we have the native hash_equals() function to compare strings that have exactly the same length, but hash_equals() will not protect you against strings of different length, while the function above will.

Damnation