昨日の記事はだいぶ注目を集めたようです。今日は自分向けの技術的なメモです。
パスワード等に使うのにSHAなどのよく知られたハッシュ関数ではなぜダメなのか？ パスワード用のハッシュ関数は何が違うのか？ という話です。なお、今回はほんとに昨日今日でいろいろ仕入れたもののため、中身も薄いし間違ってるかもしれません（また、個別のアルゴリズムやテクニックなどは陳腐化しやすいので、後日にはいろいろ変わっていることでしょう）。その辺は注意してください。
ネタ元は http://throwingfire.com/storing-passwords-securely/#notpasswordhashes など 、あと https://plus.google.com/102550604876259086885/posts/4eoNnNSQ7W6 にコメントをいただいた皆さん（ありがとうございます！）。
で。
SHAなどのハッシュ関数は、パスワード用でもいい性質を満たしているように思えます。入力文字列長に依存しない一方向関数で、元の入力の推定は難しいし、分布も一様であるらしいし（確認したことないから知らないけど……）、いい気がします。MD5やSHA1はさすがにいろいろ解析が進んでいる気がしますが、SHA256ならいまのところ安全な気がします（とはいえ、この分野の進みは速いのでいまはどうなのか……）。
ともあれ、こういうハッシュ関数はパスワードで使うには大きな欠点があるようです。それは速すぎることなのだそうです。
こういうハッシュ関数は、ダウンロードするパッケージとかCDやDVDのイメージとかの検証にも使える規模ですから、物凄く高速でスループットもいい。数Mバイトや数Gバイトでも数秒、数十秒で完了してしまいます。パスワードは数文字から、せいぜい数十文字といったところでしょう。こんなものは0.01ミリ秒とかで計算できてしまう。
そうすると、辞書攻撃で数万パターンのハッシュ値を計算しなければならないとしてもせいぜい数秒で完了しちゃいます。ソルトがあってパターン数が数千万になっても数日規模となっては、イカンわけです。
そもそもログイン時の処理について言えば、パスワードのチェックが0.01ミリ秒で終わろうが、0.1秒かかろうが、ユーザエクスペリエンスにはそれほど大きな影響はないはずです。ということは、1万倍遅くても問題ないというか、1万倍の手間をかけさせるぐらいはなんてことない。
というわけで、ハッシュの計算をたとえば1万倍繰り返して、その結果を求めるとか、そういう手間をかけさせる、といったことをしたほうが安全であるということです。こういう処理を stretching というようです。
もちろん、実際には、単に「1回目のハッシュ値を2回目の入力にし……」のような単純な連鎖にはなりません。もっと複雑にあれこれやります。なぜかというと……メモ化とかを防ぐからかな？
実際に、上のリンクで挙げられているパスワード的に安全なハッシュ関数は3つあります。
PBKDF2 は、OpenSSLなどに入っている手法です。HMACを使ってパスワードとソルトからハッシュをとって、パスワードとハッシュからまたハッシュをとって……みたいなのを繰り返して、xorして結合するみたいなイメージ。自然言語で説明するのは困難なのでリンク先ウィキペディアを眺めたほうがわかりやすいと思いました。
bcryptはBlowfishを使ったメッセージハッシュです。Blowfishは共通鍵暗号だったはずだが……と思ったのですが、ウィキペディアを見てもきちんと理解できたかは怪しいです。怪しいですが、入力キーとソルト、およびイテレーション回数に応じてキースケジュールを進めていき、そのキーを使って、ある固定の文字列を何回も何回も符号化するといった処理のように見えました。ちなみにbcryptはOpenBSDのパスワードハッシュに使われているとのこと。これも論文を読みたいと思います。
scryptはいっそう厄介ですが、 memory-hard なアルゴリズムを使ったハッシュということです。作者の論文によれば、使用メモリ量が大変でなければハードウェアに実装したり超並列化したりといったことが容易になるので、「どうあっても空間計算量が高くなるようなステップ」を間に挟むことで、超並列化しづらくするようにした由。コンセプトはわかったけれども、論文はまだ読み始めたところなので詳細はわかりません（すいません）。
さて、そういう訳で後半は腰砕けになってしまいましたが、ひとまずリソースへのリンクを自分用に貼って、読み進めたいなあと思っているわけです。
ただし、はじめのほうに書いたことを繰り返しておくと、こういう内容はすぐに陳腐化するので気をつけたほうがよいように思います。たとえばbcryptはライブラリも揃っていて使いやすそうでいいのかな、と思うと、 don't use bcrypt などというブログが出てきたりするわけです。1年後にどうなっているかはわからないので、後日この記事を読んだ人は、現状を調査することをおすすめしておきたいと思います。
パスワード等に使うのにSHAなどのよく知られたハッシュ関数ではなぜダメなのか？ パスワード用のハッシュ関数は何が違うのか？ という話です。なお、今回はほんとに昨日今日でいろいろ仕入れたもののため、中身も薄いし間違ってるかもしれません（また、個別のアルゴリズムやテクニックなどは陳腐化しやすいので、後日にはいろいろ変わっていることでしょう）。その辺は注意してください。
ネタ元は http://throwingfire.com/storing-passwords-securely/#notpasswordhashes など 、あと https://plus.google.com/102550604876259086885/posts/4eoNnNSQ7W6 にコメントをいただいた皆さん（ありがとうございます！）。
で。
SHAなどのハッシュ関数は、パスワード用でもいい性質を満たしているように思えます。入力文字列長に依存しない一方向関数で、元の入力の推定は難しいし、分布も一様であるらしいし（確認したことないから知らないけど……）、いい気がします。MD5やSHA1はさすがにいろいろ解析が進んでいる気がしますが、SHA256ならいまのところ安全な気がします（とはいえ、この分野の進みは速いのでいまはどうなのか……）。
ともあれ、こういうハッシュ関数はパスワードで使うには大きな欠点があるようです。それは速すぎることなのだそうです。
こういうハッシュ関数は、ダウンロードするパッケージとかCDやDVDのイメージとかの検証にも使える規模ですから、物凄く高速でスループットもいい。数Mバイトや数Gバイトでも数秒、数十秒で完了してしまいます。パスワードは数文字から、せいぜい数十文字といったところでしょう。こんなものは0.01ミリ秒とかで計算できてしまう。
そうすると、辞書攻撃で数万パターンのハッシュ値を計算しなければならないとしてもせいぜい数秒で完了しちゃいます。ソルトがあってパターン数が数千万になっても数日規模となっては、イカンわけです。
そもそもログイン時の処理について言えば、パスワードのチェックが0.01ミリ秒で終わろうが、0.1秒かかろうが、ユーザエクスペリエンスにはそれほど大きな影響はないはずです。ということは、1万倍遅くても問題ないというか、1万倍の手間をかけさせるぐらいはなんてことない。
というわけで、ハッシュの計算をたとえば1万倍繰り返して、その結果を求めるとか、そういう手間をかけさせる、といったことをしたほうが安全であるということです。こういう処理を stretching というようです。
もちろん、実際には、単に「1回目のハッシュ値を2回目の入力にし……」のような単純な連鎖にはなりません。もっと複雑にあれこれやります。なぜかというと……メモ化とかを防ぐからかな？
実際に、上のリンクで挙げられているパスワード的に安全なハッシュ関数は3つあります。
PBKDF2 は、OpenSSLなどに入っている手法です。HMACを使ってパスワードとソルトからハッシュをとって、パスワードとハッシュからまたハッシュをとって……みたいなのを繰り返して、xorして結合するみたいなイメージ。自然言語で説明するのは困難なのでリンク先ウィキペディアを眺めたほうがわかりやすいと思いました。
bcryptはBlowfishを使ったメッセージハッシュです。Blowfishは共通鍵暗号だったはずだが……と思ったのですが、ウィキペディアを見てもきちんと理解できたかは怪しいです。怪しいですが、入力キーとソルト、およびイテレーション回数に応じてキースケジュールを進めていき、そのキーを使って、ある固定の文字列を何回も何回も符号化するといった処理のように見えました。ちなみにbcryptはOpenBSDのパスワードハッシュに使われているとのこと。これも論文を読みたいと思います。
scryptはいっそう厄介ですが、 memory-hard なアルゴリズムを使ったハッシュということです。作者の論文によれば、使用メモリ量が大変でなければハードウェアに実装したり超並列化したりといったことが容易になるので、「どうあっても空間計算量が高くなるようなステップ」を間に挟むことで、超並列化しづらくするようにした由。コンセプトはわかったけれども、論文はまだ読み始めたところなので詳細はわかりません（すいません）。
さて、そういう訳で後半は腰砕けになってしまいましたが、ひとまずリソースへのリンクを自分用に貼って、読み進めたいなあと思っているわけです。
ただし、はじめのほうに書いたことを繰り返しておくと、こういう内容はすぐに陳腐化するので気をつけたほうがよいように思います。たとえばbcryptはライブラリも揃っていて使いやすそうでいいのかな、と思うと、 don't use bcrypt などというブログが出てきたりするわけです。1年後にどうなっているかはわからないので、後日この記事を読んだ人は、現状を調査することをおすすめしておきたいと思います。
No comments:
Post a Comment