Книга «Безопасность в PHP» (часть 5). Нехватка энтропии для случайных значений

Книга «Безопасность в PHP» (часть 1)
Книга «Безопасность в PHP» (часть 2)
Книга «Безопасность в PHP» (часть 3)
Книга «Безопасность в PHP» (часть 4)

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

1. Для случайного выбора опций из пула или диапазона известных опций.
2. Для генерирования векторов инициализации при шифровании.
3. Для генерирования непредсказуемых токенов или одноразовых значений при авторизации.
4. Для генерирования уникальных идентификаторов, например ID сессий.

Во всех этих случаях имеется характерная уязвимость. Если атакующий угадает или предскажет выходные данные вашего генератора случайных чисел (RNG, Random Number Generator) или генератора псевдослучайных чисел (PRNG, Pseudo-Random Number Generator), то он сможет вычислить токены, соли, одноразовые значения и криптографические векторы инициализации, создаваемые с помощью этого генератора. Поэтому очень важно генерировать высококачественные случайные значения, т. е. те, которые крайне трудно предсказать. Ни в коем случае не допускайте предсказуемости токенов сброса паролей, CSRF-токенов, ключей API, одноразовых значений и токенов авторизации!

В PHP со случайными значениями связаны ещё две потенциальные уязвимости:

1. Раскрытие информации (Information Disclosure).
2. Нехватка энтропии (Insufficient Entropy).

В данном контексте «раскрытие информации» относится к утечке внутреннего состояния генератора псевдослучайных чисел — его начального значения (seed value). Подобные утечки могут сильно облегчить предсказывание будущих выходных данных PRNG.

«Нехватка энтропии» описывает ситуацию, когда вариативность начального внутреннего состояния (seed) PRNG или его выходных данных столь мала, что весь диапазон возможных значений относительно легко перебирается брутфорсом. Не слишком хорошие новости для PHP-программистов.

Мы подробно рассмотрим обе уязвимости с примерами сценариев атак. Но сначала давайте разберёмся, что на самом деле представляет собой случайное значение, когда речь идёт о программировании на PHP.

Что делают случайные значения?

Путаница относительно предназначения случайных величин усугубляется и общим непониманием. Несомненно, вы слышали о разнице между криптографически стойкими случайными значениями и расплывчатыми «уникальными» значениями «для других видов использования». Основное впечатление — используемые в криптографии случайные значения требуют высококачественной случайности (или, точнее, высокой энтропии), а значения для других областей применения могут обойтись меньшей энтропией. Я считаю это впечатление фальшивым и контрпродуктивным. Реальное различие между непредсказуемыми случайными значениями и теми, что нужны для тривиальных задач, лишь в том, что предсказуемость вторых не влечёт за собой вредных последствий. Это вообще исключает криптографию из рассмотрения вопроса. Иными словами, если вы используете случайное значение в нетривиальной задаче, то автоматически должны выбрать гораздо более сильные RNG.

Сила случайных значений определяется затраченной для их генерирования энтропией. Энтропия — это мера неопределённости, выраженная в «битах». Например, если я возьму двоичный бит, его значение может быть 0 или 1. Если атакующий не знает точное значение, то мы имеем энтропию 2 бита (т. е. подбрасывание монеты). Если атакующий знает, что значение всегда равно 1, то мы имеем энтропию 0 бит, поскольку предсказуемость — антоним неопределённости. Также количество бит может находиться в диапазоне от 0 до 2. Например, если 99 % времени двоичный бит равен 1, то энтропия может чуть-чуть превышать 0. Так что чем более неопределённые двоичные биты мы выбираем, тем лучше.

В PHP это можно увидеть более наглядно. Функция mt_rand() генерирует случайные значения, это всегда цифры. Она не выдаёт буквы, специальные символы или иные значения. Это означает, что на каждый байт у атакующего приходится гораздо меньше догадок, т. е. энтропия низкая. Если заменить mt_rand() чтением байтов из Linux-источника /dev/random, то мы получим по-настоящему случайные байты: они генерируются на основе шума, формируемого драйверами системных устройств и прочими источниками. Очевидно, что этот вариант гораздо лучше, потому что обеспечивает значительно больше бит энтропии.

О нежелательности mt_rand() говорит и то, что это генератор не истинно случайных, а псевдослучайных чисел, или, как его ещё называют, детерминированный генератор случайных двоичных последовательностей (Deterministic Random Bit Generator, DRBG). В нём реализован алгоритм под названием «вихрь Мерсенна» (Mersenne Twister), который генерирует числа, распределённые таким образом, чтобы результат получался приближенным к результату работы генератора истинно случайных чисел. mt_rand() использует только одно случайное значение — начальное (seed), на его основе фиксированный алгоритм генерирует псевдослучайные значения.

Взгляните на этот пример, вы можете протестировать его самостоятельно:

mt_srand(1361152757.2);

for ($i=1; $i < 25; $i++) {
    echo mt_rand(), PHP_EOL;
}

