暗号学的ハッシュ関数

暗号学的ハッシュ関数（あんごうがくてきハッシュかんすう、英: cryptographic hash function）は、ハッシュ関数のうち、暗号など情報セキュリティの用途に適する暗号数理的性質をもつもの。任意の長さの入力を（通常は）固定長の出力に変換する。
「メッセージダイジェスト」は、暗号学的ハッシュ関数の多数ある応用のひとつであり、メールなどの「メッセージ」のビット列から暗号学的ハッシュ関数によって得たハッシュ値を、そのメッセージの内容を保証する「ダイジェスト」として利用するものである。

「困難」の意味

暗号について「困難 (hard)」と言った場合、一般に「攻撃者がどんな手段を使ってシステムを破ろうとしてもほぼ確実に防げる」ことを意味する。したがって、用途によって具体的な意味に若干の差がある。なぜなら、得られるものが大きいほど攻撃者は攻撃に手間をかけると予想されるからである。しかし、ダイジェストが長くなるとそれを破るのに必要な手間は急激に増大していくので、数ビット長くしただけでも数千倍の攻撃努力に対抗できるようになる。
計算複雑性理論では「困難 (hard)」という用語は特定の意味をもつ。しかし、ここでいう「困難」は、それとはほとんど関係がない。

用途

暗号学的ハッシュ関数の典型的な利用例を以下に示す。アリスは難しい数学問題をボブに提示し、彼女自身はそれを解いたと主張する。ボブも解いてみるが、その前にアリスがはったりをかましていないことを確認したい。このときアリスは、自分の解答にランダムな文字列 (nonce) を付けてそのハッシュ値を計算し、ボブにハッシュ値を知らせる（この時点では解答そのものとnonceは秘密にしておく）。何日かしてボブがその問題を解いたら、アリスはnonceと自分の解答をボブに示すことで、既にその問題を解いていたことが証明できる。これはコミットメントスキームの簡単な例である。実際にはアリスとボブはコンピュータプログラムであることが多く、秘密にされることは数学問題の解などといったものではなく、もっと簡単に改竄できるものである。
安全なハッシュのもう1つの重要な用途として、データ完全性の検証がある。メッセージ（あるいはファイル）に改変が加えられているかどうかの判定であり、例えばメッセージを転送する前と後でメッセージダイジェストを計算し、比較することで検証する（転送以外の事象の前後でもよい）。
メッセージダイジェストは、確実にファイルを識別する手段としてバージョン管理システムで使われている（例えば、Git、Mercurial、Monotone）。また、sha1sum を使うと様々な種類のコンテンツ（ファイル、ディレクトリツリーなど）が一意に識別できる。
関連する用途としてパスワードの検証がある。パスワードは秘匿する必要があるので、通常はそのままクリアテキストでは格納されておらず、何らかのダイジェストの形式で格納されている。利用者を認証する際、利用者が入力したパスワードにハッシュ関数を適用し、出力のハッシュ値と格納されているハッシュ値とを比較する。このような使い方を一方向暗号などと呼ぶこともある。
セキュリティ上の理由と性能上の理由から、デジタル署名アルゴリズムの多くはメッセージのダイジェストについてだけ「署名」し、メッセージそのものには署名しない。ハッシュ関数は擬似乱数ビット列の生成にも使われる。
ハッシュは Peer to Peer のファイル共有ネットワークでのファイルの識別にも使われている。例えばed2kリンクでは、MD4から派生したハッシュとファイルサイズを組み合わせ、ファイルの識別に十分な情報を提供している。他にもMagnetリンクがある。このようなファイルのハッシュは、ハッシュリストやハッシュ木のトップハッシュであることが多く、それによって別の利点も生じる。

ブロック暗号に基づくハッシュ関数

