关于恒定时间算法和字符串比较的说明

Question

我有一个问题要理解两种不同的字符串比较方法.给出以下函数来比较两个字符串.此功能在Symfony-Framework安全组件中用于比较用户登录过程中的密码.

/**
 * Compares two strings.
 *
 * This method implements a constant-time algorithm to compare strings.
 *
 * @param string $knownString The string of known length to compare against
 * @param string $userInput   The string that the user can control
 *
 * @return Boolean true if the two strings are the same, false otherwise
 */
function equals($knownString, $userInput)
{
    // Prevent issues if string length is 0
    $knownString .= chr(0);
    $userInput .= chr(0);

    $knownLen = strlen($knownString);
    $userLen = strlen($userInput);

    $result = $knownLen - $userLen;

    // Note that we ALWAYS iterate over the user-supplied length
    // This is to prevent leaking length information
    for ($i = 0; $i < $userLen; $i++) {
        // Using % here is a trick to prevent notices
        // It's safe, since if the lengths are different
        // $result is already non-0
        $result |= (ord($knownString[$i % $knownLen]) ^ ord($userInput[$i]));
    }

    // They are only identical strings if $result is exactly 0...
    return 0 === $result;
}

来源:起源片​​段

我有问题要理解equals()功能和简单比较之间的区别===.我写了一个简单的工作示例来解释我的问题.

给定字符串:

$password1 = 'Uif4yQZUqmCWRbWFQtdizZ9/qwPDyVHSLiR19gc6oO7QjAK6PlT/rrylpJDkZaEUOSI5c85xNEVA6JnuBrhWJw=='; 
$password2 = 'Uif4yQZUqmCWRbWFQtdizZ9/qwPDyVHSLiR19gc6oO7QjAK6PlT/rrylpJDkZaEUOSI5c85xNEVA6JnuBrhWJw==';
$password3 = 'iV3pT5/JpPhIXKmzTe3EOxSfZSukpYK0UC55aKUQgVaCgPXYN2SQ5FMUK/hxuj6qZoyhihz2p+M2M65Oblg1jg==';

示例1(按预期行事)

echo $password1 === $password2 ? 'True' : 'False'; // Output: True
echo equals($password1, $password2) ? 'True' : 'False'; // Output: True

示例2(按预期行事)

echo $password1 === $password3 ? 'True' : 'False'; // Output: False
echo equals($password1, $password3) ? 'True' : 'False'; // Output: False

我读到了关于Karp Rabin算法但是我不确定该equals()函数是否代表了Karp Rabin算法,并且一般我不理解维基百科的文章.

另一方面我读到这个equals()功能会阻止暴力攻击吗？有人可以解释一下它的优点equals()是什么吗？或者有人可以给我一个例子,哪里===会失败并equals()做正确的工作,所以我能理解其优势？

又是什么固定时间的算法是什么意思？我认为恒定时间与实时无关,或者如果我错了？

Answer 1

这个函数只是一个普通的字符串比较函数.这不是拉宾卡普.无论评论说什么,它都不是恒定时间,而是线性时间.它也不能阻止暴力攻击.

这个怎么运作:

1. 如果正确的和用户提供的密码长度不同,请使用$ result!= 0
2. 迭代用户提供的密码,xor每个字符与正确密码的相应字符(如果正确的密码更短,继续通过它),按位或每个结果与$ result.

由于只是按位或使用,如果任何字符不同,$ result将是!= 0.步骤1是必需的,否则,如果真实密码是"abc",则接受用户输入"abca".

为什么有时使用这种字符串比较函数

我们假设我们以通常的方式比较字符串,正确的密码是"bac".我们还假设我可以精确地测量密码检查完成所需的时间.

我(用户)尝试a,b,c...他们不工作.

然后,我试试aa.该算法比较前两个字母 - bvs a,看到它是错误的,并返回false.

我现在尝试bb.算法比较bvs b,它们匹配,所以继续写字母#2,比较avs b,看错了,返回false.现在,因为我能够准确地计算算法的执行时间,所以我知道密码以"b"开头,因为第二次传递花费的时间比第一次更长 - 我知道匹配的第一个字母.

因此,我想ba,bb,bc...他们失败.

现在我检查baa,bbb看到baa运行速度慢,所以第二个字母是a.这样,一个字母,我可以用O(cN)次数来确定密码,而不是蛮力会采取的O(c ^ N).

它通常不是一个值得关注的问题,因为这种解释可能会使它听起来很合理,因为攻击者不太可能将字符串比较计算到如此高的准确度.但有时它可以.