Это простой цикл, исполняемый после того, как PHP-функция вихря Мерсенна получила начальное, заранее установленное значение. Оно было получено на выходе функции, приводимой в качестве примера в документации к mt_srand() и использующей текущие секунды и микросекунды. Если выполнить приведённый код, то он выведет на экран 25 псевдослучайных чисел. Они выглядят случайными, никаких совпадений, всё прекрасно. Снова выполним код. Что-нибудь заметили? Именно: выводятся ТЕ ЖЕ САМЫЕ числа. Запустим в третий, четвёртый, пятый раз. В старых версиях PHP результат может быть разным, но это не относится к проблеме, поскольку она характерна для всех современных версий PHP.

Если атакующий получит начальное значение такого PRNG, то он сможет предсказать все выходные данные mt_rand(). Так что защита начального значения — дело первостепенной важности. Если вы его потеряете, то больше не имеете права генерировать случайные значения…

Вы можете сгенерировать начальное значение одним из двух способов:

• вручную, с помощью функции mt_srand(),
• вы проигнорируете mt_srand() и позволите PHP сгенерировать его автоматически.

Второй вариант предпочтительнее, но и сегодня легаси-приложения зачастую наследуют применение mt_srand(), даже после портирования на более современные версии PHP.

Это повышает риск того, что атакующий восстановит начальное значение (атака Seed Recovery Attack), что даст ему достаточно информации для предсказания будущих значений. В результате любое приложение после подобной утечки становится уязвимым для атаки раскрытия информации. Это самая настоящая уязвимость, несмотря на её очевидно пассивную природу. Утечка информации о локальной системе способна помочь атакующему в последующих атаках, что нарушит принцип эшелонированной защиты.

Случайные значения в PHP

В PHP используется три PRNG, и если злоумышленник получит доступ к начальным значениям, применяемым в их алгоритмах, то он сможет предсказывать результаты их работы:

1. Линейный конгруэнтный генератор (Linear Congruential Generator, LCG), lcg_value().
2. Вихрь Мерсенна, mt_rand().
3. Локально поддерживаемая C-функция rand().

Также эти генераторы применяются для внутренних нужд, для функций вроде array_rand() и uniqid(). Это означает, что злоумышленник может предсказывать выходные данные этих и других функций, использующих внутренние PRNG языка PHP, если заполучит все необходимые начальные значения. Также это означает, что не получится улучшить защиту, запутав нападающего с помощью многочисленных обращений к генераторам. Особенно это касается open source приложений. Злоумышленник способен предсказать ВСЕ выходные данные для любого известного ему начального значения.

Чтобы повысить качество генерируемых случайных значений для нетривиальных задач, PHP нужны внешние источники энтропии, предоставляемой операционной системой. В Linux обычно применяют /dev/urandom, можно считывать его напрямую либо обращаться не напрямую, с помощью функций openssl_pseudo_random_bytes() или mcrypt_create_iv(). Обе они могут использовать и криптографически безопасный генератор псевдослучайных чисел (CSPRNG) в Windows, но в PHP в пользовательском пространстве пока нет прямого метода получения данных от этого генератора без расширений, обеспечиваемых этими функциями. Иными словами, убедитесь, что в вашей серверной версии PHP включено расширение OpenSSL или Mcrypt.

/dev/urandom — PRNG, но зачастую он получает новые начальные значения от высокоэнтропийного источника /dev/random. Это делает его неинтересной целью для злоумышленника. Мы стараемся избегать прямого чтения из /dev/random, потому что это блокирующий ресурс. Если он исчерпает энтропию, то все чтения будут заблокированы, пока снова не наберётся достаточно энтропии от системного окружения. Хотя для наиболее важных задач следует использовать именно /dev/random.

Всё это приводит нас к правилу:

Все процессы, подразумевающие применение нетривиальных случайных чисел, ДОЛЖНЫ использовать openssl_pseudo_random_bytes(). В качестве альтернативы вы МОЖЕТЕ попытаться напрямую считывать байты из /dev/urandom. Если ни один вариант не сработал и у вас нет выбора, то вы ДОЛЖНЫ генерировать значение с помощью сильного смешивания данных от нескольких доступных источников случайных или секретных значений.

Базовую реализацию этого правила вы найдёте в эталонной библиотеке SecurityMultiTool. Как обычно, внутренности PHP предпочитают усложнять жизнь программистам вместо прямого включения безопасных решений в ядро PHP.

Хватит теории, теперь давайте посмотрим, как можно атаковать приложение, вооружившись вышеописанным.

Атака на генераторы случайных чисел в PHP

По ряду причин в PHP для решения нетривиальных задач используются PRNG.

