PHPのHashTableにおけるハッシュ衝突攻撃への耐性：Zendハッシュ関数の内部実装と衝突回避の歴史
PHPの心臓部であるZend Engineにおいて、`array`型やオブジェクトのプロパティ管理、シンボルテーブルのすべてを支えているのが HashTable である。我々が日常的に記述する連想配列は、単なる高水準なデータ構造ではない。それは、C言語のメモリ空間上に構築された高度に最適化されたバケットの配列であり、数百万件のデータに対しても $O(1)$ 近傍のアクセス速度を維持するモンスターエンジンだ。
しかし、このHashTableの根幹を揺るがす脆弱性がかつて存在した。それが ハッシュ衝突攻撃（Hash Collision Attack） である。
本稿では、PHP 7以降のZend Engineにおけるハッシュ関数の変遷、メモリ空間でのデータ配置、そして悪意ある攻撃者が引き起こす最悪の計算量劣化（$O(N^2)$ の罠）をどのように防いでいるのか、低レイヤの視点から完全に解剖する。
—
1. Zend EngineにおけるHashTableの物理構造とメモリ空間
PHP 7以前と以降では、HashTableのメモリレイアウトは根本から異なっている。PHP 7で導入された劇的なパフォーマンス改善の大部分は、このHashTableのメモリ効率化（ポインタの非参照化と連続したメモリ配置）によるものだ。
Zend EngineのHashTable（`zend_array` / `HashTable`）は、大別して以下の2つの要素で構成されている。
1. インデックス（ハッシュ値のリスト）： キーのハッシュ値から導出されたバケットのインデックスを保持する連続したメモリ領域。
2. バケット（`Bucket`構造体）： 実際のデータ（キー、値、ハッシュ値）を保持する構造体の配列。
typedef struct _bucket {
zend_ulong h; / ハッシュ値 または 整数インデックス /
zend_string key; / 文字列キー（文字列でない場合は NULL） /
zval val; / 格納される値（Zend Value） /
} Bucket;
現代のPHP（PHP 7, 8系）において、これらのバケットは `Bucket` 配列として一塊のメモリ領域（連続したヒープ領域）に確保される。これにより、CPUキャッシュヒット率（Cache Locality）が劇的に向上し、ポインタを辿るオーバーヘッドが極限まで削減されている。
—
2. ハッシュ衝突攻撃のメカニズムと $O(N^2)$ の悪夢
連想配列への書き込み（`zend_hash_add` など）や読み込みにおいて、最初に行われるのがキー文字列のハッシュ化である。与えられた文字列キーを特定のアルゴリズムにかけ、整数値（ハッシュ）を生成する。このハッシュ値をインデックスのサイズで割った余り（あるいはビットマスク）をとり、バケットの位置を特定する。
脆弱性の本質
もし、異なる複数の文字列キーがまったく同じハッシュ値（あるいは同じインデックス）を生成するように設計されていたらどうなるか？
これが ハッシュ衝突（Hash Collision） である。
衝突が発生した場合、Zend Engineは「チェーニング法（Collision Chain）」を用いて、同じインデックスに属するバケットをlinked list（またはポインタのリンク）で繋いで解決する。
正常な状態であれば、チェインの長さは高々1〜2であり、探索コストは $O(1)$ である。しかし、攻撃者が意図的に衝突する数万個のキーをリクエスト（POSTデータやクエリパラメータ）に含めて送信した場合、すべてのキーが同一のハッシュバケットに集中する。
1. 1番目の要素の挿入：$O(1)$
2. 2番目の要素の挿入（1番目との衝突チェックとリンク）：$O(1)$
3. $N$ 番目の要素の挿入：既存のすべての要素との比較が必要になり、$O(N)$ となる。
これらを $N$ 回繰り返すため、総計算量は $O(N^2)$ に跳ね上がる。
結果として、わずか数万件のPOSTデータ処理のためにCPU使用率が100%に張り付き、Webサーバー（FPMプロセス）は完全にフリーズする（Denial of Service: DoS攻撃）。これがPHP 5時代を震撼させたハッシュ衝突攻撃のメカニズムである。
—
3. Zendハッシュ関数の進化：DJBX33AからPJW、そしてMurmurHash / CityHash への系譜
この攻撃を防ぐため、PHPコアチームはハッシュ関数の実装をアップデートし続けてきた。
PHP 5時代の暗黒面：DJBX33A
PHP 5で長く使われていたのは、Daniel J. Bernstein氏による `DJBX33A`（times 33）アルゴリズムであった。
// 概念的なDJBX33Aの実装
zend_ulong hash = 5381;
while (c = str++) {
hash = ((hash << 5) + hash) + c; / hash 33 + c /
}
このアルゴリズムは非常に軽量で高速であったが、数学的に容易に衝突する文字列を生成できるという致命的な弱点があった。攻撃者はスクリプトを用いて、簡単に数万個の衝突キーを作成できた。
PHP 7以降の防御策：ランダム化シードと新しいハッシュ戦略
PHP 7以降、Zend Engineはこの問題に対して2つの強力な防衛線を張った。
1. プロセスごとのランダムシード（Hash Seed Randomization）
リクエスト起動時（あるいはプロセス開始時）、Zend Engineはエントロピーソース（`/urandom`等）から取得したランダムな乱数をハッシュ計算のシード（初期値）として組み込む。これにより、攻撃者はあらかじめローカル環境で衝突するキーを計算しても、本番サーバー上ではシードが異なるため攻撃が無効化される。
2. 高速かつ堅牢なハッシュ関数の採用
PHP 7以降のZendハッシュ関数は、単純な乗算・加算ループではなく、より雪崩効果（Avalanche effect：入力の1ビットの変更が出力の全ビットにランダムな影響を与える特性）が高いアルゴリズムへと進化している。内部では、CPUアーキテクチャ（x86_64等）の特性を活かした最適化が施されており、セキュリティと極限のパフォーマンスを両立させている。
—
4. 実践：PHP内部のハッシュ衝突耐性を検証する
以下のコードは、PHPの配列が内部でどのようにキーを扱い、大量のデータに対しても高速性を維持しているかを検証するためのものである。現代のPHPでは、ランダムシードと改善されたハッシュ関数のおかげで、単一のリクエスト内での単純な文字列衝突攻撃は事実無根の脅威へと無力化されている。
/
// 意図的に似たような文字列や連番のキーを大量に生成
$dataSize = 100000;
$hashTable = [];
echo “=== Zend HashTable 負荷テスト開始 (要素数: {$dataSize}) ===\n”;
$startTime = microtime(true);
$startMemory = memory_get_usage();
// 大量のキーを投入
for ($i = 0; $i < $dataSize; $i++) {
// プレフィックスを固定し、ハッシュ衝突を誘発しやすい構造にする
$key = "zend_engine_key_prefix_" . md5($i);
$hashTable[$key] = $i;
}
$endMemory = memory_get_usage();
$endTime = microtime(true);
echo "挿入完了時間: " . number_format(($endTime - $startTime) 1000, 2) . " ms\n";
echo "消費メモリ増分: " . number_format(($endMemory - $startMemory) / 1024 / 1024, 2) . " MB\n";
// ランダムアクセス性能の測定
$lookupStartTime = microtime(true);
for ($i = 0; $i < 10000; $i++) {
$targetKey = "zend_engine_key_prefix_" . md5(random_int(0, $dataSize - 1));
$val = $hashTable[$targetKey] ?? null;
}
$lookupEndTime = microtime(true);
echo "1万回のランダムキー検索時間: " . number_format(($lookupEndTime - $lookupStartTime) 1000, 2) . " ms\n";
echo "=== テスト終了 ===\n";
実行結果から読み解く挙動
このスクリプトを現代のPHP（PHP 8.1 / 8.2以降）で実行した場合、10万件の要素挿入およびランダムアクセスは、驚異的な速度（数十ミリ秒オーダー）で完了する。
仮に古いPHP 5系や、シードのランダム化が無効な環境であれば、$O(N^2)$ の劣化により著しい処理遅延が発生するが、現代のZend Engineはハッシュチェインが深くなりすぎた場合の自動リサイズや、衝突に強いハッシュ関数の組合せにより、アプリケーション層に致命的な影響を与えないよう設計されている。
—
5. Webシステムアーキテクトとしての防衛指針
PHPコアがどれほど堅牢であっても、Webアプリケーションの設計レイヤで油断してはならない。特に以下のポイントをアーキテクチャレベルで担保する必要がある。
1. 入力値のサイズ制限（Max Input Vars / Post Max Size）
`php.ini` における `max_input_vars` は、1リクエストあたりの最大入力変数数を制限する極めて重要なディレクティブである。これをデフォルト（1000）のまま放置するか、無制限に数万へ引き上げることは、ハッシュ衝突攻撃に対するバリアを自ら下げる行為に等しい。大規模なJSONペイロードを受け取るAPIであっても、リクエストボディのバイト数制限（`nginx` の `client_max_body_size` や PHPの `post_max_size`）を厳格に設けるべきである。
2. OPcacheとJITによるメモリ空間の保護
OPcacheプリローディング（`opcache.preload`）を使用する場合、スクリプトの関数やクラス定義のシンボルテーブルはマスタープロセス側で事前にHashTableとしてメモリ上に構築され、子プロセス（FPMワーカー）間で共有（Copy-on-Write）される。この際、ハッシュシードはマスタープロセスの起動時に一度だけ生成されるため、複数リクエスト間でハッシュ計算の挙動が予測されない仕組みが維持される。
—
結び
PHPの `array` は「何でも入る魔法の箱」として語られがちだが、その実態は、C言語のメモリ管理とアルゴリズムの粋を集めた精緻なハッシュテーブルである。
歴史的な脆弱性や攻撃手法の変遷を知ることは、単なるセキュリティ対策に留まらず、Zend VMのメモリ構造やCPUキャッシュの挙動を深く理解するための最短経路である。
低レイヤの仕様を掌握した者だけが、真にスケーラブルで堅牢なWebシステムを設計できる。PHPコアの鼓動を感じながら、さらなる高みを目指せ。