3

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

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

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

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

4

1 回答 1

3

应该可以调整任何具有提前退出的通用算法以满足要求。但这很棘手，因为如果 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;
}
于 2013-06-02T12:54:42.340 回答