Oct 30, 2007

[Misc] CAPTCHA の安全性についてメモ

CAPTCHA の安全性が話題になっているみたいなのでメモ。

凪瀬 Blog - はてなのCAPTCHAは簡単に破れる
http://blogs.wankuma.com/nagise/archive/2007/10/26/104428.aspx
Radium Software Development - Breaking CAPTCHAs with NNs
http://www.radiumsoftware.com/0611.html#061110
高木浩光@自宅の日記 - 飾りじゃないのよCAPTCHAは 〜前代未聞のCAPTCHAもどき
http://takagi-hiromitsu.jp/diary/20060810.html#p01
Wikipedia - CAPTCHA
http://ja.wikipedia.org/wiki/CAPTCHA

より安全な CAPTCHA とは?

はてなの CAPTCHA が問題視されているわけだが、「では一体どういう CAPTCHA がより安全なのだろう?」 という疑問が当然出てくる。
Breaking CAPTCHAs with NNsによると、

CAPTCHA 破りの工程は,画像から文字を1文字づつ切り出す「分割」 (segmentation) の段階と, 切り出した文字を1文字ごとに解析する「認識」 (recognition) の段階から構成されるが, このうちコンピュータにとって困難なのは「分割」の方であり,「認識」は比較的容易であるとされる。
Kumar らの研究の結果は,文字による視覚 CAPCHA に関して, 文字毎の「認識」を困難にさせることを意図した歪みやノイズには全く意味が無く, そのような労力は文字の「分割」を困難にさせる方へと注がれることが望ましいという結論を導き出している。
ということで、「分割」し難い CAPTCHA が安全であるという研究結果が発表されているそうだ。 その研究結果を直接参照してみると、何故「分割」がコンピュータにとって難しいのかが説明されている。
4.1 The segmentation problem
As a review, segmentation is difficult for the following reasons:
  1. Segmentation is computationally expensive. In order to find valid patterns, a recognizer must attempt recognition at many different candidate locations.
  2. The segmentation function is complex. To segment successfully, the system must learn to identify which patterns are valid among the set of all possible valid and non-valid patterns. This task is intrinsically more difficult than classification because the space of input is considerably larger. Unlike the space of valid patterns, the space of non-valid patterns is typically too vast to sample. This is a problem for many learning algorithms which yield too many false positives when presented non-valid patterns.
  3. Identifying valid characters among a set of valid and invalid candidates is a combinatorial problem. For example, correctly identifying which 8 characters among 20 candidates (assuming 12 false positives), has a 1 in 125,970 (20 choose 8) chances of success by random guessing.
より安全な CAPTCHA が具体的にどういうものかというと、同じ論文内では以下の様に提案されている。
4.2 Building better/harder HIPs
The idea is that the additional arcs are themselves good candidates for false characters. The previous segmentation attacks would fail on this HIP. Furthermore, simple change of fonts, distortions, or arc types would require extensive work for the attacker to adjust to.
[stronger captcha]
この方式のより詳細な情報が Building Segmentation Based Humanfriendly Human Interaction Proofs (HIPs) に記載されている。
Using Machine Learning to Break Visual Human Interaction Proofs (HIPs)
http://research.microsoft.com/~kumarc/pubs/chellapilla_nips04.pdf
Building Segmentation Based Humanfriendly Human Interaction Proofs (HIPs)
http://research.microsoft.com/~kumarc/pubs/chellapilla_hip05.pdf

CAPTCHA の実装(Java)

Wikipedia の CAPTCHA によると、CAPTCHA の Java 実装は結構あるようだ。

The JCAPTCHA Project
http://jcaptcha.sourceforge.net/
The reCAPTCHA Project
http://www.crt.realtors.org/projects/reCaptcha/
The simple CAPTCHA Project
http://simplecaptcha.sourceforge.net/
この中でどれがより安全だろうか?? JCAPTCHA の DoubleRandomListGimpyEngineCaptcha が分割しにくいように見えるけれど・・・。

Posted in Misc | このエントリーをはてなブックマークに追加 | この記事をクリップ! livedoor クリップ |