SipHashについてのメモ

SipHashとは

従来、プログラミング言語の連想配列に用いられるハッシュ関数は十分シンプル（＝高速）かつ通常の利用で衝突しにくい関数が利用されていました。多くのプログラミング言語ではDJBX33AやDJBX33Xが使われていたようです。

しかし、HashDoSという意図的にハッシュの衝突を起こすような攻撃が問題視されて紆余曲折あった後、現在多くの言語の連想配列で利用されているハッシュ関数がSipHashです。

HashDoSを防ぐには暗号論的ハッシュ関数でないといけないようで、かつ連想配列のような用途では速度も重要なのでこのような新たなハッシュ関数が開発されたようですね。詳しくはリンク先を参照のこと。

• SipHash: a fast short-input PRF
• SipHashとAdvanced Hash Flooding - 不意になにかを残すブログ
• Hash-flooding DoS と SipHash - あどけない話

各種プログラミング言語・ミドルウェアにおける実装例

• Python
• Redis
• Perlはリンク先がわからず。hv_func.hに記述があった模様。
• Rubyはリンク先がわからず。ソースコードを落としてきて確認しました。

どの実装も、基本的には/dev/urandomからseedを与える方針ですかね。