这是什么意思:在长度 - 恒定时间内比较两个字符串$ a和$ b？

Question

在学习密码散列和保存数据库时,我发现了这篇文章:https://crackstation.net/hashing-security.htm#phpsourcecode

一切都很清楚,除了这个功能,我无法理解为什么不使用正常的平等？它的意思是:在长度 - 恒定时间内比较两个字符串$ a和$ b.

// Compares two strings $a and $b in length-constant time.
function slow_equals($a, $b)
{
    $diff = strlen($a) ^ strlen($b);
    for($i = 0; $i < strlen($a) && $i < strlen($b); $i++)
    {
        $diff |= ord($a[$i]) ^ ord($b[$i]);
    }
    return $diff === 0;
}

Answer 1

当您通常比较两个字符串是否相等时,算法会在遇到第一个不等式时停止.

像这样:"aaa"=="aba"？第一个角色？两者都是"一个".第二个字符？"a"不是"b",所以停在这里以节省时间.最后一个角色没有被比较.

在比较安全相关的字符串时,攻击者可能会得到一个线索,哪个字符是正确的,哪个是错误的,因为这样的比较函数的运行时间.

考虑一下使用纯文本密码的不安全做法.如果攻击者可以通过测量密码比较运行的时间长度来判断他猜测的密码的第一个字符是否正确,那么他只需要大约62个猜测(字母字符大小写和数字)来知道第一个字母.使用一个字母,运行时间更长,因为第一个字母与真实密码相同,第二个字母进行了比较.现在第二个字母被迭代了.经过62次猜测后,众所周知.

这会大大削弱安全性,因为不知道第一个字母是否正确,你需要62*62的猜测来获得两个字母的密码.有了线索,你只需要62 + 62猜测.

长度常数比较函数比较所有字母,并且仅在最后显示字符串是否匹配.那样你就无法弄清楚哪个字母已经是正确的了.

散列字符串会混淆一些东西,但是因为你无法知道攻击者是否预先生成了一堆哈希值,或者是在动态生成它们并且如果哈希值不匹配就不会强制使用相应的密码,那么不希望任何人知道该哈希不匹配的地方.它是一个小的附加安全组件,但非常重要.