15

查看 Go 标准库，有一个ConstantTimeByteEq函数，如下所示：

func ConstantTimeByteEq(x, y uint8) int {
    z := ^(x ^ y)
    z &= z >> 4
    z &= z >> 2
    z &= z >> 1

    return int(z)
}

现在，我了解需要对恒定时间字符串（数组等）进行比较，因为常规算法可能会在第一个不相等元素后短路。但是在这种情况下，两个固定大小的整数的常规比较不是在 CPU 级别上的恒定时间操作吗？

4

3 回答 3

11

除了将结果设为 1 或 0 而不是 true 或 false （允许后续按位操作）之外，这一点可能会避免分支错误预测。

比较它的编译方式：

var a, b, c, d byte
_ =  a == b && c == d

=>

0017 (foo.go:15) MOVQ    $0,BX
0018 (foo.go:15) MOVQ    $0,DX
0019 (foo.go:15) MOVQ    $0,CX
0020 (foo.go:15) MOVQ    $0,AX
0021 (foo.go:16) JMP     ,24
0022 (foo.go:16) MOVQ    $1,AX
0023 (foo.go:16) JMP     ,30
0024 (foo.go:16) CMPB    BX,DX
0025 (foo.go:16) JNE     ,29
0026 (foo.go:16) CMPB    CX,AX
0027 (foo.go:16) JNE     ,29
0028 (foo.go:16) JMP     ,22
0029 (foo.go:16) MOVQ    $0,AX

有了这个：

var a, b, c, d byte
_ =  subtle.ConstantTimeByteEq(a, b) & subtle.ConstantTimeByteEq(c, d)

=>

0018 (foo.go:15) MOVQ    $0,DX
0019 (foo.go:15) MOVQ    $0,AX
0020 (foo.go:15) MOVQ    $0,DI
0021 (foo.go:15) MOVQ    $0,SI
0022 (foo.go:16) XORQ    AX,DX
0023 (foo.go:16) XORQ    $-1,DX
0024 (foo.go:16) MOVQ    DX,BX
0025 (foo.go:16) SHRB    $4,BX
0026 (foo.go:16) ANDQ    BX,DX
0027 (foo.go:16) MOVQ    DX,BX
0028 (foo.go:16) SHRB    $2,BX
0029 (foo.go:16) ANDQ    BX,DX
0030 (foo.go:16) MOVQ    DX,AX
0031 (foo.go:16) SHRB    $1,DX
0032 (foo.go:16) ANDQ    DX,AX
0033 (foo.go:16) MOVBQZX AX,DX
0034 (foo.go:16) MOVQ    DI,BX
0035 (foo.go:16) XORQ    SI,BX
0036 (foo.go:16) XORQ    $-1,BX
0037 (foo.go:16) MOVQ    BX,AX
0038 (foo.go:16) SHRB    $4,BX
0039 (foo.go:16) ANDQ    BX,AX
0040 (foo.go:16) MOVQ    AX,BX
0041 (foo.go:16) SHRB    $2,BX
0042 (foo.go:16) ANDQ    BX,AX
0043 (foo.go:16) MOVQ    AX,BX
0044 (foo.go:16) SHRB    $1,BX
0045 (foo.go:16) ANDQ    BX,AX
0046 (foo.go:16) MOVBQZX AX,BX

虽然后一个版本更长，但它也是线性的——没有分支。

于 2013-08-21T21:44:17.997 回答
6

不必要。而且很难说编译器在进行优化后会发出什么。对于高级“比较一个字节”，您最终可能会得到不同的机器代码。在侧通道中泄漏一点点可能会将您的加密从“基本牢不可破”更改为“希望不值得破解所需的钱”。

于 2013-08-21T20:47:09.993 回答
0

如果调用该函数的代码根据结果立即分支，则使用恒定时间方法不会提供太多额外的安全性。另一方面，如果要在一堆不同的字节对上调用函数，保持结果的总和，并且只根据最终结果进行分支，那么外部窥探者可能能够确定是否最后一个分支已被采用，但不知道之前的哪个字节比较是造成它的原因。

话虽如此，但我不确定在大多数用例中我是否看到了将方法的输出提炼为零或一的麻烦。简单地保持一个运行计数notEqual = (A0 ^ B0); notEqual |= (A1 ^ B1); notEqual |= (A2 ^ B2); ...将达到相同的效果并且速度更快。

于 2013-08-30T23:25:43.540 回答