2013年11月10日日曜日

画像認証カタログその5:あわせ絵

順番とかいろいろ考えていたのですが、先にあわせ絵を紹介しましょう。

あわせ絵

初出は2003年。残念ながらデモシステムは現在動作していないのですがおおよその動作原理はこちらです。

Awase-E: System Demonstration

デモシステムでは3×3の9枚の画像を提示します。この中に「正解画像」が一枚含まれます。その正解画像を選択すると次の同様の画面に移行します。正解画像を複数枚決めておき、例えば3枚の正解画像があれば三回上記を繰り返し全部正解すると認証が成功します。



このシステムのユニークなところは正解画像を含まない提示画面が生成されることで、その場合はスキップを選択します。



この系統の認証システムにおいては、正解画像はどう足掻いても一回認証を完了するまでに必ず表示される必要がありますので、それ以外の画像(おとり画像)とは出現頻度が変わってしまいます。気長に統計を取って行くとそこから正解画像が割り出せてしまいます。たぶん、そこを緩和するためのスキップ動作なのでしょう。

この系統の認証システムの問題は、おとり画像を増やせば増やすほど正解画像との出現頻度の差が開いてしまい破られやすくなるというところです。

ではいっそおとり画像も全部自分で用意してしまえばという気もするのですが、そうすると、「自分で撮影した写真は(記憶と結びついているため)判別しやすい」というシステムの根幹を崩してしまいます。

つまり、単純に正解画像を記憶するというのでは長いパスワードを記憶するのとさほど変わらないため、正解画像は何らかの理由で認証者本人にとって記憶しやすいものである必要があるのです。

Deja Vuでは単純な計算図形を用いるわけで、覚えるの無理という感じであり、そこをちゃんと考慮していないんじゃないの?というのは既に述べた通りです。Passfacesでは「人間は人間の顔を記憶するのが得意」という原理でそこを補っているのですが、本当か?という気がしますよね。

スキップという仕組みを入れれば、提示画像に正解画像が含まれているかどうかは分からなくなるわけなので、攻撃の手間は大きく増えることになるでしょう。

あわせ絵はスキップという画期的な仕掛けを画像認証に持ち込んだということで歴史的に
特筆されるべき方式であると言えるでしょう。

画像認証リンク集

ちょっと間が空きましたが、いろいろ紹介したいものはあるのですがひとまずリハビリ、リハビリ。

ということで「あわせ絵」を考案した方のホームページとブログはこちら。

Personal Web Page of Tetsuji Takada
Research Survey and Memo

そもそもこのブログの元ネタはほとんどここからいただいています。

最近更新がないのですよね。あわせ絵のデモシステムももう動いてないみたいですし…。

2013年5月9日木曜日

画像認証カタログその4:Deja Vu

Deja Vu

しばらく間があきましたが、4件目。Deja Vuの話です。(本当はアクセント記号がつくのだがBloggerの制限らしく入力できず。)

Déjà Vu: A User Study Using Images for Authentication

リンク先はRachna DhamijaとAdrian Perrigによって書かれた2000年の論文のようです。(usenix.org)
論文中に書かれている内容を読むと、「写真のようなものを正解画像に使用すると、それを言葉で表現することが容易になり、それをメモに取ったり他人に教えてしまったりする」ためセキュリティ強度が下がる、ということが書いてあります。これを防ぐために数学的に生成された図形を用いるというのがこの方式の核心であるようです。
で、この画像(上記リンク先より)は自分の「正解画像」を決定するための画面のようです。(ポートフォリオ構築フェーズ)


認証フェーズでは、このポートフォリオに含まれる画像とそうでない画像を複数混ぜて並べておき、正しい画像だけを選択することに成功すると認証成功になるということですね。

分類と考察

