Эта статья – вторая в ряде публикаций, посвященных уязвимостям генераторов псевдослучайных чисел (ГПСЧ).
В последнее время появился целый ряд публикаций, описывающих уязвимости ГПСЧ, начиная от самых основ ([1]) и заканчивая непосредственно уязвимостями в различных языках программирования и реализованных на их основе CMS и другого ПО ([2],[3],[4]).
Эти публикации популярны по той причине, что ГПСЧ – основа многих аспектов безопасности веб-приложений. Псевдослучайные числа/последовательности символов используются для обеспечения безопасности веб-приложений в:
- генерации различных токенов (CSRF, токены сброса пароля и т.д.);
- генерации случайных паролей;
- генерации текста в CAPTCHA;
- генерации идентификаторов сессий.
В прошлой статье мы, опираясь на исследования George Argyros и Aggelos Kiayias ([3]) научились предугадывать случайные числа в PHP на основе PHPSESSID и уменьшать различными способами энтропию псевдослучайных чисел.
Сейчас мы рассмотрим ГПСЧ в веб-приложениях, разработанных на языке Python.
Особенности ГПСЧ языка Python
В Python существует три модуля, предназначенных для генерации случайных/псевдослучайных чисел: random, urandom и _random:
- _random реализует алгоритм Mersenne Twister (MT) ([6],[7]) с небольшими изменениями на языке C;
- urandom использует внешние источники энтропии (криптопровайдер Windows в функции CryptGenRandom) на языке C;
- random является оболочкой для модуля _random на Python, совмещающей обе библиотеки и имеющей две основных функции для генерации псевдослучайных чисел: random() и SystemRandom().
RANDOM()
Первая использует алгоритм MT (модуль _random), однако прежде всего пытается инициализировать его с помощью SEED, взятого из urandom, что превращает ГПСЧ в ГСЧ (генератор случайных чисел). Если вызвать urandom не удается (например, отсутствует /dev/urandom или не удается вызвать нужную функцию из библиотеки advapi32.dll), то в качестве SEED используется int(time.time() * 256) (что, как вы уже знаете, обеспечивает недостаточную энтропию).
SYSTEMRANDOM()
SystemRandom() вызывает модуль urandom, который использует внешние источники для генерации случайных данных.
Изменения в реализации алгоритма MT заключается в том, что вместо одного числа, основанного на одном из 624 чисел из текущего состояния ГПСЧ (state), используются два числа:
random_random()
{
unsigned long a=genrand_int32(self)>>5, b=genrand_int32(self)>>6;
return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
}
Так же, в отличие от PHP, инициализировать генератор можно не только с помощью long-переменной, но и с помощью любой последовательности байт (происходит вызов init_by_array()), что и происходит при импорте модуля random с помощью внешнего источника энтропии (берется 32 байта из urandom), а в случае, когда это не удается, используется time():
if a is None: try:
a = int.from_bytes(_urandom(32), 'big')
except NotImplementedError:
import time
a = int(time.time() * 256)
Защита
Казалось бы, данные изменения, в отличие от PHP, обеспечивают достаточную энтропию генератора даже при вызове random.random(). Но не все так «плохо».
Особенностью фреймворков под Python является то, что в отличие от PHP, Python запускается один раз вместе с веб-сервером, а значит, инициализация состояния по умолчанию происходит один раз при выполнении команды import random или при принудительном вызове random.seed() (это крайне редкий случай для веб-приложений), что позволяет провести атаку на состояния MT по следующему алгоритму:
- находим сценарий, который выводит значение random.random() (например, в Plone этим занимается логер ошибок (файл SiteErrorLog.py), он выводит на страницу "ошибка с номером *** зафиксирована", где отражается случайное число);
- выполняем последовательно серию запросов, где фиксируем случайные числа. Номера запросов: 1,2,199,200,511,625;
- 313-м запросом мы совершаем предугадываемое действие (например, генерацию ссылки на сброс пароля);
- на основе запросов 1,199 мы определяем состояния state_1[1], state_1[2], state_1[397];
- на основе запросов 2,200 – состояния state_1[3], state_1[398];
- на основе запроса 511 – state_2[397];
- на основе запроса 625 – state_3[1].
Точность определения состояний зависит от индекса элемента состояния (i): для i mod 2=0 энтропия составляет 2^6, для i mod 2 = 1 – 2^5.
Далее с помощью запросов 1,2,199,200 можно определить состояния state_1[1], state_1[2], state_1[3], state_1[397], state_1[398], на основе которых генерируются состояния state_2[1] и state_2[2], из которых и получается случайное число запроса №313. Однако, энтропия этого числа составляет 2^24 (16M). Энтропия сокращается с помощью запросов 511 и 625. Эти запросы помогают вычислить состояния state_2[397], state_3[1]. Это уменьшает количество вариантов состояний до 2^8, т.е. существует всего 256 вариантов «случайного» числа, используемого в запросе №313.
Необходимым условием выполнения атаки является то, что никто не вклинится в процессе запросов, тем самым не повлияв на смену состояния ГПСЧ (другими словами, что индексы состояний будут определены правильно). Также необходимо чтобы запрос №1 использовал элементы состояния ГПСЧ с индексами не больше 224, иначе запрос №200 будет использовать другое состояние генератора, что не позволит выполнить ангоритм. Вероятность этого события составляет 36%.
Поэтому дополнительная задача запроса №625 – определить, что все предыдущие запросы действительно производились в нужных состояниях и никто не вклинился в процесс запросов.
В дополнение предлагаем вашему вниманию сценарий, который получает на вход случайные числа 6-ти запросов. На выходе формируются все возможные случайные числа запроса №313.
Практическое применение
Мы проанализировали несколько фреймворков и веб-приложений на языке Python (среди них Plone и Django). К сожалению, (а может быть и к счастью) найти среди них уязвимые не удалось.
Самым вероятным претендентом является Plone, так как в нем есть вывод случайного числа (SiteErrorLog.py) но проблема атаки на него в следующем. Plone работает под Python 2.7.*, который при выводе float в str() обрезает последние 5 цифр, что расширяет количество перебираемых вариантов (и при локальном переборе, и при внешних запросах к серверу) до очень больших чисел.
Python третьей ветки не обрезает float в функции st()r, что делает приложения на нем главными претендентами для проведения атак.
Мы предлагаем вашему вниманию сценарий, который получает на входе 6 случайных чисел (проинициализированных состоянием с нужными индексами, например, из тестового сценария vuln.py), а на выходе генерирует возможные варианты подбираемого случайного числа. Время работы этого сценария на среднестатистическом компьютере – около часа.
Примечание: данный сценарий не учитывает возможную погрешность определения элемента состояния для (i mod 2 = 1), поэтому эффективность снижается с 36% до 18%.
Заключение
Особенности выполнения кода фреймворков на Python (на стороне веб-сервера) позволяют злоумышленнику проводить атаки, невозможные или очень труднореализуемые в языке PHP. Для защиты ГПСЧ необходимо соблюдать простые правила:
- использовать модуль urandom или функцию random.SystemRandom();
- проводить инициализацию с помощью random.seed() перед каждым вызовом random.random() c достаточной энтропией SEED (если модуль urandom недоступен, то используйте, например, значение функции md5(time.time()*(int)salt1+str(salt2)), где salt1 и salt2 инициализируются в процессе установки веб-приложения);
- ограничить вывод случайных чисел в своем веб-приложении (достаточно использовать хеш-функции, типа md5).
Ссылки
[1] http://habrahabr.ru/post/151187/
[2] http://jazzy.id.au/default/2010/09/20/cracking_random_number_generators_part_1.html
[3] http://crypto.di.uoa.gr/CRYPTO.SEC/Randomness_Attacks_files/paper.pdf
[4] http://www.slideshare.net/d0znpp/dcg7812-cryptographyinwebapps-14052863
[5] http://media.blackhat.com/bh-us-10/presentations/Kamkar/BlackHat-USA-2010-Kamkar-How-I-Met-Your-Girlfriend-slides.pdf
[6] http://en.wikipedia.org/wiki/Mersenne_twister
[7] http://jazzy.id.au/default/2010/09/22/cracking_random_number_generators_part_3.html
Автор: Юнусов Тимур.
Автор: YunusovTimur
