特集
» 2011年10月06日 10時00分 UPDATE

ハッシュとソルト、ストレッチングを正しく理解する:本当は怖いパスワードの話 (3/4)

[徳丸浩,@IT]

レインボーテーブルとは何か

 総当たり探索を高速化する手法として、「逆引き表」があります。逆引き表とは、すべてのパスワードに対するハッシュ値をあらかじめ求めておき、ハッシュ値からパスワードを引けるように並べたものです。逆引き表のイメージを以下に示します。

ハッシュ値 パスワード
098f6bcd46 test
5f4dcc3b5a password
900150983c abc
d16fb36f09 xyz

 現実的には、パスワードハッシュの逆引き表はデータサイズが大きくなりすぎ、実用的ではありません。そこで、表のサイズを圧縮するために、還元関数を用いたチェインというアイデアによる「レインボーテーブル」という技法が考案されました。

 レインボーテーブルの詳細については、拙著「体系的に学ぶ 安全なWebアプリケーションの作り方」に書きましたので、よろしければそちらを参照ください。ここでは、レインボーテーブルの「威力」を示す実験結果をご覧いただきたいと思います。

HTTP C:\RainbowTable>rcrack md5_alpha_num_7\* -h b6e565a041c04725cd1ab5a337ebbd96
1111392256 bytes memory available
3 x 320000016 bytes memory allocated for table buffer
38400 bytes memory allocated for chain traverse
disk: md5_alpha_num_7\md5_loweralpha-numeric#1-7_0_2400x40000000_all.rt: 320000016 bytes read
searching for 1 hash...
disk: md5_alpha_num_7\md5_loweralpha-numeric#1-7_0_2400x40000000_all.rt: 319999984 bytes read
searching for 1 hash...
plaintext of b6e565a041c04725cd1ab5a337ebbd96 is itmedia
disk: thread aborted
 
statistics
-------------------------------------------------------
plaintext found:                              1 of 1
total time:                                   4.18 s
  time of chain traverse:                     1.79 s
  time of alarm check:                        0.25 s
  time of wait:                               2.11 s
  time of other operation:                    0.03 s
time of disk read:                            4.15 s
hash & reduce calculation of chain traverse: 5755200
hash & reduce calculation of alarm check:     620813
number of alarm:                              883
speed of chain traverse:                      3.21 million/s
speed of alarm check:                         2.47 million/s
 
result
-------------------------------------------------------
b6e565a041c04725cd1ab5a337ebbd96 itmedia hex:69746d65646961
 
C:\RainbowTable>

 total time: 4.18 sと表示されているように、わずか4秒とちょっとで元のパスワード「itmedia」が復元されました。

 今回の実験に用いたレインボーテーブルは、7文字までの、英字小文字と数字の組み合わせによるパスワードに対応したものです。しかし市販されているレインボーテーブルを用いると、「8文字までのASCII文字全部」や「10文字までの英字小文字と数字」を用いたパスワードハッシュを復元できます。

 このように、単純なハッシュによるパスワード保存では、十分にパスワードを保護できない状況になっていると考えられます。

MD5だから危険なのではない

 ここまで、ハッシュにより保存されたパスワードが意外に手早く解読されてしまう例を紹介しました。

 ここで例に使っていたハッシュアルゴリズムはMD5という方法でしたが、MD5にはいくつか弱点が発見されており、特定の応用では利用しないように勧告されています。このため、「MD5だから危険なのであって、SHA-256などを使えば安全なのだろう」と思った人も少なくないのではないでしょうか。

 しかし、これは誤解なのです。GPUによる総当たりも、レインボーテーブルも、MD5特有の性質を利用した手法ではありません。これらの手法は、MD5以外のハッシュアルゴリズムでも利用することができます。たとえSHA-256やSHA-512を用いたとしても、安全というわけではありません。

安全なパスワードの保存方法の大前提

 ここから安全なパスワード保存の方法について説明していきますが、その前に、基本的な大前提を説明しなければなりません。それは、パスワード認証の大前提は、「パスワードは利用者本人しか知らないはずの文字列を指定しているから正当な利用者と認証する」ものであって、安全なパスワードを指定するのは利用者の責任であるということです。

 たまに、パスワードの漏えい事件後にパスワードの統計情報が公表されることがあります。そこでは、よく使われているパスワードの常連として、password、abcdef、qwerty、123456などの文字列が並んでいます。これらの「ありがちな」パスワードの利用者は、上記の責任を放棄していることになりますが、なかなかそのような利用者を減らすことができないのも事実です。

 一方で、利用者が強固なパスワードを設定したくても設定できないサイトが多いのもまた現実です。大手都市銀行のインターネットバンキングでは、パスワードとして利用できるのは英数字4桁〜8桁というサイトが珍しくなく、携帯電話向けサイトに至っては、数字4桁の暗証番号がまだ主流という状況です。

 このような状況の中で、Webサイト側の最低限の要件としては、利用者が安全なパスワードを設定することを「邪魔しない」ことだと考えます。

 後述するように、8桁英数字というパスワードは、かなり危なっかしい状況になってきています。また、パスワードをハッシュで保存するという前提では、パスワードを8桁に制限する合理的な理由はありません。例えば、Amazonでは128文字までのパスワードを設定できますが、このようにパスワードの桁数(文字数)の制限は大幅に緩和するべきだと考えます。

 次に、もっと積極的に、利用者に良質なパスワードを強制するという考え方もあります。従来からも、パスワードポリシーとして文字数や文字種の制限を厳しくしているサイトはありますが、さらに前述のTwitterに見られるように、パスワードの辞書を使ったチェックも今後は有効ではないかと考えます。辞書に載っているようなパスワードを保護する有効な手段はないからです。

 次に、サイト側で取れる対策について説明します。