これも前回のPassFacesと同様「システム提供画像」型「複数絵並べる」型「画像選択」型になると思います。特徴は自然画像ではなく数学的に生成された図形を使用すること。
しかしさすがにこの図形画像を覚えるのはちょっと大変な気がします。類似の画像を並べられたときに識別できるかというのもちょっと疑問がありますね。この欠点を克服すべくもっと「覚えやすい」画像を追求したものがPassFaces等なのであろうと思います。
この論文では画像認証に特徴的な4種類の攻撃法「Brute-force攻撃」「Educated Guess攻撃」「Observer攻撃」「Intersection攻撃」が分類されて紹介されているのも注目すべきところであると思われます。

2013年4月14日日曜日

画像認証カタログその3:Passfaces

顔認証、ではなく、人間の顔認識能力を利用するPassfaces

三つ目にご紹介するのは「Passfaces」です。現在は「Passfaces Corporation」という名前になっているようですが、当時の社名はReal Userだったようですね。こういうの(PDF)が見つかるので、少なくとも2003年にはアイデアが固まっていたようです。
ちなみに、話がちょっと逸れますが、ここにかかれている「普通の文字列の」パスワードの問題点というのは今でも解決できていませんね。ここ数ヶ月は「安易な」パスワードの使い回しが原因と思われるサイト侵入が多数発生していますから、もう少し真剣に議論されるべきではないかとは思ったりします。
当時realuser.com、現在のpassfaces.comにいくつかホワイトペーパーが公開されています。「The Science Behind Passfaces」は一読の価値はあるかも知れません。
しかしrealuser.comとpassfaces.comのリンクが入り乱れていて厳しいwebサイトですね…。プレスリリース等も出ているようなので、これを主な商品として会社は今でも存続しているようです。(そのうちご紹介しますが、この業界は結構会社が短命なことも多いです。)

基本的な仕組み

基本的な仕組みは、秘密情報として顔画像を記憶しておくというものです。秘密情報に指定されたものを含めて複数の顔画像を並べて表示し、その中から正しいものを選択することによって認証を行う仕組みです。

理論的な裏付けとして述べられているのは、人間は人間の顔を識別する能力や記憶する能力が高い、という話です。そういうことはあるのかも知れません。が、難しいですよね。外国人の顔は全部同じに見える、みたいなこともよく言われますし、人の顔を覚えられない人って実際いるような気がします。似たような顔の人を二人並べられたときにどっちか言えるかというと確実じゃないような気がします。
こんなビデオがYouTubeに転がっていたりします。2009年のもの。

分類と考察

みたところ画像はシステム側が用意したものを使うようです。まあそれは当たり前かもしれません。知り合いの顔画像を使ったりしたら一発で破られてしまいますから。分類すると、「システム提供画像」型「複数絵並べる」型「画像選択」型という感じでしょうか。
すでに指摘もありますが、「毎回出現する画像」を発見されてしまうと割と簡単に突破されてしまうという話もあるので、実用的にはどうなのかなという気はします。実は画像認証ってこの画像を並べて表示して正解画像を選択させる、というタイプが多いのです。これだとランダムでも突破される確率がそれなりにあるので、そこをどうするかなどいろいろ課題は多いなあと思っていたりします。実運用されているところが見てみたいという気もするのですが、なかなかそういうところに出会いません。

2013年4月9日火曜日

画像認証カタログその2:Blonder特許

Blonder特許

この辺の論文等で引用されている中でも古い部類にはいるのが、1994年に出願された「Graphical Password」という特許(USP5559961)です。(公開1996年)Lucent Technology(AT&Tからスピンアウトした通信技術系企業、後のアルカテル=ルーセント)のGreg Blonderという人が書いたもののようです。
1996年に公開されたところまでは書誌から分かるのだけど…登録番号もらってるし登録なんだろうな。USPが特許公開制度に移行する前だったのですね。(末尾がAになっている。)

Lucentって

LucentはAT&Tからスピンアウトするときにベル研を傘下に抱えていたので1990年台後半、結構な存在感というか技術的な話題の中心的役割というかそういうのを持っていました。InfernoなんていうOSは相当面白そうだったりしたのですが。
もったいないですねえ。
ちなみに、すでにNewtonは世の中に出ていたりしましたので、このBlonder特許もPDAやペン入力コンピュータを意識したものであったのだと思います。あとタッチパネルKioskなんていうのも世の中に普通に出てきていた頃でしたね。

