PHP 的字串比較

蛤?PHP 字串比較還要特別寫一篇文章嗎?

會開始研究這個問題,主要是因為在 Laravel Fortify 中使用 hash_equals() 這個函式比對字串。

PHP 的字串比對

PHP 開發者會使用 Equal Operator 執行比對作業:

1
2
'Hello' == 'World'; // false
'Hello' == 'Hello'; // true

在大多數情況下,更建議使用 Identical Operator 進行比對:

1
2
3
4
1 == '1'; // true
1 === '1'; // false
'1' == '1'; // true
'1' === '1'; // true

兩個 Operator 的差異在於它們是否會對資料型態自動轉換。為了聚焦主題,本篇文章僅討論 Identical Operator。

實作

註:本文以 PHP 8.1.11 作為其程式碼的研究範本

Zend/zend_operators.h 中定義了 is_identical_function

1
2
3
4
5
ZEND_API zend_result ZEND_FASTCALL is_identical_function(zval *result, zval *op1, zval *op2) /* {{{ */
{
	ZVAL_BOOL(result, zend_is_identical(op1, op2));
	return SUCCESS;
}

其核心為 zend_is_identical(為了簡潔起見我們刪去不是字串比對的部份):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
ZEND_API bool ZEND_FASTCALL zend_is_identical(zval *op1, zval *op2) /* {{{ */
{
	if (Z_TYPE_P(op1) != Z_TYPE_P(op2)) {
		return 0;
	}
	switch (Z_TYPE_P(op1)) {
        // ...
		case IS_STRING:
			return zend_string_equals(Z_STR_P(op1), Z_STR_P(op2));
        // ...
	}
}

Zend/zend_string.h 中定義了 zend_string_equals()

1
2
3
4
static zend_always_inline bool zend_string_equals(zend_string *s1, zend_string *s2)
{
	return s1 == s2 || zend_string_equal_content(s1, s2);
}

並在同一處定義了 zend_string_equal_content() 比對兩者的值是否相等:

1
2
3
4
static zend_always_inline bool zend_string_equal_content(zend_string *s1, zend_string *s2)
{
	return ZSTR_LEN(s1) == ZSTR_LEN(s2) && zend_string_equal_val(s1, s2);
}

對於 zend_string_equal_val() 的實作,如果不考慮 CPU 架構及編譯器的優化,採用的是以下程式:

1
2
3
4
static zend_always_inline bool zend_string_equal_val(zend_string *s1, zend_string *s2)
{
	return !memcmp(ZSTR_VAL(s1), ZSTR_VAL(s2), ZSTR_LEN(s1));
}

註:在 GNUC 且為 i386, x86_64 時會使用組合語言進行優化,這已經超出本篇的討論範圍

hash_equals 字串比對

即便結果是相同的,但在可能會面臨時序攻擊(Timing attack)時,需要使用 hash_equals() 進行字串比對。

這是因為 memcmp 比對的所需時間會取決於字串長度,攻擊者可以利用輸入不同長度的字串進行推斷原始字串的長度,所以在一些敏感的資料中應該使用其它方式進行字串比對(在 FreeBSD 中有 consttime_memequal,但這並非 POSIX 標準的一部份)。

實作

hash_equals 的實作位於 ext/hash/hash.c 中:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
PHP_FUNCTION(hash_equals)
{
	zval *known_zval, *user_zval;
	char *known_str, *user_str;
	int result = 0;
	size_t j;

	if (zend_parse_parameters(ZEND_NUM_ARGS(), "zz", &known_zval, &user_zval) == FAILURE) {
		RETURN_THROWS();
	}

	/* We only allow comparing string to prevent unexpected results. */
	if (Z_TYPE_P(known_zval) != IS_STRING) {
		zend_argument_type_error(1, "must be of type string, %s given", zend_zval_type_name(known_zval));
		RETURN_THROWS();
	}

	if (Z_TYPE_P(user_zval) != IS_STRING) {
		zend_argument_type_error(2, "must be of type string, %s given", zend_zval_type_name(user_zval));
		RETURN_THROWS();
	}

	if (Z_STRLEN_P(known_zval) != Z_STRLEN_P(user_zval)) {
		RETURN_FALSE;
	}

	known_str = Z_STRVAL_P(known_zval);
	user_str = Z_STRVAL_P(user_zval);

	/* This is security sensitive code. Do not optimize this for speed. */
	for (j = 0; j < Z_STRLEN_P(known_zval); j++) {
		result |= known_str[j] ^ user_str[j];
	}

	RETURN_BOOL(0 == result);
}

這個實作中,有三點值得注意:

  • known_zvaluser_zval 的資料型態都必須是 string
    • 轉型的過程中會造成額外的 CPU 時間損耗
  • known_zvaluser_zval 的字串長度必須相等
    • 因為在比對的過程中是以 known_zval 的長度為準,如果此時長度不一會 Memory Leak
  • 因為無論如何都會將每個字元比對完,所以不存在提前退出導致時間差的情況

補充

intel/linux-sgx 中,有針對 consttime_memequal 的實作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <string.h>

int
consttime_memequal(const void *b1, const void *b2, size_t len)
{
	const unsigned char *c1 = b1, *c2 = b2;
	unsigned int res = 0;

	while (len--)
		res |= *c1++ ^ *c2++;

	/*
	 * Map 0 to 1 and [1, 256) to 0 using only constant-time
	 * arithmetic.
	 *
	 * This is not simply `!res' because although many CPUs support
	 * branchless conditional moves and many compilers will take
	 * advantage of them, certain compilers generate branches on
	 * certain CPUs for `!res'.
	 */
	return (1 & ((res - 1) >> 8));
}

其核心與 PHP source code 中並沒有多大差別,但對於是否使用 !res0 == res,Intel 的工程師在註解中給出一個很不錯的解釋。