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

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

このコミットは、Goランタイムにおけるハッシュ計算のセキュリティと堅牢性を向上させるための重要な変更です。具体的には、ハッシュ計算の開始時に常にハッシュシードを組み込むように修正することで、予測可能なハッシュ衝突（Hash Collision）が発生する可能性を排除し、サービス拒否（DoS）攻撃などの潜在的な脆弱性から保護することを目的としています。

コミット

commit 63bee953a2d3aea703de1f4980f557d2af645dc9
Author: Ian Lance Taylor <iant@golang.org>
Date:   Fri Jan 4 07:53:42 2013 -0800

    runtime: always incorporate hash seed at start of hash computation
    
    Otherwise we can get predictable collisions.
    
    R=golang-dev, dave, patrick, rsc
    CC=golang-dev
    https://golang.org/cl/7051043

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

https://github.com/golang/go/commit/63bee953a2d3aea703de1f4980f557d2af645dc9

元コミット内容

Goランタイムにおいて、ハッシュ計算の開始時に常にハッシュシードを組み込むように変更しました。これにより、予測可能なハッシュ衝突を防ぎます。

変更の背景

この変更の背景には、ハッシュテーブル（Go言語ではmapとして実装されている）のセキュリティとパフォーマンスに関する重要な考慮事項があります。

ハッシュ衝突とDoS攻撃

ハッシュテーブルは、キーをハッシュ関数に通して得られるハッシュ値に基づいてデータを格納・検索するデータ構造です。理想的なハッシュ関数は、異なるキーに対して均一にハッシュ値を分散させ、衝突（異なるキーが同じハッシュ値になること）を最小限に抑えます。しかし、悪意のある攻撃者がハッシュ関数の特性を悪用し、意図的に多数のキーを同じハッシュ値にマッピングするようなデータ（「衝突キー」）を生成することが可能です。

このような衝突キーが大量にハッシュテーブルに挿入されると、ハッシュテーブルのパフォーマンスは最悪の場合、O(1)（定数時間）からO(N)（線形時間）に劣化します。これは、衝突した要素がリンクリストなどの形で同じバケットに格納され、検索や挿入のたびにそのリストを線形に走査する必要が生じるためです。結果として、CPU使用率が急増し、アプリケーションが応答不能になるサービス拒否（DoS）攻撃につながる可能性があります。

予測可能なハッシュシードの問題

多くのハッシュ関数は、ハッシュ計算の開始時に「シード（seed）」と呼ばれる初期値を使用します。このシードが固定されているか、予測可能な方法で生成される場合、攻撃者はオフラインで衝突キーを事前に計算し、それを攻撃に利用することができます。

このコミット以前のGoランタイムのハッシュ計算では、ハッシュシードの組み込み方が不十分であったため、特定の条件下で予測可能な衝突が発生する可能性がありました。この脆弱性を解消し、Goアプリケーションの堅牢性を高めるために、ハッシュ計算の初期段階でランダムなシードを常に組み込むように変更する必要がありました。これにより、攻撃者が衝突キーを事前に計算することが極めて困難になり、DoS攻撃のリスクが大幅に軽減されます。

前提知識の解説

ハッシュ関数とハッシュテーブル（Map）

  • ハッシュ関数: 任意のサイズの入力データ（キー）を受け取り、固定サイズの出力（ハッシュ値）を生成する関数です。理想的には、異なる入力に対して異なるハッシュ値を生成し、ハッシュ値が均一に分布するように設計されます。
  • ハッシュテーブル（Map）: キーと値のペアを格納するデータ構造で、キーのハッシュ値を使って値を効率的に検索、挿入、削除できます。Go言語では組み込みのmap型として提供されています。

ハッシュシード

ハッシュシードは、ハッシュ関数の初期状態を決定するために使用されるランダムな値です。同じ入力データであっても、異なるハッシュシードを使用すると異なるハッシュ値が生成されます。これにより、攻撃者がハッシュ関数の内部ロジックを知っていたとしても、シードが予測不可能であれば、衝突キーを事前に生成することが困難になります。

Goランタイム

Goランタイムは、Goプログラムの実行を管理するシステムです。ガベージコレクション、スケジューリング、メモリ管理、そしてハッシュテーブルの操作など、低レベルの機能を提供します。このコミットで変更されたalg.cやiface.cは、Goランタイムのハッシュ計算ロジックを実装しているC言語のファイルです。

uintptr

uintptrはGo言語の型で、ポインタを保持するのに十分な大きさの符号なし整数型です。これは、メモリアドレスを整数として扱う際に使用されます。ハッシュ値やメモリサイズを表現するのに適しています。

IfaceとEface

