Haskellとhashに関するigrepのブックマーク (6)
-
-
-
-
以前、僕が実装している 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
-
以下を理解しようとしたときのメモ‥ Efficient Denial of Service Attacks on Web Application Platforms slides n.runs-SA-2011.004 - web programming languages and platforms - DoS through hash table概要 外部からのデータに対して、効率の悪いアルゴリズムで処理するとセキュリティホールになるという一般的な問題の一例。N要素のハッシュテーブルの作成は、平均でO(N)だが、最悪で O(N^2) となる。 いろんな言語で、DJB のハッシュが利用されている。 DJBX33A Equivalent string で衝突をたくさん作れる。理解は容易。 DJBX33X 中間一致(Meet-in-the-middle)攻撃で衝突をたくさん発見できる。この理
-
-
1