优化稳定的恒定时间阵列比较

Question

(注意:通过"常数时间",我的意思是当其中一个输入固定而不是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++)编译器或库是否提供这样的方法？请引用你的消息来源.

Answer 1

"as-if"规则要求对volatile对象的访问按写入方式执行,因此我认为以下内容可能有效:

bool compare(const char* p1, const char* p2, size_t n)
{
    volatile char c = 0;
    for (size_t i=0; i<n; ++i)
        c |= p1[i] ^ p2[i];
    return (c == 0);
}

即使编译器可以静态地确定两个输入数组是否不同,它仍然必须为所有中间存储生成代码c.因此生成的代码应始终运行一段时间n.

版本2,回应AlexD的有用评论:

bool compare(volatile const char* p1, volatile const char* p2, size_t n)
{
    volatile char c = 0;
    for (size_t i=0; i<n; ++i)
        c |= p1[i] ^ p2[i];
    return (c == 0);
}

即使编译器可以静态地确定函数的返回值,它仍然必须发出代码以完整地读取输入数组,从开始到结束,以及c在这些负载之间写入.优化仍然可以消除计算(XOR和OR),但记忆行为将是更加明显的时序特征.在权力方面,攻击者仍然可以分辨出来.

如果我们想要在return语句中消除数据相关的分支,我们可以使用类似于Go的ConstantTimeByteEq的东西

请注意,"as-if"规则的相关位已从C++ 98/03更改为C++ 11:

1)在每个序列点,所有易失性对象的值都是稳定的(先前的评估已完成,新的评估未开始)(直到C++ 11)

1)对易失性对象的访问(读取和写入)严格按照它们出现的表达式的语义发生.特别是,它们没有重新排序.(自C++ 11以来)