英文:
How does ConstantTimeByteEq work?
问题
ConstantTimeByteEq函数是Go语言密码学库中的一个函数。它的作用是比较两个字节x和y是否相等，如果相等则返回1，否则返回0。
该函数的实现原理如下：
- 首先，通过按位异或操作符
^计算x和y的异或结果，并取反得到z。 - 然后，将z与右移4位后的z进行按位与操作，再将结果赋值给z。
- 接着，将z与右移2位后的z进行按位与操作，再将结果赋值给z。
- 最后，将z与右移1位后的z进行按位与操作，再将结果赋值给z。
- 返回z的整数值。
通过这种方式，函数能够在不泄露比较结果的情况下，以恒定的时间执行字节比较操作，从而提高密码学算法的安全性。
英文:
In Go's crytography library, I found this function ConstantTimeByteEq. What does it do, how does it work?
// 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)
}
答案1
得分: 8
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 中的任何零传播到结果中，开始进行与运算：
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
因此，当 x == y 时返回1，否则返回0。
通常情况下，如果 x 和 y 都为零，则比较所需的时间可能比其他情况少。该函数试图使所有调用的时间相同，而不管其输入值的大小。这样，攻击者就无法使用基于时间的攻击。
英文:
x ^ y is x XOR y, where the result is 1 when the arguments are different and 0 when the arguments are the same:
x = 01010011
y = 00010011
x ^ y = 01000000
^(x ^ y) negates this, i.e., you get 0 when the arguments are different and 1 otherwise:
^(x ^ y) = 10111111 => z
Then we start shifting z to the right for masking its bits by itself. A shift pads the left side of the number with zero bits:
z >> 4 = 00001011
With the goal of propagating any zeros in z to the result, start ANDing:
z = 10111111
z >> 4 = 00001011
z & (z >> 4) = 00001011
also fold the new value to move any zero to the right:
z = 00001011
z >> 2 = 00000010
z & (z >> 2) = 00000010
further fold to the last bit:
z = 00000010
z >> 1 = 00000001
z & (z >> 1) = 00000000
On the other hand, if you have x == y initially, it goes like this:
z = 11111111
z (& z >> 4) = 00001111
z (& z >> 2) = 00000011
z (& z >> 1) = 00000001
So it really returns 1 when x == y, 0 otherwise.
Generally, if both x and y are zero the comparison can take less time than other cases. This function tries to make it so that all calls take the same time regardless of the values of its inputs. This way, an attacker can't use timing based attacks.
答案2
得分: 6
它完全按照文档所说的做：它检查x和y是否相等。从功能的角度来看，它只是x == y，非常简单。
以这种神秘的位操作方式进行x == y可以防止定时侧攻击算法：x == y可能会被编译成代码，如果x = y，则执行速度更快，如果x != y（或反之亦然），则执行速度较慢，这是由于CPU中的分支预测。攻击者可以利用这一点来了解加密例程处理的数据，并因此破坏安全性。
英文:
It does exactly what the documentation says: It checks if x and y are equal. From a functional point it is just x == y, dead simple.
Doing x == y in this cryptic bit-fiddling-way prevent timing side attacks to algorithms: A x == y may get compiled to code which performs faster if x = y and slower if x != y (or the other way around) due to branch prediction in CPUs. This can be used by an attacker to learn something about the data handled by the cryptographic routines and thus compromise security.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论