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

Question

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

这项技术是否容易受到基于指令时序、功率、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

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

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

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

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

1. 比较a < b取决于编译器(和 CPU)，可能需要也可能不需要固定时间。如果它被编译为简单的位操作，它可能是常数时间的；如果它被编译为使用条件跳转，则很可能不是。

2. 在高优化级别，过于聪明的编译器可能会检测到正在发生的事情(例如，根据比较将代码分成两个路径，并在将它们合并之前分别优化它们)并“优化“它回到我们试图避免的非常数时间码。

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

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

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 位减法可能会花费可变时间，具体取决于是否存在借位——这正是我们在这里试图隐藏的内容。)

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

1. 手动检查生成的汇编代码(例如，在您没有预料到的地方寻找跳转指令)，以及

2. 实际对代码进行基准测试以验证它确实需要相同的时间来运行，而不管输入如何。

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