APOP

FSE 2007 では APOP の脆弱性の話が盛りだくさんだったようです。APOP とは Authenticated POP のことで、POP のようにパスワードを生でやりとりするのではなく、APOPサーバから送られたチャレンジ(乱数)に対し、ユーザはチャレンジとパスワードの連接のハッシュ値をサーバに送り返すことで、安全なパスワード認証を実現しています（ただしメイル本文は平文のままです）。ところが APOP で使用するハッシュ関数は MD5 に限定されているため、近年おなじみのコリジョン攻撃の被害を受けてしまっています。

FSE 2007 のメインセッションでは、Leurent が "Message Freedom in MD4 and MD5 Collisions: Application to APOP" という論文を発表しています。攻撃の手法は Man-in-the-middle 攻撃で、サーバとユーザの間にいる攻撃者が、ユーザに結論としては、MD5 のコリジョン探索攻撃を用いることで、ユーザに約200回のチャレンジを送ることで、パスワードを３文字特定することが可能だそうです。どうやって Man-in-the-middle 攻撃を実現するかという問題はありますが、なかなか現実的な話だと思います。

一方、ランプセッションでは Sasaki, Aoki, Yamamoto が "Practical Password Recovery on an MD5 Challenge/Responce such as APOP" という発表をしているのですが、これがとても興味深いことに、Leurent とほぼ同じ結果であることが主張されています（詳細はプレプリントに書かれています）。何が興味深いかというと Sasaki らは IPA の脆弱性関連情報に関する届出に従って届け出たために、論文を FSE 2007 に投稿することができなかったという点です。

ところがさらに驚くことに、これらの攻撃が拡張可能であることが、FSE 2007 のランプセッションで Sasaki, Kunihiro, Ohta によって報告されています ("Extended APOP Password Recovery Attack") 。報告によると、同様の Man-in-the-middle 攻撃によって、31文字のパスワードが特定可能となっています。研究レベルでは、パスワードが１文字でも特定可能ならば攻撃できたと表現することが多いのですが、現実的に疑問視されることが多いことも事実です。しかし31文字ともなると、現実的にも危なそうな気がしてしまいます。APOP が MD5 しか使えないのがあだとなっていますね。