情報処理機構セキュリティセンターは4月，メール・サーバーの認証プロトコルの一つ「APOP」について注意を喚起した。この注意喚起は，電気通信大学の太田和夫教授のグループが，APOPで使うハッシュ関数「MD5」に新たな欠陥を発見したことに基づくもの。この欠陥は，APOPだけでなく，MD5を使う電子署名などのほかのアプリケーションの欠陥も示唆する。実際にどの程度危険なものか，技術に基づいて考えてみよう。

わからないはずのパスワードが解かれる

　APOPは，チャレンジ・レスポンスという方式を使って，メール・クライアントとメール・サーバーのやりとりを盗聴してもパスワードが解読できないようにする。パスワードを直接やりとりせずに，まずサーバーからクライアントに「チャレンジ・コード」という文字列を送る。クライアントはチャレンジ・コードとパスワードを連結したうえで，MD5というハッシュ関数を使ってハッシュ値を計算し，サーバーに「レスポンス」として送る。

サーバーは，受け取ったハッシュ値とは別に，自分が保存しているパスワードからハッシュ値を改めて計算し，一致すれば正しいパスワードが使われていると判断する。ハッシュ関数は入力値を一定の長さの「ハッシュ値」に変換する関数。入力値が少しでも変わるとまったく異なったハッシュ値になり，ハッシュ値から元の値は推測できない。このハッシュ関数の性質を利用して，クラッカがハッシュ値を盗聴してもパスワードを割り出せないようにする。

　今回の警告の内容は，ある状況下でこのパスワードが解かれてしまうことを示したもの。「APOPは期待したほど安全ではない」ということだ。ただし注意しなければいけないのは，APOPはもともとメール本体自体を安全にするものではないということ。APOPだけではメール自体は暗号化されない。

　このためパスワードが解かれなくても，盗聴されればメールの中身は読まれてしまう。このことは仕様の範囲内なので，あらためてぜい弱性として警告されることはない。メールを他人に盗み見されないようにするには，S/MIMEやPGPといったメールの暗号化プロトコルを使うか，POP/SMTP over SSLを使って認証を含めてすべて暗号化するか，SSLを使ったWebメールを使うか――のどれかにする必要がある。

パスワードを解くには偽メール・サーバーが必要

　では，実際にどのようにパスワードが解かれるのかを説明しよう。

　MD5のようなハッシュ関数は，逆演算ができないという性質を使って，パスワードを「知っているものには検証できるが，知らないものはパスワードがわからない形にして送る」。ところが，太田教授らは，直接逆演算はできないが，同じハッシュ値が得られる二つの入力値の計算法を発見した。実は，同じハッシュ値が得られる二つの入力値の計算法は，2004年に既に発見されていた。太田教授らの計算法が優れているのは，入力値のデータの一部を固定するという条件を付けながら，同じハッシュ値になる二つの入力値を計算できること。二つの入力値を得るための計算時間は5秒程度だという。

　APOPでは，チャレンジ・コードにパスワードを連結してハッシュ値を演算する。太田教授らの計算法を使えば，パスワード部分を特定の値に固定したうえで，同じハッシュ値になるチャレンジ・コードを二つ計算できる。つまり，クラッカが「予測した」パスワードを検証できる。

　検証するには，偽のメール・サーバーが必要になる。メール・クライアントに何らかの方法で偽のメール・サーバーにアクセスさせ，クラッカが予測したパスワードに基づいて，同じハッシュ値になるはずのチャレンジ・コード二つをメール・クライアントに2回に分けて渡し，同じハッシュ値が返ってくるなら予測したパスワードが「当たり」という原理だ。

　では，パスワードの「予測」はどうするのだろうか。この予測がうまくできなければ，すべてのパスワードの組み合わせを試して攻撃するブルート・フォース（総当たり）攻撃と変わらなくなる。太田教授らのグループは，MD5が内部で入力値を512ビット単位に分割して演算することに着目して，1文字ずつ解読する方法を開発した。

　太田教授の方法では，まずパスワードの1文字目を予想し，ハッシュ値が同じになる長さ504ビットのチャレンジ・コードを二つ計算する。チャレンジ・コードを504ビットにして送れば，クライアント側はパスワードとチャレンジ・コードを連結したものを，チャレンジ・コードと最初の1文字（8ビット）分を連結したものと，パスワードの残りに分割する。クライアント内部のMD5は，チャレンジ・コードと最初の1文字分を連結したもので暫定的なハッシュ値を演算し，その値とパスワードをもう一回演算して最終的なハッシュ値を演算する。

　例えば一文字目が「A」と予想してチャレンジ・コードを用意すれば，実際のパスワードが「ABC」だったとしよう。二つのチャレンジ・コードに対する暫定的なハッシュ値は同じ値になり，最終的なハッシュ値も同じになる。実際のパスワードが「AAA」の場合，最終的なハッシュ値は「ABC」のハッシュ値と異なるが，二つのチャレンジ・コードに対するハッシュ値は同じになる。1文字目を予想しながら検証し，当たったとわかれば，今度はチャレンジ・コードを496ビットにして，2文字目を予想しながら検証する。この方法で，61文字のパスワードまでを解析できるという。

　1文字が英大小文字と数字で出来ているとすれば，偽サーバーに約60回アクセスさせることで，1文字分のパスワードが解析できる。10文字程度のパスワードなら約600回のパスワードで解けてしまう。メール・クライアントが1分おきに受信メールをチェックするような設定になっていれば，約10時間でパスワードが解ける計算だ。

MD5を使った電子署名は無効になる

　実は2004年時点で，同様な方法で3文字までのパスワードは解けていた。しかし，実際には3文字以下のパスワードを使うユーザーはほとんど存在しない。このため，直ちに危険とは考えられていなかった。太田教授らのグループが61文字までのパスワードを解く方法を発見したことで，パスワードが解読される可能性が高まった。実際に偽サーバーを用意するのは難しいとはいえ，APOPを使うユーザーは，APOP用とほかのパスワードを別のものにして，できれば定期的に変えておくべきだろう。

　今回の太田教授らの発見は，MD5というハッシュ関数自体の寿命が，まもなく尽きてしまうことを示している。今まで見つかっていたMD5の欠陥に比べ，太田教授らの発見した欠陥は，一段と悪用されやすい。さらに新たな欠陥が見つかり，ハッシュ値から入力値の候補を計算したりできるようになれば，MD5はハッシュ関数としての意味を完全に失う。

　問題はAPOPだけでなく，MD5で電子署名が施されたドキュメントに及ぶ。電子署名は，文書にハッシュ値を添付することで改ざんされていないことを証明するしかけ。同じハッシュ値が得られるような改ざんができるようになれば電子書名の意味が失われる。ある日突然多数の文書の署名が一斉に無効になることがあり得るのだ。新たな電子署名にMD5を使うユーザーはほとんどいないだろうが，以前から電子署名を使っているユーザーは，必要なら別のハッシュ関数で電子署名をやり直す必要があるわけだ。