SipHashとAdvanced Hash Flooding

https://twitter.com/a4lg/status/279543990972461056
http://crypto.junod.info/2012/12/13/hash-dos-and-btrfs/
あたり経由でカーネルのBtrfs実装に関するHashDoSの話。を経由して
SipHash https://www.131002.net/siphash/
 について流し読みした。何故暗号論的ハッシュが必要か指摘していたのでめも。

SipHashは、HashDoS耐性のある高速ハッシュアルゴリズムとして使える暗号論的擬似乱数生成器。

高速性は主に、
・128bitの生成鍵（salt相当）からコストの大きな拡張関数を使わずそのまま初期状態を作れる。
・ブロックは64bit単位と小さく、状態空間は64bitx4
・ルックアップテーブルを使わない
あたりで実現されていて、
一方で暗号論的に安全なハッシュアルゴリズムを取り入れつつ
・ラウンド数は可変だがSipHash-2-4以上なら鍵の推測が難しい
・決定論的に一定時間で計算が出来る。CPUのALU実装に問題が無ければタイミング型サイドチャネル攻撃に頑強。
その他暗号論的ハッシュとして基本的な強度検討はなされているっぽい。

他にもハッシュテーブル実装目的のハッシュアルゴリズムはCityHashなどがあるが、暗号論的な一方向性はもたない。例えばCityHashでは一様性が低いらしく、攻撃者が外部から鍵（salt）を推測してHashDoSを引き起こせる可能性がある。


Advanced Hash Flooding （論文内の表現）
タイミング攻撃が可能なら暗号論的一方向性をもたないハッシュでは鍵が一定である限りHashDoSは容易という話。
まず、ハッシュテーブルを使うならタイミング攻撃、すなわち、コリジョンが起きたとき処理が少し遅くなることを検出するサイドチャネル攻撃が通用することは避けられない。

ハッシュに一方向性のない、または弱い場合では、タイミング攻撃でコリジョンが発生するペアが幾つか分かってしまえば、鍵を推測してコリジョンを起こす他のメッセージを大量生成できてしまう。
CGIなど、プロセス立ち上げの度に鍵を更新できるならいいが、寿命の長いデーモンで鍵が更新されるまでにタイミング攻撃が出来るなら、ハッシュ関数に鍵をつかっていようとHashDoSに脆弱になる。

暗号論的な一方向性があるならば、メッセージがコリジョンしたかどうかという情報から鍵を推測することは出来ないので、コリジョンが見つかったからといって、攻撃者は衝突する異なるメッセージを作成することはできない。攻撃者はコリジョンを一つずつタイミング攻撃で調べていく必要があるので、hashdosの準備がとても困難になる。大きなオンメモリデータベースなど、鍵を容易には更新できない状況下でも、hashdosへの対策としては十分になる。
というわけでSipHashでは一方向性が高いハッシュ関数を使うことを推奨している。

SipHashは強度がそこそこあり、短いメッセージに対しても性能がリニアで、短いキーを扱うことが多いインタプリタ実装のハッシュテーブルにも適しているとしている。