SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

Javaセキュアコーディング入門

ハッシュテーブルに対する攻撃手法のはなし

Javaセキュアコーディング入門(4)


  • X ポスト
  • このエントリーをはてなブックマークに追加

 昨年末にハッシュテーブルの実装に関する脆弱性が公表され、該当するアプリケーションや言語実装系が対策を行っています。今回はこの問題について解説します。

  • X ポスト
  • このエントリーをはてなブックマークに追加

ハッシュテーブル実装に対する攻撃とは

 昨年12月末にドイツで開催されたCCC(Chaos Communication Congress)において、"Effective Denial of Service attacks against web application platforms"(Webアプリケーションに対する効率的なDoS攻撃)と題した発表が行われました。タイトルに「Webアプリケーション」とついてはいますが、この問題はWebアプリケーションに限ったものではありません。以下の三つの条件が揃ったアプリケーションであれば例外なく、DoS攻撃の餌食となる危険があります。

  • ハッシュテーブルというデータ構造を使っている
  • ハッシュ値を計算するアルゴリズムが「脆弱」である
  • ハッシュテーブルに登録するデータをプログラム外部から指定できる

ハッシュテーブルとその問題

 Wikipedia(日本語版)ではハッシュテーブルについて以下のように説明しています:

(「ハッシュテーブル」概要より引用)

ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。 通常、配列の添え字には非負整数しか扱えない。そこで、キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。しかしハッシュ関数の選び方(例えば、異なるキーから頻繁に同じハッシュ値が生成される場合)によっては、性能が劣化して最悪の場合O(n)となってしまう。

 ハッシュテーブルは、大量のデータを効率よく管理したい場合に使われます。Perlやawkなどの連想配列の実装にもハッシュテーブルは活用されています。

 また、Javaでハッシュテーブルといえば、標準APIとしてHashtableクラスやHashMapクラスなどが提供されています。

ハッシュテーブル
ハッシュテーブル

 Wikipediaの説明にもあるように、ハッシュテーブルは、入力データによっては処理の効率が悪くなる場合があることに注意が必要です。Wikipediaの説明では「異なるキーから頻繁に同じハッシュ値が生成される場合」と書かれています。異なるキーが同じハッシュ値を持つということは、異なるキーに対応する値を、ハッシュテーブルの「同じ」位置に置くことになります。

 このように複数のデータのハッシュ値が同じになった場合の対処方法はいくつかありますが、単純なやり方としては例えば、テーブルの各エントリを線形リストとして用意しておき、同じハッシュ値を持つデータは該当するエントリ位置の線形リストで管理します。JDKのHashtableクラスもそのような実装になっています。

 同一のハッシュ値を持つデータが多くなるほど線形リストを辿る場面が多くなり、登録や検索の効率は悪くなります。登録するデータのほぼ全てのハッシュ値が同一であった場合、処理のほとんどは線形リストの操作となり、効率の大幅な低下を招きます。攻撃者としては、そのようなデータを与えることができれば、DoS攻撃を行うことが可能になる、というわけです。

 この攻撃手法は2003年のUSENIX Security Symposiumで最初に発表されました。2011年末のCCCにおける発表は、この手法が、今現在広く使われているアプリケーションやフレームワークにも適用可能であることを示したものです。

短期集中セミナーのお知らせ

 JPCERTコーディネーションセンターの講師陣によるAndroidセキュアコーディングセミナーを2012年3月14日に開催します(主催:翔泳社/CodeZine)。詳しくは特設ページまで!

会員登録無料すると、続きをお読みいただけます

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

次のページ
Java実行環境やJava/Androidアプリへの影響

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
Javaセキュアコーディング入門連載記事一覧

もっと読む

この記事の著者

戸田 洋三(JPCERT コーディネーションセンター)(トダ ヨウゾウ(JPCERT コーディネーションセンター))

リードアナリストJPCERTコーディネーションセンター東京工業大学情報理工学研究科修士課程修了。学生時代は、型理論および証明からのプログラム抽出を研究。その後、千葉大学総合情報処理センターのスタッフとして、学内ネットワークの運営、地域ネットワーク、IPマルチキャストの実験ネットワークであるJP-MB...

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/6396 2012/02/21 10:46

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング