2015-02-04

パスワードはバレてから変更すれば良い派(最適変更間隔変じゃね)

パスワードをどれぐらいの期間で変えたら良い?という、面白い題材なんだけど、なんか違う。

パスワードの最適変更間隔とその定量的効果評価

https://docs.google.com/document/d/1RWDerFjLc24nr_lDhF8s0vEOJ8DPKhEnEAYG9qr_oBY/pub

あと、数式が苦手なだけで、この話題をなんとなくスルーする人がいるっぽくて勿体無い。

算数を使って、簡単にサラッと解説したいと思う。

まずはランダム確率の話から

ランダムだとか確率だとか、実は厳密に話だすと超ややこしい。

なので、一旦数学的な厳密さを忘れて、「一般的な話」として聞いて欲しい。

1~6の出目のサイコロを持ってるとしよう。

「3」をパスワードとして設定していたとすると、1回振って正解を出す確率は1/6だ。

  • 1回目にあたる確率は、1/6≒17%だ。
  • 2回目にあたる確率は、11/36≒31%だ。(2連続外し(5/6x5/6=25/36)で無い)
  • 3回目にあたる確率は、91/216≒42%だ。(3連続外し(5/6x5/6x5/6=125/216)で無い)
  • 6回目にあたる確率は、31031/46656≒67%だ。

中学で習ったかもしれないが、こういうのは余事象と言う。

計算すると判るんだけど、実は間違いなく「3」を出すには29回サイコロを振る必要がある(99.5%)。

食玩コンプリーターとかにはお馴染みの計算だね。

この部分が抜けてるから変なことになってる。

パスワードクラックの話

さて、パスワードクラックの話に移ろう。

銀行パスワードを思い出して欲しい。4桁の数字だね。

0000~9999までの1万通りある。(連番や4つ同じは大抵NGだけどここでは無視する)

そうすると、例えばネットバンク10秒に1回アタックできるとすると、

という感じに、全数が試せることになる。

ただ、「平均的にどれ位でクラック成功するか?」というのは、ランダムになる。

順番に試していくなら、0001なら20秒で成功するし、9998だったらほぼ28時間かかる。

というわけで、ざっくりとどんぐらいかな?というのは、大体半分ぐらいでアタリになるよね、

ラッキーなこともないけど、超アンラッキーってこともないから、真ん中ぐらい、と想定する。

ということになる。平均すると14時間ぐらいで攻撃成功する、と。

パスワードランダムに変更しても、確率は変わらない

さてここで、攻撃を受ける側も、ランダムパスワード一定時間で変更する。

まりサイコロの「3」がアタリだったのを、「6」がアタリに変えるわけだ。

2回目で31%(11/36)だったのに、3回目をふる前に変えられちゃったら17%(1/6)に逆戻りする!

と、行きたいところなんだがそうは問屋が卸さない。

2回目までで「3」を出していない確率は、5/6x5/6=25/36だ。で、3回目に「6」を出さな確率は5/6だ。

すると、3回連続で外す確率は25/36x5/6=125/216となって、アタリは91/216≒42%と、実は変更前と同じになる。

サイコロ記憶しないんだから、当たり前の話だよね。

例の数式は、何が変なのか

(ちゃんと読んでないのがバレるが)これって、0000,0001……と順番にアタックしていって、

パスワード変更後にまた0000, 0001……とアタックを再開するってモデル計算してるように見えるんだけど、違うかな。

誕生日パラドックス

と、言うかだね、攻撃者がランダム攻撃してきてて、防御者がランダムパスワード変更するのであれば、

本来は、パスワード変更間隔が短い時のクラック時間が短くなるグラフにならなければオカシイ

チョット想像して欲しいんだが、オマエの親父さんの銀行パスワードがオレのパスワードと一致してる確率は1/10000だ。
(親父さんの銀行パスワードが、オレの設定してるパスワードである0204とたまたま一致してる確率ね)
さて、ここで、オマエラが登場する。
すると、オマエラの親父1万人+オレがいると、必ず「誰かと誰か」のパスワードは一致する。
1万通りしかパスワードが無いんだから、1万1人いれば必ず「衝突」するわけね。
さて、じゃあ親父さんが何人集まれば「衝突」の確率50%を超えるか?
直感に反して申し訳ないが、119人の親父さんが集まれば51%になる。
通勤電車は1両にだいたい140人くらい載ってるから、誰かと誰かの暗証番号はたぶん同じだね。



つまり攻撃者がランダム攻撃するのに、防御者がランダムに変更してたら、衝突の可能性はグッと上がる。
極端なことを言えば、4桁パスワード10秒間隔で攻撃ができるサイトなら、
-黙って何もしなければ平均13.9時間クラックされる
-アタックの度(つまり10秒に1回)変更すれば、平均19.8分でクラックされる
これには、「誕生日攻撃」という名前がついてる。
これがグラフに出てこないのは変なんだよね。

追記:↑と、書いてたんだが、

双方ランダムで4桁の数字を出し合って、120回で衝突するって直感的に変だと思って、手元でサラッとシミュレートしてみたんだが……

あんま関係ないな。1万程度だと影響が全くない。(パスワード変更間隔変えて1000回づつ試行

というか、大体1万回ぐらいで攻撃成功するから、元々の期待値部分も変な気がする。(およそ27.8時間攻撃成功

10stepで10~990(100秒~165分)間隔でパスワード変更してみたけど、散布図上でも傾向見えないなあ。

やっぱコレ、N(パスワード空間)が小さい時って、単純な余事象範囲内で、確率変わらないんじゃないか?

パスワードを変更する必要があるとき

パスワード(の全部もしくは一部)がバレたとき、で良いと思うんだよね。

例えば、全然家に寄りつかないドラ息子が妙にATMお金をおろさせようとする。

金をおろした後、なんかスマホで撮ってたような気がする。なんてときは、サーモグラフィで数字4つはバレたかもしれない。

すると、たかだか24通りなので、1日3回ミスロックがかかる(つまり2回までは試せる)なら、6日でほぼクラックされる。

こういう時は、即変更するべき。

まとめ

最適変更間隔を調べるよりも、どの頻度から衝突の効果が無くなるか調べた方が面白いんでないかな。

(つまり、さっきの余事象の式に、さっきまでと同じパスワードでは無いという部分を加える)

http://b.hatena.ne.jp/entry/s/docs.google.com/document/d/1RWDerFjLc24nr_lDhF8s0vEOJ8DPKhEnEAYG9qr_oBY/pub

  • http://anond.hatelabo.jp/20150204201558

    いやこれは誕生日攻撃とは違う物だろ。 その計算、「自分のパスワードをランダムに変えたら過去に使ったことがあるパスワードと偶然一致した」事象までクラックに含めちゃってるぞ...

記事への反応(ブックマークコメント)

アーカイブ ヘルプ
ログイン ユーザー登録
ようこそ ゲスト さん