OCR 耐性を有する視覚復号型秘密分散法を用いた CAPTCHA の提案

OCR 耐性を有する視覚復号型秘密分散法を用いた CAPTCHA の提案
A Proposal of CAPTCHA using Visual Cryptography with Defensiveness for OCR
言語情報学講座 0312013026 大澤奏絵
指導教員：高田豊雄 小倉加奈代 Bhed Bahadur Bista
1.
耐性を有する CAPTCHA を提案し，その有用性を
はじめに
近年，Web 上のサービスに対し，BOT を用いて
大量のアカウントを不正取得し，大量の不正なサー
検証する．
2.
ビス要求を行う DoS 攻撃が定常的に発生している．
関連研究
視覚復号型秘密分散法を用いた CAPTCHA とし
この問題に対処するため，Web 上の入力フォームな
ては鶴見の研究
どに対する入力が，悪意ある自動プログラムによる
Page1 に分散画像の 1 枚目を，Page2 に分散画像の
ものか，人間によるものか判別するテストとして
2 枚目を配置し，ユーザが認証画面下部のボタンを
CAPTCHA (Completely Automated Public Turing
押し，分散画像を遷移させた時に人間の眼の時間残
test to tell Computers and Humans Apart)が用い
像効果を利用して復号化する手法である（図 2）．文
られている．最も一般的な CAPTCHA の例として
献 2)で鶴見は分散画像を重ねて得られた画像を 2 種
は，図 1 のように画面上に文字列が書かれた画像を
類の OCR プログラムで処理しても秘密情報が得ら
表示し，ユーザがそれを読み取り入力する文字列
れなかったと報告している．しかし，鶴見の手法は
CAPTCHA があげられる．このような CAPTCHA
以下の問題点がある．

は文字列にノイズを加えたり歪みを加えたりするこ
とにより，悪意のあるプログラムによる読み取りを
3)がある．この手法は，認証画面の
ユーザの目に秘密情報が映るのが一瞬の
ため，秘密情報が読み取りにくい

困難にしている．
分散画像の重ね合わせ位置が固定である
ため，分散画像を重ね合わせた上で分散
画像の作成方法を逆に辿るようなピクセ
ル処理を行うことにより，OCR で読み取
られる危険性がある

図 1 文字列 CAPTCHA の例 1)
秘密情報が数字 2 桁しかないため，総当
たり攻撃に対して耐性がない
しかし，CAPTCHA を突破する技術も発達してお
り，光学文字認識(OCR)による突破事例も多く存在
する．文字列に加える歪みやノイズを大きくするこ
とで悪意のある BOT を排除する確率を向上できる
が, 人間にとっても読みづらいものになる．
一方，視覚復号型秘密分散法
2)は，秘密情報に画
像を用い，人間の視覚を利用することで秘密情報を
復号する手法のことである．この手法では，n 個の
分散画像のうち，どの k (≦ n )枚の画像を重ね合わ
せた場合にも隠された画像を見ることができ， k−1
図 2 既存手法のユーザインタフェース
3.
提案手法
人以下では隠された画像のいかなる情報も得ること
図 3 は，本提案で用いられる秘密画像，分散画像
ができない方式である．また，視覚復号型秘密分散
の例である．図を見てわかるように，関連研究との
法は復号の際に，計算機を使わずに済むため，計算
違いとして，認証情報の文字列が 4 桁の英数字であ
量が少なく済むという利点がある．
ること，2 枚の分散画像のサイズが異なる点が挙げ
そこで本稿では，視覚復号型秘密分散法を使用し
た CAPTCHA の既存研究の問題点である OCR への
られる．
本稿では，既存研究の問題点を解決するために，
分散画像の位置固定をせず，クライアント上で[2],
[3]のような分散画像を特定位置で重ね合わせるこ
4.
とにより，OCR に耐性を持った CAPTCHA を提案
する．これは，2 枚の分散画像の大きさが異なるこ
とにより，BOT に正しい重ね合わせ位置を全数探索
させることにより，図 3 の[1]で表示されるような認
証文字列を発見するまでの時間をかけさせることを
目的としている．
前章で説明した提案手法について，安全性とユー
ザビリティについての評価を行う．安全性とユーザ
ビリティにはトレードオフが生じるが，提案の性質
上安全性を重視して評価する．
4.1. 安全性評価
プロトタイプを用いて，悪意のあるプログラムが
処理手順は以下の通りである．
1.
サーバが，保存されている秘密画像[1]か
復号位置を特定する際の所要時間と，復号画像をピ
ら 1 枚を選び出し，視覚復号型秘密分散
クセル処理することによって OCR で読み取ること
法で分散し，2 枚の異なる大きさの分散
ができるまでの時間を計測する．
画像[2], [3]を生成する．
2.
3.
4.
5.
復号位置の特定にかかる時間とピクセル処理にか
認証に利用する秘密画像として，サーバ
かる時間を合計した時間を，BOT が CAPTCHA を
は生成された分散画像[2], [3]をクライア
突破するために必要な時間とし，安全性について考
ントに送り，クライアントは，それぞれを
察する．
事前に指定された位置に配置する．
4.2. ユーザビリティ評価
ユーザは，クライアントに表示された分
ユーザビリティについては，本学の大学生を対象と
散画像[2]を，もう一枚の分散画像[3]上で
してプロトタイプを用いた実験を行う．実験時に復
移動させて，秘密情報の探索を行う．
号 化 に 要 し た 時間 を 計 測す る ． ま た ， 実験 前 に
[2]と[3]を指定位置で重ねることで，ユー
CAPTCHA に対しての認識を確かめるアンケート
ザは秘密情報を読み取ることができる
を行い，実験後にプロトタイプを用いた感想につい
（[4]参照）．ユーザはそこで読み取った
てのアンケートを行う．復号に要した時間とアンケ
秘密情報をテキストボックスに入力する．
ートの結果から，ユーザビリティに問題がないか評
クライアントは，入力された文字をサー
価する．
バに送信し，受信したサーバは，受信した
5.
文字が正しいものであるか確認し，認証
を行う．
6.
評価方法
サーバは認証に成功した場合，その旨を
クライアントに返す．認証に失敗した場
合，失敗した旨をクライアントに返す．
分散画像の移動にはキーボードの方向キーを用い，
秘密画像を秘匿する分散画像は 2 枚用いる．また，
秘密画像の文字列に用いるフォントやそれぞれの画
像のサイズは可読性を重視して決定する．
まとめ
本稿では，視覚復号型秘密分散法を活用した
CAPTCHA の既存研究の問題点である OCR への耐
性を持つ手法を提案した．今後は，実験結果をもと
に，提案手法の改良を行う予定である．
参考文献
1)
Microsoft: https://signup.live.com（参照 201608-22）
2)
M. Naor and A. Shamir, “Visual
Cryptography”, Advances in Cryptology,
EUROCRYPT’94, pp.1-12, 1995.
3)
[1] 秘密画像
[3] 分散画像（大）
[2] 分散画像（小）
[4] 復号画像
図 3 本提案による復号の例
鶴見健太，“視覚復号型秘密分散法を用いた
CAPTCHA に関する提案”
，岩手県立大学ソフ
トウェア情報学部卒業論文 2014．