2007-08-16  高速パスワード・デコーダの開発

※この記事では，パスワードを解読する手順を述べています。肝心なことは書かないように配慮していますが，注意してください。

スキャンティ・システム，先月の下旬に全体計画を説明しました。その後，STEP3の実装物にあたるパスワード・デコーダの試作に成功しました。デコーダ（＜英＞decoder，解読器）の正体はパスワードの一覧表です。現在のパスワード・デコーダは，投稿文の9割を1件当たり0.4秒の速さで解読することができます（プロセッサ：Mobile Athlon XP-M 1800+，クロック周波数：1.2GHzの場合）。

パスワードの解読っていかにも怪しい感じがするのです。業界の人であれば「パスワードを解読するってよく聞く話だけど，実際どうやるの？」と思ったはず。今回，私はパスワードの解読を経て，さまざまな発見をしました。分かったことをすべて書いてしまうと安全上，重大な問題を引き起こしそうです。

そこで内容を吟味し，解読の手順，パスワードの全体傾向，パスワードの望ましい扱い方をお話しすることにします。

解読の手順

世の中に存在する「問題」には，簡単なものから難しいものまでいろいろとあります。パスワードの解読は「難しい問題」のひとつでしょう。なぜ難しいのか。数学的に解釈すると，パスワードの解読は「組み合わせ問題」です。組み合わせの種類は限られているので，「全部試してみればいいじゃん」と思うかもしれませんが，それは無理です。なにしろ試さなければならない数が膨大なのです。「100通り」であるとか「1,000通り」なんて可愛いものではありません。

仮にパスワードが8桁の数字だったとします。1億通りを試さなければなりません。さらに今回，扱うパスワードって，何桁なのか分かりません。全桁が数字とも限らないわけです。そうなると，組み合わせの種類の単位は「億」では済まなくて，「兆」や「京」がつく世界になります。現在のコンピュータはとても高速ですが，それでも簡単に解ける量ではありません。

さて冒頭で，「パスワードの解読は組み合わせ問題だ」とお話しました。たしかにそうなのですが，だからといってすぐに組み合わせを作るための処理の手順を考えたり，プログラムを作ってしまったりするのは早合点というものです。まずパスワードの性質を整理することにします。パスワードを解く鍵は，いつ，だれが，どんな場面で，どのようにして扱うものなのかを把握しておくことなのです。

• 扱うパスワードは人間が思いつく文字列である。機械的な乱数ではない
• 人間には覚えやすい文字の並びと，覚え難い文字の並びがある
• パスワードはキー操作によって入力する。指には関節の構造上，動かしやすい方向と，動かし難い方向が存在する

――これからはすべて，パスワードは必ずしもデタラメというわけではなくて，何らかの規則性が存在することを示唆しています。しかしながら，あくまで仮説です。なんとなくそう思うだけです。どこまで有効なのか，まったく分からないわけですね。ところで，今回のように何から手を付ければ良いのか分からない問題の場合は，仮説を検証して新たな仮説を立てて，その仮説を検証して‥‥という作業の繰り返しになります。

パスワードの全体傾向

前節では「パスワードには何らかの規則性があるはず」という仮説を立てました。さっそく仮説を検証することにしましょう。

検証作業はなるべく簡単な方法を採用すべきです。ひとまず「4桁の数字」という足かせをして，実際にパスワードを解いてみることにしました。みんながみんな4桁の数字をパスワードにしているわけではないのでしょうけれど，何割かは解ける気がしたのです。「木を見て，森を見よう」というわけです。

パスワードが4桁の数字の場合，組み合わせは1万通りあります。今回は1万件の投稿文に対して解読してみることにしました。施行回数は最大で1億回です。実際には，パスワードが解けた投稿文は以後，解読の対象から外れますので施行回数はもっと少なくなります。それでも結果が得られるまで数時間掛かりました。

以下，結果発表です。

＜画像の説明＞4桁の数字を上位2桁と下位2桁に分けて，2次元平面上に頻度を描いてみることにしました。点の有無がパスワードの有無に対応します。点が多く集まっている個所と，ほとんどない個所があることが分かりました。対角線上に点が集まっていることに気づいた人がいるかもしれません。これらは「5555」や「7777」のような，ぞろ目の数字です。覚えやすくて，しかも入力しやすい数字の並びだと言えます。

＜画像の説明＞つぎに上位2桁と下位2桁の数字の出現頻度を，度数分布表にしてみることにしました。中央の目盛線と山の勾配に注目してください。上位2桁は偏りが大きく，下位2桁は偏りが小さいことが分かりました。なぜこんな結果が得られるのか。相変わらず生年月日をパスワードにしている人がいるからなのです。月は1から12，日は1から31。子どもが生まれる月は均一ではないので（真夏や真冬に生まれると育てるのが大変でしょ），パスワードもその影響を受けてしまっているのです。

＜画像の説明＞話は飛びますが，得られた結果から高速デコーダを作ってみました。画像は高速デコーダが出力するパスワードの候補関数の分布です。端折って説明すると，高速デコーダは図の左上の領域は丁寧に調べるけれど，右下はほとんど調べないという動作をします。現在の高速デコーダは，4桁から8桁のパスワードに適用できます。過去に解読したパスワードの一覧，ならびにパスワードの統計的な偏りを利用することで，高速にパスワードを解くことができます。

いま高速デコーダの性能を高めるための準備をしています。やるべきことはすでに見当がついていて，検証作業をしているところです。

パスワードの望ましい扱い方

最後に，破られにくいパスワードのお話をします。今回，解読したのはネット掲示板の削除パスワードなので，バレてしまったからといって実生活への影響はほとんどなさそうです。

ところで銀行のキャッシュカードの暗証番号も，携帯電話のロック番号も，mixiのパスワードも「全部同じ」なんて人はいませんか。そんな人は，掲示板の削除パスワードが解読されてしまっただけで，全財産が脅かされる事態になってしまうのかもしれません。以下，注意点をお話しますので，必要であればパスワードを変えてみてくださいね。私は刺されたいわけでもなければ，他人から呪われたいわけでもないのです。

• パスワードを自分で考えてはいけない。機械的に生成したパスワードを使う
• パスワードを兼用しない
• 中途半端に強い同じパスワードを常用してはいけない。解かれてしまった場合に個人識別を容易にする。非常に危険

――ちなみに「強力なパスワードがほしいけれど思いつかなくて困っている」という方は，「yumi-ii | パスワード文字列を作る」をお試しください。機械的なパスワードが得られます。携帯電話に辞書登録しておけば，複雑なパスワードでも簡単に呼び出すことができますよ。「パスワードをいくつも覚えられないから，つい同じパスワードを使ってしまう」という人は，パスワードを3種類くらい覚えて，サービスの重要度に応じて使い分けるという方法もあるようです。