[PR]

Category:
Date:2024年04月19日

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

PHPのハッシュ衝突

Category:未選択
Date:2012年01月08日

http://koto.github.com/blog-kotowicz-net-examples/hashcollision/kill.html
の検証コードによると

EzEzEzEzEzEzEzEz
EzEzEzEzEzEzEzFY
EzEzEzEzEzEzEzG8

などが内部的なハッシュテーブルで、ハッシュ値が一致してしまうらしい。 PHPのコードの中でどれが該当するハッシュ関数なのだろうと思って調べてみたらzend_inline_hash_funcという関数がそれみたい。

	register unsigned long 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;
	}
	return hash;

たしかに

int main() {
	const char *str1 = "EzEzEzEzEzEzEzEz";
	const char *str2 = "EzEzEzEzEzEzEzFY";
	const char *str3 = "EzEzEzEzEzEzEzG8";

	unsigned long hash1 = zend_inline_hash_func(str1, strlen(str1));
	unsigned long hash2 = zend_inline_hash_func(str2, strlen(str2));
	unsigned long hash3 = zend_inline_hash_func(str3, strlen(str3));

	printf("str1=%s, hash1=%d\n", str1, hash1);
	printf("str2=%s, hash2=%d\n", str2, hash2);
	printf("str3=%s, hash3=%d\n", str3, hash3);
	return 0;
}

こんな感じで確かめてみると、

str1=EzEzEzEzEzEzEzEz, hash1=74150653
str2=EzEzEzEzEzEzEzFY, hash2=74150653
str3=EzEzEzEzEzEzEzG8, hash3=74150653

と、ハッシュの値が一致する結果になった。

[0回]