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

Безопасность криптографических систем зависит от некоторых секретных данных, которые известны уполномоченным лицам, но неизвестны и непредсказуемы для других. Чтобы добиться такой непредсказуемости, некоторая рандомизация обычно используется . Современные криптографические протоколы часто требуют частой генерации случайных величин. Криптографические атаки, которые подрывают или используют слабые места этого процесса, известны как атаки с использованием генератора случайных чисел .

Для обеспечения безопасности почти всегда требуется высококачественный процесс генерации случайных чисел (ГСЧ), а отсутствие качества обычно создает уязвимости для атак и, таким образом, приводит к отсутствию безопасности, даже к полной компрометации, в криптографических системах. Процесс RNG особенно привлекателен для злоумышленников, поскольку обычно он представляет собой отдельный изолированный аппаратный или программный компонент, который легко обнаружить. Если злоумышленник может подменить псевдослучайные биты, сгенерированные таким образом, который он может предсказать, безопасность будет полностью скомпрометирована, но, как правило, ее невозможно обнаружить при любой восходящей проверке битов. Более того, такие атаки требуют только одного доступа к скомпрометированной системе. Никакие данные не нужно отправлять обратно, в отличие, скажем, от компьютерного вируса , который крадет ключи , а затем отправляет их по электронной почте в какую-то точку доставки.

Генерация случайных величин человеком

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

Тем не менее, в конкретном случае игры в смешанные стратегии использование энтропии человеческого игрового процесса для генерации случайности изучалось Раном Халприном и Мони Наором .

Атаки

Программные генераторы случайных чисел

Как и другие компоненты криптосистемы, программный генератор случайных чисел должен быть спроектирован так, чтобы противостоять определенным атакам. Некоторые возможные атаки на ГСЧ включают (от ):

Прямая криптоаналитическая атака

когда злоумышленник получил часть потока случайных битов и может использовать это, чтобы отличить выходные данные ГСЧ от действительно случайного потока.

Атаки на основе ввода

измените входные данные ГСЧ, чтобы атаковать его, например, «вымыв» существующую энтропию из системы и приведя ее в известное состояние.

Атаки на расширение компрометации государства

когда в какой-то момент становится известно внутреннее секретное состояние ГСЧ, используйте это для прогнозирования будущих выходных данных или восстановления предыдущих выходных данных. Это может произойти, когда генератор запускается и имеет небольшую энтропию или вообще ее не имеет (особенно, если компьютер только что загрузился и выполнил очень стандартную последовательность операций), поэтому злоумышленник может получить первоначальное предположение о состоянии.

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

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

Подрыв ГСЧ

Искаженные случайные числа могут быть созданы с использованием криптографически безопасного генератора псевдослучайных чисел с начальным значением , известным злоумышленнику, но скрытым в программном обеспечении. Относительно короткая, скажем, от 24 до 40 бит, часть начального числа может быть действительно случайной, чтобы предотвратить контрольные повторения, но недостаточно длинной, чтобы помешать злоумышленнику восстановить, скажем, «случайно» созданный ключ.

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

Аппаратная схема для создания измененных битов может быть построена на интегральной схеме площадью несколько квадратных миллиметров. Самый сложный аппаратный генератор случайных чисел можно вывести из строя, поместив такой чип где-нибудь выше места оцифровки источника случайности, скажем, в микросхеме выходного драйвера или даже в кабеле, соединяющем ГСЧ с компьютером. Микросхема Subversion может включать в себя часы, ограничивающие начало работы в течение некоторого времени после первого включения устройства и прохождения приемочных испытаний, или может содержать радиоприемник для управления включением/выключением. Он может быть установлен производителем по указанию национальной службы радиоразведки или добавлен позже любым лицом, имеющим физический доступ. Чипы ЦП со встроенными аппаратными генераторами случайных чисел могут быть заменены совместимыми чипами с измененным ГСЧ в прошивке чипов.

Защита