Функция openssl_pseudo_random_bytes() была доступна только в PHP 5.3. В Windows она создавала проблемы с блокировкой, пока не вышла версия 5.3.4. Также в PHP 5.3 функция mcrypt_create_iv() в Windows стала поддерживать источник MCRYPT_DEV_URANDOM. До этого в Windows поддерживался только MCRYPT_RAND — по сути, тот же системный PRNG, используемый для внутренних нужд функцией rand(). Как видите, до появления PHP 5.3 было немало пробелов, так что многие легаси-приложения, написанные на предыдущих версиях, могли и не переключиться на более сильные PRNG.

Выбор расширений Openssl и Mcrypt — на ваше усмотрение. Поскольку нельзя положиться на их доступность даже на серверах с PHP 5.3, приложения часто используют PRNG, встроенные в PHP, в качестве запасного варианта для генерирования нетривиальных случайных значений.

Но в обоих случаях мы имеем нетривиальные задачи, которые применяют случайные значения, сгенерированные с помощью PRNG с низкоэнтропийными начальными значениями. Это делает нас уязвимыми к атакам с восстановлением начальных значений. Давайте рассмотрим простой пример.

Представим, что мы нашли в онлайне приложение, использующее следующий код для генерирования токенов, которые применяются в разных задачах по всему приложению:

$token = hash('sha512', mt_rand());

Есть и более сложные средства генерирования токенов, но это неплохой вариант. Здесь используется только один вызов mt_rand(), захешированный с помощью SHA512. На практике, если программист решит, что функции случайных значений в PHP «достаточно случайны», то он наверняка выберет упрощённый подход, пока не прозвучит слово «криптография». Например, к некриптографическим случаям относятся токены доступа, CSRF-токены, одноразовые значения API и токены сброса паролей. Прежде чем продолжить, я подробно распишу всю степень уязвимости этого приложения, чтобы вы лучше понимали, что вообще делает приложения уязвимыми.

Характеристики уязвимого приложения

Это не исчерпывающий список. На практике список характеристик может отличаться!

1. Сервер применяет mod_php, который при использовании KeepAlive позволяет обслуживать несколько запросов одним и тем же PHP-процессом

Это важно потому, что генераторы случайных чисел в PHP получают начальные значения единожды на один процесс. Если мы можем сделать к процессу два запроса и более, то он будет использовать одно и то же начальное значение. Суть атаки заключается в том, чтобы применить раскрытие одного токена для извлечения начального значения, которое нужно для предсказания другого токена, генерируемого на основе ТОГО ЖЕ начального значения (т. е. в том же процессе). Поскольку mod_php идеально подходит для использования нескольких запросов для получения связанных случайных значений, то иногда с помощью всего одного запроса можно извлечь несколько значений, относящихся к mt_rand(). Это делает избыточными любые требования к mod_php. Например, часть энтропии, используемой для генерирования начального значения для mt_rand(), может утечь через ID сессий или выходные значения в том же запросе.

2. Сервер раскрывает CSRF-токены, токены сброса паролей или подтверждения аккаунтов, сгенерированные на основе mt_rand()-токенов

Для извлечения начального значения нам нужно напрямую проверить число, созданное генераторами в PHP. Причём даже неважно, как оно используется. Мы можем извлечь его из любого доступного значения, будь то выходные данные mt_rand(), или хешированный CSRF, или токен подтверждения аккаунта. Подойдут даже косвенные источники, у которых случайное значение определяет иное поведение на выходе, что раскрывает это самое значение. Главное ограничение заключается в том, что оно должно быть из того же процесса, генерирующего второй токен, который мы пытаемся предсказать. А это уязвимость «раскрытие информации». Как мы скоро увидим, утечка выходных данных PRNG может быть крайне опасна. Обратите внимание, что уязвимость не ограничена единственным приложением: вы можете считывать выходные данные PRNG в одном приложении на сервере и применять их для определения выходных данных в другом приложении на том же сервере, если оба они используют один PHP-процесс.

3. Известный слабый алгоритм генерирования токенов

Вы можете вычислить его:

• покопавшись в исходниках open source приложения,
• дав взятку сотруднику с доступом к личному исходному коду,
• найдя бывшего сотрудника, затаившего обиду на бывшего работодателя,
• или просто предположив, какой алгоритм тут может быть.

Некоторые методы генерирования токенов более очевидны, некоторые — более популярны. По-настоящему слабые средства генерирования отличаются использованием одного из генераторов случайных чисел PHP (например, mt_rand()), слабой энтропией (нет других источников неопределённых данных) и/или слабым хешированием (например, MD5 или вообще без хеширования). Рассмотренный выше пример кода как раз имеет признаки слабого метода генерирования. Также я использовал хеширование SHA512, чтобы продемонстрировать, что маскировка — это всегда неудовлетворительное решение. SHA512 — слабое хеширование, поскольку оно быстро вычисляется, т. е. атакующий может с невероятной скоростью брутфорсить входные данные на любых CPU или GPU. И не забывайте, что закон Мура тоже ещё действует, а значит, скорость брутфорса будет расти с каждым новым поколением CPU/GPU. Поэтому пароли должны хешироваться с помощью инструментов, взлом результатов которых требует фиксированного времени вне зависимости от производительности процессоров или закона Мура.

