运行时不依赖于数据内容的字符串算法

Question

有经典的算法来检查两个相同长度的字符串是否相等，同时防止定时攻击。

foldl bitwiseOr 0 (zipWith bitwiseXor firstString secondString) == 0

在这种情况下，恶意用户让机器将隐藏的 secret 字符串与输入字符串进行比较，并报告它们是否相同。例如，考虑一种密码被加密但未散列的暴力密码攻击。如果匹配的初始字符越多，则确定密码不匹配的时间越长，如果用户可以衡量效果，他们可以从头到尾逐步猜出密码。

但是是否有任何通用算法可以回答哪个字符串更大，或者如果它们相等，从而抵御这种攻击？

Answer 1

应该可以调整任何具有提前退出的通用算法以满足要求。但这很棘手，因为如果 CPU 发现你只是在无用地旋转，它会更快地执行代码。

最安全的设计是消除循环内的所有分支。不允许 if、&& 或 ||，仅允许按位运算符。

对于整理 strcmp，我们要记住字符串之间的第一个差异以及哪一侧更大。因此，根据是否发现差异，算法自然会做完全不同的事情。我们可以使用位掩码模拟一个分支。

int obscure_strcmp( char const *l, char const *r ) {
    int result = 0;

    do {
        // compute result in case we need it
        int diff = * r - * l; // positive if l < r, negative if r < l
        int diff_pos = diff > 0; // 1 if l < r
        int diff_neg = - ( diff < 0 ); // -1 if r < l

        // assign result if it was still zero
        unsigned mask = - ( result == 0u ); // all 1's if waiting for a diff
        result |= ( diff_pos | diff_neg ) & mask;

    } while ( * l ++ && * r ++ );
    return result;
}