(Note：这里的“常数时间”是指当其中一个输入固定时，机器周期的常数，而不是O（1）。这是密码学上下文中该术语的标准含义。）
将固定值与相同大小的未知值进行比较，以使有关固定值的信息不会通过计时泄漏的最常见方法是使用XOR循环：
bool compare(const char* fixed, const char* unknown, size_t n)
{
char c = 0;
for (size_t i=0; i<n; ++i)
c |= fixed[i] ^ unknown[i];
return (c == 0);
}字符串
GCC 4.6.3和CLANG 3.0没有在AMD 64上短路这个循环，即使在-O3（我检查了生成的机器代码）。然而，我不知道C标准中有什么可以阻止一些聪明的编译器识别出如果c是非零的，那么函数只能返回false。
如果你愿意接受一个大的性能冲击和一个概率比较而不是一个确定性的比较，实现一个恒定时间比较的更偏执的方法是计算两个输入的加密哈希值并比较哈希值;如何比较散列并不重要，因为除非攻击者可以计算散列的原像，它不能对未知值进行逐次逼近。很难想象编译器会聪明到优化它，但我不能保证它不会发生。更偏执的方法是使用HMAC与特定于示例的密钥，而不是简单的哈希，尽管我仍然可以想象一个奇迹般聪明的优化器，它认识到无论使用什么键，它编译的算法只是一种进行字符串比较的缓慢方式，并相应地进行优化。通过增加额外的复杂性层，调用共享库等，我可以使我的比较任意难以优化，但我仍然不能保证没有一个符合标准的编译器可以短路我的比较，让我容易受到计时攻击。
有没有办法实现一个高效的、确定性的、恒定时间的比较，并且保证总是符合C标准？如果没有，有没有流行的C（或C++）编译器或库提供这样的方法？请引用您的来源。
1条答案
按热度按时间r8uurelv1#
“as-if”规则要求access to volatile objects be performed as written，所以我认为下面的方法可能有效：
字符串
即使编译器可以静态地确定两个输入数组是否不同，它仍然必须为
c的所有中间存储生成代码。所以生成的代码应该总是运行与n成比例的时间。版本2，响应AlexD的有用评论：
型
即使编译器可以静态地确定函数的返回值，它仍然必须发出代码来从头到尾读取两个输入数组，并在这些加载之间写入
c。优化仍然可以消除计算（XOR和OR），但内存行为将是更明显的时序特征。从功耗方面来看，攻击者仍然可以区分两者。如果我们想消除return语句中的数据依赖分支，我们可以使用类似于Go语言的ConstantTimeByteEq
只是需要注意的是，the 'as-if' rule的相关位已从C98/03更改为C11：
1)在每个序列点，所有volatile对象的值都是稳定的（之前的求值完成，新的求值尚未开始）（直到C11）
1)对volatile对象的访问（读和写）严格按照它们所在的表达式的语义发生。特别是，它们不被重新排序。（C11起）