Hash tables are one of the most commonly used data structures in computer science, due to their O(1) access time. However, this assumes a perfect hash function — the complexity can increase to O(n) when there are a lot of hash collisions. Historically, most libraries used weak, non cryptographic hashes for efficiency. These worked well for random strings, but the simplicity of the hash functions u
以前、僕が実装している 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)攻撃で衝突をたくさん発見できる。この理
HashDoS脆弱性との戦い! Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ 過去、HashDosの影響を受けたRuby。言語開発者はいかにしてこうした問題に対応してきたのでしょうか。コミッターである卜部氏の貴重な記録を公開します。 2011年の末頃、HashDoSという脆弱性が公表され、Rubyもこの影響を受けた。本稿の筆者である卜部昌平(うらべ・しょうへい/@shyouhei/以下、卜部)は、報告当初からRuby側のチームメンバーとしてプログラム本体の修正を担当した。以下はその記録である。言語開発者たちが普段どのようなことを考え、どういった技術を用いて開発やバグフィックスを行っているのか。その概要を知ってもらえれば幸いだ。 オブジェクト指向スクリプト言語 Ruby HashDoSの概要 なぜ約6年後の今、修正内容を公開するに至ったか? 前史:すでに内包されていたリスク
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く