Генерация случайного токена - предположительно маловероятное столкновение - PullRequest
Новая
       48

Генерация случайного токена - предположительно маловероятное столкновение

0 голосов
/ 09 июня 2018

Пару месяцев назад мы использовали UUID для генерации случайных строковых идентификаторов, которые должны были быть уникальными по всем направлениям.Затем я изменил алгоритм, чтобы сохранить некоторые данные и индексное пространство в нашей базе данных.Я протестировал несколько способов генерации уникальных идентификаторов строк и решил использовать эту функцию: 

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 символов с использованием цифр и букв, или вы можетескажем, эти идентификаторы являются числами в базе 36. Вероятность столкновения любых двух идентификаторов должна составлять 1/36 ^ 20, но из-за парадокса дня рождения можно ожидать, что столкновение произойдет примерно после 36 ^ 10 записей - это 3,6 квадриллионазаписей.Однако всего несколько часов назад произошло столкновение, когда в базе данных было всего 5,3 миллиона существующих записей.Я чрезвычайно неудачник, или моя функция генерирования идентификаторов имеет недостатки в отношении случайности?Я знаю, что mt_rand () на самом деле не случайная, но достаточно случайная, не так ли?

Я бы написал цикл, который проверяет, является ли сгенерированный идентификатор уникальным, и генерирует новый, если оннет, но я думал, что вероятность столкновения была настолько мала, что затраты на производительность такого цикла не стоили того.Теперь я включу такой цикл в код, но я все еще заинтересован в совершенствовании функции генерации идентификатора, если она действительно ошибочна.

Ответы [ 2 ]

0 голосов
/ 09 июня 2018

Реализация mt_rand() в PHP довольно изменчива, поэтому она может отличаться в зависимости от версии.Однако вот некоторые выдержки из кода, используемого в версии 5 PHP:

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 32 возможных состояний, поэтому если ваш скрипт выполняется примерно 2 16 раз, вполне вероятно, что mt_rand() создаст точно такую ​​же последовательность случайных чисел.

Как предполагает Россум, было бы гораздо лучше применить шифрование 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 16 итераций (что далеко не 26 16 ): 

$ sort <out | uniq -d
vnexqclzkaluntglgadgwzjnjfsvqfhp

$ grep -n vnexqclzkaluntglgadgwzjnjfsvqfhp out
34417:vnexqclzkaluntglgadgwzjnjfsvqfhp
52159:vnexqclzkaluntglgadgwzjnjfsvqfhp
0 голосов
/ 09 июня 2018

Если вам нужны гарантированные уникальные 16-байтовые идентификаторы, я бы использовал шифрование.AES использует 16-байтовые (128-битные) блоки и, пока входы уникальны, выходы также гарантированно уникальны.

Настройка AES в режиме ECB (который проще и быстрее) и шифрование чисел 0, 1, 2, 3, 4, ... Ваши входы уникальны, поэтому выходы также будут уникальными.

Криптосайты сообщат вам, что в режиме ECB есть проблемы с безопасностью, но эти проблемы применимы, только если входные данныене уникальный.Для генерации уникальных «случайных» чисел, как вам требуется, эти проблемы не применяются, поскольку все ваши входные данные уникальны.

...