md5関数を破る方法

MD5は、ハッシュを計算する関数として非常によく使われています。

初心者はパスワードのハッシュ化に使うことが多いのですが、これは元のパスワードを取り出す方法がたくさんあるため、あまり良い方法とは言えません。

そのための具体的な方法について解説します。

時間の複雑さ

すべてのセキュリティは、すべてのパスワードを試すのに不釣り合いなほど長い時間がかかるという事実の上に成り立っているのです。まあ、そうでしょうね。特に md5() アルゴリズムの問題は、この関数が非常に高速であることです。通常のコンピュータであれば、1秒間に100万以上のハッシュを計算しても問題ない。

組み合わせを1つずつ試してパスワードを破るなら、それはブルートフォース攻撃である。

クラッキング方法

いくつかの戦略があります。

• 試行錯誤の連続テスト（ブルートフォースアタック）
• 辞書パスワードのテスト
• レインボーテーブル（事前計算されたハッシュデータベース）
• グーグル検索
• アルゴリズムにおけるヒットコリジョン

この他にも様々な方法がありますが、この記事では代表的なもののみを紹介しています。

ブルートフォース・ブレーキング・ストラテジー

文字や数字など、すべての組み合わせが一度に試されます。

生成された試行は1つずつハッシュ化され、元のハッシュと比較される。

だから、たとえば

aaaaaaabaaacaaadaaaeaaaf...

この攻撃の問題は、「md5()」のアルゴリズム自体にある。アルファベットの小文字と数字だけを試すとすれば、一般に入手可能なコンピュータですべての組み合わせを試すには、せいぜい数十分かかるだろう。

そのため、長いパスワード、できれば特殊文字を含むランダムなパスワードを選択することが重要です。

辞書攻撃戦略

人々は通常、辞書に存在する弱いパスワードを選択します。

この事実を利用すれば、6w1SCq5csのようなあり得ない変種はすぐに捨て、代わりに既存の単語を推測することができる。

さらに、これまでの大企業のパスワード流出事件から、ユーザーはパスワードの先頭に大文字、末尾に数字を選んでいることがわかっています。えーと、あなたのパスワードもそうなっていますか？:)

レインボーテーブル - 事前計算されたデータベース

一つのパスワードは常に同じハッシュに対応するため、膨大なデータベースの中からどのパスワードを最初に検索するか、簡単に再計算することができる。

実際、検索はハッシュを何度も検索するよりも常に何桁も高速である。

また、大規模なデータ流出の場合は、このように並列にパスワードをハッシュ化することで、例えば全ユーザーの10％のパスワードを迅速に取り出すことが可能です。

良いパスワードデータベースは、例えばCrack Stationなどです。

グーグル検索

Googleはハッシュを含むページをインデックスしているため、多くの単純なパスワードは直接知られています。

私はいつもGoogleを第一選択肢として使っています。:)

アルゴリズムの衝突を発見する

Dirichlet Principle は、常に32文字の長さのハッシュのセットがある場合、同じハッシュを生成する33文字のパスワードが少なくとも2種類（1つは長い）存在することを説明します。

実際には、衝突を探すことに意味はないのですが、アプリケーションの作者自身が衝突を再計算することで、推測を容易にすることがあります。

例えば、こんな感じです。

$password = '暗証番号';

for ($i = 0; $i <= 1000; $i++) {
    $password = md5($password);
}

echo $password; // md5() により 1000 倍ハッシュ化されます。

この場合、元のハッシュではなく、衝突を推測するのが理にかなっている。

バストアップに乾杯!

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Kontakt