16

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

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

 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]);有什么作用？

4

2 回答 2

20

这基于和diff之间是否存在差异来设置。ab

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

将的字节与 的对应字节进行diff |= (uint)(a[i] ^ (uint)b[i])异或。如果两个字节相同，则为 0，如果不同，则为非零。然后就是这样。abordiff

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

因此，如果在and的对应字节之间发现任何差异，则最终结果diff将非零，并且仅当 and 的所有字节（和长度）都相等时才为 0。abab

然而，与典型的比较不同，这将始终执行循环，直到两个输入中较短的一个中的所有字节都与另一个中的字节进行比较。一个典型的比较将有一个早期输出，一旦发现不匹配，循环就会被打破：

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。

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

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

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

于 2013-06-06T03:35:54.203 回答
0

此版本持续输入“a”的长度

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

    private static byte GetElem(byte[] x, int i, byte[] c, int i0)
    {
        bool ok = (i < x.Length);
        return (ok ? x : c)[ok ? i : i0];
    }
于 2019-06-11T16:31:17.707 回答