75ギガバイトのインスタント検索

このページの大量のデータのクイック検索がどのように実装されたかについてです。 そこで、 PvPGNゲームサーバーのハッシュパスワードを検索し、同じハッシュを生成できます。
検索は、モジュールとサードパーティのデータベースを使用せずに、純粋なPHPで記述されています。 原則として、この方法でボリュームを数テラバイトに増やすことができ、場所があります-速度はこれによってそれほど苦しむことはありません。

さらに、最初から最後まで、ブルートフォース、テーブルのハッシュの作成、ソート、そして実際の検索を含むプロセス全体が説明されています。

ブルートフォース

パスワードを検索するためのハッシュテーブルを防ぐには、パスワードを作成するときにパスワードをソルトと混合する必要があります。 しかし、ハッシュのリストがあり、ソルトがどのように追加されるかを知っているので、単純なパスワードは徹底的な検索で見つけることができます。
したがって、PvPGNのハッシュはソルトなしで生成され、大きなキーと値のテーブル（ハッシュパスワード）を生成するというアイデアが生まれました。

C＃でのブルートフォースの最も単純な例を示し、MD5ハッシュ検索のパスワードをソートします。 また、ソートされていないテーブルの生成は、生成されたデータをCSVファイルに追加するだけです。

class Program { static bool _isFound = false; static string _findHash; static string _symbols; static int _pass_lenght; static void Main(string[] args) { _findHash = args[0]; //   _pass_lenght = int.Parse(args[1]); //    _symbols = args[2]; //     byte[] data = new byte[_symbols.Length]; Process(data, 0); Console.ReadLine(); } private static string hash; private static byte[] data_trim; private static string pass; //   static void Process(byte[] data, int index) { //     if (index == _pass_lenght) { data_trim = data.TakeWhile((v, idx) => data.Skip(idx).Any(w => w != 0x00)).ToArray(); //     pass = Encoding.ASCII.GetString(data_trim); hash = GetHash(pass); Console.Write("{0} ", pass); if (hash == _findHash) { _isFound = true; Console.WriteLine("\n\nPassword was found!\n\t{0} = {1}", hash, pass); } return; } //    foreach (byte c in _symbols) { if (_isFound) return; data[index] = c; Process(data, index + 1); } } //  md5 hash   static string GetHash(string value) { MD5 md5 = new MD5CryptoServiceProvider(); byte[] output = md5.ComputeHash(Encoding.ASCII.GetBytes(value)); return BitConverter.ToString(output).Replace("-", "").ToLower(); // hex string } } 

ソースリンクの例。
実行：BruteForce.exe [search_hash] [password_length] [password_characters]

仕分け

結果は、ソートされたデータでのみ機能するバイナリ検索になるため、ハッシュでデータをソートする必要がありました。
考え直すことなく、テスト用の5 GBのデータをコンピューターのMySQLにインポートしました。 インデックスは作成されず、クエリがCSVへのエクスポートでソートを開始しました。