• Смешайте (например, с помощью xor ) аппаратно сгенерированные случайные числа с выводом потокового шифра хорошего качества , как можно ближе к точке использования. Ключ или начальное значение потокового шифрования должно быть изменено таким образом, чтобы его можно было проверить и получить из надежного источника, например, при броске игральной кости. Генератор случайных чисел Fortuna является примером алгоритма, использующего этот механизм.
• Генерируйте пароли и кодовые фразы, используя действительно случайный источник. Некоторый системы выбирают для пользователя случайные пароли, а не позволяют пользователям предлагать свои собственные.
• Используйте системы шифрования, которые документируют, как они генерируют случайные числа, и предоставляют метод аудита процесса генерации.
• Создавайте системы безопасности с использованием готового оборудования, желательно купленного таким образом, чтобы не раскрывать его предполагаемое использование, например, в крупном розничном заведении. С этой точки зрения звуковые карты и веб-камеры могут быть лучшим источником случайности, чем оборудование, созданное для этой цели .
• Сохраняйте полный физический контроль над оборудованием после его приобретения. Оборудование должно находиться в одном месте или месте и не требует никакой другой передачи на одноранговое оборудование. Атаки происходят в сети, а не на самом оборудовании.

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

Яркие примеры

Предсказуемое начальное значение Netscape

Ранние версии протокола шифрования Netscape Secure Sockets Layer (SSL) использовали псевдослучайные величины, полученные из PRNG с тремя переменными значениями: временем суток, идентификатором процесса и идентификатором родительского процесса. Эти величины часто относительно предсказуемы, поэтому имеют небольшую энтропию и не являются случайными, поэтому в результате эта версия SSL оказалась небезопасной. О проблеме сообщил Netscape в 1994 году Филип Халлам-Бейкер , тогдашний исследователь веб-команды CERN, но до выпуска она не была исправлена. Проблема в работающем коде была обнаружена в 1995 году Яном Голдбергом и Дэвидом Вагнером . которому пришлось перепроектировать объектный код , потому что Netscape отказалась раскрыть детали генерации случайных чисел ( безопасность через неизвестность ). Этот ГСЧ был исправлен в более поздних версиях (версия 2 и выше) путем более надежного (т. е. более случайного и, следовательно, более высокой энтропии с точки зрения злоумышленника) заполнения.

Генератор случайных чисел Microsoft Windows 2000/XP

Microsoft использует неопубликованный алгоритм для генерации случайных значений для своей операционной системы Windows . Эти случайные количества доступны пользователям с помощью утилиты CryptGenRandom . В ноябре 2007 г. Лео Доррендорф и др. из Еврейского университета в Иерусалиме и Университета Хайфы опубликовали статью под названием «Криптовалютный анализ генератора случайных чисел операционной системы Windows» . В документе представлены серьезные недостатки подхода Microsoft того времени. Выводы статьи были основаны на дизассемблере кода Windows 2000, но, по мнению Microsoft, применимы и к Windows XP. Microsoft заявила, что проблемы, описанные в документе, были решены в последующих выпусках Windows, в которых используется другая реализация RNG.

Возможный бэкдор в Elliptic Curve DRBG

США Национальный институт стандартов и технологий опубликовал сборник «детерминированных генераторов случайных битов», который он рекомендует как специальную публикацию NIST 800-90. Один из генераторов, Dual_EC_DRBG , получил одобрение Агентства национальной безопасности . Dual_EC_DRBG использует технологию эллиптических кривых и включает набор рекомендуемых констант. В августе 2007 года Дэн Шумоу и Нильс Фергюсон из Microsoft показали, что константы можно сконструировать таким образом, чтобы создать клептографический бэкдор в алгоритме. В сентябре 2013 года The New York Times написала, что «АНБ вставило черный ход в стандарт 2006 года, принятый NIST… под названием стандарт Dual EC DRBG». тем самым выяснилось, что АНБ осуществило вредоносную атаку против американского народа.В декабре 2013 года агентство Reuters сообщило, что в документах, опубликованных Эдвардом Сноуденом , указано, что АНБ заплатило RSA Security 10 миллионов долларов за то, чтобы Dual_EC_DRBG использовался по умолчанию в их программном обеспечении для шифрования, и вызвало дополнительные опасения, что алгоритм может содержать бэкдор для АНБ. Из-за этих опасений в 2014 году NIST исключил Dual EC DRBG из своего проекта руководства по генераторам случайных чисел, порекомендовав «нынешним пользователям Dual_EC_DRBG как можно быстрее перейти на один из трех оставшихся утвержденных алгоритмов».

МИФАРЕ Крипто-1

