MD5 の安全性の限界に関する調査研究報告書を読んでみる

1991 年に開発され、現在でも広く用いられてきている MD5 (Message Digest 5) と呼ばれるハッシュ関数は、2004 年 8 月に異なる 2 つの元情報に対して同一の MD5 ハッシュ値を生成できる（衝突が起きる）ことが示された。

20年くらい前には既に脆弱性が発見されてたのか👀

(1) ハッシュ関数の基礎
暗号学的ハッシュ関数、もしくは暗号学的に安全なハッシュ関数とは、次の性質を
持つハッシュ関数である[Handbook04]。
・入力：任意長の系列
・出力：長さの短い系列（128 ビット、160 ビットなど）

以下の性質を満たす。
・一方向性：y が与えられたときに、y=h(x)となるx を求めることが困難である
・第二原像困難性：x が与えられ時に、h(x)=h(x’)となり、x とは異なるx’を求めることが困難である
・衝突困難性：h(x)=h(x’)となる異なるx と x’を求めることが困難である

衝突困難性は、攻撃者から見れば一番容易な攻撃であり、一方向性は一番困難な攻撃である。すなわち、一方向性を破ることが出来れば、容易に衝突困難性も破ることができる。衝突困難性ですら破れないことをハッシュ関数の最低限の安全性としては要請されている。

🖊memo: 暗号学的ハッシュ関数は、「一方向性」・「第二原像困難性」・「衝突困難性」の三つの性質を証明し、かつ最低限「衝突困難性」が破られないようにする必要がある

(2) MD5 自身の脆弱性に関する歴史
⋮
・2004 年 8 月 Wang らにより、2^{39} 回の MD5 の計算で、衝突を見つける方法が提案された[WL04]。これは、完全な実現可能な脅威である。それとともに、MD5 の衝突困難性は保証されなくなった。

・2005 年 5 月 Wang らにより、詳細な衝突発見アルゴリズムが学会で発表される[WY05]。

・2005 年 5 月 Klima により、233 回の MD5 の計算で衝突が見つけられるアルゴリズムが提案される[Klima05]。

・2005 年 11 月 Sasaki らにより、230 回の MD5 の計算で衝突が見つけられるアルゴリズムが提案される[SNKO05]。

🖊memo: 2^{39} 回は約5500億回くらい

ユーザ Alice がサービスの提供を得るために、サーバにログインする状況を考える。
ユーザのパスワードを pw とする。サーバのデータベースは、ユーザのパスワード自身ではなく、パスワードのハッシュ値を保管している。ユーザは、ログインするとき、パスワードをそのまま送るのではなく，パスワードのハッシュ値を取った値を自身のID とともに送る。サーバは、ID をもとに、データベースからユーザに対応したハッシュ値を探し、送られて来た値と一致するかをチェックする。一致していれば正しいユーザであると判定する。

この例の場合は、たとえ衝突が発見できるとしても、攻撃者はその能力を有効に利用することができない。パスワードを入手するためには、ハッシュ値から元の系列を求める必要があるが、それは、ハッシュ関数の一方向性を破る必要がある。これは、衝突困難性よりもはるかに困難であり、現在のところ、この一方向性を破る方法は、MD5 より下位レベルの MD4 においてさえ、提案されていない。以上より、衝突困難性を破るだけでは、安全性が低下されたとは必ずしも言えないことがわかる。

🖊memo: 衝突困難性を破るだけでは、安全性が低下されたとは必ずしも言えない

次に、署名の偽造を例に取る。異なるメッセージm1、m2 に対して、H(m1)=H(m2)とすることができたとしよう。このとき、m1 に対して有効な署名は、m2 に対しても有効な署名となる。そのため、署名のすり替えが可能であり、これは現実の脅威となる。しかしながら、m1,m2 ともに意味のあるメッセージでなおかつ、衝突を発見する方法は提案されていない。さらに、m1 を固定したときに、m2 を求めることは、第二原像衝突困難性を破ることになり、これも現在の技術では不可能である。

🖊memo: 現在の技術では第二原像衝突困難性を破ることは不可能。

次に提案されたのは、Postscript で記述された文書のすり替え攻撃である[DL05]。これは、ps ファイルの構造を強く利用した攻撃である。ハッシュの衝突を計算することにより、同じハッシュ値を持ちながら、任意に選んだメッセージを「表示」させることができる ps ファイルが可能である。

🖊memo: 他の要因と組み合わせると脆弱性が高まることもある

2007 年 3 月、ルクセンブルグで開かれた国際会議 Fast Software Encryption（略称FSE）で、フランスの Leurent は、APOP に対する攻撃を提案している[Leurent07]。この論文では、攻撃者がサーバになりすますことにより、3 文字までのパスワードを復元することが可能であることを示している。ほぼ同時期に、Sasaki（電通大） ,Yamamoto（NTT）、Aoki（NTT）は、同じアイデアに基づき、同じ結果を得ている[SYA07]。この二つの方式は、ともに、Wang らの MD5 の攻撃に基づいている。しかしながら、Wang らの方式に基づく限り、3 文字の限界を超えることは原理上不可能である。それに対して、Sasaki, Wang, Ohta, Kunihiro の電通大の研究グループは、3 文字という壁を突破し、実用上は 31 文字まで、理論上は、61 文字のパスワードを復元する方法を、同会議のランプセッション（採録された論文ではなく、研究速報を発表するセッション）で報告している[SWOK07]。

🖊memo: MD5 の攻撃に基づいて APOP に対する攻撃が提案され、実用上は 31 文字まで、理論上は、61 文字のパスワードを復元する方法が発見された。

上記の攻撃について

(2) 攻撃アルゴリズムに対する検討事項
Sasaki らの論文では、以下の項目が検討されていない、もしくは検討が不十分であった。

1. 攻撃の大前提として、攻撃者は、メールサーバに成りすましをしなくてはいけない。しかも、今回の攻撃の場合は、瞬間的に盗聴を行えば成功する類の攻撃ではなく、継続的に、成りすましをしなくてはいけない。さらに、このユーザは、アプリケーションとしてメールのみを使っているとは限らず、http などの各種プロトコルを使っていると考えるのが妥当である。このような状況で、攻撃者は、クライアントに気づかれることなく、攻撃を継続的に続けることは可能であろうか？また、その逆に、ユーザからみて、攻撃が仕掛けられていることは検出できないであろうか？この点をクリアにする必要がある。そのため、実際にネットワークを構築し、攻撃が成功するかの確認を行う必要がある。

2. ハッシュの衝突を実時間で発見することは可能であろうか？また、どの程度の計算能力のある計算機であれば、遅延なく、衝突を発見し、攻撃に利用できるであろうか？論文中では、可能であると記述されているが、実際に実験を行うことによりこの主張の正当性を検証する。

3. いくつかの APOP に対応した実際のメーラーが、この攻撃に対してどのような振る舞いをするかを検証する必要がある。APOP の仕様は、RFC 1939 により規定されているが、必ずしも、全てのメーラーが仕様を遵守している保証はなく、仕様の曖昧さも少なからずある。そのため、実際のメーラーの挙動、具体的には、チャレンジとして、どの文字が送られてきたときに、エラーが生じるかを実際に検証する。

4. パスワードに対する攻撃として、辞書攻撃が有効であることは良く知られている。Sasaki らの攻撃と辞書攻撃を併用する、すなわち、パスワードの次の文字の推定に辞書を用いる場合の有効性を検証する。さらに、その場合の攻撃に成功するまでの実時間の測定を行う。

以上の項目について、詳細に検討、実証を行うことが重要である。