gallu’s blog

エンジニアでゲーマーで講師で占い師なおいちゃんのブログです。

ハッシュへの考察:とりあえずのまとめ

さてはて。こーゆー流れでハッシュってのは現在に至っているようです。
で…使われ方でハッシュ関数への配慮が変わるのは当然なのですが、ちぃとまとめて見ましょう。


ハッシュ法(ハッシュ検索)として用いる場合。
衝突することは概ね前提なので、如何に「均一に衝突するようにするか」がポイントになります。予めデータの質がわかってると色々と小細工も可能ですね。
とはいえ「とりあえずざっくり作ってみて後で修正」ってケースが多いような気もしますが*1
よくJavaやらPHPやらPerlやらで出てくる「ハッシュ配列」は本質的にハッシュ検索のロジックがベースになってます。


ちなみに余談ですが。完全ハッシュ関数ってものがありまして、これは「衝突しない」ハッシュ関数です。
概ね「ある固定された母数における」という限定環境下において言及されるものです。
ちなみにコンパイラ作るときにも出てきます。予約語テーブルに対する完全ハッシュ関数があるとコンパイル楽なんですよ。…ええかなり停滞しているOOBHPの話に絡んできます(笑


閑話休題


セキュリティとしてのハッシュ関数の場合。
なによりも「衝突しないこと」が重要なのですが。まぁハッシュである以上不可避なので。
次に出てくるのは「衝突耐性 (collision resistance) 」になります。対衝突性とは「衝突を簡単に見つけられるか否か」って観点で。簡単なら弱いし難しけりゃ強いって観点ですね。
厳密には。さらにこの衝突耐性は二つの方向から見まして。


弱衝突耐性
「あるメッセージのハッシュ値が与えられたときに、そのハッシュ値をもつ別のメッセージを見つけ出すことが容易か困難かを指し示す」
代表的アタック手法:ブルートフォース
力押しで「適当に作った元メッセージを微妙に変化させていってハッシュ値がぶつかるまでリトライし続ける」。
この場合の「適当に作った元メッセージ」ってのは大抵「悪意あるアタッカーにとって有利な、すりかえたいモノ」。


強衝突耐性
「同一のハッシュ値をもつ二つのメッセージを見つけ出すことが容易か困難かを指し示す」
代表的アタック手法:誕生日攻撃(birthday attack)
まず二つのメッセージを作成。一つは「本来使われたい、攻撃される側が読んで疑惑を抱かないようなメッセージ」。もう一つは当然のごとく「悪意あるアタッカーにとって有利な、すりかえたいモノ」。ポイントは、この二つのメッセージが「同一のハッシュ値を持つ」こと。
んで。
本来使われたいメッセージを使わせてハッシュ値を計算させた後、元ファイルを「攻撃者にとって都合の良いファイル」に摩り替える。これによって正真実を打ち破ることができる。


以上がハッシュに関する考察になります。
少しはハッシュってモノが見えてきましたでしょうか?


で。元に戻しますが。
結局のところ、ここまで調べてなお「一方向ではない(恐らくは双方向、ですよねぇ?)ハッシュ」という存在については確認ができませんでした。
…というか正直なところ。「データをある程度間引く」ハッシュにおいて「一方向ではない」っていうのは…ちょっと想像しにくいんですよね。
ただ、無論「私の知らない何か」がある可能性を否定は出来ないので。また何かありましたら追記などしてみたいと思います。


捕捉1:チェックサムはハッシュか?
すごく悩ましいのですが。「完全性の確保としてのハッシュ」という基準から考えると、チェックサムもまたハッシュの一環なのかなぁ、と思います。
ただ…衝突がほとんど問題にならないとか(いやまぁだから縦横でやるんでしょうが)なんとか…どうももう一つ腑に落ちていません(苦笑


捕捉2:圧縮ロジックはハッシュか?
一瞬。ハッシュの「縮める」って部分を基準にこんなことを考えたのですが。
「出力が固定長である」という定義の部分をもって明示的に否定できることがわかりました。
同じミスしないようにここに書いておきます。

*1:昔「カオス関数でハッシュ関数をごにょごにょ」とかいう狂気の沙汰もありましたがそれは多分例外(笑