Форум АНТИЧАТ - Неслучайные числа

Недавно обнаруженная известным IT Security специалистом Стефаном Эссером уязвимость в интерпретаторе PHP теоретически может затронуть миллионы веб-сайтов, на которых используется PHP<=5.2.5. Баг затрагивает функции генерации псевдослучайных чисел rand() и mt_rand(), которые зачастую используются для создания паролей, сессий, кукисов и других различных конфиденциальных данных пользователя. Я разобрал его advisory по полочкам и постарался донести до тебя суть уязвимости.

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

Итак, что же представляют из себя функции rand() и mt_rand()? Rand() - это просто враппер для библиотеки libc rand(), а mt_rand() - враппер для генератора псевдослучайных чисел Mersenne Twister. Обе функции используют для генерации чисел так называемый seed (семя), которое можно задавать соответственно функциями srand() и mt_srand(). По дефолту же сид представляет собой 32-битный DWORD (2 в 32 степени или 4294967296 комбинаций). Обычно такой длины семени достаточно для обеспечения криптографической стойкости приложения, ибо для брутфорса того же пароля, сгенерированного с помощью одной из этих функций, необходимо знать не только сид, но и сгенерированные на основе его числа. Однако, существует ряд ситуаций, в отношении которых применим брутфорс.

Затравка

В PHP 4 и PHP 5 <= 5.2.0 присутствует следующая недоработка: любой seed, вызываемый mt_srand(), либо присваиваемый автоматически, имеет разрядность всего 31 бит, так как последний бит всегда устанавливается равным одному. Таким образом для брутфорса семени нам нужно перебрать уже 2147483648 комбинаций. Уже лучше, но все-таки для эксплуатации такого бага необходимо потратить довольно большое количество времени.
В последующих версиях PHP эту недоработку залатали, но оставили другую: в PHP 4 и PHP <= 5.2.5. Всякий раз, когда 26 последних бит становятся равными нулю, seed также принудительно становится равным нулю (либо 1, в зависимости от установки принудительных бит системой). Это правило действует для 32-битных систем. На 64-битных системах ситуация получше - сид просто становится 24-битным.

Принудительная генерация seed

Выше я раскрыл одну сторону бага, теперь самое вкусное :) Итак, если ты любишь покопаться в сорцах бесплатных PHP цмсок, то, наверняка, знаешь, что их кодеры очень любят инициализировать генераторы псевдослучайных чисел при помощи функций srand() и mt_srand():

PHP код:


		
			
mt_srand(time());

mt_srand((double) microtime() * 100000);

mt_srand((double) microtime() * 1000000);

mt_srand((double) microtime() * 10000000);

Такая инициализация не является криптоустойчивой, потому что:
1. Функция time() не является случайной. Ее значение будет известно хакеру. Даже если админы намеренно установят локальное время сервера ошибочным, его точное значение всегда будет возвращаться в HTTP-заголовках;
2-4. Первое слагаемое (double) microtime() будет равно 0, либо 1, а второе - соответственно от 100000 до 10000000. И, в итоге, имеем для брутфорса все то же число: от 100000 до 10000000 значений. При 1000000 значений процесс брутфорса сида займет всего несколько секунд!

Keep-alive соединение

Вышеизложенный материал был бы бесполезным, если бы не тот факт, что Keep-alive HTTP соединения всегда обслуживаются одним и тем же процессом на удаленном веб-сервере! Это означает, что seed, сгенерированный единожды на одном домене этого сервера, будет таким же и для другого домена на этом же сервере! То есть, если какой-либо php-скрипт выведет сгенерированные им случайные числа, мы сможем определить по ним сид и далее генерить на основе этого сида остальные случайные числа! Это правило, как ты уже понял, относится не только к одному хосту, но и ко всем хостам на удаленном сервере. Но, нельзя не заметить, что это действует только для PHP, запущенного, как модуль Апача, а для cgi генераторы псевдослучайных чисел всегда будут инициализироваться заново. Тут cgi скорее исключение, чем правило, так что не будем брать его в расчет.
Кстати, здесь Стефан Эссер подсказал один хинт. Если ты хостишься на одном сервере с жертвой, то можешь принудительно запустить свой скрипт на своем хосте с srand(0) или mt_srand(0), сид у жертвы будет, соответственно 0 :)

От теории к практике

Теперь настало время обобщить все сказанное выше. Итак, запусти следующий скрипт:

PHP код:


		
			
<?php

mt_srand(31337);

print mt_rand()."\n";

print mt_rand()."\n";

print mt_rand()."\n";

print mt_rand();

?>

При каждом выводе mt_rand() тебе будут показаны одинаковые числа, так как seed один и тот же. Теперь запусти другой скрипт:

PHP код:


		
			
<?php

print rand()."\n";

print rand();

?>

Допустим, ты получил числа 11834 и 2795. Теперь снова запускай данный код, но теперь в качестве сида укажи первое получившееся число:

PHP код:


		
			
<?php

srand(11834);

print rand()."\n";

print rand();

?>

В итоге ты получишь числа 2795 и 28744. Теперь обрати внимание на предыдущий результат :)
Эту особенность генератора обнаружил raz0r (ссылки на его адвисори смотри в сноске).

Cross Application Attacks

Итак, некоторые веб-приложения сами инициализируют seed, а затем выводят полученные на его основе псевдослучайные числа конечному пользователю. Пример такого приложения - phpBB2. Вот код из search.php:

PHP код:


		
			
mt_srand ((double) microtime() * 1000000);

$search_id = mt_rand();

В данном примере проблема заключается в том, что количество комбинаций составляет всего 1000000, плюс в html-исходнике страницы мы увидим вывод значения $search_id. А, как ты уже понял, зная сгенерированное случайное число, мы, фактически, знаем и seed! Тем более на сравнение всего лишь 1000000 результатов работы генератора с полученным $search_id уйдет совсем немного времени :) Тут простор для действий очень большое. Можно создать rainbow-таблицы со всего лишь 1000000 значений.
Такая ситуация является верной для PHP 5 => 5.2.1. В случае с PHP 4 и PHP 5 <= 5.2.0 ситуация становится еще лучше! Для них количество вариантов сокращается почти в 2 раза, то есть до 2 в 19 степени :) Причину я описал в первых абзацах.
Теперь ты спросишь, почему же в этом примере утечка сгенерированного числа является проблемой безопасности? Вот почему:

Запуск генератора случайных чисел влияет не только на представленный в примере phpBB2, но и на остальные веб-приложения, установленные на этом же сервере;
Последующие псевдослучайные числа, сгенерированные на основе предыдущего seed, являются предсказуемыми;
Остальные приложения на этом же сервере могут создавать пароли, сессии и т.д. на основе полученного ранее seed.

Теперь рассмотрим ситуацию, когда phpBB2 и любимый мной WordPress установлены на одном сервере. На основе полученной выше информации Стефан описывает следующий алгоритм атаки на веб-приложения (Cross Application Attacks):

Запускаем keep-alive соединение к поиску phpBB2 и ищем любое часто встречающееся слово, вроде "a", "the" и т.д;
Если запрос вернул более 30 результатов поиска, то смотрим html-исходник страницы. В ссылке на следующую страницу форум должен вывести случайное число в параметре search_id, запоминаем его;
Запускаем брутфорс по найденном псевдослучайному числу из search_id для определения изначального seed. Для этого raz0r предлагает следующую функцию:

PHP код:

function search_seed($rand_num) { $max = 1000000; for($seed=0;$seed<=$max;$seed++){ mt_srand($seed); $key = mt_rand(); if($key==$rand_num) return $seed; } return false; }
Запускаем mt_srand() с полученным значением seed и отбрасываем первое число - тот самый search_id;
В том же keep-alive соединении отправляем запрос на смену пароля админа блога;
На основе полученного сида генерируем случайное число для активационного ключа смены пароля, который блог должен был выслать на мыло админа;
Снова все в том же keep-alive соединении переходим по сгенерированной эксплойтом активационной ссылке. Это должно привести к смене пароля администратора;
Генерируем пароль той же функцией, с помощью которой получили активационный ключ и заходим в админскую часть WordPress :)

Кстати, если на сервере-жертве стоит PHP 4 или PHP 5 <= 5.2.0, то желательно генерировать псевдослучайные числа на той же версии PHP, то же самое относится и к PHP 5 >= 5.2.1.
Эксплойт, основанный на этом алгоритме, написал все тот же raz0r. Ссылку смотри в сноске.

Снова WordPress

