このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

宣伝

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

『暗号技術のすべて』宣伝サイト

 興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

はじめに

 ハッシュ関数はインターネットにおけるセキュリティのあらゆる分野で利用されている。例えばファイルのバイナリのハッシュ値を取っておくことで、ファイルの改竄を検知することができ、これはフォレンジックの分野でも活躍している。また、UNIXのログイン認証の際、パスワードファイルに暗号化されたパスワードが記録されているが、このときハッシュ関数が用いられていることもある。さらに、掲示板では騙り防止のためのトリップという概念が存在するが、これはハッシュ関数と考え方は同じである。

 よって、安全なハッシュ関数が必要といえる。しかし、そもそも「安全な」ハッシュ関数とはどのような意味を指すのだろうか。それを追っていくには、ハッシュ関数そのものの定義を明らかにしていかなければならない。そこで、今回はハッシュ関数の応用という観点ではなく、ハッシュ関数そのものの基礎的な部分について焦点を当てる。

圧縮関数

 ハッシュ関数の定義の前に、(固定長)圧縮関数を定義する。圧縮関数という名から推測できるが、これはある一定の長さのビット列をより短いビット列に変換する関数である。

 例えば、8ビットのビット列を4ビットのビット列に変換する圧縮関数を考えてみよう。この関数は「**** ****」のような2進8桁(8ビット)を入力したときに、「****」のような2進4桁(4ビット)を出力するものである(「*」は0または1を意味する)。ポイントは、入力値のビット数が固定されていて、なおかつ出力値のビット数も固定されているということである。定義の言葉の「一定の長さのビット列」という部分が重要である。

ハッシュ関数

 ハッシュ関数とは、任意の長さのビット列を、一定の長さのビット列に変換する関数である。

 先ほどの圧縮関数との違いがわかるだろうか。圧縮関数のときの入力はビット列が固定されていたが、ハッシュ関数のときの入力は任意のビット列、即ちビット列が固定されていないということである。

 また、圧縮関数のときは入力の長さは出力の長さより大きい必要があったが、ハッシュ関数のときはそれは触れられていない。つまり、入力の長さと出力の長さの大小関係は問題にしていないという点である。

 例えば、任意のビット列を入力とし、入力値に含まれる1が奇数個なら1、偶数個なら0という1ビットを出力するハッシュ関数を考える(ハッシュ関数の定義を満たしている)。このハッシュ関数に「0100101」を入力すれば、「1」(入力値には1が3つだから奇数)が出力される。またこのハッシュ関数に「101」を入力すれば「0」(入力値には1が2つだから偶数)が出力される。実は、この仕組みはネットワークの分野で登場するパリティチェック方式の奇数パリティと同じ考え方である。入力値に含まれる1の個数の計算は、各桁の数字をすべて単純に排他的論理和(XOR)で足し合わせればよいだけである。

 このハッシュ関数の入力値は任意であり、一方出力値は1ビットである。即ち、入力として取り得る値の候補数はいくらでもあるが、出力として取り得る値の候補数は2パターンしかない(出力値が1ビットだから)。明らかに入力値の候補数のほうが多いので、決してこの関数は単射になることはない。これはハッシュ関数すべてに言える性質である。

 これでハッシュ関数の定義はわかった。

圧縮関数からハッシュ関数を構成する

 次の問題は、任意の入力を取りつつ、一定の長さの出力を行うハッシュ関数を作れるのかという点が疑問に残る。先ほどの奇数パリティの例の具体的に作れることは明らかである。しかし、ここで問題にしているのはどんなハッシュ関数であっても作れるのかという点である。この問題は直観的に、圧縮関数があれば、ハッシュ関数も作れそうだということが定義からわかると思う。なぜならば、ハッシュ関数の入力である任意のビット長の個数分だけ、圧縮関数を用意すればよいだけだからである。ハッシュ関数に10ビットが入力されたら、内部で10ビットの入力値を取る圧縮関数を呼び出す。また、ハッシュ関数に4ビットが入力されたら、内部で4ビットの入力値を取る圧縮関数を呼び出す。こういう仕組みを考えれば、あらゆるビットの入力値を取る圧縮関数をたくさん用意しておけば、それに応じて対応できるということになる。

 これでハッシュ関数が構成できるということがいえそうだが、問題はまだ残っている。我々が欲しいハッシュ関数は「安全な」ハッシュ関数である。この問題を解決するためには、「安全な」という意味を明確にする必要がある。よって、次に安全性の説明を行う。

