Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 11501] ファイルの概要

このコミットは、Go言語のランタイムにおけるハッシュマップ（Hmap）の実装に、マップごとのハッシュシードを導入するものです。これにより、ハッシュ衝突攻撃（Hash DoS）のリスクを軽減し、ハッシュマップのパフォーマンスを向上させるための第一歩となります。具体的には、各ハッシュマップが初期化される際に、runtime.fastrand1()関数を用いてランダムなシード値（hash0）を持つようになり、このシード値がハッシュ計算の開始点として利用されます。

コミット

  • コミットハッシュ: 85aeeadaecbe48ecf0be44f030c06feb85e71eab
  • Author: Damian Gryski dgryski@gmail.com
  • Date: Tue Jan 31 00:37:03 2012 -0500
  • Summary: runtime: use per-map hash seeds

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

https://github.com/golang/go/commit/85aeeadaecbe48ecf0be44f030c06feb85e71eab

元コミット内容

runtime: use per-map hash seeds

This patch adds a hash seed to the Hmap struct. Each seed is
initialized by runtime.fastrand1(). This is the first step of a
solution to issue 2630. Fastrand1 still needs to be updated to provide
us with actually random bits.

R=golang-dev, rsc
CC=golang-dev
https://golang.org/cl/5599046

変更の背景

この変更の主な背景には、ハッシュ衝突攻撃（Hash DoS）の問題があります。ハッシュマップ（Go言語ではmap型）は、キーをハッシュ関数に通して得られるハッシュ値に基づいてデータを格納・検索するデータ構造です。理想的な状況では、ハッシュ関数は異なるキーに対して均等にハッシュ値を分散させ、高速なアクセスを提供します。

しかし、悪意のある攻撃者がハッシュ関数の特性を悪用し、意図的に多数のキーが同じハッシュ値（または少数のハッシュ値）に衝突するように細工されたデータを送信する可能性があります。このようなデータがハッシュマップに挿入されると、ハッシュ衝突が頻繁に発生し、ハッシュマップの内部で連結リスト（または同様の構造）が長大化します。これにより、マップ操作（挿入、検索、削除）の計算量がO(1)からO(N)に悪化し、CPUリソースが大量に消費され、結果としてサービス拒否（DoS）状態に陥る可能性があります。

このコミットは、Go言語のIssue 2630「mapのハッシュ関数をランダム化する」に対する解決策の第一歩として導入されました。この問題は、Goのハッシュマップが固定のハッシュ関数を使用していたため、攻撃者がハッシュ衝突を予測しやすかったことに起因します。マップごとに異なるランダムなシードを導入することで、攻撃者が事前にハッシュ衝突を計算することが困難になり、ハッシュ衝突攻撃に対する耐性を高めることが目的です。

ただし、コミットメッセージにもあるように、この時点ではruntime.fastrand1()が「実際にランダムなビット」を提供するには不十分であるという認識があり、さらなる改善が必要であることが示唆されています。これは、真のランダム性がないと、攻撃者がシードを推測し、依然として衝突を生成できる可能性があるためです。

前提知識の解説

ハッシュマップ（Hmap）

ハッシュマップは、キーと値のペアを格納するデータ構造で、キーを使って高速に値にアクセスできます。Go言語では組み込みのmap型として提供されており、内部的にはハッシュテーブルとして実装されています。ハッシュマップは、キーをハッシュ関数に通して得られるハッシュ値に基づいて、データをメモリ上の特定の位置（バケット）に格納します。

ハッシュ関数

ハッシュ関数は、任意のサイズの入力データ（キー）を受け取り、固定サイズの出力データ（ハッシュ値）を生成する関数です。良いハッシュ関数は、異なる入力に対して異なるハッシュ値を生成し、ハッシュ値が均等に分布するように設計されています。

ハッシュ衝突

異なるキーが同じハッシュ値を生成してしまう現象をハッシュ衝突と呼びます。ハッシュマップでは、衝突が発生した場合、同じバケット内に複数のキーと値のペアを格納するために、連結リストやオープンアドレス法などの衝突解決戦略が用いられます。衝突が頻繁に発生すると、マップ操作のパフォーマンスが低下します。

ハッシュ衝突攻撃（Hash DoS）

ハッシュ衝突攻撃は、ハッシュマップの脆弱性を悪用したサービス拒否攻撃の一種です。攻撃者は、ハッシュ関数の既知の特性を利用して、多数のキーが同じハッシュ値に衝突するように細工されたデータをサーバーに送信します。これにより、サーバー側のハッシュマップ操作が極端に遅くなり、リソースが枯渇してサービスが停止する可能性があります。

ランダムシード

ランダムシードは、擬似乱数生成器（PRNG）の初期値として使用される数値です。同じシード値を使用すると、同じ擬似乱数列が生成されます。ハッシュ関数にランダムシードを導入することで、同じ入力キーであっても、シードが異なれば異なるハッシュ値が生成されるようになります。これにより、攻撃者が事前にハッシュ衝突を予測することを困難にします。

runtime.fastrand1()

Go言語のランタイム内部で使用される高速な擬似乱数生成関数です。このコミットの時点では、そのランダム性がセキュリティ要件を満たすほど強力ではない可能性が示唆されています。

技術的詳細

