パスワード保存とソルトの話

先日、twitterへのハッキング行為が発見された、という発表がなされました。一部のユーザのデータが漏洩したということです。

この件について個人的に懸念を感じたため、それをこちらに書いておきました。原文では encrypted/salted password と呼ばれていたものが、日本語の公式ブログでは「暗号化されたパスワード」となり、これが朝日新聞では「パスワード」と表記されているという問題です。

専門知識があれば、ここにどういう違いがあるかはわかるのですが、そうでなければわからないのも無理はありません。しかし、わからないからといって省略して良いわけでもありません。パスワードと encrypted/salted password は大きく異なります。

ではどう違うのか？　この話について、ひと通りの解説をしてみるのも良いのではないかな、と思ったのでしてみます。

「パスワード」は保存されない

さて、twitterやらなんやら、といったウェブサービスを利用するには通常、ログインをします。つまり、みなさんも自分の twitter の ID とパスワードを入力してログインのボタンを押します。twitterのIDは誰でもわかりますが、パスワードを知っているのは（ふつうは）自分だけなので、自分がアクセスしているということがわかるわけです。

みなさんがログインボタンを押すと、twitterのIDとパスワードがtwitterに送信されます（ちなみに、この送信経路はSSLというテクノロジーで暗号化されているので、送信経路で誰かが盗聴していてもパスワードがばれることはありません）。twitterでは、このIDとパスワードの組み合わせを社内に持っているデータベースで検証して、正しければユーザのログインを許しますし、間違っていればエラーを出します。

ただし、実はtwitter社のデータベースにはパスワードそのものは保存されていません（いや、中の人じゃないので本当のところは知らないけれど、されていないと思います。その前提で以下の文章は書き進めて最後に補足します）。パスワードを忘れちゃった、という問い合わせをしても、twitterはパスワードを教えてくれませんよね。データベースにないから、教えようにも教えられないんです。そこでパスワードを再発行するためのリンクを送ってくるんです。

じゃあ何が保存されているのか？　実はtwitterでは、入力されたパスワードのデータに基づいて、何らかの計算を行っています。で、その計算結果だけを保存しています。これをハッシュ値といっています。

たとえば……そうですね、コンピュータの通信というのは結局デジタルですから、どんなパスワードも0と1で符号化されています。この0の数と1の数を数えて、かけあわせた数、というのはどうでしょうか。入力パスワードが決まれば、この値も決まります。

もちろん、これは私がいまここで思いついた計算方法で、現実にはまったく役に立ちません。本当はもっと複雑なことをします。パスワードの保存に役に立つ計算方法、というのはややこしい話なので、ちょっと後回しにしますが、とにかくそういう計算方法の物凄く複雑なやつ、というのを何かやっていると思ってください。

というわけで、上の続きです。みなさんがログインボタンを押します。するとIDとパスワードが送信されます。twitter社は受け取ったパスワードが正しいのかどうかを知りたいのですが、正しいパスワードそのものは保存していません。そこで受け取ったパスワードに、同じ計算を施します。で、計算結果の数値であるハッシュ値が、保存してあるものと同じである場合は、入力したパスワードも同じと判断してログインを許可します。

なぜこんなことをするの？　それって安全なの？

まさに、今回おきたような問題を回避するために、こういうことが行われています。

万が一に、何者かによって侵入され、データベースにアクセスされてしまったとしても、パスワードそのものは保存していませんから、侵入者にもパスワードはわかりません。また、不届きな従業員がパスワードを覗き見たりすることもない、といった効果もあるでしょう（でもまあこれは副次的なものだと思います）。

安全なのか？　というのは、もちろん計算方法によります。計算方法は様々な条件を満たさないといけません。たとえば、ハッシュ値からもとの入力をかんたんに復元できてしまったら意味がありませんよね。また、全く違う入力なのに、簡単に同じハッシュ値になってしまうようでは、すぐ間違ったパスワードでの侵入を許してしまうため、問題があります（上でわたしが例として書いた計算方法はこの問題があります）。さらにいうと、パスワードの文字数に制限はないほうがいいでしょう。何文字ででも計算ができるような式でないといけません。また、文字数が長いほうが計算結果が大きくなるとか、そういったわかりやすい関係があると、ハッシュ値からもとの入力を完全には復元できないにしても、傾向がわかってしまうため、あまりよろしくありません。計算結果の数値の範囲は固定で、しかも均等にばらけていることが望ましいと言えます。

こういう条件を満たすような計算方法を考えろ、と言われても大変な気がしますが、幸いにして数学者や暗号学者の手によっていくつかの計算方法が提案されています。私もこの分野には明るくなかったのですが、パスワード専用の手法はいくつも提案されていて、PBKDF2やbcrypt、scryptなどといったものがあるようです（詳細は専門的すぎるので省きます。SHA1などの普通の手法を思いついたエンジニアは猛省しましょう……俺のことですが）。

いずれにせよ、こうした式を使ったハッシュ値からはもとの入力をうかがい知るのは難しいため、こういうよく知られた関数を使えば、ひとまず安心であろうと思われます。

