屏蔽对于阻止旁路攻击是否有效？

Question

我正在使用一些 bigint public-key 加密代码。使用按位掩码来确保计算时序和访问的内存地址与数据值无关是否安全？

这种技术是否容易受到基于指令时序、功率、RF 辐射或其他我不知道的因素的边信道攻击？（作为参考，我知道 RSA 致盲、EC 蒙哥马利阶梯、缓存刷新等技术。）

简单代码示例 (C/C++)：

uint a = (...), b = (...);
if (a < b)
    a += b;

现在翻译为使用恒定时间掩码：

uint a = (...), b = (...);
uint mask = -(uint)(a < b);
a = ((a + b) & mask) | (a & ~mask);

注意a < b为0或1，掩码为0x00000000或0xFFFFFFFF。

类似地，对于高级操作（C++）：

Integer x = (...);
if (x.isFoo())
    x.doBar();

以下是可接受的安全翻译吗？

Integer x = (...);
uint mask = -(uint)x.isFoo();  // Assume this is constant-time
Integer y(x);                  // Copy constructor
y.doBar();                     // Assume this is constant-time
x.replace(y, mask);            // Assume this uses masking

Answer 1

在代码中使用屏蔽或其他技术可能会很粗略，因为编译器会进行您通常不知道的各种优化。您在原始 post 中提到的一些方法要好得多。

一般的经验法则是使用众所周知的加密库，因为它们应该针对侧信道攻击进行强化。否则，您通常可以转换信息、处理信息，然后再转换回结果。这对于 public 密钥加密特别有效，因为它通常是同态的。

Answer 2

这项技术可能是安全的...如果我们假设需要固定时间的操作确实如此，并且如果编译器不更改代码来执行其他操作.

特别是，让我们看一下您的第一个示例：

uint a = (...), b = (...);
uint mask = -(uint)(a < b);
a = ((a + b) & mask) | (a & ~mask);

我看到两种可能在恒定时间内无法运行的合理方式：

比较 a < b 可能会或可能不会花费常数时间，具体取决于编译器（和 CPU）。如果它被编译为简单的位操作，它可能是常数时间的；如果它被编译为使用条件跳转，则很可能不是。
在高优化级别，过于聪明的编译器可能会检测到正在发生的事情（例如，根据比较将代码分成两条路径，并在将它们合并之前分别优化它们) 和 "optimize" 它回到我们试图避免的非常数时间码。

（当然，足够聪明的编译器也有可能将朴素的、看似非恒定时间的代码优化为恒定时间操作，如果它认为这样会更有效率的话！）

避免第一个问题的一种可能方法是用显式位操作代替比较，如：

uint32_t a = (...), b = (...);
uint32_t mask = -((a - b) >> 31);
a = ((a + b) & mask) | (a & ~mask);

但是，请注意，只有当我们可以确定 a 和 b 的差异小于 2³¹ 时，这才等同于您的原始代码.如果不能保证，我们必须在减法之前将变量转换为更长的类型，例如：

uint32_t mask = (uint32_t)(( (uint64_t)a - (uint64_t)b ) >> 32);

综上所述，即使这样也不是万无一失的，因为编译器仍然可以决定将此代码转换为非恒定时间的代码。（例如，在 32 位 CPU 上进行 64 位减法可能会花费可变的时间，具体取决于是否有借位——这正是我们在这里试图隐藏的内容。）

一般来说，确保不会发生此类时间泄漏的唯一方法是：

手动检查生成的汇编代码（例如，在您没有预料到的地方寻找跳转指令），以及
实际对代码进行基准测试，以验证它确实确实需要相同的时间运行，而不管输入如何。

显然，您还需要针对希望支持的编译器和目标平台的每种组合分别执行此操作。

屏蔽对于阻止旁路攻击是否有效？

Is masking effective for thwarting side channel attacks?

c++

c

cryptography

constant-time