密码学.NET，避免定时攻击 [英] Cryptography .NET, Avoiding Timing Attack

问题描述

我在浏览crackstation.net网站时发现了这段代码，评论如下:

I was browsing crackstation.net website and came across this code which was commented as following:

在长度恒定的时间内比较两个字节数组.使用这种比较方法是为了避免使用定时攻击从在线系统中提取密码哈希，然后进行离线攻击.

Compares two byte arrays in length-constant time. This comparison method is used so that password hashes cannot be extracted from on-line systems using a timing attack and then attacked off-line.

 private static bool SlowEquals(byte[] a, byte[] b)
    {
        uint diff = (uint)a.Length ^ (uint)b.Length;
        for (int i = 0; i < a.Length && i < b.Length; i++)
            diff |= (uint)(a[i] ^ b[i]);
        return diff == 0;
    }

谁能解释一下这个函数实际是如何工作的，为什么我们需要将长度转换为无符号整数，以及这种方法如何避免定时攻击?diff |= (uint)(a[i] ^ b[i]); 行有什么作用?

Can anyone please explain how does this function actual works, why do we need to convert the length to an unsigned integer and how this method avoids a timing attack? What does the line diff |= (uint)(a[i] ^ b[i]); do?

推荐答案

这会根据a和bdiff>.

This sets diff based on whether there's a difference between a and b.

它通过始终遍历 a 和 b 两者中较短的一个来避免时间攻击，无论是否存在比这更早的不匹配.

It avoids a timing attack by always walking through the entirety of the shorter of the two of a and b, regardless of whether there's a mismatch sooner than that or not.

diff |= (uint)(a[i] ^ (uint)b[i]) 将 a 的字节与 a 进行异或b 的对应字节.如果两个字节相同，则为 0，如果不同，则为非零.然后它 ors 那与 diff.

The diff |= (uint)(a[i] ^ (uint)b[i]) takes the exclusive-or of a byte of a with a corresponding byte of b. That will be 0 if the two bytes are the same, or non-zero if they're different. It then ors that with diff.

因此，如果在迭代中发现输入之间存在差异，则 diff 将在迭代中设置为非零.一旦 diff 在循环的任何迭代中被赋予非零值，它将通过进一步的迭代保持非零值.

Therefore, diff will be set to non-zero in an iteration if a difference was found between the inputs in that iteration. Once diff is given a non-zero value at any iteration of the loop, it will retain the non-zero value through further iterations.

因此，如果在 a 和 b 的对应字节之间发现任何差异，则 diff 中的最终结果将非零，并且0 仅当 a 和 b 的所有字节(和长度)都相等时.

Therefore, the final result in diff will be non-zero if any difference is found between corresponding bytes of a and b, and 0 only if all bytes (and the lengths) of a and b are equal.

然而，与典型的比较不同，这将始终执行循环，直到两个输入中较短的一个中的所有字节都与另一个中的字节进行比较.典型的比较会提前结束，一旦发现不匹配，循环就会中断:

Unlike a typical comparison, however, this will always execute the loop until all the bytes in the shorter of the two inputs have been compared to bytes in the other. A typical comparison would have an early-out where the loop would be broken as soon as a mismatch was found:

bool equal(byte a[], byte b[]) { 
    if (a.length() != b.length())
        return false;

    for (int i=0; i<a.length(); i++)
       if (a[i] != b[i])
           return false;
    return true;
}

这样，根据返回 false 所花费的时间量，我们可以了解(至少近似)在 a 和b.假设长度的初始测试需要 10 ns，循环的每次迭代需要另外 10 ns.基于此，如果它在 50 ns 内返回 false，我们可以快速猜测我们的长度是正确的，并且 a 和 b 的前四个字节匹配.

With this, based on the amount of time consumed to return false, we can learn (at least an approximation of) the number of bytes that matched between a and b. Let's say the initial test of length takes 10 ns, and each iteration of the loop takes another 10 ns. Based on that, if it returns false in 50 ns, we can quickly guess that we have the right length, and the first four bytes of a and b match.

即使不知道确切的时间量，我们仍然可以使用时间差异来确定正确的字符串.我们从长度为 1 的字符串开始，一次增加一个字节，直到我们看到返回 false 的时间增加.然后我们遍历第一个字节中所有可能的值，直到我们看到另一个增加，这表明它已经执行了循环的另一个迭代.对连续的字节继续使用相同的方法，直到所有字节都匹配并且我们得到 true 的返回.

Even without knowing the exact amounts of time, we can still use the timing differences to determine the correct string. We start with a string of length 1, and increase that one byte at a time until we see an increase in the time taken to return false. Then we run through all the possible values in the first byte until we see another increase, indicating that it has executed another iteration of the loop. Continue with the same for successive bytes until all bytes match and we get a return of true.

原文仍然存在少许位的定时攻击——虽然我们不能轻易根据定时确定正确字符串的内容，但我们至少可以找到字符串长度基于时间.由于它只比较两个字符串中较短的一个，我们可以从长度为 1 的字符串开始，然后是 2，然后是 3，依此类推，直到时间变​​得稳定.只要时间在增加，我们建议的字符串就会比正确的字符串短.当我们给它更长的字符串，但时间保持不变时，我们知道我们的字符串比正确的字符串长.正确的字符串长度将是需要最长测试时间的最短字符串.

The original is still open to a little bit of a timing attack -- although we can't easily determine the contents of the correct string based on timing, we can at least find the string length based on timing. Since it only compares up to the shorter of the two strings, we can start with a string of length 1, then 2, then 3, and so on until the time becomes stable. As long as the time is increasing our proposed string is shorter than the correct string. When we give it longer strings, but the time remains constant, we know our string is longer than the correct string. The correct length of string will be the shortest one that takes that maximum duration to test.

这是否有用取决于情况，但无论如何，它显然会泄露一些信息.为了真正实现最大的安全性，我们可能希望将随机垃圾附加到真实字符串的末尾，使其成为用户输入的长度，因此时间与输入的长度成正比，无论它是否更短、相等到，或比正确的字符串长.

Whether this is useful or not depends on the situation, but it's clearly leaking some information, regardless. For truly maximum security, we'd probably want to append random garbage to the end of the real string to make it the length of the user's input, so the time stays proportional to the length of the input, regardless of whether it's shorter, equal to, or longer than the correct string.

这篇关于密码学.NET，避免定时攻击的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！