掩蔽是否有效阻止侧通道攻击？

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

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

\n\n

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

\n\n\n\n

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

\n\n

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

\n\n

\n

1. 比较a < b可能会也可能不会花费恒定时间，具体取决于编译器（和 CPU）。如果它被编译为简单的位操作，它可能是常数时间的；如果它被编译为使用条件跳转，则很可能不是。

\n

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

   \n\n

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

\n

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

\n

1. 手动检查生成的汇编代码（例如，在您不期望的地方查找跳转指令），以及

\n

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

\n

\n\n

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

\n