PHP カーネルの探索: ハッシュ テーブル衝突攻撃の原理、kernel_PHP チュートリアル

PHP カーネルの探索: ハッシュ テーブル衝突攻撃の原理、カーネル

以下では、PHP カーネルの探索: ハッシュ テーブル衝突攻撃の原理を写真とテキストで説明します。

最近DOS攻撃としてのHashtable衝突の話題が絶えず取り上げられており、様々な言語が影響を受けています。この記事では、PHP カーネルのソース コードを組み合わせて、この攻撃の原理と実装について説明します。

ハッシュテーブル衝突攻撃の基本原理

ハッシュテーブルは非常に検索効率の高いデータ構造であり、多くの言語が内部的にハッシュテーブルを実装しています。 PHP のハッシュ テーブルは非常に重要なデータ構造です。配列データ型を表すために使用されるだけでなく、Zend 仮想マシン内にコンテキスト情報を保存するためにも使用されます (実行コンテキストの変数と関数はすべて、ハッシュテーブル構造）。

理想的には、ハッシュ テーブルの挿入と検索操作の時間計算量は O(1) です。どのデータ項目も、ハッシュ テーブルの長さに関係なく、時間内にハッシュ値 (キー) を計算し、バケット (用語) を見つけることができます。バケットは、一定時間内のハッシュ テーブル内の位置を指します。もちろん、これは理想的な状況です。ハッシュ テーブルの長さには制限があるため、異なるデータ項目が同じハッシュ値を持つ状況が存在する必要があります。このとき、異なるデータ項目が同じバケットに割り当てられます。衝突（衝突）といいます。ハッシュ テーブルの実装では、衝突の問題を解決する必要があります。衝突を解決するには、一般に 2 つのアイデアがあります。1 つは、データが衝突した場合に、線形検出などの特定の原則に従って衝突したデータを他のバケットに割り当てることです。次に、このバケットの後のバケットを順番に検索し、最初の未使用のバケットに入れます。2 番目の戦略は、各バケットが 1 つのデータ項目のみを保持できる場所ではなく、複数のデータを保持できる場所であるということです。構造 (リンク リストや赤黒ツリーなど) を使用すると、すべての衝突データは何らかのデータ構造の形式で編成されます。

どの衝突解決戦略が使用されるかに関係なく、挿入および検索操作の時間計算量はもはや O(1) ではありません。例として検索を考えます。キーでバケットを検索して終了することはできません。元のキー (つまり、ハッシュ前のキー) が等しいかどうかも比較する必要があります。そうでない場合は、挿入と同じアルゴリズムを使用する必要があります。一致する値または確認データがハッシュ テーブルに存在しないまで検索します。

PHP は衝突データを保存するために単一リンク リストを使用するため、実際には、PHP ハッシュ テーブルの平均検索複雑さは O(L) です。ここで、L はバケット リンク リストの平均長で、最悪の複雑さは O(N; )、この すべてのデータが衝突すると、ハッシュ テーブルは単一リンク リストに縮退します。次の図は、PHP の通常のハッシュ テーブルと縮退ハッシュ テーブルの概念図です。

ハッシュテーブル衝突攻撃は、すべてのデータが衝突するようにデータを注意深く構築し、ハッシュテーブルを人為的に縮退した単一リンクリストに変えることです。このとき、ハッシュテーブルに対するさまざまな操作の時間が1桁増加します。大量の CPU リソースが使用されると、システムがリクエストに迅速に応答できなくなり、サービス拒否攻撃 (DoS) の目的が達成されます。

ご覧のとおり、ハッシュ衝突攻撃を実行する前提は、ハッシュ アルゴリズムが特に衝突を見つけやすいということです。幸いにも (または残念ながら)、ほとんどのプログラミング言語では問題になりません。ハッシュ アルゴリズムは非常にシンプルなので (これは効率性を考慮したものです)、攻撃データを簡単に構築できます。次のセクションでは、Zend 関連のカーネル コードを分析して、ハッシュ テーブルの衝突を攻撃し、PHP を攻撃する方法を見つけます。
Zend ハッシュ テーブルの内部実装データ構造
PHP はバケットを表すために Backet と呼ばれる構造を使用し、同じハッシュ値を持つすべてのバケットは単一リンク リストに編成されます。ハッシュ テーブルは HashTable 構造によって表されます。関連するソース コードは zend/Zend_hash.h にあります:

リーリー

フィールド名はその目的を明確に示しているため、これ以上の説明は不要です。次のフィールドに注目してください: Bucket の "h" は元のキーを格納するために使用されます。HashTable の nTableMask はマスクであり、通常は nTableSize - 1 に設定されます。これはハッシュ アルゴリズムについては後で説明するときに詳しく説明します。 ; arBuckets はポインターの配列を指します。各要素はバケット リストの先頭へのポインターです。
ハッシュアルゴリズム
PHP ハッシュ テーブルの最小容量は 8 (2^3)、最大容量は 0×80000000 (2^31) で、2 の整数乗に丸められます (つまり、長さは自動的に整数に拡張されます)。 2 の累乗 (13 など)。要素のハッシュ テーブルの長さは 16、要素 100 個のハッシュ テーブルの長さは 128)。 nTableMask は、ハッシュ テーブルの長さ (丸め後) から 1 を引いた値に初期化されます。具体的なコードは zend/Zend_hash.c の _zend_hash_init 関数にあります。ここでは、この記事に関連する部分を抜粋し、いくつかのコメントを追加します。

