Tech Sketch Bucket of Technical Chips by TIS Inc.

数字6桁パスワードのMD5ハッシュ値をOpenMPを使って総当たり

Pocket

皆さん、JALやANAのマイレージ番号は持っていますか。持っていらっしゃるエンジニアは、先日の JALマイレージWebサイトに不正アクセス、約2700万人にパスワード変更を依頼 (ITpro 2014/2/3) というニュースを見て、「数字4桁や6桁のパスワードなんてそもそもありえない」「脆弱な実装がとうとう公然化したか」と思ったことでしょう。実際数字6桁のパスワードハッシュなど、ごくシンプルなコードで一瞬で解析できてしまうのです。


「数字6桁パスワードのMD5ハッシュ値を総当たりする」という"お題"

「数字6桁パスワードのMD5ハッシュ値を総当たりする」というお題は、もともと kawasima氏 がQittaに投稿した パスワード問合せシステムを作る(clojureのreducers) に端を発します。 kawasima氏 に感謝を!
今回はこのお題を、Clojureと同じJVM上の言語であるScalaと、CやC++コードを簡単に並列化できてしまうOpenMPで実装してみます。

なおこの問題は、PHPやPerlなど既にいくつかの言語での実装が公開されています。他言語での実装も参照いただけると、より楽しめるかと思います。

PHP 数字6桁パスワードのハッシュ値の総当たり、PHPなら約0.25秒で終わるよ 徳丸浩氏
Perl 数字6桁パスワードのハッシュ値の総当たり、Perlでも約0.25秒で終わるよ shimx氏

Scalaの場合

では早速Scalaで実装してみましょう。
ちなみにJavaのString.formatは非常に遅いらしいので、避けて通ることにします。詳細は kawasima氏String.formatが遅い理由 等をご参照ください。

コード

計測

OS Winodws7 Pro SP1 64bit
CPU Corei7-3770K
JVM JDK 1.7.0_25
Scala cala 2.10.3

上記の環境で計測したところ、1.70秒ぐらいでした。GCの調整を全くしなかったという点を考慮しても、今ひとつですね。

OpenMPの場合

次にOpenMPを用いC言語で実装してみましょう。
OpenMP とは、メモリ共有型の並列コンピューティングで利用されることを目的にしたAPI仕様です。OpenMP自体はAPI仕様なので、この仕様に従ってプログラムを並列化できるコンパイラが必要ですが、最近のVisualStudioやXcodeは特に追加ライブラリを導入しなくともOpenMPを利用することができます。便利ですね。
このOpenMPを活用すれば、煩雑なスレッド実装を書かずとも、Cプログラムを並列化してマルチコアCPUを上手く使い切ることができるのです。

VisualStudio 2013の場合、メニューから[プロジェクト]>[(プロジェクト名)のプロパティ]>[構成プロパティ]>[C/C++]>[言語]とたどり、[OpenMPのサポート]を はい(/openmp) に変更すれば、OpenMPが使えるようになります。

コード

private(origin, hex, result, hash, ctx, i, j) と宣言することで、MD5計算用の構造体やループ変数などをスレッド内に閉じ込めることができます。これにより、複数のスレッドが同時に、しかも安全にMD5計算を行うことができるようになります。

環境構築の都合上、MD5ハッシュ計算はWindowsOSやOpenSSL等のライブラリが提供する関数ではなく、下記で公開されているシンプルなC実装を利用しました。
http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5

計測

OS Winodws7 Pro SP1 64bit
CPU Corei7-3770K
Compiler Visual Studio Express 2013 for Windows Desktop

実測したところ、0.70秒でした。
pragmaを付けずにシングルスレッドで動作させた場合は2.89秒でしたので、pragmaを2つ書くだけでほぼ1/4の処理時間になりました。OpenMPを利用することで、クアッドコアのCPUを上手く使い切れたことがわかります。

最後に

利用可能なリソースを上手く使い切れば、現実的にどの程度の処理まで実行できるものなのか、これからのプログラマは十分に知っておく必要があります。OpenMPも技術の引き出しに滑りこませておくと、どこかで役に立つかもしれません。

エンジニア採用中!私たちと一緒に働いてみませんか?