Androidのロック解除用パターンは何パターンあるのか

携帯のロック/解除には多くの場合4桁くらいのPINを使うけど、Android携帯HTC G1のロック/解除はタッチパネルを使った独自の方式の模様。どんなもんかはデモのビデオを見ればすぐわかる。これはちょっと面白い。

TechCrunchでも、セキュリティに関して懸念があると紹介されてる(ビデオ公開から5ヶ月後って遅くないか?)。

TechCrunch Japanese アーカイブ » Androidのログインはクールだがセキュリティは?

そのほかの電話機はアンロックするのに4桁の番号が必要だが、Androidではタッチスクリーンに9つのドットが正方形に並んで”draw pattern to unlock(アンロックするためのパターンを描いてください)”のメッセージが出るだけだ。どんなパターンでもいいが、4つ以上のドットを使うことが条件と聞いている。可能なパターンの数はとても多いから(数学の得意な人、いくつなのか教えて)、電話機をロック/アンロックする方法として適切だと思える。

ただし、タッチスクリーンの意外な弱点が、Googleを困らせているかも知れない。

聞いた話では、使っているうちに指の脂肪がタッチスクリーンに残るので、その形を見たらアンロックのためのパターンが分かる場合がありそうだと。とくに、パターンを左上のドットからスタートして右や下に行く人が多いので、パターンの推測も比較的やさしいとか。

指の脂でバレるかもしれないのか。面白いなあ。セキュリティについて考えるときは、あらゆる層で、あらゆる要因を考慮しなくちゃいけないことを改めて思い出させる。

それはともかく、やっぱり気になるのはこの方式の数学的な強さのほう。「数学の得意な人、いくつなのか教えて」なんて書いてるけど、こんなの計算機に数えさせれば簡単じゃん。やっぱりTechCrunchのライターは文系なのかな。

で、学生時代に授業でやったっきりのPrologを頭の隅から引っ張り出してきて書いてみた。グラフの探索ならお手の物だろうと思ったんだけど書きあがってみたら想定と全然違うコードになった。

nodes([a,b,c,d,e,f,g,h,i]).

%% horizontal and vertical
%%
%% a-b-c
%% | | |
%% d-e-f
%% | | |
%% g-h-i
%%
neighbor(a,b).
neighbor(b,a).
neighbor(b,c).
neighbor(c,b).
neighbor(d,e).
neighbor(e,d).
neighbor(e,f).
neighbor(f,e).
neighbor(g,h).
neighbor(h,g).
neighbor(h,i).
neighbor(i,h).
neighbor(a,d).
neighbor(d,a).
neighbor(d,g).
neighbor(g,d).
neighbor(b,e).
neighbor(e,b).
neighbor(e,h).
neighbor(h,e).
neighbor(c,f).
neighbor(f,c).
neighbor(f,i).
neighbor(i,f).

%% diagonal
%%
%% a b c
%%  X X
%% d e f
%%  X X
%% g h i
%%
%% neighbor(a,e).
%% neighbor(e,a).
%% neighbor(b,d).
%% neighbor(d,b).
%% neighbor(b,f).
%% neighbor(f,b).
%% neighbor(c,e).
%% neighbor(e,c).
%% neighbor(d,h).
%% neighbor(h,d).
%% neighbor(e,g).
%% neighbor(g,e).
%% neighbor(e,i).
%% neighbor(i,e).
%% neighbor(f,h).
%% neighbor(h,f).

combination(0, _, []).
combination(N, [X|T], [X|C]):- N>0, N1 is N-1, combination(N1, T, C).
combination(N, [_|T], C):- N>0, combination(N, T, C).

path([X|[Y]]) :- neighbor(X, Y).
path([X|[Y|L]]) :- neighbor(X, Y), path([Y|L]).

pattern(N, Z) :- nodes(L), combination(N, L, X), permutation(X, Z), path(Z).

count(N, 0) :- N>9, !.
count(N, K) :- findall(T, pattern(N, T), Z), length(Z, K1),
	format('~d nodes: ~d patterns~n', [N, K1]), count(N+1, K2), K is K1+K2.

68行目、combinationしてからpermutationするところがいかにも汚い。当初はここでもうグラフのトポロジーを使って枝がいっぱい刈れる予定だった。それに、このページでは順序つきの組み合わせがvariationという名前で1個の述語で書かれてる。これを使えばいいんだけど、術語としては正しいものの、うまくバックトラックしてくれない。なんかdeleteの引数の順序が違うし。うまく動くvariationを書けなかった見つけられなかったので断念。

まあ結果は出た。

斜め移動なし

?- count(4,K).
4 nodes: 80 patterns
5 nodes: 104 patterns
6 nodes: 128 patterns
7 nodes: 112 patterns
8 nodes: 112 patterns
9 nodes: 40 patterns

K = 576

斜め移動あり

?- count(4,K).
4 nodes: 496 patterns
5 nodes: 1208 patterns
6 nodes: 2240 patterns
7 nodes: 2984 patterns
8 nodes: 2384 patterns
9 nodes: 784 patterns

K = 10096

斜め移動を許さなければ576通り、斜め移動ありなら10096通り。ビデオを見る限り斜めはなしっぽいんだけどな。

4桁のPINなら10000通りなので、576通りじゃ少ないのかもしれない。でも、4桁のPINと比べてパターンが少ないことだけをもって安全でないとは言いきれないような気もする。

TechCrunch英語版(原文)のコメント欄に投稿しといた。なんとかあの英語を理解してくれる人がいるといいけど…。

広告

タグ: , ,

コメント / トラックバック4件 to “Androidのロック解除用パターンは何パターンあるのか”

  1. ちょっと席を立つ時には「LockMe Widget」 | Androidあぷぷ -Androidのオススメアプリ情報を毎日お届け- Says:

    […] Androidのロック解除用パターンは何パターンあるのか « Moukari […]

  2. のぶのぶ Says:

    はじめまして!
    Prologなんて、懐かしい響きです。

    HT-03Aの実機で試すと、上記以外のパターン登録も可能です。
    斜めについては、a-h のような桂馬飛びもできます。

    あと、ちょっとややこしいですが、
    bをまだ通過していない場合には、a-c という直接接続はできないのですが、
    bが別のルートで使用されている場合には、aからcへの接続が可能となります。
    たとえば
    a-h-f-e-c-i-d-g-b
    なんてたどり方もできます。
    なので、もっとパターン数は多くなりますね。

  3. のぶのぶ Says:

    自己レス投稿で申し訳ありません。
    ttp://beust.com/weblog/archives/000497.html
    に、先日書いた上記以外の、桂馬とびや飛び越し接続を加味した計算結果が載っています。
    これによると最終的には、389112通りとのこと、4点だけども1624通りあるようです。
    ご参考まで

  4. moukari Says:

    お返事遅くてすみません。
    桂馬飛びは思いつきませんでしたね。TechCrunchのコメントでも桂馬飛びを考えている人はいなかったように思います。ユーザから見れば、「パッと見で直線でつなげられるならば、つなげられる」という仕様になっていて、とてもいいですね。
    自分のプログラムでは、桂馬飛びはそのまま対応できますが、使用済みノードの飛び越しまで含めると対応できませんね…。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中


%d人のブロガーが「いいね」をつけました。