ハッシュ函数の困難性・耐性って?

去年末の MD5 の隙をついた偽 CA 証明書の生成以降
ハッシュ函数に対する攻撃の記事に関してちょっと敏感になってるんですが
ちょっと混乱してるので攻撃方法に関して再確認しました
Wikipedia の「ハッシュ関数」を読んだりしただけなんですが

ハッシュ函数が満たすべき・持つべき性質として

• 原像計算困難性
• 第 2 原像計算困難性
• 衝突困難性

ってのが挙げられています
去年末のやつは

• 選択プレフィックス衝突? (chosen prefix collision)

ってのを起こすのが簡単だってことで可能となった攻撃なんですが
これは衝突困難性と第 2 原像計算困難性の間にいる感じかな?

攻撃方法は色々考えられるわけですが最終的には総当たりすることになります
総当たりするまでに下拵えして総当たりの計算量減らそうってのが研究されてます
なので、減った結果の総当たりの量のことを困難性の数字での表現として取ります

衝突困難性

これは
「ハッシュ函数に対してハッシュ値が等しくなる 2 つのデータをみつけなさい」
という問題を解くのが難しいということ

攻撃方法というか、「誕生日のパラドックス」って言われてるのがありまして
「1 つのクラスに同じ誕生日の人がいる確率が 1/2 以上になるのはクラスが何人から?」
っていう問題の答が 23 人ってのは意外と少なくない?
というものです

この問題の意味が取りづらいんですが
「誰か一人選んだときにその人と同じ誕生日の人がクラスにいる確率」ではなくて
「クラス全員の誕生日を並べたときに同じものが2つ以上ある確率」を考えています

ハッシュ函数の衝突を起こすっていうのも状況は全く同じでして
誕生日の場合は
「365 日のうちから何回日付を選んでくれば衝突するか?」
でしたが、ハッシュ函数の場合は
「函数の吐くハッシュ値をいくつ取ってくれば衝突するものが現れるでしょうか?」
とになります
で、計算すると、これがハッシュ値の取りうる個数の平方根に近くなることが知られてます

例えば MD5 だと 128bit のハッシュ値なので 2⁶⁴ コのハッシュ値を計算すれば
SHA-1 だと 160bit のハッシュ値なので 2⁸⁰ コのハッシュ値を計算すれば
計算したものの中で衝突してるものがある確率が 1/2 を越える、ということです
なので、それぞれ基本の衝突困難性は 64bit, 80bit と言われていまして
それが研究者の方々によってより良い攻撃方法が発見される度に
困難性がの数字が落ちていって「破られた」とか言われたりしています
まぁ「破られた」っていうのは基本の衝突困難性よりも数字が落ちたときでしょうか

これが、MD5 だと今や、パソコンでもものの数分で計算できるところまで
衝突困難性が落っこちてしまっています

第 2 原像困難性

これは
「ハッシュ函数とデータ x に対して x とハッシュ値が等しくなるデータ y をみつけなさい」
です

RSA による署名では、元データのハッシュ値が秘密鍵で暗号化されています
元データが公開された状態なので第 2 原像困難性が破られてしまうと
どんな偽物の署名が作られる可能性が高くなってしまいます

原像困難性

これは
「ハッシュ函数とハッシュ値 h が与えられたとき、ハッシュ値が h と等しくなるデータ y をみつけなさい」
です
 
第 2 原像困難性のときはハッシュ値 h の元となるデータ x が与えられていたので
それを元に他のデータを生成することができたかもしれませんでしたが
原像困難性の場合はより少ない情報で計算する必要が出てきます

HTTP の基本認証などログイン時の認証用パスワードは
ハッシュ値が保存されていてログイン時に入力されたパスワードのハッシュ値と照合されます
万が一パスワードのハッシュ値が漏れてしまうと
この原像困難性が無くてはパスワードと同じハッシュ値を返すデータが生成されてしまい
なりすましが発生してしまいます


原像困難性は総当たりが妥当な攻撃方法だろうということで
出力される bit 長が困難性として挙げられています
MD5 なら 128bit, SHA-1 なら 160 bit になります

先日の MD5 に対する攻撃というのは
この 128bit が 123.4bit まで落ちたということのようです
こういうのはブレークスルーがおきるとあっという間だったりするので
近々劇的に困難性が落ちるかもしれません