1

だから私はハッシュテーブルとレインボーテーブルをよりよく理解しようとしており、読んでいるとコツをつかみ始めているように感じます. 次のような理解度チェックの質問があります。

「sha-256 パスワードを格納するハッシュ テーブルがあり、テーブル全体をメモリに格納する必要があり、4GB のメモリがある場合、いくつのパスワードをクラックできますか? 各チェーンに 20 個のパスワードがあるレインボー テーブルを使用する場合、何個のパスワードをクラックできますか? (パスワードを 10 文字と仮定して)"

これは、私が読んでいたものについて何か知っているかどうか、完全に疑問に思いました。これが私がこれまでに思いついたものです。

すべての ShaA-256 ハッシュのサイズが常に 256 ビットであり、1 メガバイトに 8388608 ビットが含まれていることがわかっている場合、1 メガバイトあたり 32768 個の SHA-256 パスワードに相当します。4000 メガバイトなので、32768 に 4000 を掛けると、131072000 個のパスワードがメモリに保存されます。

しかし、それをレインボー テーブルの 20 個のチェーン パスワードに適用するにはどうすればよいでしょうか? レインボー テーブルにはハッシュとその逆が格納されているので、より多くのスペースを占有する一方で、はるかに高速に解決できると考えました。失うスペースの量と、失うパスワードの数を決定するための公式または何かはありますか?

どんな助けや知識も大歓迎です。あなたの時間と知恵に感謝します。:)

4

2 に答える 2

1

次のようなレインボーテーブルを想像してください。

テーブルはチェーンのリストです

チェーンはパスワードとハッシュです

しかし待ってください...このパスワードをP1と呼び、チェーン内のハッシュをHeと呼びましょう

さらに、いくつかのハッシュ関数 h(x) とリダクション関数 R(x) があるとしましょう。これは、h(x) の出力をキースペース内の任意だが均等に分散されたパスワードに割り当てます。

チェーン長が 20 の場合、単純に次のようになります。

P1 を取る ... H1=h(P1)を計算する
P2 を R(h1) として計算する ... H2 を h(P2)として計算する Pn を R(hn-1) として計算する ... Hn
を h(Pn) として計算する
P20 と H20 を持っている 20 の手順...これは彼でもあります

ここで、P1 と He ... 別名 P1 と H20 を保存します

これはチェーンです

テーブルはリストで構成されます...チェーンのソートされたリスト...ハッシュでソートされますクラックするハッシュxがある場合は、次のようにします。

割り当て y = x見つかった場合は
テーブルで y を探し
、対応するチェーンのパスワードを取得し、チェーンを形成したすべてのパスワード/ハッシュ タプルを再構築してパスワードを探します...
見つからない場合は、y = h( を割り当てますR(y)) 一致するか、チェーンの長さに達するまで最初からやり直します

だから...あなたの最初の質問に関して...

単純な辞書を使用してパスワードを検索する場合、パスワードとハッシュのペアを保存する必要があります...ハッシュごとに1つのパスワード... 1つのペア/タプルにより、1つのパスワードを攻撃できます

レインボー テーブルを使用する場合でも、メモリにあるハッシュごとに 1 つのパスワードを保存することになります...しかし、時間メモリのトレードオフにより、より多くのハッシュを攻撃することができます...理想的な世界では、チェーンの長さ...現実の世界では、R() がどれだけ優れているかに依存します...衝突が発生する可能性があり、1 つのパスワード/ハッシュが複数のチェーンに存在し、レインボーテーブルに冗長性が導入されます

于 2016-02-01T20:56:11.303 に答える
0

レインボー テーブルでは、クラックできるハッシュの一部しか保存できません。ハッシュはチェーンで構成されており、チェーンの最初と最後の要素のみを保存する必要があります。したがって、チェーンの長さが 20 の場合、チェーンごとに 2 つのハッシュを格納し、20 のハッシュをクラックできます。したがって、10倍のゲインがあります。

したがって、レインボー テーブルを使用しない場合の結果 (131072000) に 10 を掛けると、チェーン長が 20 のレインボー テーブルを使用した場合にクラックできるパスワードの数が得られます。

実際、チェーンはハッシュとパスワードを交互に使用して構成されています。したがって、チェーンの最初と最後をハッシュではなくパスワードとして保存することを選択できます。パスワード空間はハッシュ空間よりも明らかに小さいため、各チェーンの最初と最後をパスワードの圧縮形式として保存し、さらに多くのチェーンを保存できるメモリを確保できます。

于 2016-09-05T13:30:49.293 に答える