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

タグ: Android, Prolog, 数学