Безопасность случайных чисел в Python

  • Tutorial
Эта статья – вторая в ряде публикаций, посвященных уязвимостям генераторов псевдослучайных чисел (ГПСЧ).

В последнее время появился целый ряд публикаций, описывающих уязвимости ГПСЧ, начиная от самых основ ([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];
  • на основе запроса 625state_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

Автор: Юнусов Тимур.
Метки:
Positive Technologies 174,28
Компания
Поделиться публикацией
Комментарии 11
  • –17
    random.org and no more problems
  • +7
    Только каким боком здесь питон не понятно. Любой генератор псевдо-случайных чилсел выдает детерминированную последовательность чисел, зависящую только от зерна. Тот факт что, что большинство программеров не удосуживаются «перезасеивать» генератор во время работы программы — это исключительно их проблемы.

    Ну и за использование ГПСЧ для генерации ключей сброса пароля нужно в любом случае бить по рукам. Лучше всего /dev/random ну dev/urandom, но только если критически важно отсутсвие блокировки в случае истощения пула энтропии
    • +4
      Хм. В статье рассмотрены методы атаки, специфичные именно для веб-сервисов на питоне, вот таким боком и.
    • +5
      К слову, в официальной документации к питоньему модулю random (http://docs.python.org/library/random.html) явно написано «Mersenne Twister… is completely unsuitable for cryptographic purposes». В документации к php-шному rand ( php.net/manual/en/function.rand.php ) — нет.
      • 0
        может потому что есть mt_rand?
        • 0
          Т.е. в php есть Mersenne Twister? Ну здорово, но он для криптографии не подходит (о чем в доке к питону написано). В справке к mt_rand упоминания о том, что он не подходит для криптографии, опять нет. Или вы имеете в виду, что rand для криптографии подходит? Так тоже ведь не подходит.
          • 0
            Не, я к тому что для реализации Mersenne Twister в php другая функция, не rand.
            • 0
              Что rand, что mt_rand — обе функции небезопасны и дело даже не в них, а в том, что в PHP сид задается одинаково, причем одинаково плохо и предсказуемо. Общались по этому поводу с разработчиками PHP, однако ничего менять они не собираются, согласились лишь добавить плашку в документации, хотя и той не видно.
              • 0
                там можно перезапустить генератор со своим семенем насколько я помню.

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

      Самое читаемое