随机令牌生成 - 发生了假设不太可能发生的冲突

Question

几个月前，我们使用 UUID 生成随机字符串 ID，这些 ID 需要全面唯一。然后我更改了算法，以便在我们的数据库中保存一些数据和索引 space。我测试了几种生成唯一字符串 ID 的方法，我决定使用这个函数：

function generateToken($length) {
    $characters = '0123456789abcdefghijklmnopqrstuvwxyz';
    $max = strlen($characters) - 1;

    $token = '';
    for ($i = 0; $i < $length; $i++) {
        $token .= $characters[mt_rand(0, $max)];
    }

    return $token;
}

我正在使用此函数使用数字和字母生成长度为 20 个字符的 ID，或者您可以说这些 ID 是以 36 为基数的数字。任何 2 个 ID 发生冲突的概率应该是 1/36^20 ，但由于生日悖论，预计在大约 36^10 条记录后会发生碰撞 - 即 3.6 千万亿条记录。然而，就在几个小时前发生了一次冲突，当时数据库中只有 530 万条现有记录。是我运气太差，还是我的 ID 生成函数在随机性方面存在缺陷？我知道 mt_rand() 不是真正随机的，但它足够随机，不是吗？

我会写一个循环来检查生成的 ID 是否是唯一的，如果不是则生成一个新的，但我认为发生冲突的可能性很小，以至于这样的性能成本一个循环是不值得的。我现在将在代码中包含这样一个循环，但如果确实有缺陷，我仍然有兴趣完善 ID 生成功能。

Answer 1

如果您想要保证唯一的 16 字节 ID，那么我会使用加密。 AES 使用 16 字节（128 位）块，只要输入是唯一的，输出也保证是唯一的。

在 ECB 模式下设置 AES（更简单、更快速）并加密数字 0、1、2、3、4 ... 您的输入是唯一的，因此输出也将是唯一的。

加密站点会告诉您 ECB 模式存在安全问题，但这些问题仅在输入不唯一时才存在。对于唯一的 'random' 数字生成，根据您的要求，这些问题不适用，因为您的输入都是唯一的。

Answer 2

mt_rand() 在 PHP 中的实现相当流畅，因此一个版本与下一个版本可能有所不同。但是，以下是 PHP 版本 5 中使用的代码的一些摘录：

php_rand.h:

/* MT Rand */
#define PHP_MT_RAND_MAX ((long) (0x7FFFFFFF)) /* (1<<31) - 1 */ 

#ifdef PHP_WIN32
#define GENERATE_SEED() (((long) (sapi_get_request_time(TSRMLS_C) * GetCurrentProcessId())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))
#else
#define GENERATE_SEED() (((long) (sapi_get_request_time(TSRMLS_C) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))
#endif

PHPAPI void php_srand(long seed TSRMLS_DC);
PHPAPI long php_rand(TSRMLS_D);
PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC);
PHPAPI php_uint32 php_mt_rand(TSRMLS_D);

rand.c:

PHP_FUNCTION(mt_rand)
{
    long min;
    long max;
    long number;
    int  argc = ZEND_NUM_ARGS();

    if (argc != 0) {
        if (zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE) {
            return;
        } else if (max < min) {
            php_error_docref(NULL TSRMLS_CC, E_WARNING, "max(%ld) is smaller than min(%ld)", max, min);
            RETURN_FALSE;
        }
    }

    if (!BG(mt_rand_is_seeded)) {
        php_mt_srand(GENERATE_SEED() TSRMLS_CC);
    }

从上面的最后三行可以看出，mt_rand() 是在第一次调用时自动播种的。但是，php_mt_srand() 函数接受类型为 php_uint32 的参数。 这意味着 mt_rand(). 只有 2³² 种可能的种子状态所以如果你的脚本大约运行 2¹⁶ 次，很可能 mt_rand() 会产生完全相同的随机数序列。

正如 rossum 所建议的，将 AES 加密应用于递增的 128 位值会是一个更好的主意。如果对加密结果进行 base64 编码并丢弃尾随 ==，则生成的字符串将只有 22 个字符长。

附录

我今天下午外出时留下了以下脚本运行：

for i in $(seq 1 100000) ; do
  php -r 'for ($n=0; $n<32; $n++) echo chr(mt_rand(97,122)); echo chr(10);' >>out
done &

正如预期的那样，第一次碰撞发生在大约 2¹⁶ 次迭代之后（远不及 26¹⁶）：

$ sort <out | uniq -d
vnexqclzkaluntglgadgwzjnjfsvqfhp

$ grep -n vnexqclzkaluntglgadgwzjnjfsvqfhp out
34417:vnexqclzkaluntglgadgwzjnjfsvqfhp
52159:vnexqclzkaluntglgadgwzjnjfsvqfhp

随机令牌生成 - 发生了假设不太可能发生的冲突

Random token generation - a supposedly unlikely collision occurred

random

token

uuid

birthday-paradox

php_rand.h:

rand.c:

附录