5

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

这种技术是否容易受到基于指令时序、功率、射频发射或其他我不知道的事情的侧信道攻击？（作为参考，我知道 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
4

2 回答 2

3

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

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

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

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

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

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

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

避免第一个问题的一种可能方法是将比较替换为显式位操作，如下所示：

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

但是，请注意，这仅在我们可以确定a并且b相差小于 2 31的情况下等同于您的原始代码。如果不能保证，我们必须在减法之前将变量转换为更长的类型，例如：

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

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

通常，确保不会发生此类时序泄漏的唯一方法是：

  1. 手动检查生成的汇编代码（例如，在你没想到的地方寻找跳转指令），以及

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

显然，您还需要为您希望支持的编译器和目标平台的每个组合单独执行此操作。

于 2015-01-11T15:24:11.927 回答
2

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

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

于 2015-01-11T12:11:13.583 回答