1週間前、 LinkedInのハッシュデータベースがリークしましたが 、他の人にとってはこのイベント自体は注目に値するかもしれませんが、私にとっては、まず、パスワードを解読する現代の可能性を分析する能力を意味します。 また、パスワードの中に「パスワード」という単語が見つかった回数や、6文字の組み合わせを整理するのにかかる時間については説明しません。 むしろ、複雑なパスワードが数時間で「クラッキング」される可能性があることでユーザーを怖がらせます。 そして、プログラマーにこれを効果的に実装する方法を教えます。ささやかな贈り物として、大量監査のために書いたプログラムを添付します。 また、簡単な結論でレインボーテーブルの使用に関するいくつかの教育プログラムがあります。
したがって、特別な辞書やレインボーテーブルを使用せずに、1時間で平均的な動作構成で約250万個のパスワードを「回復」することができました。 見つかったパスワードの中には、16文字の英数字の組み合わせがあり、単一のコピーではありません。
しかし、順番に始めましょう。 650万の新しいハッシュ（合計で5,787,239の一意）のデータベースに出会ったとしたら、合理的な（たとえば7日間）の時間で最大数のパスワードを回復する方法はありますか？
- レインボーテーブル ;
- 直接検索
- 辞書攻撃（ルールあり）;
- 周波数分析。
小さな教育プログラム 。 多くの人は、 レインボーテーブルの素晴らしい特性を信じています。おそらく、それらは「一度にすべてを壊すことができるもの」だと思われます。 さらに、これは大量の監査（数千または数百万のハッシュ）にとっては完全に不適切な大きな誤解です。 したがって、「クラッカーはレインボーテーブルを生成できる！」というフレーズを忘れてください。
なんで？ 100ギガバイトのサイズの脆弱なレインボーテーブルのセットを使用すると、98％の確率で1つのレジスタで8文字の英数字にパスワードを回復できます。 ちなみに、そのようなテーブルは、かなり強力なマシンで数か月のうちにどこかで生成できますが、何らかの神聖な贈り物のように、それらをすでに私たちと一緒に置いておきましょう。
このようなテーブルで1つのハッシュ値のパスワードを見つけるのに必要な時間は約1分です。 この間、100Gbでchain_length ハッシュ、削減、および検索操作を実行する必要があります。
異なるハッシュ値に対する複数のパスワードを一度に最適に検索する機能は存在しません。 ハッシュごとに、個別のレインボーチェーンを構築し、テーブルで検索する必要があります。 したがって、検索には約570万分が必要です。
これは約10年です。 したがって、この場合の私たちの神の贈り物は、ささやかな贈り物とは見なされません。
ただし、レインボーテーブルの適切なセットは、パスワードを1つのハッシュ値に数分で復元するのに役立ちます（長さが8〜9文字の同じ控えめな制限がある場合）。
直接列挙は、大量のハッキングのためのレインボーテーブルとは多少異なります -ハッシュ値の大きなセットで列挙値を見つけるために簡単に最適化されます。
セット{a..z0..9} ^ 8から各行を取得し、そのハッシュを計算し、この場合にLinkedInが慎重に提供したハッシュ値のデータベースを調べる必要があります。
また、検索はこの場合最適化が非常に簡単な操作です。 今後、私のプログラムでは、このような大規模なベースでもO（1）検索を実現しました。
検索の基本は単純なフィルタリングです。明らかに見つからないハッシュを検索しようとしないでください。 サイズSIZE、約100メガバイトのビット値の配列（検査）を作成し、ハッシュ値をこの配列のインデックスにマップする関数を作成します。 奇妙なことに、そのようなオブジェクトはハッシュ関数とも呼ばれますが、暗号化とは呼ばれず、しばしば畳み込みと呼ばれます。 LinkedInハッシュごとに、畳み込みを計算し、チェック配列の対応するビットに「1」を書き込みます。
並べ替えるとき、受信値からの畳み込み== jを考慮し、チェックアップ[j]を見て、0がある場合、セット内でそのような値を探すことはありません（これはO（1）でチェックされます）。 それ以外の場合は、O（log（N））に既に対応しているバイナリ検索を使用します。
数値に戻ると、同様の最適化を使用した直接列挙には、同じハードウェアで約1か月、ビデオカードで数日かかります。
つまり、大量のハッキングの場合、直接列挙することでさえ、テーブルよりも有益です。
しかし、8文字より長いパスワードを処理したいので、 辞書が役立ちます。 辞書はとてもクールです！ それらにはすでに誰かのパスワードが含まれており、私たちのものである可能性は、ランダムなラインよりもはるかに高くなっています。 また、特定の一連の置換ルールを追加すると、驚異的な結果が得られます。 この場合、そのような列挙の速度は、直接列挙の速度に匹敵します。
ただし、1つの欠点があります。辞書はどこかから来る必要があります。 つまり、単語の選択はランダムではなく、何らかの分析の結果でなければなりません。 そして、グローバルネットワークの広大さから辞書をダウンロードすると、完全な「ジャンク」を取得できます。その検索効率は直接検索よりも低くなります（たとえば、パスワードとしてほとんど誰も入れない行を具体的に入力します）。
自分でやる
私の意見では、 周波数分析に関連した大量のハッキング戦略が最適になりました。 そして、ハッシュのマージされたリスト以外は何も必要ありません。
最初のステップ。 キーボードから入力できるすべての文字のセット（5〜6文字まで）を直接検索します。 実際、この長さのすべてのパスワードを取得するタスクはありません。さらに分析するために、特定の数十万を取得するだけです。 6文字が短すぎる場合は、7〜8文字を使用できますが、列挙のために範囲全体を使い果たす必要はありません。
主なことは、5〜10分間機能することです。
そこで、いくつかのパスワードを見つけました。 これで、頻度分析を実施して、連続する可能性が最も高い文字の組み合わせを強調できます。 たとえば、「パス」はこれらの組み合わせの1つですが、LinkedInと「リンク」でも同様です。
ステップ2 頻繁な組み合わせの辞書とそれ自体の連結の検索を開始します。 今思い出しますが、本質が明確でない場合は、以前のメモを読むことをお勧めします。
5〜10分間も機能させ、前回よりもパスワードを見つける方がはるかに高速になることに注意してください。
そして第三のステップ。 見つかったパスワードの「クリティカルマス」を収集した後、たとえば10分の1の頻度で分析を繰り返し、取得した辞書に従って検索を再開します。 今、あなたはもうやめられません-彼は仕事をするでしょう。
現時点では、検索は停止せずに2時間機能し、毎秒50〜100個のパスワードを検出します。
結果の辞書の例を次に示します。dl.dropbox.com / u / 243445 / md5h / relevant.txt
辞書の「断片から組み立てる」ことで、パスワードのセキュリティを確認できます 。
4つ以下のピースで十分な場合、それは悪いので、変更してください。
なんとか「壊れた」
linkedinmel1234, andrea71103245, hockey101155239, magmag624222, carlito5657224, linda@790212, supercow779212, jesus143mary143, linkedin#239133, linkedinpassword123, thepassword1776000, 13051987159000, meatballstew123, latenightbreeze, whatthedillyo, friendofkellyg, hannah11emily9, linkedin7barry5, linkedin.passwd, linkedinrocksforeva, philip23marcus, 54fordpickup, nabe1959@, ge0rgin@, #1dust67, logic123tree456, ramgopal@123456, Jk971423, tiger!376400, ...
UPDは、見つかったパスワードの統計を計算した画面です（必要に応じて他のパラメーターを計算できます）。
パスワードの長さも、特殊文字の使用も、レジスタと数字の組み合わせも、ランダム性の保存もありません。
プログラム
約束どおり-これがなんとかできたプログラムです。 ちなみに、結果を繰り返す（または最高の結果を得る）のは自由です。
ソース： dl.dropbox.com/u/243445/md5h/src.7z
バイナリ： dl.dropbox.com/u/243445/md5h/MD5BLAST.exe
SHA-ではなくMD5-と呼ばれていることに驚かないでください。なぜなら、空白として、私がすでに取り上げたプログラムを取り上げたからです。
CUDA Toolkitは引き続き必要です： developer.nvidia.com/cuda-toolkit-32-downloads#Windows
GTX460のSHA1の辞書検索速度（リストに570万の一意のハッシュがある場合）-60 mpwd / s以上。 そして、「低速」をscらないでください-これは同じです：
* SHA1;
* 570万ハッシュの検索。
*任意の長さの文字列からの辞書の連結。
このタスクのためのより高速なアナログはまだありません。
検索を開始するには、ハッシュをhash_list.txtファイルに保存し、辞書をwords.txtファイルに保存して呼び出す必要があります。
MD5Blast words.txt 3 0.0
ここで、3は最大次数（辞書の連結の数）、0.0はパーセントでの初期の進捗です。
上記の図のステップ1の場合、words.txtには、キーボードから入力されたすべての文字が含まれている必要があります（各行に1つずつ）。
a
b
c
...
関連する組み合わせのリストを取得するには：
MD5Blast _found.txt relevant.txt 1.0 4.0 16.0
ここで、最初のファイルは分析のソースであり、2番目は結果の記録用です（はい、Unix方式ではありません）。
残りの3つのパラメーターは、それぞれ2文字、3文字、および4文字の組み合わせの適応周波数しきい値です（数字が大きいほど、結果として組み合わせが少なくなります。これらを試してみてください）。
小さな結論
- 大量にハッキングされたレインボーテーブルは役に立ちません。
- パスワードの長さ、特殊文字の存在、その無意味さ、さまざまなレジスタは、個々にセキュリティを構成するものではありません。
- saltを使用せずにパスワードをハッシュすることは、パスワードの半分をクリアテキストで保存するようなものです（ 私たちの間違いから学びます ）。
- 周波数分析により、「何もないところから」優れた辞書を生成できます。