Выполнение атаки

Наша атака достаточно проста. В рамках подключения к PHP-процессу мы проведём быструю сессию и отправим два отдельных HTTP-запроса (запрос А и запрос Б). Сессия будет удерживаться сервером, пока не будет получен второй запрос. Запрос А нацелен на получение какого-нибудь доступного токена вроде CSRF, токена сброса пароля (отправляется атакующему по почте) или чего-то подобного. Не забывайте и о других возможностях вроде встроенной разметки (inline markup), используемых в запросах произвольных ID и т. д. Мы будем мучить исходный токен, пока он нам не выдаст своё начальное значение. Всё это — часть атаки с восстановлением начального значения: когда у начального значения такая маленькая энтропия, что его можно брутфорсить или поискать в заранее вычисленной радужной таблице.

Запрос Б будет решать более интересную задачу. Давайте сделаем запрос на сброс локального администраторского пароля. Это запустит генерирование токена (с помощью случайного числа на базе того же начального значения, которые мы вытаскиваем с помощью запроса А, если оба запроса успешно отправляются на один и тот же PHP-процесс). Этот токен будет храниться в базе данных в ожидании момента, когда администратор воспользуется ссылкой сброса пароля, отправленной ему на почту. Если мы сможем извлечь начальное значение для токена из запроса А, то, зная, как генерируется токен из запроса Б, мы предскажем токен сброса пароля. А значит, сможем перейти по ссылке сброса до того, как администратор прочитает письмо!

Вот последовательность развития событий:

1. С помощью запроса A получаем токен и подвергаем его обратному инжинирингу для вычисления начального значения.
2. С помощью запроса Б получаем токен, сгенерированный на базе того же начального значения. Этот токен хранится в базе данных приложения для будущего сброса пароля.
3. Взламываем хеш SHA512, чтобы достать сгенерированное сервером случайное число.
4. С помощью полученного случайного значения брутфорсим начальное значение, которое было сгенерировано с его помощью.
5. Используем начальное значение для вычисления серии случайных значений, которые, вероятно, могут лежать в основе токена сброса пароля.
6. Используем этот токен(-ы) для сброса пароля администратора.
7. Получаем доступ к администраторскому аккаунту, развлекаемся и получаем выгоду. Ну, как минимум развлекаемся.

Займёмся хакингом...

Пошаговый взлом приложения

Шаг 1. Осуществляем запрос А для извлечения токена

Мы исходим из того, что целевой токен и токен сброса пароля зависят от выходных данных mt_rand(). Поэтому нужно выбрать именно его. В приложении в нашем воображаемом сценарии все токены генерируются одним и тем же способом, так что можно просто извлечь CSRF-токен и сохранить его на будущее.

Шаг 2. Осуществляем запрос Б для получения токена сброса пароля, сгенерированного для администраторского аккаунта

Этот запрос представляет собой простую отправку формы сброса пароля. Токен будет сохранён в базе данных и отправлен пользователю по почте. Нам нужно правильно вычислить этот токен. Если характеристики сервера точны, то запрос Б использует тот же PHP-процесс, что и запрос А. Следовательно, в обоих случаях вызовы mt_rand() будут применять одно и то же начальное значение. Можно даже использовать запрос А для захвата CSRF-токена формы сброса, чтобы включить ввод данных (submission) ради упорядочивания процедуры (исключаем промежуточный round trip).

Шаг 3. Взламываем хеширование SHA512 токена, полученного по запросу А

SHA512 внушает программистам благоговейный трепет: у него крупнейший номер во всём семействе алгоритмов SHA-2. Однако в методе генерирования токенов, выбранном нашей жертвой, есть одна проблема — случайные значения ограничены только цифрами (т. е. степень неопределённости, или энтропия, ничтожна). Если вы проверите выходные данные mt_getrandmax(), то обнаружите, что наибольшее случайное число, которое может сгенерировать mt_rand(), — 2,147 миллиарда с мелочью. Это ограниченное количество возможностей делает SHA512 уязвимым для брутфорса.

Только не верьте мне на слово. Если у вас есть дискретная видеокарта одного из последних поколений, то можно пойти следующим путём. Поскольку мы ищем одиночный хеш, то я решил воспользоваться замечательным инструментом для брутфорса — hashcat-lite. Это одна из самых быстрых версий hashcat, она есть для всех основных операционных систем, включая Windows.

С помощью этого кода сгенерируйте токен:

$rand = mt_rand();
echo "Random Number: ", $rand, PHP_EOL;
$token = hash('sha512', $rand);
echo "Token: ", $token, PHP_EOL;

Этот код воспроизводит токен из запроса А (он содержит нужное нам случайное число и спрятан в хеш SHA512) и прогоняет через hashcat:

./oclHashcat-lite64 -m1700 --pw-min=1 --pw-max=10 -1?d -o ./seed.txt <SHA512 Hash> ?d?d?d?d?d?d?d?d?d?d

