Случайности неслучайны. Фатальная ошибка рандомизации в PHP

Elect

Еще год назад Стефан Эссер поведал миру о предсказуемости генерации случайных чисел в PHP. Но, как это часто бывает, разработчики, да и программисты, не всегда адекватно реагируют на бюллетени безопасности (кто бы их, вообще, читал, а если и читал, то читал внимательно…). Что это? Лень? Человеческий фактор? Нежелание признавать и исправлять свои ошибки? Как бы то ни было, генератор случайных чисел PHP по-прежнему остается предсказуем.

Для правильного понимания сути уязвимости вспомним, что нам уже должно быть известно из статей Стефана Эссера, M4G'a и Raz0r'a. Материал в статьях, на мой взгляд, представлен подробно, но несколько разбросанно. Ставя один за другим эксперименты и разобравшись в деталях уязвимости, я набросал краткий курс по изучению. Полагаю, это поможет тебе более четко представить суть баги и вникнуть в тонкости процесса.

Немного теории

В PHP для генерации случайных чисел используется не сосед-программист, как в бородатом анекдоте, а две базовых функции на выбор: rand() и mt_rand().

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

Поясним, как это можно использовать, вызвав уязвимость.

Во-первых, энтропия последующего вызова rand (mt_rand) зависит от результата предыдущего вызова функции, именно поэтому алгоритм псевдослучаен. Однако начальный SEED можно задать через функцию с приставкой 's': srand (mt_srand).

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

Во-вторых, начальный SEED зачастую через srand (mt_srand) вообще не задают (по забывчивости или человеческой глупости). А если функция srand (mt_srand) не была вызвана (либо вызвана без параметров), то PHP задает начальный SEED самостоятельно. Проблема в том, что такой SEED не превышает числа 2^32, а это число можно банально перебрать.

Разберемся в особенностях генерации, когда начальный SEED задается PHP самостоятельно ввиду отсутствия вызова srand (mt_srand). Главная особенность rand (srand) заключается в том, что для функций возвращаемый результат различен под *nix и Windows.

Практикуем уязвимость

Результат предыдущего вызова rand() используется в чистом виде как начальный SEED для следующего вызова rand(). По сути:

"$SEED=rand();srand($seed);$SEED=rand();...".

Это очень полезно знать, так как не требуется искать начальный SEED, ведь его можно просто получить через вывод результата rand(), если таковой имеется.
Здесь все предельно просто: имеем вывод rand() - имеем начальный SEED.

Под WINDOWS результат вызова rand() (а значит, и начальный SEED) не превышает число 32767. Милый сердцу баг, – результат можно как два байта перебрать (спасибо Raz0r'у за исследование).

Под *NIX все немного сложнее – максимальное число SEED составляет 2^32.

Отмечу, что для mt_rand (mt_srand) имеет значение версия PHP.

Для PHP 4.x.x<=5.2.0 множество вариантов значений, возвращаемых mt_rand(), составляет 2^31. Именно 31 - так называемый «баг единички»:

"mt_rand(1)=mt_rand(2);mt_rand(3)=mt_rand(4);...".

Максимальный начальный SEED не превышает числа 2^32, но из-за повторяющихся значений количество комбинаций на порядок меньше (2^31). Это на 50% ускоряет скорость брута.

Для PHP >=5.2.1 множество вариантов возвращаемых значений mt_rand() составляет 2^32. Максимальный начальный SEED, как и в предыдущем случае - mt_rand(2^32), но количество комбинаций здесь полное(2^32).

Особенность перекрестного влияния

Функции rand (srand) и mt_rand (mt_srand) никак не влияют друг на друга. То есть, вызов srand() не повлияет на результат mt_rand() и наоборот. Это бывает важно, когда в приложении по какой-либо причине используются оба варианта генератора. Для осуществления атаки требуются следующие основные условия:

1. Мы должны прямо или косвенно иметь вывод rand (srand, mt_rand, mt_srand) для вычисления начального SEED.
2. Сервер должен поддерживать Keep-Alive соединения.
3. PHP должен работать как модуль апача (не cgi и не fastcgi).
4. Адский патч безопасности сухошина (suhoshin) не должен быть установлен.

При выполнении всех условий PHP-процесс, обслуживающий соединение с обоими субдоменами, будет одним и тем же. Это даст зависимость между вызовами функций генераторов.

В бой!

Для начала вспомним, как проводились атаки годичной давности:

1. Веб-приложение может само иметь прямой, либо косвенный вывод результата работы генератора.

Данному случаю соответствует эксплоит под Wordpress посредством восстановления пароля зарегистрированному юзеру, а затем и администратору (milw0rm.com/exploits/6421). Соответственно, из почты юзер узнает токен восстановления пароля, где по самому токену вычисляется начальный SEED.

2. Возможно осуществить кросс-атаку через веб-приложение, расположенное на субдомене данного сервера.

На данном принципе основан эксплоит Raz0r'a к Wordpress'у через PhpBB на субдомене, где PhpBB выводит mt_rand в результатах поиска (raz0r.name/wp-content/uploads/2008/08/wp1.html).

3. Начальный SEED можно получить лобовым брутфорсом либо брутфорсом по предварительно сгенерированной радужной таблице готовых значений вызовов rand (mt_rand).
Как пример, эксплоит Raz0r'a «SMF<=1.1.5 Admin Reset Password Exploit (win32)» для WINDOWS (raz0r.name/articles/magiya-sluchajnyx-chisel-chast-2).

Итак, что общего между этими алгоритмами?

Пункт #3, пожалуй, исключение, ввиду особенности rand() в Windows и брутфорса, присущего, так или иначе, всем представленным алгоритмам. Но первые два основаны на отсутствии вызова srand (mt_srand). Они базируются именно на этом, а по факту – на криптографической уязвимости генератора псевдослучайных чисел в PHP, из-за недостаточно большого начального SEED 2^32(2^31).

Патч на патч, или как не надо делать

Что же сделали создатели PHP, дабы защитить нас? Начиная с PHP 5.2.6, начальный SEED стал много больше – угадать (перебрать) его практически невозможно. Казалось бы, проблема решена. А как насчет предсказуемости? Предсказуемость псевдослучайности от предыдущих вызовов осталась такой же, как и была!

Почему это не показалось разработчикам косяком в реализации псевдослучайности – одному Богу известно. Но факт есть факт - зависимость осталась, и хакеры продолжают пить шампанское. Интересно, почему?

Антидот, или решение проблемы

Атаки на mt_rand() проходят в стиле «угадай начальный SEED и сгенерируй по нему mt_rand()». А если mt_srand() задается изначально, казалось бы - бага нет. Но это не так! Именно благодаря последовательной зависимости (предсказуемости) генерации mt_rand()->mt_rand()->mt_rand()->..., атака становится возможной.

После вызова mt_srand() в атакуемом приложении необходимо в Keep-alive-соединении обратиться к взломанному субдомену на сервере с вызовом «print mt_rand();». Получив значение N-го вызова mt_rand() после установки mt_srand(), остается лишь перебрать локально значения mt_srand(SEED) и восстановить цепочку, пока N-й вызов mt_rand() не будет равен полученному с субдомена.

Найденный SEED будет соответствовать искомому, и по нему мы сгенерируем сам токен (пароль) из (N-1) mt_rand(). Выход на самом деле прост. Все, что требуется от программиста, дабы защитить свое творение, – это повторно вызвать srand (mt_srand) после вызова rand (mt_rand).

Глумимся над движками

Настало время рассмотреть те движки, на которых сам Бог велел эксплуатировать найденную уязвимость.

• Joomla Weak Random Password Reset Token Vulnerability.

Уязвимость joomla<=1.5.6 заключается в 10-ти миллионах комбинаций возможных токенов сброса пароля. Как демону Стефану удалось перебрать 10 млн. вариантов токенов с домашнего DSL-канала за 3 часа - для меня так и останется загадкой. Начиная с версии 1.5.7, разработчики ввели 2^32 (crc32) комбинаций токенов. Однако, переборщик пусть и 10 миллионов токенов, по-моему нереален. Но то, что в последней версии джумлы токен генерируется уязвимым к атаке на mt_rand() через кросприложения\субдомен – это факт.

• Moodle 1.x mt_rand() Admin Reset Password Exploit.

При наличии шелла на субдомене можно восстановить токен сброса пароля, вызвав mt_rand() и посчитав SEED для mt_srand(). После чего сбросить пароль по найденному токену, но пароль уйдет на мыло админа, и мы его не увидим. Да и функция генерации пароля совсем другая - она основана на srand().

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

В версии 1.9.x ветки в алгоритм генерации пароля добавлен режим повышенной безопасности. Так, в простом режиме используется алгоритм «word1+num+word2», где num - число из 0123456789, а word1 и word - слова из словаря. Словарь расположен в lib/wordlist.txt (доступен прямо из Web) и по дефолту содержит 35 слов. Итого, возможно всего лишь 35*10*35=12250 комбинаций независимо от rand() и srand().

Если найти способ обойти блокировку при брутфорсе паролей - можно сбросить и перебрать его.

В режиме повышенной безопасности символы перемешиваются посредством str_shuffle(), которая зависит от srand(). Количество вариантов без учета rand() и srand() громадно - чуть меньше, чем 77^8. Но реальное количество комбинаций ограничено srand().

При эксперименте установлено, что практически нигде нет чистого вызова srand() или mt_srand(). Как ни удивительно, это хорошо.

В случае вызова «mt_srand ((double) microtime() * 1000000);» придется перебирать лишь 1 млн. комбинаций, а не 4 млрд., как при дефолтовом вызове. А значит, и криптостойкость генерации не превышает 1 млн. комбинаций.

• XMB 1.9.x mt_rand() Admin Reset Password Exploit.

И снова баг засел в системе восстановления пароля. При знании пары «Username + E-Mail» генерируется новый пароль и тут же устанавливается. На e-mail отправляется уведомление с самим паролем. Если у нас имеется шелл на поддомене - можно вызвать mt_rand в Keep-alive-соединении и восстановить начальное значение SEED для mt_srand. Подбор SEED при этом занимает считанные секунды.

Победа за хакерами

…и это далеко не весь список. Зайди на google.com/codesearch?q=mt_srand(%5C%20|)+%5C(%20lang:php и экспериментируй сам. Патчат такие баги, как показала годовая практика, - криво, не только веб-программисты, но и сами разработчики PHP. Правят либо авто-SEED, а про предсказуемость забывают (не добавляют внешнюю энтропию вроде md5(microtime()) или MySQL’овый 'select rand()' и т.д.), либо правят предсказуемость и забывают про авто-SEED. В общем, хотели как лучше, а получилось как всегда. Хакеры опять рулят миром и разбитыми PHP-движками.