 SELECT hash, pass INTO OUTFILE 'd:\\result.csv' FIELDS TERMINATED BY ',' OPTIONALLY ENCLOSED BY '' LINES TERMINATED BY '\n' FROM hashes ORDER BY hash 

彼には16時間かかりましたが、その間に、TEMPフォルダーに16ギガバイトと25ギガバイトの2つのファイルが作成されました。
しかし、インデックス（数時間作成された）を使用しても、少なくともソート中にギガバイトが吸収されるため、このオプションは依然として私には適していない。 テーブルのサイズが大きくなると、ディスクに十分なスペースがなくなります。

SQLiteでテーブルを作成しようとしましたが、大容量向けに設計されていないため、動作が非常に遅くなりました（1 GBではハッシュ検索に約6秒かかりました）。 MySQLは高速ですが、どちらの場合も最終的なサイズには適さず、元のデータのほぼ2倍以上でした（インデックスを合わせて）。

（ファイル全体をメモリにロードすることなく）ビッグデータのソートに関与したことがないため、最初に登場したアルゴリズムである「 バブルソート 」を採用しました:)。 ファイルが自動的にソートされるようにC＃で小さなコードを作成し、500メガバイトで一晩テストを実行しました。 翌日、ファイルはまだソートされていました。 最小レコードがファイルの最後にある場合、このアルゴリズムでは1行下に移動し、そのようなシフトごとにファイル全体を最初から最後まで処理する必要があるためです。

私は他のソート方法、 マージを探し始め、 ピラミッドが適切であることが判明しました。 私はそれらのハイブリッドの実装を開始しましたが、XPからWindowsにデフォルトで付属しているsortユーティリティに関する情報を偶然見つけました。 結局のところ、彼女は私の仕事に理想的でした！ どのように機能するのかわかりませんが、説明では、1回のパスでファイルをソートすると説明しています（30分で5 GBソート）。 ソート処理中に、ユーティリティは元のファイルの重量と同じだけの追加の空きスペースを必要とします（一時ファイルの場合）。

しかし、ここではすべてがスムーズではなかった。 190 GBのファイルを並べ替えると、3倍のスペースが必要になり、何かを検索して削除し、ディスクスペースを解放しました。 さらに、最終的なファイルに奇妙な「アーティファクト」が現れました。


それらはファイルのランダムな部分で約10になりました。 私は数回ソートを開始し、毎回24時間待機しましたが、依然としてアーティファクトが現れました。 私はこれがなぜ起こったのか理解していませんでした。私は12 GBのRAM、Win7 x64を持っていました。 この間にメモリが「詰まった」と仮定できます。 システムを再起動した後、同じソートが初めて成功しました。

検索する

今では馬鹿げているように思えますが、以前はファイルの検索はファイル全体をメモリにロードするか、ファイル全体を1行ずつ読み取ることによってしか実行できないといつも思っていました。 実際に大きなファイルでバイナリ検索を試してみて、それがどれくらい速く動作するかを見て、PHPでさえ、それは私にとって小さな発見であることが判明しました。 このような検索は、プロセッサをロードしたりメモリを消費したりすることなく、非常に大量のデータを処理するのと同じくらい速く動作します。


バイナリ（別名バイナリ）検索は、次の原理で機能します。

1. 配列は2つに分割され、読み取り位置が中央に移動します。
2. 中央にある現在の値は、目的の値と比較されます
3. desired>の場合、配列の後半が取得されます。必要な<current-前半の場合。
4. アレイのこの半分で1〜3ステップを実行します。

そしてもちろん、バイナリ検索の主な条件は、配列を検索キーでソートする必要があることです。

ファイルでは、バイナリ検索はまったく同じように機能します。 fseek関数を使用してオフセット位置をファイルの中央に移動し、位置を行の先頭に調整して（レコードの中央にヒットした場合）、そこにあるレコードを完全に読み取ります。

1つのBUTではない場合は、これで停止することができます...

部門

PHP_INT_MAXの値（2147483647バイト）を超えるファイルは検索できませんでした。 さらに、fseek関数が-1を返す場合もあれば、すべてが問題ない場合もありますが、オフセットはどこで明確ではありません。 その結果、必要なものがまったく読み取られません。 バグは明らかではありませんでしたが、問題を見つける過程で、バグトラッカーで情報を見つけました。 PHPドキュメントサイトには、2 GBを超えるファイルを検索するfseek関数（fseek64関数）に関するコメントもあります。 これは、ファイルの先頭からではなく、反復によって現在のオフセットから目的の場所まで読み取ることになります。 しかし、私はチェックしました、これも機能しません。

ファイルを分割する必要がありました。 ファイルを破壊するための適切なユーティリティが見つかりませんでした（おそらく検索は不十分でしたが、検索の最初のページには疑わしいインストールしかありませんでした）。 Windowsの兵器庫では、奇妙なことに、そのようなユーティリティはありません。 総司令官では、バイト単位で分割することは不可能ですが、精度が必要でした。
ソースファイルをバイト単位で読み取り、指定されたサイズの個別のファイルに順番に配置する単純なユーティリティをC＃で作成しました。

多分誰かがそれを必要とする、 ここからソースからダウンロードしてください 。
実行：Split.exe [ファイル] [in_bytes]

圧縮

まず、ソートされたデータを2つの個別のファイルに分割しました。それらのハッシュとパスワードがそれぞれ格納されている.hash、.passです。 次に、すべてのデータを1つのヘックスに「パック」しました。 数値はこの方法で最大2回まで簡単にパックされ、各値の長さが固定されているため、欠落しているギャップに0xFが追加されます。

圧縮の実行方法と検索の実行方法は、次の例で明確にわかります（ハッシュ0dd5eac5b02376a456907c705c6f6fb0b5ff67cfのパスワードを探しています）。


0D D5 EAハッシュの最初の6文字。 この方法ではハッシュが重複しますが、それほど多くはありません。 そして、パスワードはすべて保存されているため、1000のパスワードからでも、元のハッシュを非常に迅速に復元できます。

70 FF -70がここにパックされます。これは、0dd5eaで始まるハッシュのdigits.passファイルに含まれるパスワードの数です。

59 99 95 68 FF FF FF-番号59999568がここにパックされます。これは、digits.passファイル内のパスワードの読み取り開始位置です。

11a19a90 -digits.passファイル内の70個のパスワードの読み取りを開始する位置。 次のように計算されます：59999568 * 5（すでに圧縮されているパスワードの長さ、バイト単位）= 299997840（16進数に変換）

84 04 05 38 8F 8F-番号840405388がここにパックされています。これは、目的のハッシュに対応するパスワードです

次に、ファイルの最後でパスワードが切り捨てられず、PHP_INT_MAX：2147483647-（2147483647％パスワードサイズ）バイトを超えないように、.passファイルを分割します。
.hashファイルの最大サイズは185 MBであり、破損する必要はありませんでした。


実際、検索は.hashファイルでのみ実行され、パスワードのみが.passから（ファイル内の特定の位置から）ロードされます。 しかし、これはこの記事の主要なトピックを否定するものではありません。生データで速度を確認しました。

すべての未加工ファイルの重量は260 GBで、圧縮後は70 GBになりました。 このサイズには、文字の付いた数字から1〜6文字のパスワードと、7〜10文字のパスワードが含まれます。数字のみ、合計で約135億のパスワードです。 その後、1億語の単語を追加しました。 その結果、実際のP​​vPGNサーバーからのパスワードの約90％を見つける必要があります（93.5％は以前のPvPGNサーバーから見つかりました）。

少しの最適化

1人の優秀な人がPvPGNハッシュ関数をPHPからJavaScriptに移植しました（テーブル用に250 GBのスペースを持つ仮想サーバーも提供しました）。

さまざまなハッシュ実装のパフォーマンス測定を行いました。


harpywar.pvpgn.pl/?do=hashをダウンロードすると、さまざまな言語の実装を利用できます
明らかに、Cが最速です。 Firefoxはスクリプトの実行中にハングしますが、すべてのブラウザーで速度はほぼ同じです。

PHPが原因で検索が遅くなりました。 そのため、テスト直後に、このリソース集中型タスクをブラウザーでクライアントに送信することにしました。 さらに、クライアントの場合、これは完全に目に見えません-平均して、1回の検索クエリにつき1,000個以下のハッシュを生成するのにかかります。 すでに少しだったものをやり直す必要がありました。見つかったパスワードは、JSON配列でクライアントに渡され、ブラウザでパスワードを繰り返し、ハッシュを生成します。 生成されたハッシュが検索されたハッシュと一致する場合、パスワードは見つかったと見なされます。
スクリーンショットでこれがどのように機能するかの大まかなしかし明確な例（まだ圧縮されていないファイルがあります）：

まとめ

大規模なデータセット、またはターンキーソリューションを検索する他の方法がおそらくあります。 しかし、特定のタスクのために、私の実装は非常に高速で、非常に重要なこと-非常にコンパクトであることが判明しました。 バックグラウンドの生成とテーブルの並べ替えを含め、これに約1週間を費やしました。

ブルートフォースコードが並列化されてGPUに移植されると、非常に多くの文字を含むパスワードが比較的迅速にソートされるため、これはおそらく何かを作成するのに最適な例ではありません。
しかし、その過程で多くの知識と経験を得たので、それらを共有したいと思いました。

更新する

-興味のある人のためにPHPのソースをレイアウトしましたが、テーブルファイルがなければ、その調査は面白くないかもしれません： index.php 、 hashcrack.class.php 。

-例として、ファイル内のバイナリ検索を使用して、大きなログのデータをスライスすることができます（特定の日付の「開始」と「終了」の統計を分析する必要がある場合）

-私はトータルコマンダーでミスを犯しました-それを利用して、バイト単位でファイルを正確に分割することができます（ Joshua5が提案）。

-さまざまなデータベースの機能にあまり詳しくないため、検索に時間がかかりました。
Alexey Pechnikovは、SQLiteではパフォーマンスが非常に高くなる可能性があると言っていますが、テーブルでは「fts4」を使用する必要がありました。 MySQLにはおそらく似たようなものがあります。

-以下のコメントには、データを整理して検索する方法に関するアイデアがあります。

-webhamsterからのコメントは、このトピックで示したかったことを完全に反映しています