随机睡眠可以防止定时攻击吗

Question

来自维基百科

在密码学中，定时攻击是一种侧信道攻击，其中攻击者试图通过分析时间来破坏密码系统用来执行加密算法。

事实上，为了防止定时攻击，我使用了以下来自这个答案的函数：

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;
}

但我在想，如果可以使用这样的随机睡眠来防止这种攻击

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

或者可能增加睡眠的随机性

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

这种方法可以完全防止定时攻击吗？还是只是让工作更努力？

Answer 1

这种方法可以完全防止定时攻击吗？还是只是让工作更努力？

两者都没有。它并不能阻止定时攻击，也不会让它们变得更加困难。

要了解原因，请查看睡眠文档。具体来说，第一个参数的含义：

暂停时间（秒）。

因此，你的应用程序需要0.3秒才能在不睡觉的情况下做出响应。睡眠需要0.3、1.3、2.3等…

所以实际上，为了得到我们关心的部分（时间差），我们只需要去掉整数部分：

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

但让我们更进一步。假设您使用usleep随机睡眠。这要精细得多。这是以微秒为单位的睡眠。

嗯，测量是在15-50纳米秒的范围内进行的。因此，睡眠的颗粒度仍然是测量值的100倍。所以我们可以平均到一微秒：

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

并且仍然拥有有意义的数据。

你可以更进一步，使用time_nanosleep，它可以达到纳秒级的精度。

然后你就可以开始篡改数字了。

但数据仍然存在。随机性的美妙之处在于，你可以将其平均：

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

运行足够多次，你会得到一个漂亮的图形。你会发现大约有10000个不同的数字，所以你可以平均掉随机性，推导出"私有"15。

因为表现良好的随机性是无偏的，所以在足够大的样本上进行统计检测是非常容易的。

所以我想问的问题是：

既然你能正确地解决问题，为什么还要用类似睡眠的技巧呢

Answer 2

Anthony Ferrara在他的博客文章《这都是关于时间的》中回答了这个问题。我强烈推荐这篇文章。

很多人，当他们听到定时攻击时，会想"好吧，我只添加一个随机延迟！这会起作用的！"。但事实并非如此。

Answer 3

如果攻击者唯一可观察到的副通道是响应时间，那么对于单个请求来说，这是可以的。

然而，如果攻击者发出足够的请求，这种随机延迟可能会平均化，正如@Scott引用ircmaxell博客文章的回答所指出的那样：

因此，如果我们需要运行49000次测试以获得15ns的准确度（没有随机延迟），那么我们可能需要100000或1000000次测试来获得相同的准确度和随机延迟。或者可能是100000000。但数据仍然存在。

举个例子，让我们估计一次定时攻击需要获得一个有效的160位会话ID（如PHP）的请求数量，每个字符6位，长度为27个字符。假设，就像链接的答案一样，一次只能对一个用户进行攻击（因为他们将用户存储在cookie中进行查找）。

以博客文章中最好的情况100000为例，排列的数量将是100,000 * 2^6 * 27。

平均而言，攻击者会在排列次数的一半找到该值。

这使得从定时攻击中发现会话ID所需的请求数为86400000。相比之下，在没有您建议的定时保护的情况下，这是42336000个请求（假设像博客文章一样准确度为15ns）。

在博客文章中，测试的最长长度14，平均耗时0.01171秒，这意味着86400000将耗时1011744秒，相当于11天17小时2分24秒。

随机睡眠能防止定时攻击吗？

这取决于使用随机睡眠的上下文，以及它所保护的字符串的比特强度。如果是"让我登录"功能，这是链接问题中的上下文，那么攻击者花11天时间使用定时攻击来强行获取值可能是值得的。然而，这是假设完美的条件（即，对于测试的每个字符串位置，应用程序的响应时间相当一致，并且没有重置或翻转ID）。此外，攻击者的这些类型的活动会产生大量噪音，很可能会通过IDS和IPS被发现。

它不能完全阻止它们，但会使攻击者更难执行它们。使用像hash-equals这样的东西会更容易、更好，它可以完全防止定时攻击，前提是字符串长度相等。

您建议的代码

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

请注意，PHP rand函数在加密方面不安全：

小心此函数不会生成加密安全值，不应用于加密目的。如果您需要加密安全的值，请考虑使用openssl_random_pseudo_bytes()。

这意味着，从理论上讲，攻击者可以预测rand将生成什么，然后使用这些信息来确定应用程序的响应时间延迟是否是由于随机睡眠造成的。

实现安全性的最佳方法是假设攻击者知道你的源代码——对攻击者来说唯一保密的东西应该是密钥和密码——假设他们知道所使用的算法和功能。如果你仍然可以说你的系统是安全的，即使攻击者确切地知道它是如何工作的，那么你将在很大程度上做到这一点。像rand这样的函数通常设置为以当前时间为种子，因此攻击者可以确保他们的系统时钟设置为与您的服务器相同，然后请求验证他们的生成器是否与您的生成器匹配。

因此，最好避免像rand这样不安全的随机函数，并将实现更改为使用openssl_random_pseudo_bytes，这将是不可预测的。

此外，根据ircmaxell的评论，sleep不够精细，因为它只接受一个整数来表示秒数。如果您要尝试这种方法，请查看随机数为纳秒的time_nanosleep。

这些指针应该有助于保护您的实现免受这种类型的定时攻击。

Answer 4

这种方法可以完全防止定时攻击吗？还是只是让工作更努力？

ircmaxell已经回答了为什么这只会让工作更加困难，

但是防止PHP中定时攻击的解决方案通常是

/**
 * 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}");
}

使用这种方法，您的代码可能是

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

不利的一面是，你应该选择一个大幅度的数字，这意味着你会浪费相对多的时间睡觉。。在我的笔记本电脑上，我不得不用0.2（200毫秒）将2个精确的1-GiB字符串与Core i7-8565U（一个奇怪的2018年中端笔记本电脑cpu，我从未听说过）进行比较

这个循环：

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));
}

以大约65兆字节/int（65126401）的

（但你需要多久对65MB以上的字符串进行一次恒定时间比较？我想这并不常见）

• 你可能会认为"；则攻击者可以发送一个巨大的字符串进行比较，并检查抛出异常需要多长时间；但我认为这不起作用，===首先检查两个字符串是否具有相同的长度，如果它们具有不同的长度则短路，只有当攻击者能够将两个字符串的长度设置为足够大以使超时时，这种攻击才应该起作用

• 今天，我们有了原生的hashequals（）函数来比较长度完全相同的字符串，但hashequals）不会保护您免受不同长度的字符串的影响，而上面的函数会。