(注意:通过"常数时间",我的意思是当其中一个输入固定而不是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不会在AMD64上短路此循环,即使在-O3(我检查了生成的机器代码).但是,我不知道C标准中的任何内容会阻止某些聪明的编译器识别出如果c非零,那么该函数只能返回false.
如果你愿意接受大的性能损失和概率比较而不是确定性的比较,那么实现恒定时间比较的更偏执方式是计算两个输入的加密哈希值并比较哈希值; 如何对哈希进行比较并不重要,因为除非攻击者能够计算哈希的前映像,否则它不能进行未知值的连续近似.很难想象编译器有足够的智能来优化它,但我无法保证它不会发生.更偏执的方法是使用HMAC和特定于实例的键而不是简单的哈希,尽管我仍然可以想象一个奇迹般智能的优化器,它可以识别出无论使用什么键,它编译的算法只是一种缓慢的方式.进行字符串比较并相应地优化.通过添加额外的复杂层,调用共享库等,我可以使我的比较任意难以优化,但我仍然不能保证没有符合标准的编译器可以使我的比较短路并让我容易受到攻击定时攻击.
有没有办法实现有效的,确定性的,恒定时间的比较,保证始终按照C标准工作？如果没有,任何流行的C(或C++)编译器或库是否提供这样的方法？请引用你的消息来源.