データベースセキュリティとテーブル検索攻撃における MD5 暗号化アルゴリズムの応用

MD5 は最も広く使用されているハッシュアルゴリズムの 1 つです。1992 年に MIT の Ronald L. Riverst によって提案され、MD4 から進化しました。このアルゴリズムは、インターネット Web サイトのユーザーデータの暗号化に広く使用されており、ユーザーパスワードを 128 ビットの長整数に暗号化できます。データベースは、ユーザーのパスワードをプレーンテキストで保存しません。代わりに、ユーザーがログインするときに入力したパスワード文字列は MD5 で暗号化され、データベースに保存されている MD5 値と照合されるため、パスワードデータベースが盗まれた後のユーザー損失のリスクが軽減されます。

しかし、ハッシュ衝突が存在するため、MD5 暗号化データは安全ではなく、同じハッシュ値を生成する文字列によって解読される可能性があります。そのため、乱数ソルトを追加する MD5 暗号化方式が提案されており、これにより辞書攻撃の困難さがある程度高まります。

問題

少し前に、誰かが Sina Weibo に次のような投稿をしました。「インターネットセキュリティの常識に関する数学の問題です。Web サイトのすべてのユーザーパスワードが md5 (一方向ハッシュ、非可逆) で暗号化されており、Web サイトのメンバーが 10 万人いると仮定します。ユーザーデータベースが失われた場合、メンバーのパスワードが何件解読されるでしょうか。考えてみてください。」当時、私の友人は 10 万件のパスワードがすべて解読されるだろうと考えていましたが、私はそうは思いませんでした。なぜなら、私の事前の知識によると、

（1） MD5暗号化アルゴリズムは、インターネットアプリケーションで広く使用されています。MD5は単純な古典的な暗号化アルゴリズムではなく、逆復号化では解読できません。ハッシュ衝突（ハック）によってのみ解読できます。

（２）同じ文字列をMD5暗号化した結果を見たことがあるが、結果はランダムな文字列だった（後で情報を検索したところ、私が見たのは単純なMD5暗号化ではなく、ソルトを追加した結果であることが判明した）。

（３） MD5をパスワード暗号化アルゴリズムとして使用すると、ハッシュ衝突が発生する可能性があるため、絶対に安全というわけではありません。単純なパスワードのMD5暗号化は、レインボーテーブルを使用して見つけることができます。

