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(N^2) かかる。これを悪用するのが、Hash-flooding DoS。"Hash-flooding" という言葉は、Daniel J. Bernstein (DJB) 氏が実装した dnscache のコメントで最初に使われた(1999年)。

2003 年に Scott A. Crosby 氏と Dan S. Wallach 氏は、Hash-flooding DoS に関する論文を発表した。これまでの DoS は実装の不備を悪用していたが、この DoS はアルゴリズムの欠点を突く。今時のプログラミング言語ではハッシュがいたるところに使われていて、外部からの入力に対してハッシュを取るようになっていると、この攻撃の餌食となる。アルゴリズムの欠陥を突いていることを強調するために、題名に "Algorithmic Complexity" という言葉が使われているのが興味深い。

Denial of Service via Algorithmic Complexity Attacks, Scott A. Crosby and Dan S. Wallach, in Proceeding of SSYM'03 Proceedings of the 12th conference on USENIX Security Symposium - Volume 12, 2003

2011年、Alexander Klink 氏は Julian Wälde 氏は、広範囲のWebアプリがこの攻撃に対して脆弱であることを示した。以下が攻撃方法を説明したスライド。

Efficient Denial of Service Attacks on Web Application Platforms, Alexander Klink and Julian Wälde, 2011

この時期に多くのプログラミング言語で使われていたハッシュは、DJB氏が開発したDJBX33AやDJBX33X。この後、多くのプログラミング言語は初期値を乱数化する対処療法を実施した。例えば、ruby のアナウンスを参照。

その後、いくつかのプログラミング言語は、ハッシュ値の乱数性が高い MurmurHash を採用することなった。例えば、Ruby 1.9。また、Google では CityHash が使われている。

2012年に Martin Boßlet 氏と共同で、Jean Philippe Aumasson 氏と DJB 氏は、MurmurHash、CityHash、および、Pythonのハッシュが脆弱であることを示した。初期値を乱数化しても、ハッシュを衝突されてしまう。

Hash-flooding DoS reloaded: attacks and defenses, Jean-Philippe Aumasson and Daniel J. Bernstein and Martin Boßlet, 2012

これらのハッシュ関数は、入力をブロックに分割して処理する。初期値には乱数を利用するが、それぞれのブロックでは乱数を使わない。あるブロックの処理でハッシュに差が生じるが(更新されるが)、次のブロックの値をうまく選べば、この差を打ち消すことが可能。適当なデータに、この二つのブロックを繰り返し付けていけば、衝突する入力をいくらでも生成できる。

2012 年に、Jean Philippe Aumasson 氏と DJB 氏は、一方向性を持つ暗号学的なハッシュ関数をいわゆるハッシュ関数として用いることを提案した。