Безопасность криптографических систем зависит от некоторых секретных данных, которые известны уполномоченным лицам, но неизвестны и непредсказуемо для других. Для достижения этой непредсказуемости обычно используется некоторая рандомизация. Современные криптографические протоколы часто требуют частой генерации случайных величин. Криптографические атаки, которые разрушают или используют слабые места в этом процессе, известны как атаки с генератором случайных чисел .
Высококачественный процесс генерации случайных чисел (ГСЧ) почти всегда требуется для обеспечения безопасности, а отсутствие качества обычно обеспечивает уязвимости для атак и, таким образом, приводит к отсутствию безопасности, даже для полной компрометации, в криптографических системах. Процесс ГСЧ особенно привлекателен для злоумышленников, поскольку обычно представляет собой отдельный изолированный аппаратный или программный компонент, который легко найти. Если злоумышленник может заменить псевдослучайные биты, сгенерированные так, как он может предсказать, безопасность будет полностью скомпрометирована, но, как правило, не обнаруживается никаким восходящим тестом битов. Более того, такие атаки требуют только однократного доступа к компрометируемой системе. В отличие от, скажем, компьютерного вируса, который крадет ключи и затем отправляет их по электронной почте в какую-либо точку приема, не требуется отправлять данные.
Люди обычно плохо справляются с генерацией случайных величин. Маги, профессиональные игроки и аферисты зависят от предсказуемости человеческого поведения. Во время Второй мировой войны немецкие кодовые клерки были проинструктированы случайным образом выбирать три буквы в качестве начальных настроек ротора для каждого сообщения машины Enigma. Вместо этого некоторые выбрали предсказуемые значения, такие как их собственные инициалы или инициалы подруги, что значительно помогло союзникам взломать эти системы шифрования. Другой пример - это часто предсказуемые способы выбора паролей пользователями компьютеров (см. взлом паролей ).
Тем не менее, в конкретном случае игры со смешанной стратегией, использование человеческого игрового процесса энтропии для генерации случайности было изучено Ран Халприн и Мони Наор.
Так же, как и в случае с другими компонентами криптосистемы, программный генератор случайных чисел должен быть разработан для защиты от определенных атак. Некоторые возможные атаки на ГСЧ включают (от):
Возможен ряд атак на аппаратные генераторы случайных чисел, в том числе попытки перехвата радиочастотных излучений компьютера (получение времени прерывания жесткого диска из-за шума двигателя, например) или попытки подать управляемые сигналы в предположительно случайный источник (например, выключить свет в лавовой лампе или подать сильный известный сигнал в звуковую карту).
Подрывные случайные числа могут быть созданы с помощью криптографически безопасного генератора псевдослучайных чисел с начальным значением, известным злоумышленнику, но скрытым в программное обеспечение. Относительно короткая, скажем, от 24 до 40 бит, часть начального числа может быть действительно случайной, чтобы предотвратить контрольные повторения, но не достаточно длинной, чтобы помешать злоумышленнику восстановить, скажем, «случайно» созданный ключ.
Случайные числа обычно проходят через несколько уровней аппаратного и программного обеспечения, прежде чем они будут использованы. Биты могут быть сгенерированы на периферийном устройстве, отправлены по последовательному кабелю, собраны в служебной программе операционной системы и извлечены с помощью системного вызова. Подмененные биты могут быть заменены в любой момент этого процесса с небольшой вероятностью обнаружения.
Аппаратная схема для получения искаженных битов может быть построена на интегральной схеме площадью несколько квадратных миллиметров. Самый сложный аппаратный генератор случайных чисел можно разрушить, разместив такой чип в любом месте перед тем, где оцифровывается источник случайности, например, в микросхеме выходного драйвера или даже в кабеле, соединяющем ГСЧ с компьютером. Чип Subversion может включать в себя часы, чтобы ограничить начало работы некоторым временем после того, как устройство было впервые включено и прошло приемочные испытания, или он может содержать радиоприемник для управления включением / выключением. Он может быть установлен производителем по требованию национальной службы разведки сигналов или добавлен позже любым лицом, имеющим физический доступ. ЦП микросхемы со встроенными аппаратными генераторами случайных чисел могут быть заменены совместимыми микросхемами с измененным ГСЧ в прошивке микросхем.
Проектирование безопасного генератора случайных чисел требует, по крайней мере, такого же высокого уровня осторожности, как и проектирование других элементов криптографической системы.
Использовались ранние версии Netscape Secure Socket Layer (SSL) протокола шифрования псевдослучайные величины, полученные из ГПСЧ, заполненного тремя значениями переменных: временем дня, идентификатором процесса и идентификатором родительского процесса. Эти количества часто относительно предсказуемы, поэтому имеют небольшую энтропию и менее случайны, и в результате эта версия SSL оказалась небезопасной. О проблеме сообщил Netscape в 1994 году Филип Халлам-Бейкер, в то время исследователь в группе CERN Web, но не была исправлена до выпуска. Проблема в работающем коде была обнаружена в 1995 г. Яном Голдбергом и Дэвидом Вагнером, которым пришлось перепроектировать объектный код , потому что Netscape отказался раскрыть детали генерации случайных чисел (безопасность через неясность ). Этот ГСЧ был исправлен в более поздних выпусках (версия 2 и выше) за счет более надежного (то есть более случайного и, следовательно, более высокой энтропии с точки зрения атакующего).
Microsoft использует неопубликованный алгоритм для генерации случайных значений для своей операционной системы Windows. Эти случайные величины предоставляются пользователям с помощью утилиты CryptGenRandom. В ноябре 2007 года Лео Доррендорф и др. из Еврейского университета Иерусалима и Хайфского университета опубликовали статью под названием «Криптоанализ генератора случайных чисел в операционной системе Windows». В документе были представлены серьезные недостатки подхода Microsoft того времени. Выводы статьи были основаны на дизассемблировании кода в Windows 2000, но, по мнению Microsoft, применимы и к Windows XP. Microsoft заявила, что проблемы, описанные в документе, были решены в последующих выпусках Windows, в которых используется другая реализация RNG.
The US National Институт стандартов и технологий опубликовал сборник «детерминированных генераторов случайных битов», который он рекомендует в специальной публикации NIST 800-90. Один из генераторов, Dual_EC_DRBG, был одобрен Агентством национальной безопасности. Dual_EC_DRBG использует технологию эллиптических кривых и включает набор рекомендуемых констант. В августе 2007 года Дэн Шумов и Нильс Фергюсон из Microsoft показали, что константы могут быть сконструированы таким образом, чтобы создать в алгоритме клептографический бэкдор. В сентябре 2013 года The New York Times написала, что «Агентство национальной безопасности США вставило лазейку в стандарт 2006 года, принятый N.I.S.T... названный стандартом Dual EC DRBG», тем самым раскрывая, что АНБ провело вредоносную атаку против американского народа. В декабре 2013 года агентство Reuters сообщило, что документы, опубликованные Эдвардом Сноуденом, показали, что АНБ заплатило RSA Security 10 миллионов долларов, чтобы сделать Dual_EC_DRBG по умолчанию в их программном обеспечении для шифрования, и выразил дополнительные опасения, что алгоритм может содержать бэкдор для АНБ. Из-за этих опасений в 2014 году NIST исключил Dual EC DRBG из своего проекта руководства по генераторам случайных чисел, порекомендовав «текущим пользователям Dual_EC_DRBG как можно скорее перейти на один из трех оставшихся утвержденных алгоритмов».
Crypto-1 - это криптосистема, разработанная NXP для использования на чипах MIFARE. Система проприетарная и изначально алгоритм не был опубликован. При обратном проектировании чипа исследователи из Университета Вирджинии и компьютерного клуба Chaos обнаружили атаку на Crypto-1 с использованием плохо инициализированного генератора случайных чисел.
В мае 2008 года исследователь безопасности раскрыл свое открытие, что изменения, внесенные в 2006 году в генератор случайных чисел в версии пакета OpenSSL, распространяемого с Debian GNU / Linux и другими Debian дистрибутивы на основе, такие как Ubuntu, резко снизили энтропию генерируемых значений и сделали множество ключей безопасности уязвимыми для атак. Слабость системы безопасности была вызвана изменениями, внесенными в код openssl разработчиком Debian в ответ на предупреждения компилятора о явно избыточном коде. Это вызвало массовую регенерацию ключей во всем мире, и, несмотря на все внимание к проблеме, можно было предположить, что многие из этих старых ключей все еще используются. Затрагиваемые типы ключей включают ключи SSH, ключи OpenVPN, ключи DNSSEC, материал ключа для использования в сертификатах X.509 и ключи сеанса, используемые в соединениях SSL / TLS. Ключи, сгенерированные с помощью GnuPG или GNUTLS, не затрагиваются, поскольку эти программы использовали разные методы для генерации случайных чисел. Ключи, сгенерированные дистрибутивами Linux, отличными от Debian, также не затронуты. Уязвимость, связанная с генерацией слабого ключа, была незамедлительно исправлена после того, как о ней было сообщено, но любые службы, все еще использующие ключи, созданные старым кодом, остаются уязвимыми. Ряд программных пакетов теперь содержат проверки по черному списку слабых ключей, чтобы попытаться предотвратить использование любого из этих оставшихся слабых ключей, но исследователи продолжают находить реализации слабых ключей.
В В декабре 2010 года группа, называющая себя fail0verflow, объявила о восстановлении закрытого ключа алгоритма цифровой подписи эллиптической кривой (ECDSA), используемого Sony для подписи программного обеспечения для PlayStation 3 игровая консоль. Атака стала возможной, потому что Sony не удалось сгенерировать новый случайный одноразовый номер для каждой подписи.
Анализ, сравнивающий миллионы RSA открытые ключи, собранные из Интернета, были объявлены в 2012 году Ленстра, Хьюзом, Ожье, Босом, Кляйнджунгом и Вахтером. Они смогли разложить 0,2% ключей, используя только алгоритм Евклида. Они использовали уникальную уязвимость криптосистем, основанную на целочисленной факторизации. Если n = pq - один открытый ключ, а n ′ = p′q ′ - другой, то если случайно p = p ′, тогда простое вычисление gcd (n, n ′) = p множит как n, так и n ′, полностью компрометация обоих ключей. Надя Хенингер, часть группы, проводившей аналогичный эксперимент, сказала, что плохие ключи почти полностью возникли во встроенных приложениях, и пояснила, что проблема с одним общим простым числом обнаружена две группы возникают в результате ситуаций, когда генератор псевдослучайных чисел изначально плохо заполнен, а затем повторно заполнен между генерацией первого и второго простых чисел.
В августе 2013 года было обнаружено, что ошибки в Java class SecureRandom могут вызывать конфликты в используемых значениях k nonce. для ECDSA в реализациях Биткойн на Android. Когда это произошло, закрытый ключ можно было восстановить, что, в свою очередь, позволило украсть биткойны из содержащего кошелька.