2

文字列比較の 2 つの異なる方法を理解するのに問題があります。2 つの文字列を比較する次の関数が与えられます。この関数は 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;
}

origin:オリジン スニペット

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 Algorithmについて読みましたが、equals()関数がKarp Rabin Algorithmを表しているかどうかはわかりません。一般的に、ウィキペディアの記事を理解していませんでした。

一方、equals()ブルート フォース攻撃を防ぐ機能があると読みましたが、そうですか。誰かが利点が何であるかを説明できますかequals()? ===または、誰かが失敗して正しい動作をする例を教えてくれるequals()ので、利点を理解できますか?

そして、一定時間アルゴリズムとはどういう意味ですか? 定数時間はリアルタイムとは何の関係もないと思いますか、それとも間違っているのでしょうか?

4

1 に答える 1

5

この関数は、通常の文字列比較関数です。ラビン・カープではありません。コメントの内容に関係なく、一定時間ではなく、線形時間です。また、ブルート フォース攻撃も防ぎません。

使い方：

  1. 正しいパスワードとユーザー提供のパスワードの長さが異なる場合は、 $result != 0 を作成します
  2. ユーザーが提供したパスワードを反復し、その各文字を正しいパスワードの対応する文字と xor し (正しいパスワードが短い場合は、円で続けます)、ビット単位または $result を使用して各結果を返します。

ビット単位の or のみが使用されるため、いずれかの文字が異なる場合、$result は != 0 になります。ステップ 1 が必要です。そうしないと、実際のパスワードが「abc」の場合にユーザー入力「abca」が受け入れられるためです。

そのような文字列比較関数が時々使用される理由

通常の方法で文字列を比較し、正しいパスワードが「bac」であるとしましょう。また、パスワード チェックが完了するまでにかかる時間を正確に測定できると仮定します。

私 (ユーザー) は、、、... を試しますaがb、うまくいきcません。

次に、試してみaaます。アルゴリズムは最初の 2 文字 - bvsaを比較し、それが間違っていることを確認して false を返します。

で試してみbbます。アルゴリズムはbvsを比較bし、それらが一致するため、文字 #2 に進み、avsを比較bし、間違っていると判断し、false を返します。これで、アルゴリズムの実行時間を正確に計ることができたので、パスワードが「b」で始まることがわかりました。これは、2 回目のパスが最初のパスよりも時間がかかったためです。最初の文字が一致したことがわかりました。

だから私は試してみますba、、...彼らは失敗します。bbbc

今baa、bbb私は をチェックしbaaますa。このようにして、文字ごとに、ブルートフォースがかかる O(c^N) ではなく、O(cN) 回の試行でパスワードを決定できます。

攻撃者がこのような正確さで文字列の比較を行う可能性は低いため、通常は、この説明が聞こえるほど大きな問題にはなりません。しかし、そうなる場合もあります。

于 2013-09-20T12:31:02.483 に答える