Вот что означают все эти опции:

• -m1700: определяет алгоритм хеширования, где 1700 означает SHA512.
• --pw-min=1: определяет минимальную входную длину хешируемого значения.
• --pw-max=10: определяет максимальную входную длину хешируемого значения (10 для mt_rand()).
• -1?d: определяет, что нам нужен кастомный словарь из одних лишь цифр (т. е. 0—9).
• -o ./seed.txt: файл для записи результатов. На экран ничего не выводится, так что не забудьте задать этот параметр!
• ?d?d?d?d?d?d?d?d?d?d: маска, задающая используемый формат (все цифры максимум до 10).

Если всё сработает правильно и ваш GPU не расплавится, Hashcat вычислит захешированное случайное число за пару минут. Да, минут. Ранее я уже объяснял, как работает энтропия. Убедитесь в этом сами. У функции mt_rand() так мало возможностей, что SHA512-хеши всех значений реально вычислить за очень короткое время. Так что бессмысленно было хешировать выходные данные mt_rand().

Шаг 4. Восстанавливаем начальное значение с помощью свежевзломанного случайного числа

Как мы видели выше, на извлечение из SHA512 любого сгенерированного mt_rand() значения требуется всего пара минут. Вооружившись случайным значением, мы можем запустить другой инструмент для брутфорса — php_mt_seed. Эта маленькая утилита берёт выходные данные mt_rand() и после брутфорса вычисляет начальное значение, на основании которого могло быть сгенерировано анализируемое. Скачайте текущую версию, скомпилируйте и запустите. Если появятся проблемы с компиляцией, попробуйте более старую версию (с новыми у меня были проблемы с виртуальными средами).

./php_mt_seed <RANDOM NUMBER>

Это может занять немного больше времени, чем взлом SHA512, поскольку выполняется на CPU. На приличном процессоре утилита найдёт весь возможный диапазон начального значения за несколько минут. Результат — одно или несколько возможных значений (т. е. значений, на основании которых могло быть получено данное случайное число). Повторюсь: мы наблюдаем результат слабой энтропии, только на этот раз в отношении генерирования в PHP начальных значений для функции вихря Мерсенна. Позднее мы рассмотрим, как были сгенерированы эти значения, так что вы увидите, почему можно так быстро выполнять брутфорс.

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

Шаг 5. Генерируем возможные токены сброса пароля администраторского аккаунта

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

function predict($seed) {
    /**
     * Передаём в PRNG начальное значение
     */
    mt_srand($seed);
    /**
     * Пропускаем вызов функции из запроса А
     */
    mt_rand();
    /**
     * Предсказываем и возвращаем сгенерированный в запросе Б токен
     */
    $token = hash('sha512', mt_rand());
    return $token;
}

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

Шаги 6 и 7. Сбрасываем пароль администраторского аккаунта и веселимся!

Теперь нужно собрать URL, содержащий токен, который позволит сбросить администраторский пароль благодаря уязвимости приложения и получить доступ к аккаунту. Возможно, выяснится, что на форуме или в статье можно публиковать нефильтрованный HTML (частое нарушение принципа эшелонированной защиты). Это позволит вам выполнить обширную XSS-атаку на всех остальных пользователей приложения, инфицировав их компьютеры зловредом и средствами мониторинга «человек в браузере» (Man-In-The-Browser). Серьёзно, зачем останавливаться на одном лишь получении доступа? Суть этих, на первый взгляд, пассивных и не слишком опасных уязвимостей заключается в том, чтобы помочь злоумышленнику медленно проникнуть туда, откуда он сможет наконец достичь своей главной цели. Хакинг — это как игра в аркадный файтинг, когда вам нужно быстро нажать нужную комбинацию, чтобы провести серию мощных ударов.

Анализ после атаки

Вышеприведённый сценарий и простота шагов должны ясно продемонстрировать вам опасность mt_rand(). Риски столь очевидны, что теперь мы можем считать любые слабо скрытые выходные значения mt_rand(), доступные нападающему в любой форме, уязвимостью «раскрытие информации».

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

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

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

А теперь всё то же самое

Теперь мы знаем, что использование PRNG, встроенных в PHP, считается уязвимостью нехватки энтропии (т. е. снижение неопределённости облегчает брутфорс). Можно расширить нашу атаку:

$token = hash('sha512', uniqid(mt_rand()));

Уязвимость раскрытия информации делает этот метод генерирования токенов совершенно бесполезным. Чтобы понять причину, давайте внимательнее посмотрим на PHP-функцию uniqid(). Её определение:

На основе текущего времени в микросекундах получает уникальный префикс-идентификатор.

Как вы помните, энтропия — это мера неопределённости. Из-за уязвимости раскрытия информации возможна утечка значений, генерируемых mt_rand(), так что использование mt_rand() в качестве уникального префикса-идентификатора добавляет нулевую неопределённость. В нашем примере единственный другой вид входных данных для uniqid() — это время. Но оно точно НЕ является неопределённым. Оно изменяется линейно и предсказуемо. А у предсказуемых значений крайне низкая энтропия.

