私は現在、10 年生のサイエンス フェア プロジェクトに取り組んでいますが、壁にぶち当たりました。私のプロジェクトでは、md5 パスワード ハッシュの総当たり攻撃の効率に対する並列処理の効果をテストしています。1、4、16、32、64、128、512、および 1024 のスレッドを使用して、1 秒あたりのパスワードの組み合わせの数を計算し、その効率性を確認します。辞書のブルートフォースを行うか、純粋なブルートフォースを行うかはわかりません。辞書の方が並列化が簡単だと思います。リストをスレッドごとに均等に分割するだけです。私はまだ多くのコードを書いていません。コーディングを開始する前に、計画を立てようとしています。
私の質問は次のとおりです。
テストされたパスワードの組み合わせ/秒を計算することは、スレッド数に基づいてパフォーマンスを判断するための最良の方法ですか?
辞書か純粋な力ずくか？純粋な力ずくの場合、タスクを可変数のスレッドにどのように分割しますか?
他の提案はありますか？
あなたの熱意を弱めようとしているわけではありませんが、これはすでに十分に理解されている問題です。以下で何が期待できるかを説明しようと思います。しかし、あなたのプロジェクトを別の地域で行う方が良いかもしれません。「MD5 ハッシュ スループットの最大化」についてはどうですか。スレッドを見るだけに制限されることはありません。
プロジェクトを作成するときは、並列処理が適切な場合とそうでない場合について、何らかの分析を提供する必要があると思います。
CPU が別のスレッドに変更されるたびに、現在のスレッド コンテキストを保持し、新しいスレッド コンテキストをロードする必要があります。このオーバーヘッドは、シングル スレッド プロセスでは発生しません (ガベージ コレクションなどのマネージド サービスを除く)。したがって、他のすべてが等しい場合、スレッドを追加してもパフォーマンスは向上しません。これは、元のワークロードに加えてすべてのコンテキスト切り替えを実行する必要があるためです。
ただし、複数の CPU (コア) を自由に使用できる場合、CPU ごとに 1 つのスレッドを作成すると、コンテキスト切り替えのコストを発生させずに計算を並列化できます。CPU よりも多くのスレッドがある場合、コンテキストの切り替えが問題になります。
計算には、IO バウンドと計算バウンドの 2 つのクラスがあります。IO バウンドの計算では、ネットワーク カードやハードディスクなどのハードウェアからの応答を待機するために大量の CPU サイクルが費やされる可能性があります。このオーバーヘッドにより、CPU が再び最大になるポイントまでスレッドの数を増やすことができ、これによりコンテキスト切り替えのコストをキャンセルできます。ただし、スレッドの数には制限があり、それを超えると、スレッドが IO のブロックに費やすよりもコンテキストの切り替えに時間がかかります。
コンピューティング バウンドの計算では、単純に計算処理に CPU 時間が必要です。これは、パスワード クラッカーが使用する種類の計算です。コンピューティング バウンドの操作はブロックされないため、CPU よりも多くのスレッドを追加すると、全体的なスループットが低下します。
C# ThreadPoolは、既にこれらすべてを処理しています。タスクを追加するだけで、スレッドが使用可能になるまでそれらをキューに入れます。新しいスレッドは、スレッドがブロックされたときにのみ作成されます。そうすれば、コンテキストの切り替えが最小限に抑えられます。
私はクアッドコア マシンを使用しています。問題を 4 つのスレッドに分割し、それぞれが独自のコアで実行すると、私のマシンがパスワードをブルート フォースできるのとほぼ同じくらい高速になります。
この問題を真剣に並列化するには、多くの CPU が必要になります。グラフィックス カードの GPU を使用してこの問題に対処することについて読んだことがあります。
ここに書いた攻撃ベクトルの分析があります。レインボー テーブルとプロセッサ/メモリのトレードオフは、プロジェクトを実行するためのもう 1 つの興味深い領域です。
あなたの質問に答えるには: 1) スレッドのパフォーマンスをテストする最良の方法はありません。対象となる問題の各操作がどの程度独立しているかに応じて、問題が異なると、スレッドの規模も異なります。だから、辞書のことを試すことができます。ただし、結果を分析すると、取得した結果がすべての問題に適用できるとは限りません。ただし、非常に一般的な例の 1 つは、スレッドごとに一定の回数だけカウンターが増加する共有カウンターを試すというものです。
2) ブルート フォースは多数のケースをカバーします。実際、力ずくで、無限の可能性が存在する可能性があります。そのため、パスワードの最大長など、いくつかの制約によってパスワードを制限する必要がある場合があります。ブルート フォースを分散させる 1 つの方法は、各スレッドに異なるパスワードの開始文字を割り当てることです。次に、スレッドは、その開始文字に対して考えられるすべてのパスワードをテストします。スレッドが作業を終了すると、可能なすべての開始記号を使用するまで、スレッドは別の開始文字を取得します。
3) 私があなたに提供したい 1 つの提案は、もう少し少ない数のスレッドでテストすることです。最大 1024 スレッドになります。それは良い考えではありません。マシンのコア数は一般的に 4 ～ 10 です。そのため、コア数よりも膨大な数だけスレッド数を超えないようにしてください。プロセッサは同時に複数のスレッドを実行できないためです。任意の時点でプロセッサごとに 1 つのスレッド。代わりに、さまざまなスレッドに問題を割り当てるために、さまざまなスキームのパフォーマンスを測定してみてください。
これが役立つかどうか教えてください！
可能性のあるすべてのパスワードの辞書とブルート フォースの両方で機能する 1 つの解決策は、ジョブをワーク ユニットに分割することに基づくアプローチを使用することです。問題空間を作業単位 (理想的には、それぞれ 100 ミリ秒から 5 秒に相当する作業) に分割する役割を担う共有オブジェクトを用意し、開始する各スレッドにこのオブジェクトへの参照を与えます。各スレッドは、次のようなループで動作します。
for work_block in work_block_generator.get():
for item in work_block:
# Do work
前もってワークスペース全体をスレッドごとに 1 つのチャンクに分割することに対するこの利点は、あるスレッドが他のスレッドよりも高速に動作する場合、作業が不足することはなく、アイドル状態のままになることです。より多くのチャンクを取得します。
理想的には、作業項目ジェネレーターには、呼び出されたときに反復子を返すインターフェイスがあり、それ自体がテストする個々のパスワードを返します。次に、辞書ベースのものは辞書から範囲を選択しますが、ブルートフォースのものは各バッチでテストするプレフィックスを選択します。もちろん、作業単位を取得しようとする異なるスレッド間の競合を停止するには、同期プリミティブを使用する必要があります。
辞書と力ずくの方法の両方で、問題はEmbarrassingly Parallelです。n 個のスレッドでブルート フォースの問題を分割するには、最初の 2 つ (または 3 つ) の文字 (「プレフィックス」) を n 個のピースに分割します。次に、各スレッドには一連のプレフィックスが割り当てられます。たとえば、「aa - fz」のように、プレフィックスに続くすべてのテストのみを担当します。
通常、辞書はより多くのパスワードをクラックするために統計的にわずかに優れていますが、ブルートフォースはすべてをカバーするため、ターゲットの長さ内のパスワードを見逃すことはできません.