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
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 ・ルックアップテーブルを使わない あたりで実現されていて、 一方で暗号論的
ASFWS 2012 - Hash-flooding DoS reloaded: attacks and defenses par Jean-Philippe Aumasson / Martin Boßlet
At 28c3, Klink and Waelde demonstrated that a number of technologies (PHP, .NET, Ruby, Java, etc.) remained vulnerable to the decade-old hash-flooding DoS attacks. These attacks work by enforcing worst-case insert time in hash tables by sending many inputs hashing to the same value (a “multicollision”). Many vendors fixed the issue by replacing the weak deterministic hash function with stronger an
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
