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

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

[徳丸浩,@IT]

ハッシュとは何か

 このように、暗号化は運用が難しいために、パスワードはハッシュで保存することが一般的になりました。

 さて、いままでハッシュという言葉を説明なしに用いてきましたが、ここでハッシュについて説明しましょう。

 任意長のデータを固定長のデータに圧縮する操作を「ハッシュ関数」といい、ハッシュ関数によって得られた固定長データのことを「ハッシュ」、あるいは「ハッシュ値」といいます。ハッシュはセキュリティの目的以外にもデータ探索なども用いられます。ちなみに、Perlの連想配列(文字列をキーとする配列)のことをハッシュと呼ぶのは、連想配列の実装にハッシュアルゴリズムを用いていたことに由来します。

 ハッシュ関数の中でも暗号的な特性を満たすものを「暗号学的ハッシュ関数」と呼びます。文脈上ハッシュという言葉が暗号学的に用いられていることが自明な場合は、暗号学的ハッシュ関数のことを単にハッシュ関数と呼ぶ場合もあります。本稿でもそうします。

 (暗号学的)ハッシュ関数の満たすべき特性の1つに、原像計算困難性あるいは一方向性というものがあります。これは、ハッシュ値から元の文字列を求めることが困難ということです。この性質をパスワードの保存に用います。

 ここで、具体的にハッシュを求めてみましょう。MD5という有名なハッシュアルゴリズムを用いて、「itmedia」というパスワードのハッシュを求めてみます。以下は、Linux(Ubuntu)上でmd5sumという標準コマンドを用いた計算例です。

$ echo -n itmedia | md5sum
b6e565a041c04725cd1ab5a337ebbd96 -
$ echo -n itmedib | md5sum
9af6cb7fa1503d3760d67a7fc8f35838 -

 表示されているように、「itmedia」という7文字の単語から得られるハッシュ値は、一見ランダムに見える32文字の文字列です。次に、itmediaの最後の文字を1つずらした「itmedib」という単語からハッシュ値を求めると、先のハッシュ値とはまったく異なる文字列が得られています。

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

 ハッシュで保存されたパスワードを用いて認証処理を行う場合、ハッシュ値から元のパスワードを得ることはできません。そこで、ユーザーが入力したパスワードからハッシュ値を求め、データベースに保存されたハッシュ値と照合して、一致していれば認証されたと見なします(図1)。

図1 ハッシュによるパスワード保存 図1 ハッシュによるパスワード保存

 ハッシュによるパスワード保存には鍵を用いないため、鍵管理の煩わしさもありません。

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

 ここまで、ハッシュ値を用いたパスワード保存の方法と、鍵を用いないことによる利点を説明しました。一方、ハッシュ値で保存されたパスワードに対するオフライン攻撃方法が知られています。

オフライン攻撃の前提として、すべてが「ばれている」と想定する

 基本的な前提として、ハッシュ保存されたパスワードに対するオフライン攻撃を検討する際には、ハッシュのアルゴリズムその他の情報は、すべて攻撃者にとって既知であると想定すべきだと考えます。

 すなわち、ハッシュ値のほか、ハッシュアルゴリズム、ソルト(後述)、ストレッチングの有無や回数(後述)はすべて攻撃者に「ばれている」状態で、それでも元の(平文の)パスワードが保護できるかを考えるべきです。典型的には、PSN事件のように、攻撃者にルート権限を取られた状態でもパスワードだけは保護できるかどうかが論点になります。

 一方、もしも攻撃者が絶対に取得できない情報保管手段があると前提してもよいのであれば、その方法でパスワード自体を保存するか、安全な方法で暗号鍵を保存してパスワードを暗号化すればよいことになり、必ずしもハッシュを用いる必要はありません。

 しかし現実には、そのような便利な手段は、特殊なためあまり普及していません。ですので、すべてが「ばれている」という前提で考えるわけです。

オフライン攻撃の種類

 ハッシュ保存されたパスワードに対する代表的な攻撃手法としては以下があります。

  • オフライン辞書攻撃
  • オフライン総当たり攻撃
  • レインボーテーブルによる探索

 以下、順に説明していきます。

オフライン辞書攻撃

 オフライン辞書攻撃というのは、パスワード辞書に対するハッシュ値を順に求めては、入手したパスワードデータに保存されたハッシュ値と照合し、一致するものがあれば、そのハッシュ値に対応するパスワードが求められるという方法です。パスワード辞書に載っているパスワードであれば、短時間でパスワードが求められます。

図2 オフライン辞書攻撃のイメージ 図2 オフライン辞書攻撃のイメージ

 オフライン辞書攻撃に対しては、システム側でアカウントロックを掛けることもできないので、利用者に良質のパスワードを付けてもらうしか対抗策はありません。

 そのような試みの例として、Twitterのアカウント登録画面があります。以下は、Twitterのパスワード登録の画面の一部ですが、「password123」という入力に対して「パスワードが単純すぎます」というエラーが表示されています。これは、パスワード欄を表示するアドオンを使って表示しています。

画面1 簡単すぎるパスワードを付けたときに表示されるTwitterのエラー 画面1 簡単すぎるパスワードを付けたときに表示されるTwitterのエラー

オフライン総当たり攻撃

 利用者が良質なパスワードを付けている場合でも、オフラインの場合は、総当たり攻撃(ブルートフォース攻撃)が現実的な脅威となります。

 オンライン攻撃の場合、秒間の試行回数はせいぜい10回程度で、秒間の試行回数をあまり増やすとアカウントロックに引っかかったり、IPアドレス単位のアクセス制限により遮断されてしまい、現実的ではありません。これに対して、オフラインの総当たり攻撃は、いくらでも好きなだけ時間をかけて、何回でも試行できます。

 パスワードのハッシュは、1秒間にどの程度計算できるものなのでしょうか。CPUなどの性能にもよりますが、一般に、秒間100万回〜1000万回といわれています。これでもずいぶん速い気がしますが、さらに高速化する手法が知られています。それは、GPU(Graphics Processing Unit)を利用する方法です。

 GPUは、その名の示すようにグラフィック処理に特化したプロセッサで、複雑な条件分岐は不得意なものの、同じ計算の繰り返しについては、多数の演算プロセッサの威力で非常に高速に行います。ハッシュ値の計算はこの特性に合致しており、家庭用のGPUでも秒間数十億回のハッシュ値の計算が可能です。

 仮に秒間20億回ハッシュ値が計算できるとして、8文字のパスワード(英大文字・小文字・数字)のパスワードすべてのハッシュ値を照合するのにかかる時間を計算してみましょう。

パスワードに使える文字種 = 26 + 26 + 10 = 62

すべてのパスワードの総数 628 = 約218兆

試行に掛かる秒数 = 218兆÷20億 = 約11万秒 = 約30時間


 約30時間ですべてのパスワードのハッシュ値を照合できることになります。すなわち、たとえハッシュで保存していても、現在広く用いられている8文字英数字のパスワードであれば、1日程度で元のパスワードを解読されてしまうことになります。

 オフライン総当たり探索への対策には「ストレッチング」という方法を使います。ストレッチングについては後述します。

Index

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

Page1

PSN侵入の件から始めよう

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

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

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

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


Page2

ハッシュとは何か

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

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

オフライン辞書攻撃

オフライン総当たり攻撃


Page3

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

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

対策1:ソルト

対策2:ストレッチング

暗号化の併用も可能


Page4

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

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


Copyright© 2017 ITmedia, Inc. All Rights Reserved.

@IT Special

- PR -

TechTargetジャパン

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

Focus

- PR -

RSSについて

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

メールマガジン登録

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