Компания
313,45
рейтинг
20 августа 2012 в 16:50

Разработка → Случайные числа. Take Two

Недавно вышла замечательнейшая работа про атаки на генератор случайных чисел в 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 млн сидов в секунду.

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



Скорость — около 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/



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

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



Арсений Реутов
Тимур Юнусов
Дмитрий Нагибин
Автор: @ptsecurity
Positive Technologies
рейтинг 313,45

Похожие публикации

Комментарии (40)

  • +2
    Мне интересно знать, насколько такой рандом юзабелен:

    $random = uniqid(mt_rand(), true);
    
    • 0
      Именно mt_rand, а не /dev/urandom.
      • 0
        Через PHPSESSID можно подобрать php_combined_lcg, а от него значения и mt_rand, и uniqid, так что такой рандом уязвим.
        • 0
          То есть даже session_regenerate_id(true) не спасет?
          • +5
            Нет
          • +6
            Да.
            • +8
              В смысле, да, не спасет
  • –1
    Гениально.
  • +4
    А откуда мы узнаем когда и во сколько была создана сессия, идентификатор которой мы подбираем?
    • 0
      Можно просто не послать id сессии в куке, и тогда она будет каждый раз генериться заново
      • 0
        Идентификатор собственной сессии чем-то секретным не является.
        • +1
          Смысл в том, что нужен как раз собственный PHPSESSID, с помощью него мы можем получить сид для mt_rand(), uniqid(), т.е. предугадывать все случайные числа.
          • 0
            Я оригинал почитаю ещё статьи.

            Прямо все все все случайные числа предугадывать, а не результат первого вызова PHP: rand в момент создания сессии?
            • 0
              Числа не случайные, а псевдо случайные, поэтому узнав сид, можно предугадывать все последующие.
    • +1
      Если обратиться к скрипту с session_start() без Cookie PHPSESSID, генерируется новый PHPSESSID, отправляется клиенту в Set-Cookie. php_combined_lcg инициализируется при запуске нового процесса, поэтому задача атакующего — заставить веб-сервер создать несколько свежих процессов, при чем так, чтобы microtime обладал наиболее низкой энтропией (с помощью техник ATS и Request Twins). Создать новые процессы можно путем отправки большого количества Keep-Alive запросов. Т.е. отправляя keep-alive запросы на скрипт c session_start, можно получить PHPSESSID из свежего процесса, в котором атакующий брутит pid, microtime, две дельты. IP и время (заголовок Date), естественно известны.
    • 0
      Тут не подбирается id сессии, он известен, тут описывается уязвимость в функциях типа mt_rand
  • +2
    Ссылка на оригинал: crypto.di.uoa.gr/CRYPTO.SEC/Randomness_Attacks.html
  • 0
    Допустим, Вы занимаетесь подбором сессий, и для этого Вам необходимо сделать N запросов к серверу.
    Как на это отреагирует аппаратная часть защиты, которая ведет мониторинг трафика на наличие аномалий? ( к примеру Cisco IPS 4200)
    • 0
      нет их делать не надо) в том то и вся соль, запросов там будет десятка 2 не более
    • +2
      Сессии мы брутим у себя, требуется отправлять запросы лишь для создания новых процессов. Как правило, требуется всего ~100 keep-alive запросов для Apache+mod_php, чтобы веб-сервер начал создавать новые процессы.
      • +1
        Спасибо, теперь понял. Идея довольно интересная! =)
  • 0
    Тогда вопрос: как сделать ту же uniqid менее угадываемой?
    • 0
      Единственная безопасная функция — openssl_random_pseudo_bytes. uniqid не уязвим, если стоит suhosin extension (не путать с патчем).
  • +1
    Хм, а откуда информация о том, что PHPSESSID это 32x (то есть генерируется именно из md5)?
    Проверил — выдаётся строка из 26 символов вида «vranubpab5ab56aedat6r8jak6», в документации по PHP не сказано про md5(неважночто).
    • +1
      В PHP есть две директивы:
      • session.hash-function — по умолчанию 0 (md5), 1 — sha1
      • session.hash-bits-per-character — преобразовывает байты хэша в удобочитаемый формат, возможные значения '4' (0-9, a-f), '5' (0-9, a-v) и '6' (0-9, a-z, A-Z, "-", ","). У нас реализован только режим '4', так как он наиболее часто используется, но мы скоро добавим поддержку и остальных форматов.
      • 0
        Хмм, то есть vranubpab5ab56aedat6r8jak6 это те же самые байты хеша, но в другой последовательности?
        • 0
          Да, это тот же md5. Функция bin_to_readable.
  • +5
    И вдогонку — что скажете о следующих настройках сервера?
    session.entropy_file = /dev/urandom
    session.entropy_length = 128
    
    • +2
      Да, использование этих директив устраняет уязвимость, но по умолчанию они отключены.
  • +1
    А в чем различия от исследлования Сами 2010 года?

    media.blackhat.com/bh-us-10/whitepapers/Kamkar/BlackHat-USA-2010-Kamkar-How-I-Met-Your-Girlfriend-wp.pdf
    samy.pl/phpwn/

    Я не «обидеть» или «наехать» хочу, если что… просто он(Сами) про это рассказывал давно, и вроде идея та же самая была и софт он показал (практическая реализация), а перечитывать и искать новизну — лень, все таки раз это исследование, то обзор аналогов обязательная часть 8)))

    Спасибо за статью в любом случае!
    • +2
      Да, с этой работой мы разумеется знакомы. Действительно, идея та же, но софт Сами в реальных условиях едва ли применим, так как требует информацию, которую можно получить только локально на атакуемой машине, например pid и вывод функции lcg_value(). Новизна в том, что энтропию microtime можно значительно уменьшить за счет техник ATS и Request Twins, кроме того, в работе Сами не учитывается то, что у атакующего есть возможность заставить веб-сервер создавать новые процессы со свежими сидами для php_combined_lcg.
      Софт Сами можно назвать просто PoC'ом, так как не реализует даже многопоточности, нам же было необходимо готовое решение для внутреннего пользования, что привело к созданию такой программы (есть и pro версия ;))
      • +1
        Спасибо за ответ, теперь вижу лучше =) Второй вопрос, чем отличается PRO версия и как ее достать?
        • +2
          Скоро отправим CFP на Zero Nights :)
  • +1
    Спасибо за хороший инструмент и статью! А можете собрать вариант для ATI карточек под OpenCL? Они быстрее и дешевле Nvidia.

    Есть практические суровые НО, на которые стоит обратить внимание администраторам, прежде чем пытаться решить проблему на стороне каких-то Cisco.
    Эта атака имеет существенное ограничение, про которое не стоит забывать — ей нельзя атаковать реальные веб-проекты. Дело в том, что заголок Date, который необходим в реальной жизни переписывает фронтэндом или балансером. Поэтому мешается. Keep-alive тоже в 50% случаях запрещен просто на балансирующей nginx и приехали. В этих условиях беда-беда, особенно если таймзона аппсервера и балансера разбежались. Это даже если открыт server-status, который в реальной жизни встречается в 5% случаев.

    По статье, все очень грамотно изложено, но причем тут фраза «Принцип такой. Отправляем два запроса один за другим: первый на сброс пароля себе, второй — на сброс пароля админа. Разница в microseconds будет минимальна.» и как это связано с PHPSESSID хоть убейте — не понимаю!

    Также просьба — пишите, пожалуйста, ссылки на исследования, которые легли в основу в тексте, в частности www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/ забыли. Ссылки в комментах искать нереально, а разобраться почему работает тот же keep-alive, просто по атаке, очень трудно.

    Еще раз спасибо за инструмент и статью, вы МОЛОДЦЫ!
    • 0
      А можете собрать вариант для ATI карточек под OpenCL? Они быстрее и дешевле Nvidia.

      OpenCL не планируем, если реализовывать в отдельности под каждую GPU-платформу, скорость будет выше.
      ей нельзя атаковать реальные веб-проекты

      Не надо преувеличивать, согласен, что на некоторых серверах могут возникнуть трудности с keep-alive и Date, но на самом деле все не так плохо.
      и как это связано с PHPSESSID хоть убейте — не понимаю!

      Здесь не упомянули возможность извлечения значения microseconds из токена.

      Ссылки добавим, спасибо за комментарий!
    • +2
      ей нельзя атаковать реальные веб-проекты

      Собственно, проверяли мы на реальных веб-хостингах реальные веб-приложения и показатель успешности демонстрирует то, что реальные веб-проекты на реальных системах с помощью этой методики можно атаковать!
  • 0
    Самая главная сложность — server-status. С этого можно начать и закончить.
    Про Date — вы так атаковали хотя бы один сервер с балансером или фронотэдом? Как?

    Про атаки на сами веб-приложения все-таки не совсем не понятно по статье. Давайте разделять — веб-сервер с пыхом в целом, и там генерация PHPSESSID и отдельно веб-приложения, в частности, с выводом mt_rand значений в HTTP ответ. Тогда с примерами покажите как это связать вместе.
    • 0
      Про Date — вы так атаковали хотя бы один сервер с балансером или фронотэдом?

      Атаки проводились на Virtual hosting-и хостеров, доступ к аккаунтам которых у нас был.
  • 0
    На тему получения pid+microtime от самого аппсервера решал эту задачу и добавил в слайды с Defcon-Russia: oxod.ru/DCG7812-Cryptography-in-webapps.pdf
    Вместе с этим инструментов и хотел бы использовать, но AMD все испортило :(((

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

Самое читаемое Разработка