security - レインボーテーブルで使用されるリダクション関数はどのように機能しますか？

Question

私はレインボーテーブルについて注意深く読みましたが、1つもわかりません。ハッシュチェーンを構築するために、削減関数が使用されます。どういうわけかハッシュをパスワードにマッピングする関数です。この記事では、リダクション関数はハッシュの逆関数ではなく、単なるマッピングであると述べています。

わかりません-ハッシュ関数の逆でもないマッピングの使用は何ですか？このようなマッピングは実際にどのように機能し、パスワードの推測に役立つのでしょうか。

Answer 1

レインボーテーブルは、事前に計算されたハッシュの大きなテーブルのための「まさに」スマートな圧縮方法です。テーブルの構築中に対応する入力が考慮された場合にのみ、テーブルがハッシュ出力を「反転」できるという考え方です。

各テーブル行（「チェーン」）は、ハッシュ関数呼び出しのシーケンスです。秘訣は、各入力がチェーン内の前の出力から決定論的に計算されるため、次のようになります。

• チェーンの開始点と終了点を保存することで、チェーン全体を「道徳的に」保存し、自由に再構築できます（これは、レインボーテーブルを圧縮方法と見なすことができる場所です）。
• ハッシュ関数の出力からチェーンの再構築を開始できます。

リダクション関数は、ハッシュ関数の出力を適切な入力に変換する接着剤です（たとえば、印刷可能な文字のみで構成される、本物のパスワードのように見える文字列）。その役割は主に、処理するランダムデータが与えられた場合に、ほぼ均一な確率で可能なハッシュ入力を生成できるようにすることです（ハッシュ出力は許容できるほどランダムになります）。削減関数は、特にハッシュ関数自体がどのように機能するかに関して、特定の構造を持つ必要はありません。リダクション関数は、スプリアス衝突をあまり発生させずにチェーンを構築し続けることができるようにする必要があります。

Answer 2

リダクション関数がハッシュの逆関数ではない理由は、ハッシュの真の逆関数が関数ではないためです（「関数」の実際の定義では、1つの入力に対して1つの出力が必要です）。

ハッシュ関数は、対応する入力よりも短い文字列を生成します。鳩の巣原理によ​​り、これは2つの入力が同じ出力を持つことができることを意味します。任意の長さの文字列をハッシュできる場合、実際には、無限の数の文字列が同じ出力を持つ可能性があります。それでも、レインボーテーブルは通常、ハッシュごとに1つの出力しか保持しないため、真の逆になることはできません。

ほとんどのレインボーテーブルが使用するリダクション関数は、「このハッシュを持つ最短の文字列を格納する」です。

Answer 3

生成されるものがパスワードであるかどうかは関係ありません。取得するものはパスワードとしても機能し、元のパスワードと同じようにログインできます。