対策1:ソルト

 サイト側の対策として、まずソルト(Salt)は必ず採用すべきです。ソルトというのは、ハッシュ値を計算する前にパスワードの前後に付け加える短い文字列です。

ソルト化ハッシュ = hash(パスワード + ソルト)

            ※注: +は連結演算子


 ソルトによる効果は以下の通りです。

  • 同じパスワードを付けていても、ハッシュ値は異なるようにできる
  • ハッシュ値の元となる文字列を長くすることにより、レインボーテーブル探索を妨害する

 これらの効果を得るために、ソルトには以下の要件が必要となります。

  • ユーザーごとに異なるソルトを使う
  • ある程度の長さ(20文字程度以上)を確保する

 教科書などでは、ソルトに乱数を使っている実装をよく見かけますが、原理的には乱数である必要はありません。通常、ソルトはハッシュ値とともに保存するので、オフライン攻撃者にとってソルトは秘密情報ではありません。また、ある程度長さが確保できれば、ユーザーIDそのものをソルトにすることもできますが、ユーザーIDを後から変更できるサイトの場合は実装に工夫が必要になります。

 ソルトを使うと、レインボーテーブルに対しては絶大な効果を発揮しますが、総当たり攻撃に対してほとんど効果はありません。このため、次に説明するストレッチングという方法を併用します。

対策2:ストレッチング

 ストレッチングというのは、ハッシュ値の計算を何回も(1000回〜数万回程度)繰り返すことです。一般にハッシュ関数は高速性を求められますが、この高速性は総当たり攻撃に対しては脆弱な方向に働きます。総当たりに要する時間も短縮されるからです。

 しかし、ハッシュ保存用にわざわざ低速なアルゴリズムを開発するのも手間が掛かるので、高速なハッシュを繰り返し用いることで速度を遅くするというのが、ストレッチングの考え方です。

 ストレッチングの回数は多いほど安全にはなりますが、サーバ負荷が増えるというデメリットもあります。このため、実機でサーバ負荷を見ながら調整するとよいでしょう。あまりに負荷が高くなると、認証のページを同時にアクセスすることでDoS攻撃に悪用されるリスクも生じます。

 仮にストレッチングを1万回とすると、先に紹介した「8文字英数字のパスワード」のハッシュ値をすべて求めるのには30万時間、約34年かかることになります。数字だけ見ると十分なようにも見えますが、GPUの処理速度の向上や並列処理による時間短縮を考慮すると、決して十分安全ともいえないのが実情なのです。

暗号化の併用も可能

 攻撃者によってすべての情報が盗まれるという前提に立つと、パスワードを安全に守る現状のベストプラクティスは「ソルト+ハッシュ+ストレッチング」です。しかし、この方法で将来にわたって安心というわけではありません。

 そこで、仮に情報漏えいの経路がSQLインジェクション攻撃に限定できるのであれば、ハッシュ値をさらに暗号化するという方法も考えられます。暗号鍵はDB以外の設定ファイルなどに保存します。

 しかし、情報漏えいの経路がSQLインジェクションしかないという証明も難しいことから、これでも絶対に安全というわけではありません。

Index

本当は怖いパスワードの話
 ハッシュとソルト、ストレッチングを正しく理解する

Page1

PSN侵入の件から始めよう

オンライン攻撃とオフライン攻撃

パスワードに対するオンライン攻撃とオフライン攻撃

なぜパスワードを保護するのか

なぜ暗号化ではだめなのか


Page2

ハッシュとは何か

ハッシュを用いた認証処理

ハッシュ保存されたパスワードに対するオフライン攻撃

オフライン辞書攻撃

オフライン総当たり攻撃


Page3

レインボーテーブルとは何か

安全なパスワードの保存方法の大前提

対策1:ソルト

対策2:ストレッチング

暗号化の併用も可能


Page4

ハッシュ保存により生じる課題

これからも最新動向のウォッチを


Copyright© 2017 ITmedia, Inc. All Rights Reserved.

@IT Special

- PR -

TechTargetジャパン

この記事に関連するホワイトペーパー

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。