Прогнозирование вывода PHP rand ()

Я читал в многочисленных источниках, что вывод PHP rand () предсказуем как PRNG, и я в основном принимаю это как факт просто потому, что видел его во многих местах.

Я заинтересован в проверке концепции: как бы я мог предсказать вывод rand ()? Прочитав эту статью, я понимаю, что случайное число - это число, возвращаемое из списка, начинающегося с указателя (начального числа), - но я не могу представить, насколько это предсказуемо.

Может ли кто-нибудь разумно выяснить, какой случайный # был сгенерирован с помощью rand () в данный момент времени в течение нескольких тысяч предположений? или даже 10000 догадок? Как?

Это происходит потому, что я увидел библиотеку аутентификации, которая использует rand () для создания токена для пользователей, которые потеряли пароли, и я предположил, что это потенциальная дыра в безопасности. С тех пор я заменил метод хэшированием смеси openssl_random_pseudo_bytes(), оригинального хэшированного пароля и микротайма. После этого я понял, что если бы я смотрел снаружи, я бы не знал, как угадать токен, даже зная, что это md5 из rand ().

Способность угадать следующее значение randзависит от способности определять, что srandвызывалось. В частности, посев srandс заданным числом приводит к предсказуемому результату ! Из интерактивной подсказки PHP:

[charles@charles-workstation ~]$ php -a
Interactive shell

php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > 

Это не просто случайность. Большинство версий PHP ^* на большинстве платформ ^** будут генерировать последовательность 97, 97, 39, 77, 93, когда srandс 1024.

Чтобы было ясно, это не проблема с PHP, это проблема с его реализацией rand. Та же проблема возникает в других языках, которые используют ту же (или похожую) реализацию, включая Perl.

Хитрость в том, что любая здравомыслящая версия PHP будет предварительно заполнена srand«неизвестным» значением. О, но это не совсем неизвестно. От ext/standard/php_rand.h:

#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

Итак, это некоторая математика с time(), PID и результат php_combined_lcg, который определен в ext/standard/lcg.c. Я не собираюсь заходить сюда, так как мои глаза застеклены, и я решил прекратить охоту.

Немного Googling показывает, что другие области PHP не обладают лучшими свойствами генерации случайности , и призывает php_combined_lcgвыделиться здесь, особенно этот фрагмент анализа:

Эта функция ( gettimeofday) не только возвращает нам точную временную метку сервера на серебряном блюде, она также добавляет вывод LCG, если мы запрашиваем «больше энтропии» (из PHP uniqid).

Да, этоuniqid . Кажется, что значение php_combined_lcg- это то, что мы видим, когда смотрим на полученные шестнадцатеричные цифры после вызова uniqidсо вторым аргументом, установленным в истинное значение.

Теперь, где мы были?

О да. srand,

Итак, если код, из которого вы пытаетесь предсказать случайные значения , не вызывает srand, вам нужно будет определить значение php_combined_lcg, которое вы можете получить (косвенно?) Через вызов uniqid. С этим значением в руке, это возможно , чтобы перебор остальных значений - time(), то PID и некоторые математики. Связанная проблема безопасности связана с прерыванием сеансов, но здесь будет работать та же техника. Опять же из статьи:

Вот краткое описание шагов атаки, описанных выше:

• дождитесь перезагрузки сервера
• получить уникальное значение
• грубая сила RNG семян из этого
• опросить онлайн статус, чтобы дождаться появления цели
• чередовать опросы состояния с уникальными опросами, чтобы отслеживать текущее время сервера и значение ГСЧ
• идентификатор сеанса перебора против сервера с использованием времени и интервала значений ГСЧ, установленных при опросе

Просто замените этот последний шаг, как требуется.

(Об этой проблеме безопасности сообщалось в более ранней версии PHP (5.3.2), чем у нас в настоящее время (5.3.6), поэтому возможно, что поведение uniqidи / или php_combined_lcgизменилось, поэтому этот конкретный метод может больше не работать). YMMV.)