リーリー

2 の整数乗に丸める PHP の方法は非常に賢く、覚えて必要なときに使用できることは言及する価値があります。

Zend HashTable のハッシュ アルゴリズムは非常にシンプルです:

コードをコピーします コードは次のとおりです:
ハッシュ(キー)=キー&nテーブルマスク

つまり、データの元のキーと HashTable の nTableMask の間でビットごとの AND を実行するだけです。

元のキーが文字列の場合は、まず Times33 アルゴリズムを使用して文字列を整数に変換し、次に nTableMask とビット単位の AND を実行します。

复制代码 代码如下:
hash(strkey)=time33(strkey)&nTableMask

下面是Zend源码中查找哈希表的代码：

ZEND_API int zend_hash_index_find(constHashTable *ht, ulong h, void **pData)
{
 uint nIndex;
 Bucket *p;
 IS_CONSISTENT(ht);
 nIndex = h & ht->nTableMask;
 p = ht->arBuckets[nIndex];
 while(p != NULL) {
 if((p->h == h) && (p->nKeyLength == 0)) {
  *pData = p->pData;
  returnSUCCESS;
 }
 p = p->pNext;
 }
 returnFAILURE;
}
ZEND_API int zend_hash_find(constHashTable *ht, constchar *arKey, uint nKeyLength, void **pData)
{
 ulong h;
 uint nIndex;
 Bucket *p;
 IS_CONSISTENT(ht);
 h = zend_inline_hash_func(arKey, nKeyLength);
 nIndex = h & ht->nTableMask;
 p = ht->arBuckets[nIndex];
 while(p != NULL) {
 if((p->h == h) && (p->nKeyLength == nKeyLength)) {
  if(!memcmp(p->arKey, arKey, nKeyLength)) {
  *pData = p->pData;
  returnSUCCESS;
  }
 }
 p = p->pNext;
 }
 returnFAILURE;
}

其中zend_hash_index_find用于查找整数key的情况，zend_hash_find用于查找字符串key。逻辑基本一致，只是字符串key会通过zend_inline_hash_func转为整数key，zend_inline_hash_func封装了times33算法，具体代码就不贴出了。
攻击 基本攻击
知道了PHP内部哈希表的算法，就可以利用其原理构造用于攻击的数据。一种最简单的方法是利用掩码规律制造碰撞。上文提到Zend HashTable的长度nTableSize会被圆整为2的整数次幂，假设我们构造一个2^16的哈希表，则nTableSize的二进制表示为：1 0000 0000 0000 0000，而nTableMask = nTableSize - 1为：0 1111 1111 1111 1111。接下来，可以以0为初始值，以2^16为步长，制造足够多的数据，可以得到如下推测：