辞書攻撃

ところが頭のいい人がいたもので、いまではこのハッシュ値でも安全でない可能性が指摘されています。計算結果からもとのパスワードを割り出す方法そのものは見つかっていないのですが、ハッシュ値に対してもとのパスワードをうまく見つけ出す方法があるのです。その有力な手法のひとつが辞書攻撃です。

辞書攻撃、という名前は面白いですが、やることはすごく単純です。計算方法がよく知られているので、ユーザがパスワードに使いそうな文字列（"abcd" とか）を入力してやれば、計算結果もすぐに計算できます。

今回のように25万人のデータが抜き出したとすると、そのうち何人かはこういう適当なパスワードを使っているかもしれません。ですから、ハッシュ値だけしかなくても、よくある単語からハッシュ値を計算してみればよく、その計算結果と一致した人がいれば、その人のパスワードはその「よくある単語」だということがわかるわけです。

さらに、よくある単語リストから単語同士を組み合わせたり、oを0に置き換える、みたいなよくあるパターンを作り出すプログラムを書いてしまえば、ちょっと凝った程度のパスワードはみんな機械的にリストアップできます。で、そのリストのすべてのハッシュ値を計算するプログラムを書いてしまえばいい。ちょっと凝った程度のパスワードは、だいたいこれですべて破られてしまうでしょう。こういうよくある単語リストみたいなものを「辞書」と呼んでいるため、こういう名前になっています。

さらに言うと、そんな計算結果などは、データを抜き出したあとでのんびり計算するまでもなく、事前に計算しておいて手元のデータベースに保存しておけばいいのです。そうすれば単に比較するだけでパスワードを割り出せてしまいます。これをレインボーテーブルといいます。

複雑なパスワードにしておけば、こういうパターンとは合致しないため、ハッシュ値が渡ったとしても過度に心配することはないかもしれません。ただし、侵入者がどういう手法でパスワードを生成するか、ということは予想もつかないことなので、安心はできません。自分では凝りに凝ったつもりが、コンピュータにしてみればわりと単純だった、というのもよくあることですので。

ソルトによる攻撃耐性

さて、以上の前提を経てようやくソルトの話ができます。

データベースにハッシュ値しか保存しなかったとしても、辞書攻撃やレインボーテーブルによる解析には対抗できません。対抗できないのですが、攻撃側の手間を増大させる方法があります。それがソルトです。

ソルトは単なるランダムなデータです。ユーザがアカウント作成時にパスワードを決めたとき（もしくはパスワードを再発行したとき）、twitterの側でランダムに生成します。そして、パスワードからハッシュ値を計算するのではなく、ソルトとパスワードを連結したものに対してハッシュ値を計算します。そして、ハッシュ値とソルトの両方を保存しておきます。

というわけで、本当のログインはもうちょっと複雑です。ログインボタンを押してIDとパスワードが送信されると、twitter社はまずデータベースを調べ、ソルトを発見します。そしたらソルトと入力されたパスワードを連結し、そのハッシュ値を計算します。で、ハッシュ値が一致していればログインを許可します。

このソルト自体にはまったく意味がないように思えるかもしれません。単に計算の手間を増やしているだけに思えます。実際、私ひとりのパスワードのハッシュ値が漏洩したとして、これを辞書攻撃で解析しようとした場合、ソルトがあるかどうかはほぼ関係がありません。だってソルトはわかっているので、同じようによくある単語パターンからハッシュ値を計算すればよいだけだからです。

ですが、今回のように数万人といったユーザのデータが漏洩した場合には確実に意味があります。

まず、レインボーテーブルの攻撃を無効化できます。あらかじめ計算しておこうにも、ソルトというのはランダムな文字列ですから、よくあるパスワード文字列に加えて、可能なランダムパターンすべてを連結して事前に計算しておくことは、事実上不可能になってしまいます。

また、レインボーテーブルを用いない場合でも、攻撃者の手間はすごく増えます。25万人分のソルトのないデータベースに対して辞書攻撃をしたい、とします。パスワードのパターンは1000個ぐらい作ったとしましょう。そうしたら1000個のハッシュ値を作る必要があります。たとえば "abcd" というパターンに対してハッシュ値を計算したら、25万人分のハッシュ値のなかから一致するものを見つけ出せばいいのです。

これがソルトになると、話はそう簡単ではありません。たとえばAさんとBさんのパスワードが両方たまたま "abcd" だったとしても、ふたりのソルトは（ランダムに生成されているので）異なっており、したがってハッシュ値も違っています。ということは攻撃者は、Aさんのソルトを見て、"abcd"とそのソルトからハッシュ値を計算し、比較したとしても、その計算結果はBさんのパスワードを解析するときには一切使えなくなります。このため、1000x250000個のハッシュ値を計算しないといけなくなります（比較回数は同じですが、まあ比較するのはそれほど大変ではありません）。ハッシュ値の計算はそれほど時間がかからないのですが（でないとログインに時間がかかってしまいます）、上で説明したように様々な条件を満たすためにけっこう複雑な計算はしています。それの計算回数が25万倍になったら、相当な手間になるな、というわけです。

