IVSで優勝したというパズル型CAPTCHA Capyを突破してみた

こんにちは KOBA789 です。前回に引き続き Capy のパズルタイプを突破するお話です。

Capy がより堅牢な CAPTCHA ソリューションにためには突破するためのアルゴリズムを公開することが重要だと考え、解説をするに至りました。

ちなみに今回紹介するアルゴリズムは前回の記事とはまったく別物です。今日の夕方頃、Capy に仕様変更があり、背景画像のバリエーションが増えたようです。前回紹介したアルゴリズムはそのような仕様変更でほぼ無効化されると思われます。しかし、今回紹介するアルゴリズムはそのような変更の影響を原理的に受けません。影響を受けない理由も考えて解説をお読みいただければと思います。

Capy とは

前回の記事では執筆時間の関係で端折ったのですが、今回は少しまともに解説をしておきましょう。

公式サイトより引用します。

Capyが提供する国際特許出願済のソリューションは、“セキュリティ x デザイン”の合わせ技。今まで“ストレスの種”となっていたCAPTCHAが“楽しい”とすら感じる、全く新しいCapy CAPTCHAの開発に成功しました。Capy CAPTCHAはサイトの統一性を保ちながらも高いセキュリティ性を発揮し、サイト訪問者とサイト運営者のニーズを両方同時に満たすことができるのです。 Capy CAPTCHAはPCだけでなく、スマートフォンやタブレットなどのタッチデバイスにも完全対応。指一本の動作で認証完了です。

従来のイライラするだけの CAPTCHA ではない、というのがウリのようです。個人的にはスマートフォンでの操作性が一番嬉しいんですけどね。

パズルタイプ

さてこの Capy にはいくつかタイプがありまして、そのうちのひとつが パズルタイプ です。

このように、ピースの形が繰り抜かれた画像が上に、そこにピッタリ収まるピースが下にあるという画面構成が、パズルタイプです。ユーザーは、ピースをドラッグして上の画像に重ね、ピッタリの位置にドロップします。送信ボタンを押すとピースの座標が送信され、サーバーサイドで一致の確認が行われます。

今回突破するのはこのタイプです。

デモ

今回紹介するアルゴリズムを実装したデモです。実際に動かしてご確認ください。またソースも読めるようになっていますので、参考にしてください。

デモ: CAPY HACK

アルゴリズム

今回対象となるのはこの画像です。

アルゴリズムは至って単純です。細かいことはソースコードを読んでいただくとして、概要だけ説明します。手順は主に2つです。

1.ピースのエッジ検出

左が元画像です。ピースのエッジ(輪郭)を抽出し、そのピクセルの色相を求めます。そしてそれらを表として保持します。

2.マッチング

まず、最適なピースの位置では、ピースのエッジとその隣のピクセルの色相の差が最も小さくなるはずであるという仮定をします。根拠としては、写真のような画像は1ピクセル隣の色相がいきなり反転するような並びを含みにくいからです。

ということで、エッジの色相の差を計算します。次の図を参照してください。

マス目を各ピクセルに見立てています。エッジより左が背景部分、右がピース部分だと思ってください。正方形内の数字は色相の値、点線内の数字は右と左の差の値です。これらの差の値をすべて足し、合計を求めます。その合計が小さいほど、「その位置がピースの位置にふさわしい」ということになります。

実際の画像ではこのようになります。わかりやすいように黒でエッジを描いてあります。

内側に青、外側にオレンジで色をつけたものがこちらです。

さらに拡大し、ピクセルをそれぞれの色で囲みました。するとこうです。

よって、最適な位置を見つけるためには、少しづつ位置をずらしならがら色相の差を求め、その値が最小となる位置を記録すればよいことになります。

Capy では 10px ごとにスナップする仕様なので、一度にずらす量は 10px でよいということになります。執筆時点の仕様では背景部分が 400px * 267px、ピース部分が 120px * 120px の画像ですので、((400 - 120) / 10) * ((267 - 120) / 10) = 411.6 ということで 411 回ほどこのマッチング処理を行えばいいようです。

アルゴリズムの解説は以上です。RGB から色相を求める式などについては説明しませんでしたが、簡単ですし、調べればいくらでもわかるかと思います。また、JavaScript や HTML5 など、実装に用いた技術についての解説は本質ではないため、していません。

まとめ

自動でパズルを解く仕組みを理解していただけましたでしょうか。所詮、2時間程度で書いたコードですのでひどい実装ではあるのですが、アルゴリズムとしてはそこそこの精度が出ます(デモでお試しください)。1回間違えると即スパム判定でボツ、という仕様でもない限りは順調にチェックをすり抜けることができるかと思います。

この解説が Capy がなぜ脆弱であるか、どうしたら堅牢にできるのかを考えるための礎となれば幸いです。