21

语境

OpenSSL 中的功能 BN_consttime_swap很漂亮。在此代码段中，condition已计算为0or (BN_ULONG)-1：

#define BN_CONSTTIME_SWAP(ind) \
    do { \
            t = (a->d[ind] ^ b->d[ind]) & condition; \
            a->d[ind] ^= t; \
            b->d[ind] ^= t; \
    } while (0)
…
    BN_CONSTTIME_SWAP(9);
…
    BN_CONSTTIME_SWAP(8);
…
    BN_CONSTTIME_SWAP(7);

目的是为了确保更高级别的 bignum 操作花费恒定的时间，这个函数要么交换两个 bignum，要么在恒定的时间内将它们留在原处。当它把它们留在原地时，它实际上读取每个 bignum 的每个单词，计算一个与旧单词相同的新单词，并将结果写回原始位置。

目的是这将花费与 bignums 被有效交换的时间相同的时间。

在这个问题中，我假设一个现代的、广泛使用的架构，例如 Agner Fog 在他的优化手册中描述的架构。还假定将 C 代码直接转换为汇编（没有 C 编译器取消程序员的努力）。

问题

我试图理解上面的构造是否被描述为“尽力而为”的恒定时间执行，还是完美的恒定时间执行。

特别是，我担心调用a函数时 bignum 已经在 L1 数据缓存中BN_consttime_swap，而函数返回后的代码立即开始处理 bignum的情况a。在现代处理器上，可以同时运行足够多的指令，以便在使用 bignum 时复制不会在技术上完成a。允许调用后的指令BN_consttime_swap工作的机制a是内存依赖推测。为了论证，让我们假设幼稚的内存依赖推测。

这个问题似乎归结为：

当处理器最终检测到BN_consttime_swap从内存中读取的代码（与推测相反，已写入函数内部）时，它是在检测到地址已被写入后立即取消推测执行，还是允许自己当它检测到已写入的值与已经存在的值相同时保留它？

在第一种情况下，BN_consttime_swap看起来它实现了完美的恒定时间。在第二种情况下，它只是尽力而为的常数时间：如果没有交换 bignums，则调用之后的代码的执行BN_consttime_swap速度将比交换它们时快得多。

即使在第二种情况下，这看起来也可以在可预见的未来（只要处理器保持足够幼稚）通过为两个 bignums 中的每一个的每个单词写入一个与两个可能的 final 不同的值来修复值之前再次写入旧值或新值。在某些时候可能需要使用volatile类型限定符以防止普通编译器过度优化序列，但听起来仍然可行。

注意：我知道商店转发，但商店转发只是一个捷径。它不会阻止在它应该之后的写入之前执行读取。在某些情况下它会失败，尽管在这种情况下人们不会期望它会失败。

4

3 回答 3

17

还假定将 C 代码直接转换为汇编（没有 C 编译器取消程序员的努力）。

我知道这不是你问题的重点，我知道你知道这一点，但我需要咆哮一分钟。这甚至没有资格作为提供恒定时间执行的“尽力而为”的尝试。编译器被许可检查 的值，如果为零condition则跳过整个过程。condition混淆 的设置condition使这种情况不太可能发生，但不能保证。

据称“恒定时间”代码不应该用 C 编写，句号。即使今天是固定时间，在您测试的编译器上，一个更智能的编译器也会出现并击败您。您的一位用户将在您使用此编译器之前使用此编译器，他们不会意识到您已将他们暴露在风险之下。我所知道的实现恒定时间的确切方法有三种：专用硬件、程序集或生成机器代码的 DSL 以及恒定时间执行的证明。

一边咆哮一边讨论手头的实际架构问题：假设一个愚蠢的天真编译器，这段代码在我熟悉到足以评估这个问题的 µarches 上是恒定的时间，我希望它大体上是正确的，原因很简单：力量。我希望检查存储队列或缓存是否存储的值与已经存在的值匹配并有条件地短路存储或避免在每个存储上弄脏缓存行消耗的能量比在极少数情况下节省的能量更多避免一些工作。但是，我不是 CPU 设计者，也不敢代表他们发言，因此请与几汤匙盐一起食用，并在假设这是真的之前先咨询一下。

于 2015-03-19T16:18:29.647 回答
3

这篇博文以及作者亨利就这个问题发表的评论应该被认为是权威的，因为任何人都应该期待。我将在此处复制后者以供存档：

我不认为用相同的值覆盖内存位置的情况有实际用途。我认为答案是在当前的处理器中，store 的值无关紧要，只有地址很重要。

在学术界，我听说过两种消除内存歧义的方法：基于地址或基于值。据我所知，目前的处理器都做基于地址的消歧。

我认为当前的微基准有一些证据表明该值不相关。许多情况涉及将相同的值重复存储到相同的位置（尤其是偏移量 = 0 的那些）。这些并没有异常快。

基于地址的方案使用存储队列和加载队列来跟踪未完成的内存操作。加载检查存储队列以查找地址匹配（此加载是否应该执行存储到加载转发而不是从缓存中读取？），而存储检查加载队列（此存储是否破坏了我允许执行的稍后加载的位置早期的？）。这些检查完全基于地址（存储和加载冲突的地方）。这种方案的一个优点是它是存储到加载转发之上的一个相当简单的扩展，因为那里也使用了存储队列搜索。

基于值的方案摆脱了关联搜索（即更快、更低功耗等），但需要更好的预测器来进行存储到加载转发（现在您必须猜测是否转发以及在哪里转发，而不是搜索平方）。这些方案通过在提交时重新执行加载并检查它们的值是否正确来检查顺序违规（和不正确的转发）。在这些方案中，如果您的存储冲突（或犯了其他错误）仍然导致正确的结果值，则不会将其检测为排序违规。

未来的处理器能否转向基于价值的方案？我怀疑他们可能会。它们是在 2000 年代中期（？）提出的，以降低内存执行硬件的复杂性。

于 2015-04-29T16:50:34.533 回答
1

恒定时间实现背后的想法并不是在恒定时间内实际执行所有操作。这永远不会发生在无序架构上。要求是时序分析不能泄露任何秘密信息。为了防止这种情况，基本上有两个要求：

a) 不要使用任何秘密作为循环的停止条件，或作为分支的谓词。如果不这样做，您将面临分支预测攻击https://eprint.iacr.org/2006/351.pdf

b) 不要使用任何秘密作为内存访问的索引。这会导致缓存定时攻击http://www.daemonology.net/papers/htt.pdf

至于您的代码：假设您的秘密是“条件”并且可能是 a 和 b 的内容，则代码是完全恒定的时间，因为它的执行不依赖于 a、b 和条件的实际内容。当然 a 和 b 在内存中的位置会影响循环的执行时间，但不会影响秘密的 CONTENTS。那是假设当然条件是以恒定时间方式计算的。至于 C 优化：编译器只能根据它知道的信息来优化代码。如果“条件”是真正的秘密，编译器应该无法识别它的内容并进行优化。如果可以从您的代码中扣除它，那么编译器很可能会针对 0 情况进行优化。

于 2015-04-03T16:38:49.323 回答