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

Question

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

phpsecuritycryptographytimingtiming-attack

18

时序攻击（Timing attack）是密码学中的一种侧信道攻击，攻击者尝试通过分析加密算法执行所需的时间来破解加密系统。

实际上，为了防止时序攻击，我正在使用从这个回答中提取出来的以下函数：

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

或者是增强睡眠的随机性

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

这种做法能完全防止时序攻击吗？还是只是让攻击变得更困难了？

- DrKey

2

只需使用 hash_equals()，然后结束它。 - Scott Arciszewski

4个回答

9

如果攻击者唯一可观察的旁路信道是响应时间，则对于单个请求，这是可以接受的。

然而，如果攻击者发出足够多的请求，则该随机延迟可能会平均为@Scott's answer中引用ircmaxell's blog post所述：

因此，如果我们需要运行49,000次测试以获得15ns的准确性[没有随机延迟]，那么我们可能需要100,000或1,000,000次测试才能获得相同的准确性。或者可能需要1亿次。但数据仍然存在。

作为一个例子，让我们估计一下一个时序攻击需要多少个请求才能获得一个有效的160位会话ID，比如PHP 每个字符6位，长度为27个字符。假设像链接的答案中所说，攻击只能针对一个用户进行（因为他们将要查找的用户存储在cookie中）。

从博客文章中得出最好的情况，即100,000次尝试，排列的数量将是100,000 * 2^6 * 27。

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

这就给出了发现会话ID所需的请求次数为86,400,000次。这与没有您提议的时间保护的情况下的42,336,000次请求进行比较（假设精度为15ns，就像博客文章中所述）。

在博客文章中，取测试的最长长度14，平均需要0.01171秒，这意味着86,400,000个请求需要1,011,744秒，相当于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。

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

- SilverlightFox

1

另外，sleep()接受秒作为参数。这种粒度太低了，无法隐藏任何东西... - ircmaxell

在我看来，随机睡眠不是一个好的选择。即使使用 openssl_random_pseudo_bytes，因为好的随机数是均匀分布的。这意味着当你进行足够的请求时，你总是会增加平均睡眠时间。 - slowjack2k

9

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

许多人听说时序攻击时，会想：“好吧，我只需要添加一个随机延迟！那就可以解决了！”但并不是这样的。

- Scott Arciszewski

2

@Phil_1984_ 1) 粒度。大多数“随机”睡眠都在毫秒级别，而我们测量的差异在10纳秒级别。2) 局部性。硬件上的代理可以监视CPU负载并从活动中分辨出睡眠（在虚拟机中等）。3) 统计上，这些随机睡眠可以平均掉。4) 这只是一个临时措施。它没有减轻问题，也没有解决根本问题，只是让你看不到它。这是模糊不清。 - ircmaxell

@Phil_1984_ 仅仅进行哈希不足以保证安全（因为哈希是可预测的）。你需要使用随机字符串进行哈希（最好使用HMAC）：https://www.isecpartners.com/blog/2011/february/double-hmac-verification.aspx （请注意，该文章使用了静态密钥，但我们中的许多人建议使用随机密钥）。 - ircmaxell

是的，如果您对正确解决方案过敏，使用带有nonce的双重HMAC确实可以使时序攻击变得不切实际。 - Scott Arciszewski

虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。仅有链接的答案如果链接页面发生更改可能会变得无效。 - Michael Irigoyen

好文章。它确实说“将时间夹紧”到最小值会起作用。我怀疑至少一些询问如何添加随机时间的人实际上是在考虑这种所谓的“夹紧”，但他们没有表达清楚。 - Buttons840

显示剩余2条评论

1

这种方法能完全防止时序攻击吗？还是只是让攻击更加困难？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);
}

缺点是你需要选择一个较大的数字，意味着相对较长的时间会浪费在睡眠中。就我个人而言，在我的笔记本电脑上，为了比较2个完全相同的1GB字符串，我不得不使用0.2（200毫秒），使用了一款2018年中端奇怪的Core i7-8565U笔记本电脑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兆字节/整数(65126401)时，程序会崩溃。

(但是，你有多少次需要比较超过65MB的字符串?我想这种情况并不经常发生)

你可能会认为“那么攻击者可以发送一个巨大的字符串进行比较，并检查抛出异常所需的时间”，但我不认为这会起作用，===首先检查两个字符串是否具有相同的长度，并在它们具有不同长度时短路，只有当攻击者能够将两个字符串的长度都设置足够大以超时时，这样的攻击才能奏效。
今天我们有本地的hash_equals()函数来比较完全相同长度的字符串，但hash_equals()不能保护您免受不同长度的字符串的攻击，而上面的函数可以。

- hanshenrik

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ircmaxell · Accepted Answer

这种方法能够完全防止时间攻击吗？或者只是让攻击更困难了一些？

都不是。它既不能防止时间攻击，也不会使攻击变得更加困难。

要理解原因，请查看sleep文档，特别是第一个参数的含义：

“停止时间（以秒为单位）。”

因此，如果您的应用程序在没有sleep的情况下需要0.3秒才能响应，则使用sleep需要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。

由于行为良好的随机性是无偏的，通过足够大的样本进行统计分析就相当容易检测到。

所以我要问的问题是：

当你可以正确解决问题时，何必费心去处理类似睡眠的hack呢？