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都为零,则比较可以比其他情况花费更少的时间.此函数尝试使其无论输入的值如何,所有调用都会占用相同的时间.这样,攻击者就无法使用基于时间的攻击.

Answer 2

它完全符合文档所说的内容:它检查x和y是否相等.从功能的角度来看,这很x == y简单.

这样做x == y在这个隐蔽位摆弄路防止定时侧攻击算法:一个x == y可被编译至其中如果x = y和较慢如果X = Y(或反过来)由于在CPU的分支预测执行得更快代码!.攻击者可以使用它来了解加密例程处理的数据,从而危及安全性.