Graphical Password

で、特許の中身ですが、ユーザーが画像上で指示した座標をメモリにパスワードとして保存する方法および、ユーザーが指示した座標がメモリにパスワードとして保存されたものと一致していたらアクセスを承認し、一致していなかったら承認しない、という話です。その1で取り上げたPassPointsとあまり変わらないというか、基本原理はそのものですね。
PassPointsは入力された座標が一致しているかという判定を(クリックする座標はブレるものなので)ある範囲で容認するとかそういう実装面での工夫が入ったのだと思います。まあPassPointsは特許ではなく論文だったのでそこも関係しているのかと思います。

分類と考察

考察と言うほどは見てなかったりします。PassPointsがリアル実装なのを考えると分類的には「システム提供画像」型「一枚絵」型「座標」型なのでしょうかね。ある意味記念碑的な特許のような気がします。とはいえこの特許で引用されているさらなる先行特許もあったりします。その辺もそのうち研究してみよう。

2013年4月8日月曜日

画像認証カタログその1:PassPoints

画像認証ブログなう

画像認証と言うと「CAPTCHA」がすっかり有名になりました。有名というか悪名高いというか、まあ面倒な仕組みとして認識されているものと思います。
このブログではCAPTCHAは脇においておいて、画像で認証する方式を扱いたいと思っています。つまりパスワードの役割を果たすような画像を用いた認証方式について綴っていきたいと思っています。もちろんCAPTCHAとここで言う意味の「画像認証」はある意味親戚というか地続きなのですが、原理や用途が少しずれているので一応区別していきたいと思います。

画像で認証してパスワードにする話

画像で認証してログインできるようにするという話は昔からあるにはあるらしいです。
そんなに珍しい発想ではないらしい。
まあ詳しい歴史とかは今後また研究していこうかと思いますが、ひとまず有名どころを一個ずつ紹介していこうかなとか。

PassPoints

最初のやつはPassPointsです。
PassPoints: Design and longitudinal evaluation of a graphical password system
2005年の論文ですね。原理は、画像を提示されたらその上の座標を複数順番にクリックするというものです。ある意味、現在のWindows 8の画像認証の直接のご先祖様のようなシステムです。(Windows 8の方式については後々触れる機会があるでしょう。)



分類と考察

分類としては「システム提供画像」型「一枚絵」型「座標」型になるかと思います。(分類については追々整理していきます。)
そんなに穴のあるシステムではないと思います。そこそこの実用性と堅牢性があるんじゃないかと思っています。何もないところから破ろうと思えばかなり困難ではないかと思いますし、ポイント数を増やせば強度は上げることができます。
ただし画像が毎回同じというのが弱点でしょう。人間がこの手の画像上に任意に座標を設定しようとする場合、多分、何か目印になるものを選ぶと思います。たとえば写っている人物の顔とかパラソルの先端とか…。そういうところから突破されそうですね。
それと現代のタッチパネルシステムで実装することを考えた場合、パネルに指紋が残りますので、それを利用すると突破されやすい気がします。
あとネットワーク越しにサーバーに座標を送って認証することを考えてみると、ちょっと難しいんじゃないかという考察ができます。座標を生で送信するのは論外として、一枚の画像を表示したままにしてその上のクリックされた座標を次々送信するというのは大変かも知れません。盗聴されると怖いですし。
Webで実装するとしたらどうするのだろう。JavaAppletで実装して座標は最後にまとめて暗号化して送信すればいいのかな。HTMLで構成したweb UIでもJavaScriptを駆使すればなんとかなるのかな。

まとめ

実はPassPointsそこそこ面白いというのが分かりました。
Modeling user choice in the PassPoints graphical password scheme(2007)
Purely Automated Attacks on PassPoints-Style Graphical Passwords(2010)
みたいな関連論文も出てますね。自動攻撃の論文は面白そうです。