内存依赖推测是否会阻止 BN_consttime_swap 成为恒定时间？
Does memory dependence speculation prevent BN_consttime_swap from being constant-time?
上下文
OpenSSL 中的 function BN_consttime_swap 是一件美妙的事情。在此代码段中，condition 已计算为 0 或 (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 在他的 optimization manuals 中所描述的架构。还假定将 C 代码直接转换为汇编代码（无需 C 编译器取消程序员的工作）。
问题
我想知道上面的构造是“尽力而为”的恒定时间执行，还是完美的恒定时间执行。
我特别关心调用函数BN_consttime_swap时bignuma已经在L1数据缓存中的场景，而函数[=66=之后的代码] 立即开始研究 bignum a。在现代处理器上，可以同时运行足够多的指令，以便在使用 bignum a 时从技术上讲不会完成复制。允许调用 BN_consttime_swap 后的指令在 a 上工作的机制是 内存依赖推测 。为了论证，让我们假设 naive memory dependence speculation。
问题似乎归结为：
当处理器最终检测到BN_consttime_swap之后从内存中读取的代码与推测相反，被写入函数内部时，它是否会尽快取消推测执行它检测到该地址已被写入，或者当它检测到已写入的值与已经存在的值相同时，它是否允许自己保留它？
在第一种情况下，BN_consttime_swap 看起来它实现了完美的恒定时间。在第二种情况下，它只是尽力而为的恒定时间：如果 bignums 没有被交换，调用 BN_consttime_swap 之后的代码的执行将明显快于它们被交换的情况。
即使在第二种情况下，这看起来也可以在可预见的未来解决（只要处理器保持足够天真），对于两个 bignums 中的每一个的每个单词，写一个不同的值在再次写入旧值或新值之前，从两个可能的最终值。在某些时候可能需要使用 volatile 类型限定符，以防止普通编译器过度优化序列，但听起来仍然可行。
注意：我知道 store forwarding，但存储转发只是一种捷径。它不会阻止读取被执行 before 它应该在写入之后。在某些情况下它会失败，尽管在这种情况下人们不会期望它会失败。
Straightforward translation of the C code to assembly (without the C compiler undoing the efforts of the programmer) is also assumed.
我知道这不是你问题的重点，我知道你知道这一点，但我需要吐槽一下。这甚至不符合 "best effort" 提供恒定时间执行的尝试。编译器被授权检查 condition 的值，如果 condition 为零则跳过整个过程。混淆 condition 的设置可以降低这种情况发生的可能性，但不能保证。
据称 "constant-time" 代码不应该用 C 语言编写，句号。即使今天是恒定时间，在你测试的编译器上，一个更聪明的编译器也会出现并打败你。您的一位用户会在您之前使用此编译器，他们不会意识到您让他们面临的风险。我所知道的实现恒定时间的方法只有三种：专用硬件、程序集或生成机器代码的 DSL 以及恒定时间执行的证明。
抛开咆哮，关于手头的实际架构问题：假设一个愚蠢天真的编译器，这段代码是 µarches 上的恒定时间，我已经足够熟悉来评估这个问题，我希望它大致是正确的原因很简单：权力。我希望如果存储的值与已经存在的值匹配并有条件地使存储短路或避免弄脏每个存储上的缓存行，那么检查存储队列或缓存会消耗比在极少数情况下保存的能量更多的能量避免一些工作。但是，我不是 CPU 设计师，也不敢代表他们发言，因此请多加几汤匙盐，在假设这是真的之前请咨询一位。
恒定时间实现背后的想法并不是在恒定时间内实际执行所有操作。这永远不会发生在无序架构上。
要求是不能通过时序分析泄露秘密信息。
为了防止这种情况，基本上有两个要求：
a) 不要使用任何秘密作为循环的停止条件，或作为分支的谓词。如果不这样做，您将面临分支预测攻击 https://eprint.iacr.org/2006/351.pdf
b) 不要使用任何秘密作为内存访问的索引。这导致缓存定时攻击http://www.daemonology.net/papers/htt.pdf
至于你的代码：假设你的秘密是 "condition" 并且可能是 a 和 b 的内容代码是完全恒定的时间，因为它的执行不依赖于 a 的实际内容， b 和条件。当然 a 和 b 在内存中的位置会影响循环的执行时间，但不会影响机密的 CONTENTS。
那当然是假设条件是以恒定时间的方式计算的。
至于 C 优化：编译器只能根据它知道的信息优化代码。如果 "condition" 是真正的秘密，编译器应该无法辨别它的内容并进行优化。如果它可以从您的代码中扣除，那么编译器很可能会针对 0 情况进行优化。
作者 Henry 就此问题所做的 blog post, and the comments 应该被认为是权威的，正如任何人都应该允许的那样。我将在此处复制后者以供存档：
I didn’t think the case of overwriting a memory location with the same value had a practical use. I think the answer is that in current processors, the value of the store is irrelevant, only the address is important.
Out here in academia, I’ve heard of two approaches to doing memory disambiguation: Address-based, or value-based. As far as I know, current processors all do address-based disambiguation.
I think the current microbenchmark has some evidence that the value isn’t relevant. Many of the cases involve repeatedly storing the same value into the same location (particularly those with offset = 0). These were not abnormally fast.
Address-based schemes uses a store queue and a load queue to track outstanding memory operations. Loads check the store queue to for an address match (Should this load do store-to-load forwarding instead of reading from cache?), while stores check the load queue (Did this store clobber the location of a later load I allowed to execute early?). These checks are based entirely on addresses (where a store and load collided). One advantage of this scheme is that it’s a fairly straightforward extension on top of store-to-load forwarding, since the store queue search is also used there.
Value-based schemes get rid of the associative search (i.e., faster, lower power, etc.), but requires a better predictor to do store-to-load forwarding (Now you have to guess whether and where to forward, rather than searching the SQ). These schemes check for ordering violations (and incorrect forwarding) by re-executing loads at commit time and checking whether their values are correct. In these schemes, if you have a conflicting store (or made some other mistake) that still resulted in the correct result value, it would not be detected as an ordering violation.
Could future processors move to value-based schemes? I suspect they might. They were proposed in the mid-2000s(?) to reduce the complexity of the memory execution hardware.
上下文
OpenSSL 中的 function BN_consttime_swap 是一件美妙的事情。在此代码段中，condition 已计算为 0 或 (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 在他的 optimization manuals 中所描述的架构。还假定将 C 代码直接转换为汇编代码（无需 C 编译器取消程序员的工作）。
问题
我想知道上面的构造是“尽力而为”的恒定时间执行，还是完美的恒定时间执行。
我特别关心调用函数BN_consttime_swap时bignuma已经在L1数据缓存中的场景，而函数[=66=之后的代码] 立即开始研究 bignum a。在现代处理器上，可以同时运行足够多的指令，以便在使用 bignum a 时从技术上讲不会完成复制。允许调用 BN_consttime_swap 后的指令在 a 上工作的机制是 内存依赖推测 。为了论证，让我们假设 naive memory dependence speculation。
问题似乎归结为：
当处理器最终检测到BN_consttime_swap之后从内存中读取的代码与推测相反，被写入函数内部时，它是否会尽快取消推测执行它检测到该地址已被写入，或者当它检测到已写入的值与已经存在的值相同时，它是否允许自己保留它？
在第一种情况下，BN_consttime_swap 看起来它实现了完美的恒定时间。在第二种情况下，它只是尽力而为的恒定时间：如果 bignums 没有被交换，调用 BN_consttime_swap 之后的代码的执行将明显快于它们被交换的情况。
即使在第二种情况下，这看起来也可以在可预见的未来解决（只要处理器保持足够天真），对于两个 bignums 中的每一个的每个单词，写一个不同的值在再次写入旧值或新值之前，从两个可能的最终值。在某些时候可能需要使用 volatile 类型限定符，以防止普通编译器过度优化序列，但听起来仍然可行。
注意：我知道 store forwarding，但存储转发只是一种捷径。它不会阻止读取被执行 before 它应该在写入之后。在某些情况下它会失败，尽管在这种情况下人们不会期望它会失败。
Straightforward translation of the C code to assembly (without the C compiler undoing the efforts of the programmer) is also assumed.
我知道这不是你问题的重点，我知道你知道这一点，但我需要吐槽一下。这甚至不符合 "best effort" 提供恒定时间执行的尝试。编译器被授权检查 condition 的值，如果 condition 为零则跳过整个过程。混淆 condition 的设置可以降低这种情况发生的可能性，但不能保证。
据称 "constant-time" 代码不应该用 C 语言编写，句号。即使今天是恒定时间，在你测试的编译器上，一个更聪明的编译器也会出现并打败你。您的一位用户会在您之前使用此编译器，他们不会意识到您让他们面临的风险。我所知道的实现恒定时间的方法只有三种：专用硬件、程序集或生成机器代码的 DSL 以及恒定时间执行的证明。
抛开咆哮，关于手头的实际架构问题：假设一个愚蠢天真的编译器，这段代码是 µarches 上的恒定时间，我已经足够熟悉来评估这个问题，我希望它大致是正确的原因很简单：权力。我希望如果存储的值与已经存在的值匹配并有条件地使存储短路或避免弄脏每个存储上的缓存行，那么检查存储队列或缓存会消耗比在极少数情况下保存的能量更多的能量避免一些工作。但是，我不是 CPU 设计师，也不敢代表他们发言，因此请多加几汤匙盐，在假设这是真的之前请咨询一位。
恒定时间实现背后的想法并不是在恒定时间内实际执行所有操作。这永远不会发生在无序架构上。 要求是不能通过时序分析泄露秘密信息。 为了防止这种情况，基本上有两个要求：
a) 不要使用任何秘密作为循环的停止条件，或作为分支的谓词。如果不这样做，您将面临分支预测攻击 https://eprint.iacr.org/2006/351.pdf
b) 不要使用任何秘密作为内存访问的索引。这导致缓存定时攻击http://www.daemonology.net/papers/htt.pdf
至于你的代码：假设你的秘密是 "condition" 并且可能是 a 和 b 的内容代码是完全恒定的时间，因为它的执行不依赖于 a 的实际内容， b 和条件。当然 a 和 b 在内存中的位置会影响循环的执行时间，但不会影响机密的 CONTENTS。 那当然是假设条件是以恒定时间的方式计算的。 至于 C 优化：编译器只能根据它知道的信息优化代码。如果 "condition" 是真正的秘密，编译器应该无法辨别它的内容并进行优化。如果它可以从您的代码中扣除，那么编译器很可能会针对 0 情况进行优化。
作者 Henry 就此问题所做的 blog post, and the comments 应该被认为是权威的，正如任何人都应该允许的那样。我将在此处复制后者以供存档：
I didn’t think the case of overwriting a memory location with the same value had a practical use. I think the answer is that in current processors, the value of the store is irrelevant, only the address is important.
Out here in academia, I’ve heard of two approaches to doing memory disambiguation: Address-based, or value-based. As far as I know, current processors all do address-based disambiguation.
I think the current microbenchmark has some evidence that the value isn’t relevant. Many of the cases involve repeatedly storing the same value into the same location (particularly those with offset = 0). These were not abnormally fast.
Address-based schemes uses a store queue and a load queue to track outstanding memory operations. Loads check the store queue to for an address match (Should this load do store-to-load forwarding instead of reading from cache?), while stores check the load queue (Did this store clobber the location of a later load I allowed to execute early?). These checks are based entirely on addresses (where a store and load collided). One advantage of this scheme is that it’s a fairly straightforward extension on top of store-to-load forwarding, since the store queue search is also used there.
Value-based schemes get rid of the associative search (i.e., faster, lower power, etc.), but requires a better predictor to do store-to-load forwarding (Now you have to guess whether and where to forward, rather than searching the SQ). These schemes check for ordering violations (and incorrect forwarding) by re-executing loads at commit time and checking whether their values are correct. In these schemes, if you have a conflicting store (or made some other mistake) that still resulted in the correct result value, it would not be detected as an ordering violation.
Could future processors move to value-based schemes? I suspect they might. They were proposed in the mid-2000s(?) to reduce the complexity of the memory execution hardware.