暗号学的ハッシュ関数
以上のような要求される性質にもとづき、暗号学的ハッシュ関数の特性について、もう少し詳細に説明する。
暗号学的ハッシュ関数は、任意長のビット列を入力とし、固定長のビット列を出力とする。その出力が「入力に対するハッシュ値」である。2019年現在の時点では、多くのコンピュータシステムがデータ量としてオクテット単位であるため、オクテット列を入力としている実装がもっぱらではある。
暗号学的ハッシュ関数には、少なくとも次のような特性が必須である。
暗号学的ハッシュ関数の典型的な利用例を以下に示す。アリスは難しい数学問題をボブに提示し、彼女自身はそれを解いたと主張する。ボブも解いてみるが、その前にアリスがはったりをかましていないことを確認したい。このときアリスは、自分の解答にランダムな文字列 (nonce) を付けてそのハッシュ値を計算し、ボブにハッシュ値を知らせる(この時点では解答そのものとnonceは秘密にしておく)。何日かしてボブがその問題を解いたら、アリスはnonceと自分の解答をボブに示すことで、既にその問題を解いていたことが証明できる。これはコミットメントスキームの簡単な例である。実際にはアリスとボブはコンピュータプログラムであることが多く、秘密にされることは数学問題の解などといったものではなく、もっと簡単に改竄できるものである。
安全なハッシュのもう1つの重要な用途として、データ完全性の検証がある。メッセージ(あるいはファイル)に改変が加えられているかどうかの判定であり、例えばメッセージを転送する前と後でメッセージダイジェストを計算し、比較することで検証する(転送以外の事象の前後でもよい)。
メッセージダイジェストは、確実にファイルを識別する手段としてバージョン管理システムで使われている(例えば、Git、Mercurial、Monotone)。
強衝突耐性 h = hash(m1) = hash(m2) となるような2つの異なるメッセージ m1 と m2 を探し出すことが困難でなければならない。第2原像計算困難性と異なる点として、h は任意に選んでよい。一般に誕生日のパラドックスによって、強衝突耐性を持つためには、原像計算困難性を持つために必要なハッシュ値の2倍の長さのハッシュ値が必要である。
これらの特性は、悪意ある攻撃者でもダイジェストを変化させずに入力データを改竄できないことを示すものである。したがって、2つの文字列のダイジェストが同じ場合、それらが同一のメッセージである可能性は非常に高い。
これらの基準に適合した関数でも、好ましくない特性をもつものがありうる。現在よく使われている暗号学的ハッシュ関数は伸長攻撃に対して脆弱である。すなわち、ハッシュ値 h(m) とメッセージ長 len(m) が分かっていて m そのものは不明の場合、適当な m' を選んで h (m || m') が計算できる。ここで、|| はメッセージの連結を意味する。