ハッシュテーブル攻撃とHaskell

Haskell

以下を理解しようとしたときのメモ：

概要

外部からのデータに対して、効率の悪いアルゴリズムで処理するとセキュリティホールになるという一般的な問題の一例。N要素のハッシュテーブルの作成は、平均でO(N)だが、最悪で O(N^2) となる。

いろんな言語で、DJB のハッシュが利用されている。

  • DJBX33A
    • Equivalent string で衝突をたくさん作れる。理解は容易。
  • DJBX33X
    • 中間一致(Meet-in-the-middle)攻撃で衝突をたくさん発見できる。この理解は少し難しい。
    • Haskell の hashable パッケージはこっちを使っている。

DJBX33X

XOR を使っているので、基本的に総当たり攻撃で衝突を発見する。中間一致攻撃を使うと、計算量を格段に低減できる。中間一致攻撃を実現するためには、DJBX33X の逆関数が必要。

もし逆関数があるなら、以下のように中間一致攻撃が実現できる。実際に使われている初期値を調べる。適当に最終的な値を決める。この値が衝突する値。3文字程度のランダムな文字列(suffix と呼ぶ)をたくさん用意し、最終的な値と文字列から逆関数を使って中間値をたくさん求める。衝突もあるけど、概ね用意した文字列の数、中間値が求まる。

7文字程度のランダムな文字列(prefixと呼ぶ)をたくさん用意する。初期値と文字列から DJBX33X を使ってハッシュ値を計算し、中間値の中に一致するものを調べる。一致すれば、prefix+suffix が得たい文字列。この文字列はたくさん発見でき、すべて初期値から同じ最終的な値を生成する。つまり、衝突する文字列がたくさん手に入る。

実際に Haskell でコードを書いてみたら、驚くほどたくさん見つかった。

DJBX33X の逆関数

f × g = 1 を満たすのが、f の逆関数 g。

DJBX33X を数値式で表すと：

h_n+1 = (33 h_n) xor x   (mod 2^m)

A xor B xor B = A だから、両辺に xor x を右から施すと：

h_n+1 xor x = 33 h_n  (mod 2^m)

あとは、法 2^m における 33 の逆元を求めればよい。これは拡張ユークリッドの互除法を用いれば、簡単に見つかる。それを (1/33) と表現すると：

(h_n+1 xor x) × (1/33) = h_n  (mod 2^m)

よって逆関数が求まった。

サーバ攻撃

フォームのデータとして key と value の組を POST する。この key に求めたたくさんの文字列を使う。サーバは自動的にハッシュテーブルを生成するので、CPU 時間をたくさん消費する。

Haskell

Haskell では、ハッシュテーブル(辞書という方が適切)の実装に木が用いられているので、基本的にこの攻撃には弱くない。つまり、Data.Map や Data.IntMap は平均でも最悪の場合でも O(N log N)。

hashable パッケージの Hashable クラスを利用している hashmap の Map や unordered-containers の HashMap は、DJBX33X を使うことになる。

  • hashmap の Map は、木であり、末端も木(Data.Map)
    • すべての要素が衝突するなら、木は成長しないので O(1)
    • 衝突した要素の挿入は O(log N)
    • よって、最悪 O(N log N) となる
  • unordered-containers の HashMap は、木であるが、末端はリスト(FullList)
    • すべての要素が衝突するなら、木は成長しないので O(1)
    • 衝突した要素の挿入は O(N)
    • よって、最悪 O(N^2) となる

対策

Hashable の hash ではなく hashWithSalt とランダムな Salt を使う。Salt とは初期値。初期値が推測できなければ、衝突する文字列を発見するのは困難。Johan によれば、以下のようにして秘密の(ランダムな) secretSalt と mix を定義すればいいのではないかとのこと。

newtype SaltedString = SS ByteString

instance Hashable SaltedString where
  hashWithSalt salt (SS str) = hashWithSalt (secretSalt `mix` salt) str