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，对于x和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            = 00001010
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均为零，则比较所需的时间将少于其他情况。该函数试图使之不顾其输入值而使所有调用花费相同的时间。这样，攻击者无法使用基于定时的攻击。