Crypto-1 — это криптосистема, разработанная NXP для использования в чипах MIFARE . Система является частной собственностью, и изначально алгоритм не был опубликован. После обратного проектирования чипа исследователи из Университета Вирджинии и Компьютерного клуба Хаоса обнаружили атаку на Crypto-1 с использованием плохо инициализированного генератора случайных чисел.

Debian OpenSSL

В мае 2008 года исследователь безопасности Лучиано Белло сообщил о своем открытии, что изменения, внесенные в 2006 году в генератор случайных чисел в версии пакета OpenSSL , распространяемой с Debian Linux и другими дистрибутивами на основе Debian, такими как Ubuntu , резко снизили энтропию генерируемых значений. и сделал множество ключей безопасности уязвимыми для атак. Слабость безопасности была вызвана изменениями, внесенными в код openssl разработчиком Debian в ответ на предупреждения компилятора о явно избыточном коде. Это вызвало массовую регенерацию ключей по всему миру, и, несмотря на все внимание, которое привлекла эта проблема, можно предположить, что многие из этих старых ключей все еще используются. Затронутые типы ключей включают ключи SSH , ключи OpenVPN , ключи DNSSEC , ключевой материал для использования в сертификатах X.509 и сеансовые ключи , используемые в соединениях SSL/TLS . Ключи, сгенерированные с помощью GnuPG или GNUTLS, не затрагиваются, поскольку эти программы используют разные методы для генерации случайных чисел. Ключи, созданные дистрибутивами Linux, не основанными на Debian, также не затрагиваются. Уязвимость генерации слабых ключей была оперативно исправлена ​​после того, как о ней было сообщено, но любые службы, все еще использующие ключи, сгенерированные старым кодом, остаются уязвимыми. Ряд программных пакетов теперь содержат проверки на черный список слабых ключей, чтобы попытаться предотвратить использование любого из этих оставшихся слабых ключей, но исследователи продолжают находить реализации слабых ключей.

PlayStation 3

В декабре 2010 года группа, назвавшая себя Fail0verflow , объявила о восстановлении закрытого ключа алгоритма цифровой подписи на основе эллиптической кривой (ECDSA), используемого Sony для подписи программного обеспечения для игровой консоли PlayStation 3 . Атака стала возможной, потому что Sony не удалось сгенерировать новый случайный одноразовый номер для каждой подписи.

Факторинг открытого ключа RSA

Анализ, сравнивающий миллионы открытых ключей RSA, собранных из Интернета, был анонсирован в 2012 году Ленстра, Хьюз, Ожье, Бос, Кляйнджунг и Вахтер. Им удалось факторизовать 0,2% ключей, используя только алгоритм Евклида . Они воспользовались слабостью, уникальной для криптосистем, основанных на факторизации целых чисел . Если n = pq является одним открытым ключом, а n ′ = p ′ q ′ является другим, то если случайно p = p ′ , то простое вычисление gcd( n , n ′) = p учитывает оба n и n ′, полностью скомпрометировав оба ключа. Надя Хенингер , участница группы, проводившей аналогичный эксперимент, сказала, что неверные ключи почти полностью возникали во встроенных приложениях , и объясняет, что проблема с одним общим простым числом, обнаруженная двумя группами, возникает в ситуациях, когда генератор псевдослучайных чисел плохо работает. первоначально засеивается, а затем повторно засевается между генерацией первого и второго простых чисел.

Java одноразовое столкновение

В августе 2013 года было обнаружено, что ошибки в Java -классе SecureRandom могут привести к коллизиям значений k nonce, используемых для ECDSA в реализациях Биткойна на Android . Когда это произошло, закрытый ключ можно было восстановить, что, в свою очередь, позволило украсть биткойны из содержащего его кошелька .

См. также

• Генератор псевдослучайных чисел
• Криптографически безопасный генератор псевдослучайных чисел
• Генерация ключей
• Одноразовый блокнот
• Соль
• одноразовый

Дальнейшее чтение

• Гаттерман, Цви; Бенни Пинкас; Цахи Рейнман (2006). «Анализ генератора случайных чисел Linux» (PDF) . Симпозиум IEEE 2006 г. по безопасности и конфиденциальности (S&P'06) . п. 385. дои : 10.1109/SP.2006.5 . ISBN  978-0-7695-2574-7 . S2CID   6385808 .
• Истлейк, Д.; Дж. Шиллер; С. Крокер (июнь 2005 г.). «Требования случайности для безопасности» . РФК . IETF .