tobioka.net

1日遅れの話題ですが。

Linkedinのパスワードが流出、650万件がハッカーフォーラムで公開との報道

今時そんな、漏れたぐらいですぐ問題になるような保存の仕方はしないでしょう、と思ってたら
6.5 Million LinkedIn Passwords Reportedly Leaked, LinkedIn Is “Looking Into” It | TechCrunch に、

The passwords are stored as unsalted SHA-1 hashes

って書いてあった。事実なら確かに脆弱。

NISTの2010年問題で、生SHA-1はパスワード保存に使っちゃダメって言われてたはず。
Linkedinは米国政府と取引なかったのかしら。
（なかったら脆弱でもいいというわけではもちろんないけど。）

SNS嫌いの僕は幸いLinkedinのアカウントを持ってなかったのでスルーで良かったんだけど、
一つ疑問が。
SHA-1は確かに脆弱と言われてるけど、短時間で30万件も衝突させれるほどだっけ？

いかんなぁ。金融システムを離れてセキュリティに暗くなっていく一方だ。
恥を忍んでハッシュ関数についておさらいしておこう。

そもそもハッシュ関数とは

あるデータから固定長のユニークな値を生成する仕組み。
base64などのエンコード（デコードできる）と違い、一方方向の変換のみで、元に戻せない。

パスワードみたいに、元データを持たずに後から入力値が同じかを確認したい時に使える。
つまり、送られてきたパスワードをハッシュ化して、登録時にハッシュ化したものと比較すれば良い。

改ざん防止にも使える。オープンソースプロダクトのダウンロードリンクの横にたまに書いてあるあるやつがそう。ダウンロードした後にハッシュ化してそれと一致すれば改ざんされてない。
（まぁサイト自体が改ざんされてた場合は、ハッシュ値も書き換えちゃうだろうけど）

「ハッシュ関数による暗号化」とかよく言われるけど、暗号でもない。
暗号は復号できるから、一方方向じゃない。
（今回の件でも多くの記事が暗号と書いてて悲しいかぎり）

ハッシュ関数の脆弱性

（強・弱）衝突耐性だとか、現像攻撃とか似たような定義でわかりづらいけど、wikipediaさんがうまくまとめてくれてた。

暗号学的ハッシュ関数 – Wikipedia

原像計算困難性 (preimage resistance)
ハッシュ値 h が与えられたとき、そこから h = hash(m) となるような任意のメッセージ m を探すことが困難でなければならない。これは一方向性関数の原像計算困難性に関連している。この特性がない関数は原像攻撃に対して脆弱である。

第2原像計算困難性 (second preimage resistance)
入力 m1 が与えられたとき、hash(m1) = hash(m2) となるようなもう1つの入力 m2（m1とは異なる入力）を見つけることが困難でなければならない。これを「弱衝突困難性 (weak collision resistance)」ともいう。この特性がない関数は第2原像攻撃に対して脆弱である。

衝突困難性 (collision resistance)
hash(m1) = hash(m2) となるような2つの異なるメッセージ m1 と m2 を探すことが困難でなければならない。このような組を衝突と呼び、この特性を「強衝突困難性 (strong collision resistance)」ともいう。原像計算困難性を持つハッシュ値よりも少なくとも2倍の長さのハッシュ値を必要とし、さもなくば誕生日攻撃によって衝突を探し当てられる可能性がある。

1つ目が破られたらもはやハッシュとして意味がないので置いておくとして、問題になってくるのは下2つ。

• 強衝突耐性は、ハッシュ値が同じになる２つの入力値を求めるのが難しいこと。
• 弱衝突耐性は、あるハッシュ値と同じになる別の入力値を求めるのが難しいこと。

元々ハッシュ関数というのは、これらの衝突が不可能というわけではなく、総当りだと天文学的な時間がかかることで安全とされている。
そのため、ある攻撃手法によって、 総当りよりも少ない計算量で衝突が発見出来れば、そのハッシュ関数の脆弱性が発見された、ということになる。

結局SHA-1は？

今回のように漏洩したハッシュ化パスワードを元に認証を不正に突破するためには、
弱衝突耐性を突破しなければいけない。

パスワードのハッシュ値がわかってるので、それと同じハッシュ値になる入力値を探すわけだ。
（元のパスワードと同じじゃなくても良い。ハッシュ値が同じであれば認証は突破できる。）

で、今回のSHA-1はというと、

MD5とSHA | 情報保護とDRMのサイファー・テック

●2004年に衝突耐性に対する脆弱性が発見されて依頼、様々な攻撃法が考え出されてきましたが、2008年10月現在で具体的に衝突が起こる例が求まったわけではない状態です。

2008年でこの状態だったらしい。
それ以降日本語情報ではあんまりアップデートがなくてよくわからなかった。（英語で調べるほど元気はなかった、ごめんなさい）

4年もたてばもっと進んでるんだろうけど、数日とかのオーダーで30万件も解読できるほどではなさそうだけど、どうなんだろう？？
この前mysqlのパスワード（md5）忘れちゃった時、試しに攻撃ツール使ってみたけど死ぬほど時間かかってたしなぁ。

問題はもっと単純だった

と、ここまで考えて、数学的な攻撃じゃなく、リンクトインで使われそうなパスワードをもとにやっていけば、30万件ぐらい軽く行くのかもと思った。（簡単なパスワード使ってる人いっぱいいそうだし。password1とか。）
そうだとしたら弱いパスワードを許容してた設定の問題だなぁ。

とか書いてたら続報が来てた。
LinkedIn、侵入および「一部」ユーザーのパスワード漏洩を認める
これを見るとアルファベットだけのパスワードを許容してたみたい。

そしてなんと、改めて最初にあげたTechCrunchの記事を見返したら辞書使ったって書いてあったというオチでした。

でもブログ書いてみて、いかに自分がセキュリティに対して疎くなっているか、改めて実感できたので良かったです。徳丸先生の本や結城先生の本を読みなおそうと思います…。

理解が誤っている部分とか多々あると思うので、突っ込み大歓迎です。

ちなみにリンクドインじゃなくリンクトインらしいです。
あと関係ないけど、百度もバイドゥ↓ではなくバイドゥ↑（ドゥがあがる）なんですって。

それでは。