Истощение энтропии и ошибки из-за слабых ключей

Истощение энтропии происходит, когда системе не хватает непредсказуемых входных данных для инициализации CSPRNG. Это случается на недавно запущенных встраиваемых устройствах, виртуализированных серверах или системах без пользовательского ввода. Вывод RNG становится предсказуемым.

В 2006 году разработчик Debian удалил строку, отмеченную Valgrind: MD_Update(&m, buf, j). Эта строка была источником энтропии. В результате OpenSSL в Debian инициализировался только с использованием PID (максимум 32 768 значений). Все ключи, созданные в 2006–2008 годах, принадлежат множеству из 32 768 возможных вариантов.

Ключи RSA, DSA и ECDSA, ключи узлов SSH, сертификаты TLS и ключи SSL VPN, созданные в системах Debian/Ubuntu в 2006–2008 годах, были скомпрометированы. Затронутые системы: Debian Etch, Debian Lenny, Ubuntu 7.04–8.04. Были опубликованы чёрные списки, а сертификаты отозваны.

Виртуальные машины можно клонировать с одинаковым состоянием диска. Если обе виртуальные машины генерируют ключи из одного и того же состояния CSPRNG, они создают одинаковые ключи. Теперь гипервизоры добавляют энтропию через VirtIO RNG или таблицы ACPI, однако неправильно настроенные виртуальные машины всё ещё сталкиваются с этим риском при запуске.

Устройства IoT (маршрутизаторы, камеры) часто создают ключи SSH/TLS при первом запуске, ещё до накопления энтропии. Исследования выявили миллионы устройств, использующих несколько тысяч одинаковых пар ключей RSA, поскольку все они инициализировались из одного и того же начального состояния с низкой энтропией.

Ленстра и соавторы (2012) собрали 11,7 миллиона сертификатов TLS и вычислили попарные GCD. Были обнаружены 12 720 ключей RSA с общим простым множителем — это означает, что оба ключа можно было полностью разложить на множители. Были взломаны 0,2 % всех открытых ключей. Причина: недостаточная энтропия при запуске.

ECDSA требует уникального случайного одноразового числа k для каждой подписи. Если k используется повторно (или является слабым), закрытый ключ можно немедленно восстановить: d = (s1-s2)^{-1} * (z1-z2) * k / (r1-r2) mod n. В PS3 от Sony использовалось постоянное значение k — все игры можно было подписывать с помощью восстановленного ключа.

Java SecureRandom на Android 4.x в определённых условиях инициализировался системным временем. Несколько приложений для кошельков Bitcoin создавали подписи с одним и тем же одноразовым числом k, раскрывая закрытые ключи. Были украдены миллионы долларов. Google исправила реализацию SecureRandom.

Инструменты: ssh-vulnkey (проверяет ключи по чёрному списку слабых ключей Debian), badkeys (проверяет сертификаты TLS на наличие известных слабых простых множителей), алгоритм GCD-batch для массовой проверки ключей RSA. Журналы Certificate Transparency позволяют проводить анализ в масштабе всей совокупности сертификатов.

Используйте getrandom(GRND_RANDOM) при первой генерации ключа. После ожидания первоначальной инициализации читайте данные из /dev/urandom (проверьте, что /proc/sys/kernel/random/entropy_avail > 128). Используйте аппаратный RNG (RDRAND) как дополнительный источник энтропии. Никогда не создавайте ключи сразу после первого запуска без задержки.

Сохраняйте состояние CSPRNG между перезапусками: при завершении работы сохраните 32 байта из /dev/urandom в файл с начальным значением; при запуске прочитайте их и передайте обратно генератору. Это обеспечивает непрерывность энтропии между холодными запусками. Linux делает это автоматически, а встраиваемые системы часто не делают.

Какова была первопричина сбоя энтропии OpenSSL в Debian?

Истощение энтропии приводит к созданию предсказуемых ключей. Реальные взломы: OpenSSL в Debian (начальное значение только из PID), атаки GCD на устройства IoT, повторное использование одноразового числа ECDSA в PS3, кошельки Bitcoin на Android. Всегда инициализируйте генератор из энтропии OS и тщательно проверяйте создание ключей во встраиваемых системах. Далее: безопасное создание ключей, одноразовых чисел и IV.