go - ConstantTimeByteEq 是如何工作的？

Question

在 Go 的密码库中，我找到了这个函数ConstantTimeByteEq。它有什么作用，它是如何工作的？

// ConstantTimeByteEq returns 1 if x == y and 0 otherwise.
func ConstantTimeByteEq(x, y uint8) int {
    z := ^(x ^ y)
    z &= z >> 4
    z &= z >> 2
    z &= z >> 1

    return int(z)
}

Answer 1

x ^ y是x XOR y，其中当参数不同时结果为 1，当参数相同时结果为 0：

x            = 01010011
y            = 00010011
x ^ y        = 01000000

^(x ^ y)否定这一点，即当参数不同时得到 0，否则得到 1：

^(x ^ y)     = 10111111 => z

然后我们开始z向右移动以自行屏蔽其位。移位用零位填充数字的左侧：

z >> 4       = 00001011

为了将任何零传播z到结果中，开始 ANDing：

z            = 10111111
z >> 4       = 00001011
z & (z >> 4) = 00001011

还折叠新值以将任何零向右移动：

z            = 00001011
z >> 2       = 00000010
z & (z >> 2) = 00000010

进一步折叠到最后一位：

z            = 00000010
z >> 1       = 00000001
z & (z >> 1) = 00000000

另一方面，如果你x == y最初有，它是这样的：

z            = 11111111
z (& z >> 4) = 00001111
z (& z >> 2) = 00000011
z (& z >> 1) = 00000001

所以当 时它真的返回 1 x == y，否则返回 0。

通常，如果 x 和 y 都为零，则比较可能比其他情况花费更少的时间。该函数试图使所有调用都花费相同的时间，而不管其输入的值如何。这样，攻击者就不能使用基于时间的攻击。

Answer 2

它完全按照文档所说的那样做：它检查 x 和 y 是否相等。从功能的角度来看，它非常x == y简单。

以这种神秘的比特摆弄x == y方式来防止对算法的时序侧攻击：x == y由于 CPU 中的分支预测，A 可能会被编译为如果 x = y 则执行得更快而 x != y （或相反）则执行得更慢的代码。攻击者可以使用它来了解有关加密例程处理的数据的信息，从而危及安全性。