С другой стороны, если код, который вы пытаетесь создать, вызывает srandвручную , тогда, если они не используют что-то во много раз лучше, чем результат php_combined_lcg, вам, вероятно, будет гораздо проще угадать значение и заполнить ваш локальный генератор с нужным номером. Большинство людей, которые будут звонить вручную, srandтакже не поймут, насколько это ужасно, и поэтому вряд ли будут использовать лучшие значения.

Стоит отметить, что mt_randтакже страдает от этой же проблемы. Посев mt_srandс известным значением также даст предсказуемые результаты. Опираясь на свою энтропию openssl_random_pseudo_bytes, вероятно, безопаснее.

tl; dr: для достижения наилучших результатов не заполняйте генератор случайных чисел в PHP, и, ради бога, не выставляйте uniqidпользователям. Выполнение одного или обоих из них может сделать ваши случайные числа более предсказуемыми.

Обновление для PHP 7:

PHP 7.0 вводит random_bytesи в random_intкачестве основных функций. Они используют реализацию CSPRNG базовой системы, освобождая их от проблем, с которыми сталкивается генератор случайных чисел. Они практически аналогичны openssl_random_pseudo_bytes, только без необходимости установки расширения. Polyfill доступен для PHP5 .

*: Исправление безопасности Suhosin изменяет поведение randи так mt_rand, что они всегда появляются заново при каждом вызове. Suhosin предоставляется третьей стороной. Некоторые дистрибутивы Linux включают его в свои официальные пакеты PHP по умолчанию, в то время как другие делают это опцией, а другие полностью ее игнорируют.

**: В зависимости от платформы и используемых библиотечных вызовов будут генерироваться последовательности, отличные от задокументированных здесь, но результаты должны быть повторяемыми, если не используется исправление Suhosin.

Чтобы наглядно проиллюстрировать неслучайную rand()функцию, вот изображение, где все пиксели сделаны из «случайных» значений красного, зеленого и синего:

Обычно на изображениях не должно быть рисунков.

Я пробовал вызывать srand()с разными значениями, это не меняет предсказуемость этой функции.

Обратите внимание, что оба они не криптографически безопасны и дают предсказуемые результаты.

вывод PHP rand () предсказуем как его PRNG

Это линейный генератор конгруэнтности . Это означает , что у вас есть функция, которая эффективно: NEW_NUMBER = (A * OLD_NUMBER + B) MOD C. Если вы построите график NEW_NUMBER против OLD_NUMBER, вы начнете видеть диагональные линии. В некоторых примечаниях к документации RAND PHP приведены примеры того, как это сделать.

Это происходит потому, что я увидел библиотеку аутентификации, которая использует rand () для создания токена для пользователей, которые потеряли пароли, и я предположил, что это потенциальная дыра в безопасности.

На Windows-машине максимальное значение RAND составляет 2 ^ 15. Это дает атакующему только 32 768 возможностей для проверки.

Может ли кто-нибудь разумно выяснить, какой случайный # был сгенерирован с помощью rand () в данный момент времени в течение нескольких тысяч предположений? или даже 10000 догадок? Как?

Хотя эта статья не совсем та, которую вы ищете, она показывает, как некоторые исследователи взяли существующую реализацию генератора случайных чисел и использовали ее для заработка на Техасском Холдеме. Есть 52! возможны перемешанные колоды, но реализация использовала 32-битный генератор случайных чисел (который является максимальным числом из mt_getrandmax на машине с Windows), и затравил его временем в миллисекундах с полуночи. Это уменьшило число возможных перетасованных колод с примерно 2 226 до примерно 2 27, что позволило осуществлять поиск в реальном времени и знать, какая колода была сдана.

После этого я понял, что если бы я смотрел снаружи, я бы не знал, как угадать токен, даже зная, что это md5 из rand ().

Я бы порекомендовал использовать что-то в семействе SHA-2, так как федералы считают md5 неработающим. Некоторые люди используют Google для расшифровки хэшей md5, потому что они очень распространены. Просто зашифруйте что-нибудь, а затем добавьте хеш в поиск Google - в основном Google превратился в гигантскую радужную таблицу .

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