Hash-flooding DoS と SipHash - あどけない話

以前、僕が実装している web サーバ Mighty が、Haskell で書いているにも関わらず、セグメンテーションフォールトを起こしていた。調べたところ hashable ライブラリがリンクする C の DJBX33X が、SipHash に変わったことが原因だった。このときから SipHash が気になっていたし、以前社内で説明した "Efficient Denial of Service Attacks" との関係も知りたかったので、少し調べてみた。この記事は、その覚え書き。 Hash-flooding DoS の歴史 1998 年に Alexander Peslyak 氏が Phrack Magazine で、Hash-flooding DoS を受けたことを報告している。ハッシュは、N 個の要素を挿入するのに通常 O(N) かかるが、ハッシュ値がすべて衝突する最悪の場合では O

[efcl]

ハッシュ衝突によるDDoSの歴史。 オブジェクトのマップにハッシュを使う言語が多いため、そのハッシュアルゴリズムの影響を受ける。 DJBX33A、MurmurHash、SipHash、wyhash

[progrhyme]

今はSipHashが標準なのかな

[a_bicky]

Hash-flooding DoS の歴史とか

[ya--mada]

この辺、自分あまいとこ、追いかけたい

[tmatsuu]

ほほう。あとでさらに突っ込んでSipHash調べる

[ukky3]

Hash-flooding DoS と SipHash - あどけない話