このコミットでは、Goランタイムのハッシュマップ構造体Hmapにhash0という新しいフィールドが追加されました。このhash0はuintptr型で、各ハッシュマップインスタンスに固有のハッシュシードとして機能します。

  1. Hmap構造体へのhash0フィールドの追加: src/pkg/runtime/hashmap.c内のHmap構造体にuintptr hash0; /* hash seed */が追加されました。これにより、各ハッシュマップが独自のシードを持つためのメモリ領域が確保されます。

  2. hash_init関数でのhash0の初期化: ハッシュマップが初期化される際に呼び出されるhash_init関数内で、新しく追加されたh->hash0フィールドがruntime·fastrand1()の戻り値で初期化されるようになりました。これにより、マップが作成されるたびに異なる（擬似）ランダムなシードが割り当てられます。

  3. ハッシュ計算におけるhash0の利用: hash_lookup（検索）、hash_remove（削除）、hash_insert（挿入）といったハッシュマップの主要な操作において、ハッシュ値の計算を開始する際に、固定値の0ではなく、マップ固有のh->hash0が初期ハッシュ値として使用されるようになりました。 具体的には、hash = 0;という行がhash = h->hash0;に変更されています。これにより、同じキーであっても、異なるHmapインスタンス（異なるhash0を持つマップ）では異なる最終ハッシュ値が生成される可能性が高まります。

この変更により、攻撃者が特定のハッシュ関数と固定シードを前提としてハッシュ衝突を計算する戦略が困難になります。各マップが異なるシードを持つため、攻撃者は個々のマップのシードを推測しない限り、効率的な衝突セットを生成できなくなります。

コアとなるコードの変更箇所

diff --git a/src/pkg/runtime/hashmap.c b/src/pkg/runtime/hashmap.c
index 642995df89..1def96727a 100644
--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -13,6 +13,7 @@ struct Hmap {\t   /* a hash table; initialize with hash_init() */
 	uint8 indirectval;\t/* storing pointers to values */
 	uint8 valoff;\t/* offset of value in key+value data block */
 	int32 changes;\t      /* inc\'ed whenever a subtable is created/grown */
+	uintptr hash0;      /* hash seed */
 	struct hash_subtable *st;    /* first-level table */
 };
 
@@ -118,6 +119,7 @@ hash_init (Hmap *h, int32 datasize, int64 hint)\
 	h->count = 0;\
 	h->changes = 0;\
 	h->st = hash_subtable_new (h, init_power, 0);\
+	h->hash0 = runtime·fastrand1();\
 }\
 \
 static void\
@@ -266,7 +268,7 @@ hash_lookup (MapType *t, Hmap *h, void *data, void **pres)\
 	struct hash_entry *end_e;\
 	bool eq;\
 	\
-	hash = 0;\
+	hash = h->hash0;\
 	(*t->key->alg->hash) (&hash, t->key->size, data);\
 	hash &= ~HASH_MASK;\
 	hash += HASH_ADJUST (hash);\
@@ -311,7 +313,7 @@ hash_remove (MapType *t, Hmap *h, void *data)\
 	struct hash_entry *end_e;\
 	bool eq;\
 \
-	hash = 0;\
+	hash = h->hash0;\
 	(*t->key->alg->hash) (&hash, t->key->size, data);\
 	hash &= ~HASH_MASK;\
 	hash += HASH_ADJUST (hash);\
@@ -435,7 +437,7 @@ hash_insert (MapType *t, Hmap *h, void *data, void **pres)\
 	uintptr hash;\
 	int32 rc;\
 	\
-	hash = 0;\
+	hash = h->hash0;\
 	(*t->key->alg->hash) (&hash, t->key->size, data);\
 	rc = hash_insert_internal (t, &h->st, 0, hash, h, data, pres);\
 \

コアとなるコードの解説

上記のdiffは、src/pkg/runtime/hashmap.cファイルに対する変更を示しています。

  1. struct Hmapの変更:

    struct Hmap {   /* a hash table; initialize with hash_init() */
    // ... 既存のフィールド ...
    int32 changes;        /* inc'ed whenever a subtable is created/grown */
    uintptr hash0;      /* hash seed */ // <-- 追加された行
    struct hash_subtable *st;    /* first-level table */
};

    Hmap構造体にhash0というuintptr型のフィールドが追加されました。これは、各ハッシュマップインスタンスが持つ固有のハッシュシードを格納するためのものです。uintptrはポインタを保持できる整数型で、ここではハッシュ値の一部として利用されます。

  2. hash_init関数の変更:

    hash_init (Hmap *h, int32 datasize, int64 hint)
{
    // ... 既存の初期化処理 ...
    h->st = hash_subtable_new (h, init_power, 0);
    h->hash0 = runtime·fastrand1(); // <-- 追加された行
}

    hash_init関数は、新しいハッシュマップが作成される際に呼び出される初期化関数です。この関数内で、新しく追加されたh->hash0フィールドがruntime·fastrand1()関数の戻り値で初期化されます。これにより、マップが作成されるたびに異なる（擬似）ランダムなシード値がhash0に設定されます。

  3. hash_lookup, hash_remove, hash_insert関数の変更:

    // hash_lookup, hash_remove, hash_insert のいずれかの関数内
// ...
uintptr hash;
// ...
-   hash = 0; // <-- 削除された行
+   hash = h->hash0; // <-- 変更された行
    (*t->key->alg->hash) (&hash, t->key->size, data);
// ...

    これらの関数は、ハッシュマップのキーに対するハッシュ値を計算する際に使用されます。変更前は、ハッシュ計算の初期値として0が使われていました。変更後は、マップ固有のシード値であるh->hash0が初期値として使用されるようになりました。 (*t->key->alg->hash) (&hash, t->key->size, data);の行は、キーの実際のハッシュアルゴリズムを呼び出し、hash変数にハッシュ値を累積していく部分です。hash0を初期値とすることで、最終的なハッシュ値がマップごとに異なるシードに依存するようになります。

これらの変更により、Goのハッシュマップは、マップごとに異なるハッシュシードを持つようになり、ハッシュ衝突攻撃に対する耐性が向上しました。

関連リンク

参考にした情報源リンク