Конечно, определение указывает на «микросекунды», т. е. на миллионные доли секунды. Это даёт нам 1 000 000 возможных чисел. Здесь я игнорирую значения больше 1 секунды, поскольку их фракция и измеряемость так велики (например, заголовок HTTP Date в отклике), что это почти ничего не даёт. Прежде чем углубиться в детали, давайте препарируем функцию uniqid() и посмотрим на её С-код:

gettimeofday((struct timeval *) &tv, (struct timezone *) NULL);
sec = (int) tv.tv_sec;
usec = (int) (tv.tv_usec % 0x100000);

/* usec может иметь максимальное значение 0xF423F, так что мы используем
 * usecs только пять шестнадцатеричных чисел.
 */
if (more_entropy) {
    spprintf(&uniqid, 0, "%s%08x%05x%.8F", prefix, sec, usec, php_combined_lcg(TSRMLS_C) * 10);
} else {
    spprintf(&uniqid, 0, "%s%08x%05x", prefix, sec, usec);
}

RETURN_STRING(uniqid, 0);

Если это выглядит слишком сложно, то можно реплицировать всё в старый добрый PHP:

function unique_id($prefix = '', $more_entropy = false) {
    list($usec, $sec) = explode(' ', microtime());
    $usec *= 1000000;
    if(true === $more_entropy) {
        return sprintf('%s%08x%05x%.8F', $prefix, $sec, $usec, lcg_value()*10);
    } else {
        return sprintf('%s%08x%05x', $prefix, $sec, $usec);
    }
}

Этот код говорит нам, что простой вызов uniqid() без параметров вернёт нам строку из 13 символов. Первые 8 символов — текущая временная метка в Unix (в секундах), выраженная в шестнадцатеричной форме. Последние 5 символов — дополнительные микросекунды в шестнадцатеричной форме. Иными словами, базовая функция uniqid() обеспечивает очень точное измерение системного времени, которое можно извлечь из простого вызова uniqid() с помощью подобного кода:

$id = uniqid();
$time = str_split($id, 8);
$sec = hexdec('0x' . $time[0]);
$usec = hexdec('0x' . $time[1]);
echo 'Seconds: ', $sec, PHP_EOL, 'Microseconds: ', $usec, PHP_EOL;

Посмотрите на С-код. Точное системное время в выходных данных никогда не бывает скрыто, вне зависимости от параметров:

echo uniqid(), PHP_EOL;                 // 514ee7f81c4b8
echo uniqid('prefix-'), PHP_EOL;        // prefix-514ee7f81c746
echo uniqid('prefix-', true), PHP_EOL;  // prefix-514ee7f81c8993.39593322

Брутфорс уникальных идентификаторов

Если поразмыслить, то становится очевидно, что раскрытие злоумышленнику любого значения uniqid() — ещё один пример потенциальной уязвимости раскрытия информации. Происходит утечка очень точного системного времени, которое можно использовать для прогнозирования входных данных для последующих вызовов uniqid(). Это помогает решать любые дилеммы, возникающие при попытке предсказывания микросекунд, за счёт сужения 1 000 000 возможностей до более узкого диапазона. Поскольку об этой утечке можно было упомянуть позже, то в нашем примере технически она не нужна. Давайте снова посмотрим на оригинальный код токена uniqid():

$token = hash('sha512', uniqid(mt_rand()));

Из этого примера мы видим, что, выполнив против mt_rand() атаку с восстановлением начального значения в совокупности с раскрытием информации из uniqid(), мы вычислим относительно небольшой набор SHA512-хешей, которые могут оказаться сбросом пароля или другими важными токенами. Если вам нужен узкий диапазон временных меток без использования утечки системного времени из uniqid(), то проанализируем серверные отклики, которые обычно содержат заголовок HTTP Date. Отсюда можно почерпнуть точные серверные временные метки. А поскольку в этом случае энтропия равна одному миллиону возможных значений микросекунд, то можно забрутфорсить её за несколько секунд!

<?php
echo PHP_EOL;

/**
 * Генерирует токен для взлома без утечки микросекунд
 */
mt_srand(1361723136.7);
$token = hash('sha512', uniqid(mt_rand()));

/**
 * Теперь взламываем токен без измерения микросекунд,
 * но помните, что секунды получены из заголовка HTTP Date и начального значения
 * для mt_rand() с помощью более раннего сценария атаки ;)
 */
$httpDateSeconds = time();
$bruteForcedSeed = 1361723136.7;
mt_srand($bruteForcedSeed);
$prefix = mt_rand();

/**
 * Инкрементируем HTTP Date на несколько секунд, чтобы исключить возможность
 * пересечения отсчёта секунд (second tick) между вызовами uniqid() и time().
 */