Теперь подойдем к описанной уязвимости с другой стороны и рассмотрим последний эксплойт для WordPress, названный Wordpress 2.6.1 (SQL Column Truncation) Admin Takeover Exploit.
Алгоритм эксплойта основан сразу на двух глобальных уязвимостях: на, собственно, предсказуемости псевдослучайных чисел и на SQL Column Truncation - усечении данных в MySQL.
Теперь сделаю небольшое отступление и расскажу об этом самом пресловутом усечении данных в мускуле.
Итак, уже известный тебе Стефан Эссер опубликовал в своем блоге очередную advisory, посвященную новой уязвимости, связанной с особенностями сравнения строк и автоматического усечения данных в MySQL. Как известно, любой столбец в таблице имеет определенную длину. Допустим, существует поле varchar(60) (как в WordPress<=2.6.1 для логина пользователя). Что будет, если записаит в это поле любое значение, которое превысит обозначенные 60 символов? Все очень просто! Лишние символы отсекутся! В поле останутся лишь первые 60 символов, которые мы попытались туда записать. Теперь далее. Если мы имеем поле в базе данных со значением "admin" и попытаемся сравнить это значение с, например, "admin " (admin и 2 пробела), то мускул успешно проведет сравнение и скажет нам, что эти поля равны :) Данная особенность MySQL работает в дефолтной конфигурации, так что это открывает новый вектор атаки на веб-приложения. Подробнее о данной уязвимости советую прочитать по адресам, указанным в сноске. Но вернемся к нашему эксплойту.
Итак, принцип его работы следующий:
1. Регистрируем нового пользователя с логином admin[55 пробелов]x, далее конечный символ "x" отсекается, и в базе мы получаем пользователя admin с 55 пробелами, что для мускула фактически будет равно просто логину "admin";
2. Запрашиваем линк сброса пароля на свое мыло, получаем уникальный ключ из параметра key, который был сгенерирован функцией mt_rand();
3. Сбрасываем пароль администратора с полученным ключом, в итоге, новый пароль уйдет только на мыло админа;
4. На основе полученного ранее ключа ищем сид для вновь сгенерированного пароля. Причем, тут можно сгенерировать rainbow таблицы для поиска, которые будут весить примерно 4294967296 (строк, возможных значений сида, номер строки=seed) * 20 (количество символов кея для смены пароля) = 85899345920 байт или 80 гигабайт. Для версий PHP 4, PHP 5 <= 5.2.0 и PHP 5 >= 5.2.1 нужно генерировать отдельные таблицы. Также в эксплойте есть возможность искать seed и без применения радужных таблиц. Но займет сей процесс очень долгое время. Делается это следующей функцией:

PHP код:


		
			
    function getseed($resetkey) {

        echo "[-] calculating rand seed for $resetkey (this will take a looong time)";

        $max = pow(2,(32-BUGGY));

        for($x=0;$x<=$max;$x++) {

            $seed = BUGGY ? ($x << 1) + 1 : $x;

            mt_srand($seed);

            $testkey = wp_generate_password(20,false);

            if($testkey==$resetkey) { echo "o\n"; return $seed; }



            if(!($x % 10000)) echo ".";

        }

        echo "\n";

        return false;

    }

Параметр BUGGY есть не что иное, как вышеописанный баг, когда 26 последних бит сида становятся равными нулю, то есть число всех значений для перебора становится равным 2 в 31 степени. Вычисляется бажность генератора так:

PHP код:


		
			
mt_srand(2); $a = mt_rand(); mt_srand(3); $b = mt_rand();

define('BUGGY', $a == $b);

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

Злоключение

Пока что эксплойты на вышеописанных багах не очень распространены. Я думаю это из-за того, что для многих эксплуатация уязвимостей генераторов псевдослучайных чисел может показаться чересчур сложной. На самом деле это не так. Для хакера я посоветовал бы изучить исходники эксплойтов, ссылки на которые есть в сноске, и написать на основе полученной информации свои мегапробивные релизы. А для админов и просто юзеров - обновить свой PHP до последней версии и поставить Suhosin патч от Стефана Эссера. Good luck!

Ссылки по теме

Цитата:

http://www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/ - оригинальное advisory Стефана Эссера на тему mt_rand()
http://www.suspekt.org/2008/08/18/mysql-and-sql-column-truncation-vulnerabilities/ - MySQL and SQL Column Truncation Vulnerabilities
http://milw0rm.com/exploits/6421 - Wordpress 2.6.1 (SQL Column Truncation) Admin Takeover Exploit
http://raz0r.name/wp-content/uploads/2008/08/wp1.html - Wordpress 2.5 <= 2.6.1 through phpBB2 Reset Admin Password Exploit
http://raz0r.name/articles/predskazyvaem-sluchajnye-chisla-v-php/ - исследование raz0r'а на тему предсказуемости случайных чисел в mt_rand()
http://raz0r.name/vulnerabilities/sql-column-truncation-security/ - исследование raz0r'а на тему усечения данных в MySQL
http://raz0r.name/articles/magiya-sluchajnyx-chisel-chast-2/ - исследование raz0r'а на тему предсказуемости случайных чисел в rand()
http://raz0r.name/vulnerabilities/uyazvimosti-v-simple-machines-forum/ - уязвимости SMF на основе предсказуемости случайных чисел
http://www.hardened-php.net/suhosin/index.html - официальная страница проекта Suhosin

UPD Баг с rand() затрагивает только win32 системы
(c) M4g, журнал Хакер, ноябрь 2008