こういうわけで、大規模な情報漏えいに対しては、ソルトは大きな意味を持ちます。ただし、「攻撃の手間を増やす」といった程度の差しかなく、本質的に安全性が増すわけではありません。

ハッシュ値とか、ソルトの有無って、報道する上でそんなに大事なの

大事だと思います。

まず、パスワードそのものを保存するウェブサービスだった場合、大変な問題が起きます。全員の全パスワードが攻撃者の手元にそのまんま来るからです。慌てて変えても手遅れである危険性がとても高いです。

また、私がちょっとした封筒の裏の計算をしてみたところでは、ソルトなしのパスワードハッシュの場合、パターン生成の規模にもよりますが長くても数日以内にすべての解析が完了すると思います。そもそもソルトがないのであれば、レインボーテーブルを使えばよく、その場合はその日のうちに解析が完了します。レインボーテーブルがある場合、記事を見る頃にはやはり手遅れであろうと思います。ただしハッシュが漏洩した場合は、辞書攻撃ではバレないような凝ったパスワードを使っていたユーザについては、実は問題がなかったということになります。

ソルトがある場合、レインボーテーブルは使えませんし、この「数日」というのが一人あたりにかかるコストになります。ちょっとパターン数を少なくして、ひとりあたり1日かけるとしても、全員の解析が完了するのは250000日後ですから、全然現実的ではありません。もっとも、この処理は簡単にそのまま並列化できます。1万台のコンピュータがあれば25日で完了します。とはいえ、何日以上かの猶予はあるとみなせるのではないでしょうか。

以上のことから、私が個人的に感じたところでは、

• パスワードそのものの漏洩というのは、報道されるころにはとっくに手遅れになっていて、わたしたちにはなすすべもない
• パスワードのハッシュ値（ソルトなし）の場合、攻撃者はふつうレインボーテーブルを使うことが予想されるので、やはり手遅れである可能性が高い。レインボーテーブルがなければじゃっかんの猶予はあるかも
• ソルトがある場合は、攻撃者に計算機資源がない場合は全員に対する解析をあきらめさせるほどの負荷がかかる。また、どれだけ頑張ってもおそらく何日間か以上の猶予はあるので、報道されてからパスワードを変えても意味はある

……といった差があるだろうと思います。

ようは、「パスワードが漏洩した」という報道は「こんな風に被害を受けた人がいる」という話ですが、「ソルト付きパスワードのハッシュ値が漏洩した」というのは「急いで対処してください」という注意喚起であるといった差もあるだろうと思います。

以上の情報から、ぼくたちは何をすべきか

実は、当初の公式発表となんら変わりません。

最低でも10文字、大文字と小文字、数字、記号などを混ぜたパスワードをご利用下さい。また、パスワードの使い回しは情報へのアクセスの可能性を大きくしますので、他のサービスとは同じパスワードを利用されないことをお勧めします。

第一に、パスワードの共有化を避けるということです。パスワードをなんのために盗むかというと、twitterを乗っ取るというよりは、他のサービスにログインするといったことがあると思います。実際、今回はtwitter側が、漏洩した可能性のある全員に対してパスワードをリセットするなどの処置を行ったため、乗っ取られる心配は、とりあえずなくなりました。でもtwitterのパスワードを銀行のパスワードと同じにしていたら、銀行口座を操られる可能性がありますし、gmailと同じにしていたら機密のメールが読まれる可能性があります。こういった問題を防ぐには、パスワードの共通化を避けること、gmailなどに二段階認証を導入することです。

第二に、コンピュータに予測されづらいパスワードを使うことです。パスワードそのものを保存せず、ハッシュ値のみを保存する場合の有効な攻撃手段は、辞書攻撃ぐらいしか知られていません。しかもおそらく攻撃者は、人間がよく使うであろうパスワードから順番に試します。凝れば凝るほど、自分のパスワードがばれるまでにはより時間がかかるようになり、最終的には攻撃者が諦めるといったことが考えられます。

で、なんなの？　ほんとにそうだって誰が言えるの？

ぼくは中の人ではないし、セキュリティについても明るくないので、上で書いたような内容がすべて見当違いであり、本当はもっと違った仕組みでパスワードを保存しているかもしれないし、漏洩したデータが全然違うといった可能性もあります。

ですが（細かい手法はさておき）パスワードを保存する場合にハッシュを使うとかソルトを入れるとかいった事柄は、ソフトウェアエンジニアリングでは広く知られた手法であり、これでない手法を取っているということは考え辛いことです。また「ソルト」というのも、パスワードをハッシュで保存するという場合にのみ使われる概念なので、ソルトを使っている、と言及したということはつまりこういったやり方でパスワードを保存していると考えてよいだろうと思います。(追記: ソルトはほかの暗号化手法でも出てくることがあるのに気づきました。OpenSSHのパスフレーズから鍵を生成するところとか。でもまぁ、やっぱこっちなんじゃないかなあ、と私は思っています)