SHA1でハッシュ化したパスワード

を読みました。その記事に関連したことを書きます。

記事を読んで思い出したのは、既にパスワードをハッシュ化して保存していて、そのアルゴリズムが脆弱になった場合に、いかにアルゴリズムを切替えるかという問題です。

ハッシュデータは元に戻せないため、アルゴリズムを切替えるのも難しいのです。

上記の日記で、この問題を扱っています。その日記の中では、

という方式が提案されています。この方式では、システム更新後に、ログインしたユーザから順次新しいアルゴリズムになります。ログインしないユーザは、旧アルゴリズムのままとなります。

もう少し別のやり方もあるでしょう。例えば、DBに保存されている、旧アルゴリズムでのハッシュを、新アルゴリズムでさらにハッシュ化する方法です。要は「二重ハッシュ」の状態にします。

ログインの際には、ユーザが入力したパスワードを、旧アルゴリズムと新アルゴリズムでハッシュ化して、DBのデータと突合せします。必要であれば、初回ログインの際に、DB保存データを、二重ハッシュから新アルゴリズムでの一重ハッシュに切替えることもできます。

いずれにせよ、アルゴリズムの切替えによって、ロジックが若干複雑になります。何度もアルゴリズムを切替えると、その度にロジックは複雑になっていきます。これはパスワードをハッシュ化する場合に発生する、特有の問題のように思います。

思いつくままに、いくつかのトピックについて書きます。

ハッシュ化パスワードを破るのは、それほど難しいことではないようです。辞書攻撃・ブルートフォース攻撃、Salt無しの場合はコンパイル済み辞書攻撃*1の手段もあります。環境や方法にも依るのでしょうが、数秒〜数分で破れる場合もあるようです。

これはハッシュアルゴリズムではなく、パスワード自体が脆弱なことが原因です。SHA1の出力は160bitですが、通常のパスワードはそれより遥かに少ないエントロピー（情報量）しか持ちません。パスワード1文字あたりのエントロピーを4bitとすると*2、8文字で32bitしかありません。

これを補うためには、大垣さんの元記事にあるように、秘密情報―全ユーザ共通の情報―を足してエントロピーをかさ上げする必要があります。いわゆる「鍵付きハッシュ」にするということです。

きちんとした秘密情報を使い（160bit以上の安全な乱数）、それが秘密に守られる場合、ハッシュ化パスワードの強度は、アルゴリズムの強度と等価になるはずです。つまり、（脆弱性の無い）SHA1への攻撃*3には2の160乗回の試行が必要になります。

Saltは、コンパイル済み辞書攻撃を難しくします。また、同一のパスワードが同一のハッシュ値になることを防ぎます。後者は、鍵付きハッシュでは得られない性質です。

鍵付きハッシュでは、万が一外部の攻撃者や内部の犯罪者に鍵付きハッシュが漏洩しても、元のパスワードを知ることは事実上不可能です。秘密情報も同時に漏洩しても、パスワードそのもののエントロピーが最後の防護壁になります。

パスワードを暗号化して保存する方法では、この最後の防護壁はありません。一方で、情報の取り扱いの容易さでは、暗号化が勝っています。

前述のように、ハッシュでは、アルゴリズムや秘密情報の切替えがしにくい問題があります。暗号化形式では、サーバ側だけでそれが完結します。

また、ハッシュの場合、APOPなどチャレンジ・レスポンス型の認証プロトコルに対応できません。他にも、カスタムメイドのプログラムから、既製の製品にID管理を移行する際などにも、「生のパスワードが判らない」ことが障害になるかもしれません（推測です）。

つまりパスワードのハッシュ化には、安全という大きな利点がありますが、サーバ側の自由度を損なうという欠点もあります。

暗号化とハッシュで、それぞれ利点・欠点がありますが、その中間のようなやり方も考えられます。それは公開鍵暗号を使う方式です（単なる思い付きです）。

これは、パスワードを公開鍵で暗号化して保存する方法です。公開鍵はハッシュの秘密情報と同等の役割を持っているので、世間には公開しません。復号のための秘密鍵は、普段は金庫にでもしまっておいて、システムの切替えなど生パスワードを必要とする特別な場合にだけ使います。

基本的には、共通鍵暗号を使った方法と同じく「可逆」ですが、復号化に使う秘密鍵を常時サーバに置いておく必要が無いため、漏れにくいと期待できます。ただし、「遅い」「データ量が増える」などの問題はあるでしょう。

SHA1をパスワードのハッシュ化に使用しているWeb APは、すぐにハッシュアルゴリズムを切替える必要があるのでしょうか。

ハッシュ化や暗号化は、解析に途方も無い時間やデータ量が必要な性質を利用して、情報を守ります。本来攻撃に必要な2の160乗回の試行回数（秘密情報を使う場合）が、アルゴリズムの脆弱性によってどれだけ減るのかが問題です。

残念ながら、暗号学の専門家ではない私には判りません。ただ、ハッシュに要求される重要な性質である衝突耐性（Collision Resistance）が危うくなっていて、少なくとも新規に開発するシステムでは、SHA1の使用は避けるべきのようです。

既存のシステムについてはどうでしょう。ネット上で見つけた資料には、以下のように書いていました。

・SHA1の継続利用は実用上当面問題ないが...
・SHA256利用のシステムが増加中
・SHA256は十分安全であると考えられる
・アルゴリズム変更にかかる費用は少なくない
・SHA256にすぐ移行か、2011年を待つかの決断
暗号技術の最新動向―ハッシュ関数の安全性をめぐる話題―（抜粋）

なお、PHP（>=5.1.2）では、$ php -r 'print_r(hash_algos());' で判るように、SHA2、Whirlpoolを含む多くのハッシュ関数がデフォルトで利用できます。

*1:いわゆるレインボーテーブルを使った攻撃

*3:ハッシュから元の値を求める攻撃（First Pre-image Attack）。