パスワード防御に対する風評

元記事は、期間限定で無料で読める記事だから、はてブのページを示しておく。

はてなブックマーク - 「ハッシュ化したから安全」と主張するのをそろそろやめようか | 日経 xTECH（クロステック）

元記事の内容は、パスワードをハッシュ化しているから大丈夫、というのは言いすぎだ、という内容で、それはごもっともなのだが、後半にかけて、いかに危険なのかを煽る内容になっていた。

大雑把に言えば、「ハッシュ化していたとしても、パスワードが判明することがある」ということを主張しているのだが、攻撃手法と防衛手法がきちんと整理されていない印象だった。

パスワード・クラッキングの手法には、下記のようなものがある。

逆引き

ハッシュ化された値が分っている「オフライン・クラッキング」の場合に可能な手法で、平文のパスワードと、ハッシュ化後の値との組み合わせをデータベース化したものを用意し、それを検索することで元のパスワード知る方法。

普通にやると、そのデータベースが簡単に巨大になってしまうので、この目的のための効率的なデータ構造として登場したのが、いわゆる「レインボーテーブル」。

この手法の特徴は、他の手法に比べて圧倒的に短い時間でパスワードが判明すること。ただし、

• ハッシュ化のアルゴリズム毎にデータを用意する必要がある。
• レインボーテーブルで容量を小さくできる、と言っても、パスワードが1文字増えれば、用意すべきデータは２桁ぐらい大きくなるので、長いパスワードに対応しようとすると、必要なリソースが簡単に大きくなってしまう。

というのが弱点。

辞書攻撃

人間がつけそうなパスワード文字列を準備・生成し、その文字列に対してハッシュ化の計算をしたり、実際に対象システムに送信する。

いわゆる「脆弱なパスワード」は高確率で元のパスワードを発見することができるが、本気でランダムな長いパスワードは、そもそも試行されないことになるので、発見されることは、基本的には無い。

どのくらいの確率でパスワードが判明するかは、辞書がどれだけ豊富なのか、ということになるが、最近は、すでに漏洩されているアカウント情報が広く流通していることを考えると、人間がつけやすい、だけじゃなく、一度、誰かが設定したパスワードに合致、というケースもあるかもしれない。

総当たり攻撃

この世のすべての文字列を試す、というもの。原理的には、どんなパスワードでも発見できるが、パスワード長がちょっと長くなると、あっという間にこの攻撃は破綻する。ASCII 図形文字と半角スペース合わせて 95 種の文字が使えるとしたら、n 文字のパスワードは 95ⁿ通りとなる。実際に計算して見れば分かるが、10 文字でも 59,873,693,923,837,890,625 通りに達する。1文字増えれば、95 倍になる。

一世を風靡した Ophcrack も、基本的にはレインボーテーブルを使うが、4文字までは ASCII 文字の総当たりを行う。

オフライン・クラッキングに対して、防御方法としてソルトとストレッチングがあるが、ソルトは上記の攻撃のうち、逆引きに対抗するものであり、辞書攻撃や総当たり攻撃には効果はない。逆に、ストレッチングは、ストレッチングの回数やアルゴリズムが分かっている場合、逆引きには効果は無い*1

• ソルト ... 逆引き対策
• ストレッチング ... 辞書攻撃や総当たり攻撃に対する対策

 なので、ソルト付きでストレチング済みであれば、簡単に元のパスワードが判明することはないのだが、元記事で、

ただ両方の工夫を適用しても、解析に時間がかかるようになるだけだ。解析できなくなるわけではない。

と書かれた。

この文章だとまるで、ソルト付きストレッチングが気休めのように読めてしまうが、実際はそんなことはない。きちんとソルトがついていれば逆引きは実質的に不可能だし、ストレッチングをしていれば、仮に、1時間で判明するパスワードが、1,000 回のストレッチングで 42 日後になる。パスワードを変更して漏洩の被害を回避する時間を作ることができる*2。

 元記事で自分が一番気になったのは、上記の文章に続いてこう書かれていたことだった。

例えば、漏洩データの検索サービスを提供していたLeakedSourceが2016年9月、ソルトを採用していたサービスから漏洩した4350万件以上のアカウント情報を2時間で96％解析したとしている。

ソルト付きのパスワードで 4000 万件以上のパスワードが 2 時間で判明、という事に強烈な違和感を感じた。ソルト付きであれば、

• ソルトがアカウントによらず固定
• その固定のソルトが付いているケースのテーブルが整備済み

じゃないと、2時間で 4000 万件、毎秒 5,500 件以上のというのは、クラウドのおかげで計算リソースの調達が容易になったご時世でも、現実的な数字とは思えない。

記事中には、この LeakedSource の話のソースが示されていないが、おそらくこれではないか、というページを見つけた。

leakedsource.ru

これが正しいとすると、

• 元記事で 2016 年 9 月と書いているが、上記ページが書かれたのが 2016 年 9 月であって、話の内容は 2012 年 3 月。
• 「4350 万件」「96%」「2時間」と言っているのは、Last.fm から漏洩したもの。
• 「Passwords were stored using unsalted MD5 hashing.」と書いているから、ソルトなしの MD5 ハッシュ値。
• 得られたパスワードを見たら、なんと安易なパスワードの多いこと。

という話になる。

安易なパスワードが多くて、ソルトなしの MD5なら*3、普通にレインボーテーブルで短時間にパスワードが見つかるのは当然である。

元記事では「ソルトを採用していた」と書かれているが、私が見つけたページが正しいとすれば、大きな事実誤認ということになる。故に、この話をもって「ソルト付きストレッチングは気休め」と風潮するのは間違いと言わざるを得ない。

ちょっと話は変わるが、この件のブクマコメントで、徳丸さんが

BCryptでもArgon2でも通常Saltはハッシュ値とともに保存するので辞書攻撃には対抗できないでしょ。

と書かれている。辞書攻撃で判明してしまうパスワードは、どんな形式保存しても見つけられてしまう。脆弱なパスワードに対しては、ソルトもストレッチングも気休め言わざるを得ない。

システム側が頑張ったところで、脆弱なパスワードを付けたユーザを守ることはできない。保存形式を適切に保てば、きちんとしたユーザを守ることはできる。

ということで、皆さん、

• 十分に長いパスワードで
• 使い回しをしない

という原則を守りましょう。

*1:もし、同じストレッチング回数とアルゴリズムのレインボーテーブルが無いなら、それを作らなければいけないし、ストレッチングしていればテーブル作成に時間がかかる、という効果はある。

*2:逆に、漏洩したことをどれだけ迅速に検知できるか、が重要になってくる

*3:「MD5なら」というのは、MD5 の衝突耐性の問題ではなく、ビット長が比較的短く、メジャーなハッシュ関数だから、すでにレインボーテーブルが充実している、という理由。任意のハッシュ値に対して、そのハッシュ値を持つビット列を求めるのは、MD5 でも、そこまで容易ではない。MD5 が使えないのは、ハッシュ値は何でも良いから、同じハッシュ値を持つユニークなビット列を見つける、という強衝突耐性の問題。