病みつきエンジニアブログ

機械学習、iPhoneアプリ、Javascript,Ruby on Railsなどなど。

IVSで優勝した「Capy CAPTCHA」は脆弱すぎると思う

Capy CAPTCHAは一瞬で突破できる - 素人がプログラミングを勉強していたブログ という記事を見て「これなら俺も一瞬で突破できそう」とか思って挑戦してみた。惨敗だった()

しかし画像処理技術や機械学習の技術を使わなくても、理論的に、容易に突破可能なはずだ。

Capyについて

Capyというのは、パズル型のCAPTCHA技術であり、先日行われたInfinity Ventures Summit 2013 FallのLaunchPadで優勝し、注目されている(Launch Pad 優勝は「Capy CAPTCHA」 Infinity Venture Summit 2日目 【@maskin】 #IVS | TechWave*1 )。

無料版の場合は、CAPTCHAに使われる画像として広告画像が使われるようであるが(離脱率10%を超えるCaptchaをたのしくすることで、セキュリティ認識の底上げを目指す「Capy」 - THE BRIDGE)、有料版であれば自由に画像を差し替えられるようである。

類似製品としてはKeyCAPTCHAなどがある。

Capyのデモ

Capyには、4種類のデモがある。このうち、画像ベースのものは2種類あるが、そのうち「フリースタイルパズル」の方が難しいので「フリースタイルパズル」をどのように突破するか、という視点で考えることにする。

画像処理的アプローチ

先にCapy CAPTCHAは一瞬で突破できる - 素人がプログラミングを勉強していたブログを紹介したが、ここで紹介されているうち「画像処理的な手法」はあまり堅牢ではないように思える。

理由は単純で、いくつかの仮定を置かざるを得ないからである。例えば、「パズルのピースの大きさがちゃんと一致する」とか「エッジがちゃんと検出できる」とか「ノイズがない」などである。すなわち、今のバージョンで一瞬で突破できるアルゴリズムを作っても、運営用によって一瞬で対応されるだろう、ということだ。

次の例はあくまで勝手に作った例だが、このような画像のエッジを検出できるのだろうか。

f:id:yamitzky:20131207064527j:plain

そこで、「背景画像の種類は少なくならざるを得ない」という性質を利用して、このCAPTCHAを突破することを考える

背景画像の種類が少ない仮定の元で突破する手法

例えば、背景画像の種類が1種類しかなかったとしよう。その場合、だいたい3回ちょっとアクセスすれば本来の背景画像が取得できることになる。下のような3つの画像の各画素ごとに、多数決を取ればよいからである。

f:id:yamitzky:20131207065602j:plain

背景画像の種類が100種類だったとしても、数百回程度アクセスすれば本来の画像が取得できる*2。本来の画像がわかれば、その差分がパズルのピースをはめるべき場所である。先ほどの画像も、差の絶対値を取れば以下のようになる*3

f:id:yamitzky:20131207071532j:plain

以上より、背景画像の種類が少なければ、本来の背景画像が容易に取得でき、一瞬でパズルを解くことができる

背景画像の種類が少ない根拠

「背景画像の種類は少なくならざるを得ない」と言ったが、その根拠を述べる。

Capyの背景画像は2種類ある。「ユーザーが設定した画像」か「広告画像」である。

まず、「ユーザーが設定した画像」についてだが、これはサイトごとに設定される。従って、各サイトがたくさんの種類の画像を用意しなければならないことになる。そうでなければ、先ほど述べたようにCAPTCHAが一瞬で解けてしまう。サイトがたくさん用意さえすれば良いので、背景画像の種類が少なくない可能性もあるが、限界があるだろう

次に、「広告画像」について。これは出稿する企業数によって、10000種類超えの画像が存在する可能性はあるから、堅牢かもしれない。ただし、一切の最適化が行われない、という前提であれば

普通、広告というのは、その広告を置くページのコンテンツ内容や、閲覧するユーザーに最適化を行う。しかしCapyのシステムで広告の最適化を行ってしまうと、広告画像の種類が少なくなってしまう可能性がある。そのコンテンツやユーザーに応じて、広告画像(=背景画像)の種類が絞られてしまう

以上より、「背景画像の種類は少ない」と考えるのが自然だと思うし、背景画像が少ない元ではCapy CAPTCHAは容易に破られてしまうだろう。他にもいくつか想定してみるも、自分の想像の範囲内では間違いなく突破できる。何か対策や、論理のほころびがあれば指摘していただけると幸いである。

使い道がないわけではない

Capy CAPTCHAは仕組み上脆弱にならざるを得ないと思うが、使い道がないわけではない。

本来CAPTCHAというのは別に絶対的な仕組みではないし(突破されることがある*4 )、あくまで当たる確率を下げ、「総当り」の精度を下げることに意味がある。例えば総当りで不正ログインを試みようとした時、1%の確率でしか突破できないCAPTCHAがあれば、その総当たり攻撃に必要な時間を100倍に伸ばすことができる(もしくはそこでロックできる)。

ただ、上であげたような画像差分による手法であれば準備さえすれば100%突破できるだろう。従って、現状は準備さえされなければ堅牢であるようなCAPTCHAであり、マイナーであるうちは使えるだろう*5

私としては、ちゃんと脆弱である可能性を説明した上で、利用してもらうのが正しいやり方だと思う。そんなまとめ方。

*1:ちなみに今年は2013年であるとともに「CAPTCHA」が正しい名称である

*2:コンプガチャの定理により、300回とはならない

*3:これも広義の画像処理的手法といえるかもしれないが、あまりに単純なのでそうではないこととする

*4:そもそも理論的には、どう頑張っても0にはできない。例えば完全なランダムでも、数千万回やれば当たる可能性がある

*5:メジャーになった暁には、何か特別な方法で、真に堅牢になっている可能性もある

広告を非表示にする