0000 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0001 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0010 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0011 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0100 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

……

概况来说只要保证后16位均为0，则与掩码位于后得到的哈希值全部碰撞在位置0。

下面是利用这个原理写的一段攻击代码：

<&#63;php
$size= pow(2, 16);
$startTime= microtime(true);
$array= array();
for($key= 0, $maxKey= ($size- 1) * $size; $key<= $maxKey; $key+= $size) {
 $array[$key] = 0;
}
$endTime= microtime(true);
echo $endTime- $startTime, " seconds";

这段代码在我的VPS上(单CPU，512M内存)上用了近88秒才完成，并且在此期间CPU资源几乎被用尽：

而普通的同样大小的哈希表插入仅用时0.036秒：

<&#63;php
$size= pow(2, 16);
$startTime= microtime(true);
$array= array();
for($key= 0, $maxKey= ($size- 1) * $size; $key<= $size; $key+= 1) {
 $array[$key] = 0;
}
$endTime= microtime(true);
echo $endTime- $startTime, " seconds";

可以证明第二段代码插入N个元素的时间在O(N)水平，而第一段攻击代码则需O(N^2)的时间去插入N个元素。

POST攻击

当然，一般情况下很难遇到攻击者可以直接修改PHP代码的情况，但是攻击者仍可以通过一些方法间接构造哈希表来进行攻击。例如PHP会将接收到的HTTP POST请求中的数据构造为$_POST，而这是一个Array，内部就是通过Zend HashTable表示，因此攻击者只要构造一个含有大量碰撞key的post请求，就可以达到攻击的目的。具体做法不再演示。

防护 POST攻击的防护

针对POST方式的哈希碰撞攻击，目前PHP的防护措施是控制POST数据的数量。在>=PHP5.3.9的版本中增加了一个配置项max_input_vars，用于标识一次http请求最大接收的参数个数，默认为1000。因此PHP5.3.x的用户可以通过升级至5.3.9来避免哈希碰撞攻击。5.2.x的用户可以使用这个patch： http://www.laruence.com/2011/12/30/2440.html 。

另外的防护方法是在Web服务器层面进行处理，例如限制http请求body的大小和参数的数量等，这个是现在用的最多的临时处理方案。具体做法与不同Web服务器相关，不再详述。

其它防护

上面的防护方法只是限制POST数据的数量，而不能彻底解决这个问题。例如，如果某个POST字段是一个json数据类型，会被PHP json_decode ，那么只要构造一个超大的json攻击数据照样可以达到攻击目的。理论上，只要PHP代码中某处构造Array的数据依赖于外部输入，则都可能造成这个问题，因此彻底的解决方案要从Zend底层HashTable的实现动手。一般来说有两种方式，一是限制每个桶链表的最长长度；二是使用其它数据结构如 红黑树 取代链表组织碰撞哈希(并不解决哈希碰撞，只是减轻攻击影响，将N个数据的操作时间从O(N^2)降至O(NlogN)，代价是普通情况下接近O(1)的操作均变为O(logN))。

目前使用最多的仍然是POST数据攻击，因此建议生产环境的PHP均进行升级或打补丁。至于从数据结构层面修复这个问题，目前还没有任何方面的消息。

以上所述就是本文的全部内容，希望大家喜欢。

http://www.bkjia.com/PHPjc/1041337.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/1041337.html技術記事 PHP カーネルの探索: ハッシュ テーブル衝突攻撃の原理 以下のカーネルでは、PHP カーネルの探索: ハッシュ テーブル衝突攻撃の原理を画像とテキストで示します。 最近のハッシュ テーブル衝突攻撃 (...

)