(4) MD5 暗号化を解読する Web サイトをいくつか見たことがあります (http://www.cmd5.com/)。そのほとんどは、まずユーザーに無料のブルートフォースクラッキングを提供します。簡単なパスワードを解読するのに十分なデータベースが蓄積された後、解読サービスに料金を請求し始めます。したがって、MD5 パスワードの解読はそれほど簡単ではないはずです。

この問題について白熱した議論が交わされて間もなく、CSDNデータベース漏洩事件が発生し、600万件のデータベースレコードが無断で拡散されました。その後すぐに、天亜フォーラムのデータベースも流出し、2000万件のデータベースレコードのほぼすべてにログインできることが確認されました。これら 2 つの Web サイトのデータベースに保存されているユーザーパスワードは暗号化されておらず、プレーンテキストで保存されています。この種の事件は、ウェブサイトのデータベースに保存されているユーザーパスワードを暗号化することの重要性をさらに裏付けています。

現在普及しているユーザーパスワード暗号化アルゴリズムの中で、MD5 暗号化は最も広く使用されているアルゴリズムの 1 つです。

背景

ハッシュ関数h(x)は、以下の性質を満たす必要がある[1]。

圧縮: 与えられた入力 x に対して、出力の長さ y=h(x) は小さくなります。

効率性: 与えられた入力 x に対して、y = h(x) を計算するのは簡単です。

一方向: ハッシュ関数 H は一方向関数です。つまり、ほとんどすべての x に対して、H(x) の値 y が与えられた場合に x を見つけることは不可能です。

弱い衝突なし: x が与えられたとき、H(x')==H(x) となる x' を見つけることは計算上不可能である。

強い衝突なし: 任意の x≠x' に対して、H(x')==H(x) は計算上不可能です。

MD5 の正式名称は Message-Digest Algorithm 5 で、1991 年に MIT の Ronald L. Riverst 氏によって提案されました。MD4 から進化し、最終的に 128 ビット (4 つの 32 ビットの 16 進数) の情報ダイジェストアルゴリズムを生成しました。 [2] MD5アルゴリズムは不可逆な文字列変換アルゴリズムです。つまり、ソースコードとアルゴリズムの説明を見ても、MD5値を元の文字列に戻すことはできません。

1993 年、DenBoer と Bosselaers は限定的な「疑似衝突」の結果を発表しました。

1996 年、MD5 アルゴリズムの設計に欠陥があることが判明しました。当時、この欠陥が致命的であるとは証明されていませんでしたが、暗号化の専門家は他の暗号化アルゴリズム (SHA-1 など) の使用を推奨しました。

2004 年、MD5 アルゴリズムはハッシュ衝突により安全でないことが証明されました。 [3]

2007 年、研究者は、Chosen-prefixCollision メソッドを使用すると、悪意のあるコードを含むプログラムが正当な MD5 値を生成できることを発見しました。

2008 年に研究者たちは、同じ MD5 ハッシュ値を生成する 2 つの実行可能ファイルを発見しました。

上記の例は、MD5 アルゴリズムのセキュリティが高くなく、セキュリティ要件が非常に高い SSL 暗号化やデジタル署名には使用できないことを証明しています。現在最も推奨されるハッシュ暗号化アルゴリズムは、SHA-2 暗号化アルゴリズムです。

MD5アルゴリズムの説明

MD5 アルゴリズムは、可変長の入力に対して 128 ビットの固定長の暗号化された情報を出力できます。 MD5 は入力情報を 512 ビットにグループ化し、各グループは 16 個の 32 ビットサブグループに分割されます。アルゴリズム処理の後、最終的に 4 つの 32 ビットデータが生成され、128 ビットのハッシュに結合されます。アルゴリズムの具体的なプロセスは以下の通りである[4]。

（１）情報は、そのビット長を512で割った値が448になるようにパディングされる。メッセージの長さは N*512+448 に拡張されます。ここで、N は負でない整数であり、N は 0 になる場合があります。埋め方は、条件が満たされるまで情報の後に1と無数の0を埋めていくというものです。

（２）パディング前の情報の長さの64ビットバイナリ表現をこの結果に追加します。これら 2 つのステップの後、情報の現在のビット長 = N*512+448+64=(N+1)*512、つまり、長さは正確に 512 の整数倍になります。これを行う理由は、後続の処理における情報の長さの要件を満たすためです。 MD5にはChainingVariableと呼ばれる32ビット整数パラメータが4つあり、その初期値はA=0×67452301、B=0xefcdab89、C=0x98badcfe、D=0×10325476です。

（３）アルゴリズムの４つのメインループ操作を入力します。サイクル数は、メッセージ内の 512 ビットの情報ブロックの数です。メインループには 4 つのラウンドがあり、各ラウンドは非常に似ています。第一ラウンドでは16件の手術が行われました。各操作では、a、b、c、d の 3 つに非線形関数を適用し、その結果を 4 番目の変数、テキストのサブグループ、および定数に追加します。次に、結果を不定数だけ左にシフトし、a、b、c、d のいずれかを追加します。最後に、結果を使用して a、b、c、または d のいずれかを置き換えます。

（4）ビットごとの演算を4回繰り返した後、A、B、C、Dをそれぞれa、b、c、dに加えます。次に、次のデータグループでアルゴリズムが再度実行され、最終出力は A、B、C、および D の連結になります。

問題点

MD5 は一方向ハッシュ暗号化であり、不可逆ですが、鳩の巣原理によれば、MD5 アルゴリズムによって生成される 32 ビット出力で表現できる空間のサイズは 1632 です。つまり、サンプルが 1632≈3.4×1038 より大きい場合、ハッシュ衝突が発生します。この結論から、大量のパスワードサンプルに対してハッシュ値を生成し、パスワードとハッシュ値との1対1の対応を取得し、この対応に基づいて逆チェックを行うことで、ハッシュ値に対応するパスワードを取得できることがわかります。しかし、パスワードの MD5 値を解読する前に、大量のデータに対応する MD5 値を事前に計算する必要があります。

インターネットアプリケーションの場合、冒頭で述べたように、ユーザーパスワードが単純に MD5 で暗号化されていると、テーブルを参照することでユーザーアカウントにハッキングされる可能性があります (ただし、パスワードがユーザーの元のパスワードではない可能性があります)。ただし、強力なパスワードの場合、ブルートフォースによって MD5 値を解読するコストもかなり高くなります。しかし、統計的な結論[5]によれば、相当数のユーザーが弱いパスワードを使用している[6]。したがって、統計的なルールに基づいて単純なパスワードに対応するMD5値テーブルを作成し、単純なパスワードを使用するユーザーアカウントに侵入することができます。

改善方法

暗号ハッシュ関数には、雪崩効果、または厳密な雪崩効果を持つという特性も必要となるためです。目標は、入力に対する小さな変更が出力に大きな変化をもたらすことです。理想的には、入力を変更することによって得られる出力は無関係であるため、衝突を探している攻撃者は徹底的な検索を実行する必要があります[1]。 MD5 アルゴリズムのこの効果により、ユーザーパスワードを作成するときにランダムな文字列 (Salt と呼ばれ、別のデータテーブルまたはデータベースに保存されます) を生成し、それをユーザーパスワードに接続し、ハッシュ関数を使用して文字列を MD5 で暗号化し、MD5 暗号化の結果をデータベースに保存することができます。 Salt 値の数が十分に大きい場合、ハッカーはデータベースに Salt とユーザーパスワードの MD5 値をそれほど多く保存できないため、よく使用されるパスワードに対する辞書攻撃が実際に排除されます。もちろん、ハッカーがデータベース内のすべての情報 (Salt テーブルを含む) を入手した場合でも、単一のユーザーのパスワードをブルートフォース攻撃で解読することは可能です。ただし、各パスワードの後にランダムな文字列を追加すると、ブルートフォース列挙の難易度が確実に高まり、パスワードが弱いという問題は発生しません。より安全な方法は、各パスワードにランダムな Salt 値を設定することです。これにより、ブルートフォース列挙を使用してユーザーのパスワードが解読されたとしても、他のユーザーのパスワードを解読することは困難になります。

MD5 アルゴリズムにソルトを追加することに加えて、ユーザーパスワードのセキュリティを強化するための他の予防策としては、より時間のかかる暗号化アルゴリズムを使用する (これにより、パスワードの解読に必要な時間が大幅に長くなります)、SHA-2 アルゴリズムなどのより安全な暗号化アルゴリズムに置き換える、Twitter のようにユーザーに複雑なパスワードの使用を強制するなどがあります。

結論は

この記事の冒頭で提起した疑問に戻りましょう。私のウェブサイトに保存されている 10 万件の MD5 パスワードのデータベースがハッカーの手に渡った場合、最近の CSDN パスワード漏洩の統計パターンに基づくと、600 万のアカウントのうち 239 万のアカウントが他のアカウントと同じパスワードを使用しており[5]、これらすべてのアカウントが弱いパスワードを使用しており、これらすべての弱いパスワードに対応するプレーンテキスト情報を持っているという最も楽観的な仮定を立てると、約 40% のパスワードが解読されることになります。記事冒頭で提起した疑問に関して言えば、約4万人のユーザーのパスワードが破られることになる。より保守的な仮定を立てて、CSDN事件の最も弱いパスワードトップ10を例にとると、最も弱いパスワードトップ10を使用した人は合計748,350人で、0.1%を占めます。最も弱いパスワードトップ1,000を実際に使用している人の数が100*0.1%=10%であると仮定し、弱いパスワードの80%に相当する平文情報を持っているとすると、冒頭で提起した疑問に対して、約8,000人のユーザーのパスワードが解読されることになります。このことから、ユーザーパスワードを単純に MD5 で暗号化するだけでは、すべてのユーザーのパスワードの安全性を保証することはできないことがわかります。約 8,000 ～ 40,000 人のユーザーのパスワードがテーブル検索によって解読されることになります。

(この推定方法にはいくつかの問題があります。実際の状況に基づいて弱いパスワードの使用に関するより良い統計的結論が見つかっておらず、CSDN によって漏洩されたデータベースがないため、Guokr.com のデータのみをベンチマークとして使用できます。また、Guokr.com によって提供されるデータの量が非常に少ないため、推定方法は正確ではなく、大まかな推定値にすぎず、最終結果は定性的な結論にすぎません。この問題は、後で定量的に調査することもできます。)

編集者注：この記事の著者は北京師範大学3年生の張喬さんで、女性オタクです。CSDNなどの大手ウェブサイトのユーザーデータが漏洩した後、彼女はMD5暗号化問題についてこの記事を書き、自分の意見を述べました。著者とさらに議論したい読者は、Sina Weibo @阿豆拉で彼女をフォローしてください。

【編集者のおすすめ】