[インデックス 10012] マップ反復処理のランダム化によるセキュリティ強化

コミット

コミットハッシュ: e40d6e066a58019f3256635bc19b86b1fe4e7b8a
作成者: Russ Cox rsc@golang.org
日付: 2011年10月17日 18:49:02 -0400
コミットメッセージ: runtime: random offset for map iteration

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/e40d6e066a58019f3256635bc19b86b1fe4e7b8a

元コミット内容

このコミットは、Goランタイムにおけるマップ反復処理にランダムオフセットを導入する重要な変更を実装しました。変更されたファイルは以下の通りです：

doc/go_spec.html: 言語仕様の更新
src/cmd/gc/go.h: コンパイラのヘッダーファイルの更新
src/pkg/runtime/hashmap.c: ハッシュマップ実装の中核部分
src/pkg/runtime/hashmap.h: ハッシュマップのヘッダーファイル

合計で63行の追加と19行の削除が行われました。

変更の背景

2011年末、多くのプログラミング言語（PHP、Python、Java、ASP.NET等）が重大なセキュリティ脆弱性に直面しました。これはoCERT-2011-003として知られる脆弱性で、ハッシュテーブルのコリジョン攻撃により、意図的に設計されたデータでサーバーを過負荷状態にすることが可能でした。

この攻撃は、攻撃者がハッシュ関数の予測可能性を悪用して、大量のハッシュコリジョンを発生させることで、本来O(1)であるべきハッシュテーブルの操作をO(n)まで劣化させるものでした。WebアプリケーションではPOSTデータを通じてこの攻撃が実行される可能性があり、サーバーのCPU使用率を100%まで上昇させることができました。

Goチームは、この脆弱性に対する防御策として、マップ反復処理の開始位置をランダム化することを決定しました。これにより、攻撃者が特定の反復順序に依存した攻撃を実行することを防ぐことができます。

前提知識の解説

ハッシュテーブルとは

ハッシュテーブルは、キーと値のペアを効率的に格納・検索するデータ構造です。理想的には、挿入、削除、検索の全てがO(1)の時間計算量で実行されます。

ハッシュコリジョン攻撃の仕組み

ハッシュコリジョン攻撃は以下のような仕組みで動作します：

ハッシュ関数の予測: 攻撃者がシステムで使用されているハッシュ関数の動作を予測
コリジョン発生: 意図的に同じハッシュ値を持つキーを大量に生成
性能劣化: ハッシュテーブルの特定のバケットに全ての要素が集中し、線形探索が発生
DoS攻撃: CPU使用率が極端に高くなり、サーバーが応答不能になる

Go言語におけるマップの実装

Go言語のマップは、C言語で実装されたハッシュテーブルを使用しています。各マップは複数のバケットを持ち、各バケットには複数のキー・値ペアが格納されます。反復処理は通常、最初のバケットから順番に全てのバケットを走査します。

2011年のセキュリティ脆弱性

2011年12月28日、oCERT（Open Source Computer Emergency Response Team）は、多くのプログラミング言語のハッシュテーブル実装に存在する重大なセキュリティ脆弱性を公開しました。この脆弱性により、攻撃者は以下のような攻撃を実行できました：

DoS攻撃: 特定のキーを使用してハッシュテーブルの性能を意図的に劣化させる
CPU使用率の激増: 本来O(1)の操作がO(n)まで劣化することで、サーバーのCPU使用率を100%まで上昇させる
Webアプリケーションへの攻撃: POSTデータを通じて悪意のあるキーを送信し、サーバーを過負荷状態にする

技術的詳細

1. 言語仕様の更新

doc/go_spec.htmlでは、マップの反復順序に関する仕様が明確化されました：

-The iteration order over maps is not specified.
+The iteration order over maps is not specified
+and is not guaranteed to be the same from one iteration to the next.

この変更により、開発者がマップの反復順序に依存することを明確に禁止し、プログラムの移植性を向上させました。

2. イテレータ構造体の拡張

src/cmd/gc/go.hおよびsrc/pkg/runtime/hashmap.hにおいて、Hiter構造体に新しいフィールドが追加されました：

cycled: 反復処理が一周したかどうかを示すブール値
cycle: 反復処理を開始したハッシュ値を記録

3. ランダムオフセットの生成

hash_iter_init関数では、新しいランダムオフセット生成ロジックが実装されました：

// fastrand1 returns 31 useful bits.
// We don't care about not having a bottom bit but we
// do want top bits.
if(sizeof(void*) == 8)
    it->cycle = (uint64)runtime·fastrand1()<<33 | (uint64)runtime·fastrand1()<<2;
else
    it->cycle = runtime·fastrand1()<<1;

この実装では、32ビットおよび64ビットシステムの両方に対応したランダム値生成が行われています。

hash_next関数の再構築 (67-173行): 反復処理の中核ロジックが完全に書き直され、循環型アルゴリズムが実装されました。
hash_iter_init関数の拡張 (581-156行): イテレータ初期化時にランダムオフセットの生成と設定が追加されました。
循環検出ロジック (108-116行, 129-137行): 反復処理が一周したことを検出し、重複を避けるためのロジックが実装されました。

`src/pkg/runtime/hashmap.h`の構造体変更

hash_iter構造体に以下のフィールドが追加されました：

bool cycled;        /* have reached the end and wrapped to 0 */
hash_hash_t cycle;  /* hash value where we started */

コアとなるコードの解説

ランダムオフセット生成の詳細

if(sizeof(void*) == 8)
    it->cycle = (uint64)runtime·fastrand1()<<33 | (uint64)runtime·fastrand1()<<2;
else
    it->cycle = runtime·fastrand1()<<1;

このコードは、システムのアーキテクチャに応じて異なるランダム値生成方法を使用します：

64ビットシステム: 2つの31ビットランダム値を組み合わせて64ビット値を生成
32ビットシステム: 1つの31ビットランダム値をシフトして32ビット値を生成

循環型反復処理の実装

if(!it->cycled) {
    // Wrap to zero and iterate up until it->cycle.
    it->cycled = true;
    it->last_hash = 0;
    it->subtable_state[0].e = it->h->st->entry;
    it->subtable_state[0].start = it->h->st->entry;
    it->subtable_state[0].last = it->h->st->last;
    goto Again;
}

この部分では、反復処理がテーブルの終端に到達した際に、先頭に戻って開始位置まで続行するロジックが実装されています。

重複防止機能

if(it->cycled && e->hash > it->cycle) {
    // Already returned this.
    it->last_hash = ~(uintptr_t)0;
    it->changes--;
    return (0);
}

このコードは、循環処理中に既に返された要素を再度返すことを防ぐためのチェック機能です。

変更検出機能

if (it->changes != it->h->changes) {    /* hash table's structure changed; recompute */
    if (~it->last_hash == 0)
        return (0);
    it->changes = it->h->changes;
    it->i = 0;
    iter_restart (it, it->h->st, 0);
}

このメカニズムにより、マップの構造が変更された場合（要素の追加や削除）に反復処理を適切に再開できます。

comemo