「安全な」という意味

 ハッシュ関数における安全性とは2つの意味がある。第1に、具体的なハッシュ関数、例えばMD5,SHA1などといったハッシュ関数そのものに関する安全性である。第2に、すべてのハッシュ関数に共通して存在する安全性である。今回は具体的なハッシュ関数について取り上げる予定がなく、まず共通した安全性が述べられていないうちから具体的なハッシュ関数の問題点を述べても意味があまりないので、すべてのハッシュ関数に共通して存在する安全性を議論の中心とする。

 先ほどの奇数パリティの例でいうと、入力値が「111」や「10101」の場合、どちらとも出力値は「1」になる。このように入力値が異なるのに、出力値が一致してしまった値のことをコリジョン(衝突)という。すべての圧縮関数、すべてのハッシュ関数はコリジョンを持つ。なぜならば単射ではないから、これは避けられない。問題は不正を行う(多項式時間アルゴリズムである)敵が、コリジョンを持つような入力値の作れるかという点である。即ち、敵が出力値が一致するような入力値のペアを計算できるかどうかという点である。

 これは2つの状況が考えられる。まず、1つ目は敵が自由にコリジョンを発生させる入力値のペアを計算するという状況である。次に、ある指定された入力値の出力値と同じ出力値を持つ入力値を計算するという状況、即ち入力値のペアの片方が指定されて、そのもう片方を計算するという状況である。敵にとって、前者の問題を衝突困難問題、後者の問題を弱衝突困難問題という。

 問題を明確にするために、式を使って考える。ここではハッシュ関数をhとする。

  • 衝突困難問題
    • (敵に与えられる)入力:h
    • (敵が解く値である)出力:h(x)=h(x')を満たすペア(x,x')
  • 弱衝突困難問題
    • (敵に与えられる)入力:h,x
    • (敵が解く値である)出力:h(x)=h(x')を満たすx'

 2つの問題の違いがわかっただろうか。では、敵にとってどちらの問題の方が難しいだろうか。「弱」と付いているからといって問題が簡単と勘違いしてはならない。実際には衝突困難問題より、弱衝突困難問題のほうが難しい。ポイントは衝突困難問題の場合、コリジョンを発生させるどのようなペア(x,x')を出力すればよいだけである。一方、弱衝突困難問題の場合、xは固定されていて、それに対応するx'を求める必要があるのである。

 例えば、コリジョンは必ず存在することを述べた。そして、最大でコリジョンは出力値の候補数分だけ存在する。しかもひとつのコリジョンでも、入力値のペアは色々なパターンがある。そのパターンの1つでも求められればよいのが衝突困難問題である。一方、入力値のペアは色々なパターンがあるが、そのうちペアのうちの1つが固定されているので、パターン対象が少なくなっている。この少ないパターンから1つ求めるのが弱衝突困難問題である。つまり、答えの候補が少なくなっているので、弱衝突困難問題のほうが直観的に難しいというのが理解できると思う。

 実際に暗号の世界できちんと証明しようとすれば、帰着法を用いる。つまり、衝突困難問題を解くアルゴリズムが存在すると仮定して、弱衝突困難問題を解くアルゴリズムを構成できることを示せばよい。これはすごく簡単なので各自考えてもらいたい。

 ここで、任意の敵にとって圧縮関数(もしくはハッシュ関数)の衝突困難問題(もしくは弱衝突困難問題)が解けないとき、衝突困難(もしくは弱衝突困難)な圧縮関数(もしくはハッシュ関数)と呼ぶことにする。

 これらがハッシュ関数の安全性に対応する性質である。問題の場合は衝突困難問題より弱衝突困難問題のほうが難しいと述べたが、安全性の強弱はこれと逆になる。意味で考えるとわかりやすい。容易な問題を敵が解くことができないとするほうが安全性が強い。つまり、、弱衝突困難な圧縮関数(もしくはハッシュ関数)より、衝突困難な圧縮関数(もしくはハッシュ関数)の方が安全だといえる。よって、衝突困難なハッシュ関数のほうが存在意義が大きいことになる。

安全なハッシュ関数の構成

 衝突困難な圧縮関数が存在するならば、衝突困難なハッシュ関数を構成する手法が知られている。この手法をMD変換という。

 また、安全な暗号スキームが存在すれば、衝突困難な圧縮関数は存在することも知られている。

 以上のことをまとめると、安全な暗号スキームが存在すれば、衝突困難なハッシュ関数が存在するということである。

 注意してもらいたいのはあくまで「安全な暗号スキームが存在すれば、衝突困難なハッシュ関数が存在する」ことが証明されただけであり、具体的に衝突困難なハッシュ関数はいまだ1つも発見されていない。つまり、衝突困難なハッシュ関数は仮定を置くことで数学的に存在が証明されるが、実際にはまだ1つの衝突困難なハッシュ関数も発見されていないのだ。

 それでは仮定の妥当性が問題であることが疑われるが、仮定には特に問題ない。(効率的かどうかはべつとして)安全な暗号スキームは具体的にいくつも発見されている。それなのに、衝突困難なハッシュ関数は1つもまだ発見されていないのである。

 この事実は現在インターネット上で使われているハッシュ関数はすべて衝突困難でないことも意味している。このことが問題かどうかということは、現在のコンピュータが実行できるビット長や、別の安全性なども考慮しなければならないので、一概にはいえない。しかしながら、少なくとも現在は、理想的な状況ではないということだけは言えるだろう。