ハッシュチェイン

ハッシュチェインとは、あるデータに対して暗号学的ハッシュ関数を繰り返し適用したものである。コンピュータセキュリティにおいて、ハッシュチェインは一つの鍵とパスワードから大量のワンタイムパスワードを作り出すのに使われる。また、否認防止のために、データの追加部分に対してハッシュ関数を次々に適用することで、データの存在を時系列に沿って記録するのにも使われる。

定義

ハッシュチェインは、文字列に対して暗号学的ハッシュ関数 $h(x)$ を繰り返し適用すること（写像の合成）で作成される。例えば、

h(h(h(h(x))))

は長さ4のハッシュチェインを与える。これは $(h\circ h\circ h\circ h)(x)$ や $h^{4}(x)$ のように書かれることもある。

応用

詳細は「S/KEY」を参照

レスリー・ランポートは、安全でない環境におけるパスワードの保護にハッシュチェインを利用することを提案している。^[1]認証を行うサーバは平文のパスワードの代わりにハッシュチェインを保管しておくことで、通信経路上でパスワードが盗まれることやサーバからパスワードが盗まれることを防ぐ。例えば、ユーザから与えられた $h^{1000}(\mathrm {password} )$ がサーバに保存されていたとする。認証を行う際には、ユーザはサーバに $h^{999}(\mathrm {password} )$ を送信する。サーバは $h(h^{999}(\mathrm {password} ))=h^{1000}(\mathrm {password} )$ を計算し、これが保存されているハッシュチェインと一致することを確かめる。その後、サーバは次回の認証で使うために $h^{999}(\mathrm {password} )$ を保存しておく。

サーバへ送信された $h^{999}(\mathrm {password} )$ が盗聴されていたとしても、同じハッシュチェインをサーバへ再送して認証を行うことはできない。なぜなら、サーバはその時点では $h^{998}(\mathrm {password} )$ を期待しているためである。また、暗号学的ハッシュ関数の一方向性により、盗聴者がハッシュ関数を逆転させてハッシュチェイン中の一つ前のハッシュ得ることは不可能である。この例では、ユーザはハッシュチェインを使い尽くすまでに1000回認証を行うことができる。ハッシュ値は毎回異なるので、攻撃者が複製をすることも不可能である。