Go言語のインターフェースは、内部的には2つの構造体で表現されます。

  • Iface: メソッドを持つインターフェース型（例: io.Reader）を表します。内部には、型情報（itab）とデータポインタ（data）が含まれます。
  • Eface: メソッドを持たない空のインターフェース型（interface{}）を表します。内部には、型情報（_type）とデータポインタ（data）が含まれます。 これらのインターフェース値のハッシュ計算も、このコミットの対象となっています。

技術的詳細

このコミットの主要な変更点は、Goランタイムにおけるハッシュ計算の初期段階で、ハッシュシード（*hまたはM0と既存のハッシュ値のXOR）を組み込むように修正したことです。これにより、ハッシュ計算の予測可能性が排除され、ハッシュ衝突攻撃に対する耐性が向上します。

具体的には、以下の関数が変更されました。

  1. runtime·memhash:

    • この関数は、任意のメモリブロックのハッシュを計算します。
    • 変更前は、hash = M0; でハッシュ計算を開始していましたが、変更後は hash = M0 ^ *h; となりました。ここで*hはハッシュシードとして機能します。これにより、ハッシュ計算の初期値に外部から与えられたシードが常に反映されるようになります。
    • また、最終的なハッシュ値を*hに格納する際も、変更前は *h = (*h ^ hash) * M1; と既存の*hと計算結果をXORしていましたが、変更後は *h = hash; となり、計算されたハッシュ値そのものを*hに格納するようになりました。これは、*hがハッシュシードとしてのみ機能し、最終的なハッシュ結果はhash変数に保持されるという役割分担を明確にしています。

  2. runtime·interhash および runtime·efacehash:

    • これらの関数は、それぞれIface（メソッドを持つインターフェース）とEface（空のインターフェース）のハッシュを計算します。
    • 変更前は、これらの関数は単にインターフェース値を受け取り、内部でハッシュ計算を行っていました。
    • 変更後は、これらの関数がuintptr hという追加の引数を受け取るようになりました。このhがハッシュシードとして機能します。
    • 関数呼び出し元では、*h ^ M0という形でシードを渡しています。M0はGoランタイムで定義されている定数で、ハッシュ計算の初期値の一部として使われます。

  3. ifacehash1:

    • runtime·ifacehashとruntime·efacehashから内部的に呼び出されるヘルパー関数です。
    • この関数も、uintptr hという引数を追加で受け取るようになりました。
    • 変更前は、h = 0; と内部でハッシュ値を0に初期化していましたが、変更後はこの行が削除され、外部から渡されたhがそのままハッシュ計算の初期値として使用されるようになりました。

これらの変更により、Goランタイムのハッシュ計算は、常に外部から与えられた（または内部で生成されたランダムな）シード値に基づいて開始されるようになり、ハッシュ衝突の予測可能性が大幅に低下しました。

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

diff --git a/src/pkg/runtime/alg.c b/src/pkg/runtime/alg.c
index c7424bc262..ad85b43aef 100644
--- a/src/pkg/runtime/alg.c
+++ b/src/pkg/runtime/alg.c
@@ -19,13 +19,13 @@ runtime·memhash(uintptr *h, uintptr s, void *a)
 	uintptr hash;
 
 	b = a;
-	hash = M0;
+	hash = M0 ^ *h;
 	while(s > 0) {
 		hash = (hash ^ *b) * M1;
 		b++;
 		s--;
 	}
-	*h = (*h ^ hash) * M1;
+	*h = hash;
 }
 
 void
@@ -355,7 +355,7 @@ void
 runtime·interhash(uintptr *h, uintptr s, void *a)
 {
 	USED(s);
-	*h = (*h ^ runtime·ifacehash(*(Iface*)a)) * M1;
+	*h = runtime·ifacehash(*(Iface*)a, *h ^ M0) * M1;
 }
 
 void
@@ -389,7 +389,7 @@ void
 runtime·nilinterhash(uintptr *h, uintptr s, void *a)
 {
 	USED(s);\n-\t*h = (*h ^ runtime·efacehash(*(Eface*)a)) * M1;
+\t*h = runtime·efacehash(*(Eface*)a, *h ^ M0) * M1;
 }
 
 void
diff --git a/src/pkg/runtime/iface.c b/src/pkg/runtime/iface.c
index 3a7c45fd14..370edffb81 100644
--- a/src/pkg/runtime/iface.c
+++ b/src/pkg/runtime/iface.c
@@ -546,10 +546,10 @@ runtime·assertE2E2(InterfaceType* inter, Eface e, Eface ret, bool ok)
 }
 
 static uintptr
