暗号学的ハッシュとは？
任意の長さのメッセージを、固定長のハッシュ値にマッピングするアルゴリズム。
Hashに求められる要件
端的に言えば、以下の特徴を理解しておくことが重要。
決定性
同じメッセージからは必ず同じハッシュ値が得られる。
効率性
任意の長さのメッセージに対して、ハッシュ値を求める効率的なアルゴリズムが存在する。
現像計算困難性
hash値から元のメッセージを解読することが事実上不可能。一方向性関数が持つ性質に関連し、この性質を持たないハッシュアルゴリズムは（第一）現像攻撃に対して脆弱である。言い換えれば、ハッシュ値から元のメッセージを復元できてしまう。
弱耐衝突性
メッセージ$m_1$のハッシュ値$h = f(m_1)$が与えられた時、それと衝突するメッセージ$m_2$を発見することが事実上不可能。この性質は第二現像計算困難性とも呼ばれ、この特性を持たないハッシュアルゴリズムは、（第二）現像攻撃に対して脆弱である。このハッシュ値$h$は与えられたものであり、任意には選べない（後述：強耐衝突性との差）。
強耐衝突性
ハッシュ値$h$に衝突するメッセージ$m_1, m_2$を発見することが事実上不可能である。弱耐衝突性と異なり、ハッシュ値$h$は任意に選んで良い（任意に選べたとしても衝突する2つのメッセージを発見できないということ）。強耐衝突性のためには、弱耐衝突性に必要なハッシュ空間の倍の大きさが必要であることが知られている。
雪崩効果
メッセージが僅かにでも変わると、ハッシュ値が予測不可能な様式で大きく変更される。
用途
パスワードハッシュ
ユーザに対してログインなどのパスワード認証を必要とするサービスは、ユーザの検証のためにパスワードを保存しておく必要があるが、これが平文で置かれていると当然まずい。このため、ハッシュ値を保存しておき、ユーザから送られてきたパスワードのハッシュ値と突合することでユーザを認証する。
事実を知っていたことの表明
AliceとBobが同じ問題を解くことを考える。AliceはBobに先んじて問題を解けたが、答えをBobに伝えず、自分はある時刻で答えを導いたと表明したい。
この時、AliceはBobに対して、Hashアルゴリズムと、(答え + nonce)のハッシュ値を送信する。この時点で、ハッシュ値からは元のメッセージが復元できないため、BobはAliceから受け取ったハッシュ化されたメッセージからでは答えがわからない。
その後、Bobが答えがわかったとAliceに表明したら、AliceはBobに対して答えとnonceを送信する。Bobは、Aliceから受け取った答えとnonceを事前に共有されていたハッシュアルゴリズム使ってハッシュ化し、Aliceからもともと受け取っていたハッシュ値と一致することを確認する。こうすることで、Bobは、Aliceが過去のある時点で確かに答えを導いていたと確認できる。
代表的なハッシュアルゴリズム
- SHA-256
- MD2
- MD5
MD2は脆弱性が報告されているものの、今でも公開鍵基盤として使用されている。
また、最近聞いた話だと、RTX4090を使えばMD5の8文字（半角英数）も1時間あれば解けてしまうとのこと。ブルートフォースなので、後述の誕生日攻撃であるはずだが、処理能力の向上は、Polynomialの壁を攀じ登りつつあるように思う(https://pc.watch.impress.co.jp/docs/news/1588850.html)
誕生日攻撃
鳩の巣原理的に、ハッシュ空間の大きさが$N$であるとき、$N+1$個のインプットを与えると、必ず衝突が起こる。しかしながら、確率論的には、インプットの数が$N+1$に到達するよりもはるかに前に、かなりの高確率で衝突が生じる。具体的には、$N$が十分に大きい時、平均的には$1.25\sqrt{N}$回の試行で衝突する相異なるメッセージ$m_1, m_2$を発見できる。極論、全てのハッシュアルゴリズムは誕生日攻撃に対して脆弱だが、計算複雑性が高すぎるために事実上不可能となっている。
よって、全てのハッシュアルゴリズムに対して要求されるのは、そのハッシュアルゴリズムの現像計算攻撃が、少なくとも誕生日攻撃よりも効率的なアルゴリズムが存在しないことである。