PHP哈希表碰撞攻击

typedef struct bucket {
        ulong h;                                                /* Used for numeric indexing */
        uint nKeyLength;
        void *pData;
        void *pDataPtr;
        struct bucket *pListNext;
        struct bucket *pListLast;
        struct bucket *pNext;
        struct bucket *pLast;
        const char *arKey;
} Bucket;

typedef struct _hashtable {
        uint nTableSize;
        uint nTableMask;
        uint nNumOfElements;
        ulong nNextFreeElement;
        Bucket *pInternalPointer;       /* Used for element traversal */
        Bucket *pListHead;
        Bucket *pListTail;
        Bucket **arBuckets;
        dtor_func_t pDestructor;
        zend_bool persistent;
        unsigned char nApplyCount;
        zend_bool bApplyProtection;
#if ZEND_DEBUG
        int inconsistent;
#endif
} HashTable;

/*
 * DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
 *
 * This is Daniel J. Bernstein‘s popular `times 33‘ hash function as
 * posted by him years ago on comp.lang.c. It basically uses a function
 * like ``hash(i) = hash(i-1) * 33 + str[i]‘‘. This is one of the best
 * known hash functions for strings. Because it is both computed very
 * fast and distributes very well.
 *
 * The magic of number 33, i.e. why it works better than many other
 * constants, prime or not, has never been adequately explained by
 * anyone. So I try an explanation: if one experimentally tests all
 * multipliers between 1 and 256 (as RSE did now) one detects that even
 * numbers are not useable at all. The remaining 128 odd numbers
 * (except for the number 1) work more or less all equally well. They
 * all distribute in an acceptable way and this way fill a hash table
 * with an average percent of approx. 86%. 
 *
 * If one compares the Chi^2 values of the variants, the number 33 not
 * even has the best value. But the number 33 and a few other equally
 * good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
 * advantage to the remaining numbers in the large set of possible
* multipliers: their multiply operation can be replaced by a faster
 * operation based on just one shift plus either a single addition
 * or subtraction operation. And because a hash function has to both
 * distribute good _and_ has to be very fast to compute, those few
 * numbers should be preferred and seems to be the reason why Daniel J.
 * Bernstein also preferred it.
 *
 *
 *                  -- Ralf S. Engelschall <[email protected]>
 */

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
        register ulong hash = 5381;

        /* variant with the hash unrolled eight times */
        for (; nKeyLength >= 8; nKeyLength -= 8) {
                hash = ((hash << 5) + hash) + *arKey++;
                hash = ((hash << 5) + hash) + *arKey++;
                hash = ((hash << 5) + hash) + *arKey++;
                hash = ((hash << 5) + hash) + *arKey++;
                hash = ((hash << 5) + hash) + *arKey++;
                hash = ((hash << 5) + hash) + *arKey++;
                hash = ((hash << 5) + hash) + *arKey++;
                hash = ((hash << 5) + hash) + *arKey++;
        }
        switch (nKeyLength) {
                case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
                case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
                case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
                case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
                case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
                case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
                case 1: hash = ((hash << 5) + hash) + *arKey++; break;
                case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
  }
        return hash;
}

<?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‘, "\n";

/********************************************************************************************************/

$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";