for ($j=$httpDateSeconds; $j < $httpDateSeconds+2; $j++) {
    for ($i=0; $i < 1000000; $i++) {
        /** Replicate uniqid() token generator in PHP */
        $guess = hash('sha512', sprintf('%s%8x%5x', $prefix, $j, $i));
        if ($token == $guess) {
            echo PHP_EOL, 'Actual Token: ', $token, PHP_EOL,
                'Forced Token: ', $guess, PHP_EOL;
            exit(0);
        }
        if (($i % 20000) == 0) {
            echo '~';
        }
    }
}

Спасёт ли нас увеличение энтропии?

Конечно, есть возможность добавить энтропию в uniqid() путём присвоения второму параметру функции значения TRUE:

$token = hash('sha512', uniqid(mt_rand(), true));

Как показывает С-код, новый источник энтропии использует выходные данные внутренней функции php_combined_lcg(). Эта функция выводится в пользовательское пространство посредством функции lcg_value(), которую я применял в своём PHP-преобразовании функции uniqid(). По сути, она комбинирует два значения, сгенерированных с помощью двух линейных конгруэнтных генераторов, получивших отдельные начальные значения. Ниже представлен код, который снабжал генераторы этими начальными значениями. Как в случае с mt_rand(), они генерируются один раз для каждого PHP-процесса и многократно используются во всех последующих вызовах.

static void lcg_seed(TSRMLS_D) /* {{{ */
{
    struct timeval tv;

    if (gettimeofday(&tv, NULL) == 0) {
        LCG(s1) = tv.tv_sec ^ (tv.tv_usec<<11);
    } else {
        LCG(s1) = 1;
    }
    #ifdef ZTS
    LCG(s2) = (long) tsrm_thread_id();
    #else
    LCG(s2) = (long) getpid();
    #endif

    /* Add entropy to s2 by calling gettimeofday() again */
    if (gettimeofday(&tv, NULL) == 0) {
        LCG(s2) ^= (tv.tv_usec<<11);
    }

    LCG(seeded) = 1;
}

Если вы будете слишком долго на это смотреть и захотите кинуть чем-нибудь в монитор, то лучше не надо. Мониторы нынче дороги.

Оба начальных значения используют в С функцию gettimeofday() для захвата текущего времени в секундах и микросекундах начиная с Unix Epoch (относится к серверным часам). Нужно отметить, что оба вызова реализованы в исходном коде, так что значение счётчика microsecond() между ними будет минимальным, что снижает вносимую неопределённость. Второе начальное значение также окажется подмешано в ID текущего процесса, который в большинстве случаев под Linux не превысит 32 768. Конечно, можно вручную поднять границу примерно до 4 миллионов, изменив /proc/sys/kernel/pid_max, но это очень нежелательно.

Получается, что первичный источник энтропии, используемый этими LCG, это микросекунды. К примеру, помните наше начальное значение mt_rand()? Угадайте, как оно вычисляется.

#ifdef PHP_WIN32
#define GENERATE_SEED() (((long) (time(0) * GetCurrentProcessId())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))
#else
#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))
#endif

Это означает, что все используемые в PHP начальные значения взаимозависимы. Даже несколько раз смешиваются одинаковые входные данные. Возможно, вы ограничите диапазон начальных микросекунд, как мы это обсуждали выше: с помощью двух запросов, когда первый делает переход между секундами (так что микровремя будет 0 + время выполнения следующего С-вызова gettimeofday()). Вы даже можете вычислить дельту в микросекундах между другими вызовами gettimeofday(), имея доступ к исходному коду (открытость кода PHP играет на руку). Не говоря уже о том, что брутфорс начального значения mt_rand() даёт вам финальное начальное значение, позволяющее выполнять офлайновую верификацию.

Однако основная проблема кроется в php_combined_lcg(). Это нижнеуровневая реализация функции lcg_value() из пользовательского пространства, которая получает начальное значение один раз на каждый PHP-процесс. И если вам известно это значение, то вы можете предсказать выходные данные. Если разгрызть этот орешек — то всё, игра окончена.

Для этого есть приложение...

Я уделил немало внимания практическим вещам, так что давайте снова к ним вернёмся. Не так просто получить два начальных значения, используемых php_combined_lcg(), — возможно, прямую утечку не получится организовать. Функция lcg_value() относительно малоизвестна, и программисты чаще полагаются на mt_rand(), когда им нужен PRNG, встроенный в PHP. Я не хочу предотвращать утечку значения для lcg_value(), но это непопулярная функция. Пара скомбинированных LCG также не отражают функцию генерирования начального значения (так что не получится просто поискать вызовы к mt_srand(), чтобы определить дырявый механизм создания начальных значений, унаследованный из чьего-то легаси-кода). Однако есть надёжный источник, напрямую предоставляющий данные для брутфорса начальных значений: идентификаторы сессий в PHP.

spprintf(&buf, 0, "%.15s%ld%ld%0.8F", remote_addr ? remote_addr : "", tv.tv_sec,
(long int)tv.tv_usec, php_combined_lcg(TSRMLS_C) * 10);

