MD5withRSA を用いた証明書の偽造（その１）

このところ世間を騒がせている、MD5withRSA を用いた証明書の偽造についてまとめてみようと思います。前半のこの記事で概要を、後半のこの記事で偽造原理を説明してみます。誤りや勘違いが含まれていると思うので、その際には、是非、ご指摘下さい。

話の発端は、2008年12月27日～30日に Berlin で開催された 25th Chaos Communication Congress (25C3) において発表された次の講演です。

Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger

"MD5 considered harmful today: creating a rogue CA certificate"

内容としては、先頭部指定型衝突攻撃（ターゲット衝突攻撃）を用いることで、

• MD5withRSA を用いた SSL サーバ証明書
• MD5withRSA を用いた中間 CA 証明書

が偽造できたという報告です。しかも証明書は実在する SSL サーバ証明書認証局が発行したように見せかけられ、証明書のユーザ名は任意に設定できるというのです。さらには、偽造の単なる理論を示すだけでなく、具体的な偽造証明書の例も示されているなど、非常にインパクトのある内容となっています（ただし証明書の有効期限が2004年に設定されているため、実害はないように配慮されています）。

SSL サーバ証明書が偽造できる、というのはそれはそれで問題なのですが、やはり自分で証明書を発行できるようになってしまうと言う点で 中間 CA 証明書の偽造の方が影響は大きいでしょう。（ITpro や Internet Watch の記事ではそこまで触れられていないのがちょっと不思議です。）

ではどうやった対策をしたら良いか、という話になるのですが、なかなか話が複雑なため、一言には説明しにくいのです。そこで、（せっかく内容が理解できた気がするので）偽造原理をながめてから、対策法に戻りたいと思います。

まずハッシュ関数の安全性についてまとめましょう。暗号で使用するハッシュ関数 H は、以下の３つの安全性を全て満たす必要があります：

• 原像困難性（一方向性）： 原像攻撃が困難なこと。つまり、与えられたハッシュ値 h から、H(x)=h となるメッセージ x を求めるのが困難なこと。
• 第２原像困難性： 第２原像攻撃が困難なこと。つまり、与えられたメッセージ x に対し、H(x)=H(y) となるメッセージ y を求めるのが困難なこと。
• 衝突困難性： 衝突攻撃が困難なこと。つまり、 ハッシュ値が等しい２つのメッセージ x, y を求めるのが困難なこと。

原像攻撃とはハッシュ値からその原像を求める攻撃なので、原像攻撃ができてしまうようなハッシュ関数はそもそも安全ではありません（というか、ハッシュ関数と呼べるわけもありません）。しかしハッシュ関数が安全であるためには、単に原像困難性だけでは不十分で、さらに第２原像困難性と衝突困難性も必要です。

攻撃者の立場から考えると、上で紹介した３つの攻撃のうち、最も簡単なのは衝突攻撃で、最も難しいのは原像攻撃です。衝突攻撃では、メッセージ x, y も、その共通のハッシュ値も攻撃者が選択できるのに対し、原像攻撃・第２原像攻撃では、攻撃者はハッシュ値を指定されているからです。

しかし今回の MD5withRSA を用いた証明書偽造では、次の先頭部指定型衝突困難性（が成り立たない）という性質が使用されました。

• 先頭部指定型衝突困難性： 先頭部指定型衝突攻撃が困難なこと。つまり、与えられた２つの先頭部 a, b に対し、ハッシュ値が等しく、かつ与えられた先頭部から始まる２つのメッセージ a||x, b||y を求めるのが困難なこと（|| は連接記号）。

先頭部指定型衝突攻撃の攻撃者は、出力するメッセージの先頭部を指定されているため、単なる衝突攻撃よりも難しいことを要求されています。つまり先頭部指定型衝突攻撃は、単なる衝突攻撃よりも難しい攻撃です。

しかし先頭部指定型衝突攻撃の攻撃者は、出力するハッシュ値を自分で定めることができる（つまり、ハッシュ値の原像や第２原像を求めることを要求されていない）ため、第２原像攻撃よりは易しい攻撃といえます。

次にハッシュ関数 MD5 に対する攻撃状況をまとめます。MD5 に対する（単なる）衝突攻撃は、2004 年に発表されました（発表論文はこちら）。計算量は 2^37 （のMD5計算）でしたが、その後の改良により、現在の計算量は 2^29 位まで低減されています。衝突を計算するプログラムも入手可能な状態で、通常のＰＣでも１分程度衝突が求められる状況になっています。

2006 年になると、MD5 に対する先頭部指定型衝突攻撃が発表されました（発表論文はこちら）。計算量は 2^52（のMD5計算）で、衝突を求めるのに最大1200台の計算機を６ヶ月程度しようしたそうです。

そして 2009 年に入り、MD5 に対する原像攻撃が発表されました。論文は見つけられていないのですが、おそらくは理論的な攻撃であり、実際に原像が計算できる域には手が届いていないと思われます。

これら攻撃状況により、MD5 はもはや安全なハッシュ関数とは呼べなくなりました。このように安全でない MD5 を使用し続けると何が起こるか、という好例が、今回の MD5withRSA を用いた署名偽造ということになります。後半では、これら攻撃を使って、どうやって偽造署名を構成するか説明していきたいと思います。