-ifacehash1(void *data, Type *t)
+ifacehash1(void *data, Type *t, uintptr h)
 {
 	Alg *alg;
-\tuintptr size, h;
+\tuintptr size;\n \tEface err;\n \n \tif(t == nil)\n@@ -563,7 +563,6 @@ ifacehash1(void *data, Type *t)
 \t\truntime·newErrorString(runtime·catstring(runtime·gostringnocopy((byte*)\"hash of unhashable type \"), *t->string), &err);\n \t\truntime·panic(err);\n \t}\n-\th = 0;\n \tif(size <= sizeof(data))\n \t\talg->hash(&h, size, &data);\n \telse\n@@ -572,17 +571,17 @@ ifacehash1(void *data, Type *t)
 }
 
 uintptr
-runtime·ifacehash(Iface a)
+runtime·ifacehash(Iface a, uintptr h)
 {
 	if(a.tab == nil)\n-\t\treturn 0;\n-\treturn ifacehash1(a.data, a.tab->type);\n+\t\treturn h;\n+\treturn ifacehash1(a.data, a.tab->type, h);\n }
 
 uintptr
-runtime·efacehash(Eface a)
+runtime·efacehash(Eface a, uintptr h)
 {
-\treturn ifacehash1(a.data, a.type);\n+\treturn ifacehash1(a.data, a.type, h);\n }
 
 static bool
diff --git a/src/pkg/runtime/runtime.h b/src/pkg/runtime/runtime.h
index 0c941f819b..a228b06e32 100644
--- a/src/pkg/runtime/runtime.h
+++ b/src/pkg/runtime/runtime.h
@@ -644,8 +644,8 @@ void	runtime·freemcache(MCache*);
 void	runtime·mallocinit(void);
 bool	runtime·ifaceeq_c(Iface, Iface);
 bool	runtime·efaceeq_c(Eface, Eface);
-uintptr	runtime·ifacehash(Iface);
-uintptr	runtime·efacehash(Eface);
+uintptr	runtime·ifacehash(Iface, uintptr);
+uintptr	runtime·efacehash(Eface, uintptr);
 void*	runtime·malloc(uintptr size);
 void	runtime·free(void *v);
 bool	runtime·addfinalizer(void*, void(*fn)(void*), uintptr);

コアとなるコードの解説

src/pkg/runtime/alg.c の変更

  • runtime·memhash 関数:

    • hash = M0 ^ *h; : ハッシュ計算の初期値として、定数M0と、引数hが指すハッシュシードのXORを取るように変更されました。これにより、ハッシュ計算の開始段階でランダムなシードが組み込まれることが保証されます。
    • *h = hash; : 最終的なハッシュ結果を*hに格納するように変更されました。以前は(*h ^ hash) * M1という形で既存の*hと計算結果を混ぜていましたが、新しいロジックでは*hは純粋にシードとして機能し、計算されたハッシュ値が直接返されるようになりました。

  • runtime·interhash および runtime·nilinterhash 関数:

    • これらの関数は、インターフェースのハッシュを計算する際に、runtime·ifacehash および runtime·efacehash を呼び出します。
    • 変更前は、これらの関数はインターフェース値のみを渡していましたが、変更後は *h ^ M0 という形でハッシュシードを渡すようになりました。これにより、インターフェースのハッシュ計算もシードに基づいて行われるようになります。

src/pkg/runtime/iface.c の変更

  • ifacehash1 関数:

    • 関数のシグネチャが ifacehash1(void *data, Type *t) から ifacehash1(void *data, Type *t, uintptr h) に変更され、ハッシュシードhを受け取るようになりました。
    • h = 0; の行が削除されました。これにより、ハッシュ計算の初期値が常に外部から渡されたシードhによって決定されるようになり、内部で0に初期化されることがなくなりました。

  • runtime·ifacehash および runtime·efacehash 関数:

    • 関数のシグネチャがそれぞれ runtime·ifacehash(Iface a) から runtime·ifacehash(Iface a, uintptr h)、runtime·efacehash(Eface a) から runtime·efacehash(Eface a, uintptr h) に変更され、ハッシュシードhを受け取るようになりました。
    • if(a.tab == nil) return 0; の部分が if(a.tab == nil) return h; に変更されました。これは、nilインターフェースのハッシュ値が固定の0ではなく、渡されたシードhになることを意味します。これにより、nilインターフェースのハッシュ値も予測不可能になります。
    • ifacehash1 の呼び出しも、新しいシグネチャに合わせて ifacehash1(a.data, a.tab->type) から ifacehash1(a.data, a.tab->type, h) に変更されました。

src/pkg/runtime/runtime.h の変更

  • runtime·ifacehash および runtime·efacehash 関数のプロトタイプ宣言が、新しいシグネチャに合わせて更新されました。これにより、これらの関数がハッシュシードを引数として受け取るようになったことが、ヘッダーファイルで明示されます。

これらの変更は、Goランタイムのハッシュ計算ロジック全体にわたって、ハッシュシードの利用を徹底し、ハッシュテーブルのセキュリティと堅牢性を向上させるためのものです。

関連リンク

参考にした情報源リンク