ブロック暗号を使って暗号学的ハッシュ関数、特に一方向性圧縮関数を構築する手法はいくつかある。
その手法は、暗号化に通常使われるブロック暗号の暗号利用モードに似ている。よく知られているハッシュ関数（MD4、MD5、SHA-1、SHA-2など）はブロック暗号的なコンポーネントを使った設計になっていて、関数が全単射にならないようフィードバックをかけている。
AESのような標準的ブロック暗号を暗号学的ハッシュ関数のブロック暗号部分に利用することも可能だが、一般に性能低下が問題となる。しかし、ハッシュと同時にブロック暗号を使った暗号化のような暗号機能も必要とするシステムで、しかもICカードのような組み込みシステムでは、コードの大きさやハードウェアの規模が制限されているので、共通化が有利となるかもしれない。

Merkle-Damgård construction

暗号学的ハッシュ関数は、任意長のメッセージを固定長の出力に変換しなければならない。したがって、入力を一連の固定長のブロックに分割し、それらに順次一方向性圧縮関数を作用させる。この圧縮関数はハッシュのために特に設計したものでもよいし、ブロック暗号を使って構築したものでもよい。Merkle-Damgård construction で構築されたハッシュ関数は、その圧縮関数と同程度の衝突困難性がある。ハッシュ関数全体で発生する衝突は、圧縮関数での衝突に起因する。最後のブロックには明らかにパディングが必要で、この部分はセキュリティ上重要である。
このような構築法を Merkle-Damgård construction と呼ぶ。SHA-1やMD5などのよく使われているハッシュ関数は、この形式である。
この構築法の本質的欠点として、length-extension 攻撃や generate-and-paste 攻撃に弱く、並列処理できないという点が挙げられる。より新しいハッシュ関数であるSHA-3は全く異なる構築法を採用している。

他の暗号の構築における利用

暗号学的ハッシュ関数（以下では「暗号学的」を省略する）は他の暗号の構築に使える。それらが暗号学的に安全であるためには、正しく構築するよう注意が必要である。
メッセージ認証符号 (MAC) はハッシュ関数から構築することが多い。例えばHMACがある。
ブロック暗号を使ってハッシュ関数を構築できると同時に、ハッシュ関数を使ってブロック暗号が構築できる。Feistel構造で構築されたブロック暗号は、使用したハッシュ関数が安全である限り、その暗号自体も安全であるといえる。また多くのハッシュ関数（SHAなど）は専用のブロック暗号を使い Davis-Mayer などの構成法で構築されている。そのような暗号は、ブロック暗号として従来のモードでも使えるが、同程度のセキュリティは保証できない。
擬似乱数列生成器 (PRNG) を、ハッシュ関数を使って構築できるが、そのままでは通常の「一般の擬似乱数列生成器の出力を暗号学的ハッシュ関数を通すようにして安全にしたもの」のような安全性はない（過去の出力結果が十分にあれば、未来の結果が予測可能だから）。安全にするにはさらにハッシュ関数を通さなければならない。また、現代的な擬似乱数列生成器では通常、周期は確定的だが、ハッシュ関数を利用したPRNGの周期は、衝突の確率でしか推定できず、確定的ではない。
ストリーム暗号はハッシュ関数を使って構築できる。多くの場合、暗号論的擬似乱数生成器をまず構築し、それが生成するランダムなバイト列を鍵ストリームとして使用する。SEALというストリーム暗号は、SHA-1を使って内部の表を生成し、その表は鍵ストリーム生成に使われる。

ハッシュ関数の連結

複数のハッシュ関数の出力を連結すると、連結対象のハッシュ関数のうち最強のものと少なくとも同等以上の衝突困難性を提供できる。例えば、TLS/SSLはMD5とSHA-1を連結して利用している。これによって、どちらか一方が破られても全体としてはセキュリティが保てるようにしている。
しかし、Merkle-Damgård で構成したハッシュ関数は連結しても個々のハッシュ関数と同等な強度にしかならず、より強くなることはない。Jouxによれば、MD5のハッシュ値が同じになる2つのメッセージを見つけることができれば、攻撃者がさらに同じハッシュ値となるメッセージを見つけることは簡単である。MD5で衝突を起こす多数のメッセージの中にはSHA-1でも衝突を起こすものもありうるだろう。そうなれば、SHA-1での衝突を探すのに必要な時間は多項式時間でしかない。この論旨はハル・フィニーが要約している。