Случайные числа. Take Two

^[1]Недавно вышла замечательнейшая работа про атаки на генератор случайных чисел в PHP, однако в ней никаких практических примеров представлено не было. Мы провели собственное исследование данной темы, которое вылилось в создание набора инструментов для реализации подобного рода атак.

Получение сида mt_rand через PHPSESSID

PHPSESSID генерируется следующим образом.
md5( Client IP. timestamp. microseconds1. php_combined_lcg() )

• Client IP известен атакующему
• Timestamp известен (заголовок Date в ответе веб-сервера)
• microseconds1 — значение от 0 до 1000000
• php_combined_lcg() — пример значения: 0.12345678

Для генерирования php_combined_lcg() используются 2 сида:

S1 = timestamp XOR (microseconds2 << 11)
S2 = pid XOR (microseconds3 << 11)

• timestamp тот же
• microseconds2 на 0-3 больше, чем при первом замере (microseconds1)
• pid — process id текущего процесса (0-32768)
• microseconds3 на 1-4 больше microseconds2

Наибольшая энтропия — в microseconds, однако с помощью двух техник энтропию значения microseconds можно в значительной степени снизить.

Синхронизация сервера и клиента

Смысл техники в том, чтобы, последовательно отправляя пары запросов, определить момент, когда в заголовке Date меняется секунда.

HTTP/1.1 200 OK
Date: Wed, 08 Aug 2012 06:05:14 GMT
…
HTTP/1.1 200 OK
Date: Wed, 08 Aug 2012 06:05:15 GMT

Если это произошло, значит между нашими запросами microseconds обнулились. Отправляя запросы с динамическими задержками, можно синхронизировать локальное значение microseconds c серверным значением.

Request Twins

Принцип такой. Отправляем два запроса один за другим: первый на сброс пароля себе, второй — на сброс пароля админа. Разница в microseconds будет минимальна.

Таким образом, брут md5 PHPSESSID заключается в подборе microseconds, дельт последующих замеров microseconds, а также pid. Что касается pid, авторы забыли про такую штуку Apache, как server-status, которая показывает — помимо прочей информации — «пиды» процессов, обслуживающие запросы клиентов, что может очень пригодится.

Для брута был первоначально написан модуль для PasswordsPro, однако при таком подходе невозможно реализовать учет корреляции дельт microseconds, поэтому приходилось брутить полный диапазон. Скорость составила примерно 12 млн сидов в секунду.

Впоследствии была написана специальная программа ^[2].

Скорость — около 16 млн сидов в секунду, расчет сида — менее часа (3,2 Ггц x 4 i5).
Получив pid и значение php_combined_lcg(), можно рассчитать сид для mt_rand, который генерируется следующим образом.

(timestamp x pid) XOR (106 x php_combined_lcg())

Кроме того, php_combined_lcg() используется в качестве дополнительной энтропии для функции uniqid (при вызове со вторым параметром = true).

Таким образом, при использовании веб-приложением стандартных сессий PHP есть возможность предугадывать mt_rand(), rand(), uniqid().

Получение сида mt_rand через вывод одного из случайных чисел

Значение сида для mt_rand() — целое число 2^32. Если имеется вывод случайного числа, есть возможность подобрать сид, что на самом деле вполне реально с помощью rainbow tables, которые позволяют найти сид примерно за 10 минут.

Сценарии генерации таблиц, подбора сида и уже готовые таблицы здесь: http://www.gat3way.eu/poc/mtrt/ ^[3]

Что искать в коде?
Все вызовы mt_rand(), rand(), uniqid(), shuffle(), lcg_value() и т. п. Единственная неуязвимая функция — openssl_random_pseudo_bytes(), но она практически нигде не используется. Основные способы защиты:

• MySQL-функция RAND() — с большой долей вероятности ее также можно предугадать;
• Suhosin patch — по умолчанию не патчит функции mt_srand, srand; защита будет обеспечена, когда Suhosin устанавливается отдельно в качестве расширения;
• /dev/urandom — железный способ.

Арсений Реутов
Тимур Юнусов
Дмитрий Нагибин

Автор: ptsecurity