(4) 衝突耐性の定義

本記事は 暗号学一人アドベントカレンダー 第4日目(相当)の記事です。

前回の記事はブロック暗号/ストリーム暗号のセキュリティ定義の話をしましたが、今回は暗号学的ハッシュ関数のセキュリティ定義である「衝突耐性」(collision resistance)を説明します。前回の内容に比べるとかなり軽い内容です（配分ミスった感がある）。

暗号学的ハッシュ関数(MD5, SHA-1, SHA-2, etc.)は長いメッセージから予測困難なハッシュ値を生成するための関数です。これも2日目の基礎編で書くべきだった内容かもしれませんが「パスワードを暗号化して保存しています」と言っているのは厳密には嘘で、暗号化して保存していたら復号ができてしまうので、そうではなくハッシュ値を保存しています。そのような用途から、ハッシュ値からメッセージ本体を予測できたり、あるハッシュ値を得る別のメッセージを容易に生成できてしまってはいけません。このため、いくつかの攻撃ケースに対して耐えるというセキュリティ定義が用意されています。

原像計算困難性

あるハッシュ値が攻撃者に与えられたとき、同じハッシュ値を得るメッセージが推測できない、という性質が原像計算困難性です。これが満たされていないと、パスワードのハッシュ値を手に入れることが実質的にパスワードを手に入れることとほぼ同じ難易度になるので、「パスワードをハッシュ化して保存する」というのが安全ではなくなります。原像計算困難性まで突破された暗号学的ハッシュ関数はもはや暗号学的ハッシュ関数と呼んでいいのか、というくらいですが、現在知られているほとんどのMD5やSHA-1に対する攻撃は原像攻撃ではありません。

弱衝突耐性 vs 強衝突耐性

攻撃者にハッシュ値とそれを生成するメッセージが与えられたとき、同じハッシュ値を生成する他のメッセージを生成するのが困難である、という性質が第2原像計算困難性、あるいは弱衝突耐性と呼ばれます。一方で、H(m1) = H(m2)となる2つのメッセージm1, m2を見つけることが困難であるという性質が衝突耐性、あるいは強衝突耐性と言われる性質です。日本語での訳語で弱衝突耐性/強衝突耐性という語が使われるのが若干ミスリーディングである気がしていて、弱衝突耐性のほうが与えられたメッセージに対して衝突を与えなくてはいけない分強い仮定を置いている問題で、そのぶん突破が難しい性質です。「SHA-1が突破された」といわれるのは強衝突耐性のほうで、任意にメッセージとハッシュ値を与えたら衝突ができるという弱衝突耐性は現時点では突破されていません。

---

次回の記事では衝突攻撃で用いられる「誕生日のパラドックス」の計算を追いかけてみます（初見で追えなかったので復習用）。