Этот код генерирует предхешевое (pre-hash) значение для ID сессии, используя IP, временную метку, микросекунды и… выходные данные php_combined_lcg(). Учитывая существенное снижение количества микровременных возможностей (этому коду нужна 1 для генерирования ID и 2 для php_combined_lcg(), что приводит к минимальной разнице между ними), мы теперь можем выполнить брутфорс. Ну, вероятно.

Как вы, наверное, помните, PHP теперь поддерживает новые опции сессий наподобие session.entropy_file и session.entropy_length. Это сделано для предотвращения брутфорса ID сессий, в ходе которого можно быстро (это не займёт часы) получить два начальных значения для объединённых с помощью php_combined_lcg() LCG-генераторов. Если вы используете PHP 5.3 или ниже, то, возможно, неправильно настроили эти опции. А это означает наличие другой полезной уязвимости раскрытия информации, позволяющей выполнять брутфорс ID сессий ради получения начальных значений для LCG.

Для подобных случаев существует Windows-приложение, позволяющее вычислять LCG-значения.

Кстати, знание состояний LCG позволяет понять, как mt_rand() получает начальное значение, так что это ещё один способ обойти нехватку утечек значения mt_rand().

Что всё это означает с точки зрения добавления энтропии в возвращаемые значения uniqid()?

$token = hash('sha512', uniqid(mt_rand(), true));

Это другой пример потенциальной уязвимости нехватки энтропии. Нельзя полагаться на энтропию с утечками (даже если вы не отвечаете за них!). Благодаря утечке информации об ID сессии злоумышленник может предсказать и то значение энтропии, что было дополнительно добавлено в этот ID.

Опять же, кого винить? Если приложение Х полагается на uniqid(), но пользователь или другое приложение на том же сервере допускает утечку внутреннего состояния LCG, то нужно принимать меры в обеих ситуациях. Пользователи должны быть уверены, что ID сессий используют достаточно высокую энтропию, а сторонние программисты должны понимать, что их методам генерирования случайных значений не хватает энтропии, поэтому нужно переключиться на более подходящие альтернативы (даже если доступны только источники слабой энтропии!).

В поисках энтропии

PHP сам по себе не способен генерировать сильную энтропию. Здесь даже нет базового API для передачи данных из PRNG-генераторов уровня операционной системы, являющихся надёжными источниками сильной энтропии. Поэтому вам нужно полагаться на опциональное наличие расширений openssl и mcrypt. Они предлагают функции, которые гораздо лучше своих дырявых, предсказуемых, низкоэнтропийных родственниц.

К сожалению, поскольку оба расширения опциональны, в некоторых случаях у нас нет иного выбора, кроме как полагаться на источники слабой энтропии в качестве последнего отчаянного рубежа. Когда такое случается, нужно дополнять слабую энтропию mt_rand() с помощью дополнительных источников неопределённости, смешивая их данные в единый пул, из которого можно черпать псевдослучайные байты. Подобный случайный генератор, использующий миксер сильной энтропии, уж реализовал Энтони Феррара в своей библиотеке RandomLib. Вот что следует по возможности делать программистам.

Избегайте соблазна скрыть слабость своей энтропии с помощью хеширования сложных математических преобразований. Всё это повторит злоумышленник, как только он узнает первичное начальное значение. Подобные ухищрения лишь незначительно увеличат объём вычислений при брутфорсе. Не забывайте: чем меньше энтропия, тем меньше неопределённости; чем меньше неопределённости, тем меньше возможностей необходимо брутфорсить. Единственное оправданное решение — любыми доступными способами увеличить пул используемой вами энтропии.

Библиотека RandomLib генерирует случайные байты путём смешивания данных из разных источников энтропии и локализации информации, которая может понадобиться злоумышленнику для предположений. Например, можно смешать выходные данные mt_rand(), uniqid() и lcg_value(), добавить PID, потребление памяти, ещё какое-то измерение микровремени, сериализацию $_ENV, posix_times() и т. д. Или пойти ещё дальше, это позволяет расширяемость RandomLib. Допустим, использовать какие-то дельты в микросекундах (т. е. измерять, сколько микросекунд нужно какой-то функции для работы с псевдослучайными входными данными наподобие вызовов hash()).

/**
 * Генерируем 32-байтное случайное значение. Можно использовать и другие методы:
 *  — generateInt() для получения целочисленных вплоть до PHP_INT_MAX
 *  — generateString() для получения значений в определённом диапазоне символов
 */
$factory = new RandomLibFactory;
$generator = $factory->getMediumStrengthGenerator();
$token = hash('sha512', $generator->generate(32));

Возможно, в связи с доступностью расширений OpenSSL и Mcrypt и потреблением памяти (footprint) библиотекой RandomLib вы будете использовать RandomLib в качестве запасного варианта, как в классе PRNG-генератора SecurityMultiTool.

Автор: AloneCoder

Источник