Безопасность криптографических систем зависит от некоторых секретных данных, которые известны уполномоченным лицам, но неизвестны и непредсказуемы для других. Для достижения этой непредсказуемости обычно используется некоторая рандомизация . Современные криптографические протоколы часто требуют частой генерации случайных величин. Криптографические атаки, которые подрывают или используют слабые места в этом процессе, известны как атаки с генератором случайных чисел .
Высококачественный процесс генерации случайных чисел (ГСЧ) почти всегда требуется для обеспечения безопасности, а отсутствие качества обычно создает уязвимости для атак и, таким образом, приводит к отсутствию безопасности, даже для полной компрометации, в криптографических системах. [1] Процесс ГСЧ особенно привлекателен для злоумышленников, поскольку обычно представляет собой отдельный изолированный аппаратный или программный компонент, который легко найти. Если злоумышленник может заменить псевдослучайные биты, сгенерированные так, как он может предсказать, безопасность будет полностью скомпрометирована, но, как правило, не обнаруживается никаким восходящим тестом битов. Более того, такие атаки требуют только однократного доступа к компрометируемой системе. Нет необходимости отправлять данные обратно, в отличие, скажем, от компьютерного вируса, который крадет ключи. а затем отправляет их по электронной почте в какую-то точку приема.
Генерация случайных величин человеком
Люди обычно плохо генерируют случайные величины. Маги, профессиональные игроки и мошенники зависят от предсказуемости человеческого поведения. Во время Второй мировой войны немецкие кодовые клерки были проинструктированы случайным образом выбирать три буквы в качестве начальных настроек ротора для каждого сообщения машины Enigma . Вместо этого некоторые выбрали предсказуемые значения, такие как их собственные инициалы или инициалы подруги, что значительно помогло союзникам взломать эти системы шифрования. Другой пример - это часто предсказуемые способы, которыми пользователи компьютеров выбирают пароли (см. « Взлом паролей» ).
Тем не менее, в конкретном случае игры со смешанными стратегиями использование энтропии человеческого игрового процесса для генерации случайности было изучено Ран Халприн и Мони Наор . [2]
Атаки
Программные ГСЧ
Как и другие компоненты криптосистемы, программный генератор случайных чисел должен быть спроектирован так, чтобы противостоять определенным атакам. Некоторые возможные атаки на ГСЧ включают (из [3] ):
- Прямая криптоаналитическая атака
- когда злоумышленник получил часть потока случайных битов и может использовать это, чтобы отличить вывод ГСЧ от действительно случайного потока.
- Атаки на основе ввода
- изменить входные данные для ГСЧ, чтобы атаковать его, например, «вымыв» существующую энтропию из системы и переведя ее в известное состояние.
- Атаки с расширением компрометации состояния
- когда внутреннее секретное состояние ГСЧ известно в какой-то момент, используйте это для прогнозирования будущих выходных данных или для восстановления предыдущих выходных данных. Это может произойти, когда генератор запускается и имеет небольшую энтропию или ее нет (особенно, если компьютер только что был загружен и выполнял очень стандартную последовательность операций), поэтому злоумышленник может получить первоначальное предположение о состоянии.
Аппаратные ГСЧ
Возможен ряд атак на аппаратные генераторы случайных чисел , включая попытку захвата радиочастотного излучения компьютера (например, получение значений времени прерывания жесткого диска из-за шума двигателя) или попытку подачи управляемых сигналов в предположительно случайный источник (например, как выключение света в лавовой лампе или подача сильного известного сигнала в звуковую карту).
Подрыв ГСЧ
Искаженные случайные числа могут быть созданы с использованием криптографически безопасного генератора псевдослучайных чисел с начальным значением, известным злоумышленнику, но скрытым в программном обеспечении. Относительно короткая, скажем, от 24 до 40 битов, часть начального числа может быть действительно случайной, чтобы предотвратить контрольные повторения, но не достаточно длинной, чтобы помешать злоумышленнику восстановить, скажем, «случайно» созданный ключ.
Случайные числа обычно проходят через несколько уровней аппаратного и программного обеспечения, прежде чем они будут использованы. Биты могут быть сгенерированы на периферийном устройстве, отправлены по последовательному кабелю, собраны в служебной программе операционной системы и извлечены системным вызовом. Поврежденные биты могут быть заменены в любой момент этого процесса с небольшой вероятностью обнаружения.
Аппаратная схема для получения искаженных битов может быть построена на интегральной схеме площадью несколько квадратных миллиметров. Самый сложный аппаратный генератор случайных чисел можно разрушить, поместив такой чип в любом месте перед тем, где оцифровывается источник случайности, например, в микросхеме выходного драйвера или даже в кабеле, соединяющем ГСЧ с компьютером. Чип Subversion может включать в себя часы, чтобы ограничить начало работы некоторым временем после того, как устройство было впервые включено и прошло приемочные испытания, или он может содержать радиоприемник для управления включением / выключением. Он может быть установлен производителем по требованию национальной службы разведки сигналов или добавлен позже любым лицом, имеющим физический доступ. Микросхемы ЦП со встроенными аппаратными генераторами случайных чисел могут быть заменены совместимыми микросхемами с измененным ГСЧ в прошивке микросхем.
Оборона
- Смешивайте (например, с помощью xor ) случайные числа, генерируемые оборудованием, с выходом потокового шифра хорошего качества , как можно ближе к точке использования. Ключ или начальное значение потокового шифра должно быть изменяемым таким образом, чтобы его можно было проверять и извлекать из надежного источника, например, бросков костей. Фортуна Генератор случайных чисел является примером алгоритма , который использует этот механизм.
- Создавайте пароли и парольные фразы, используя истинный случайный источник. Некоторые [ необходимы пояснения ] системы выбирают для пользователя случайные пароли, а не позволяют пользователям предлагать свои собственные.
- Используйте системы шифрования, которые документируют, как они генерируют случайные числа, и предоставляют метод для аудита процесса генерации.
- Создавайте системы безопасности с помощью готового оборудования, желательно приобретенного способами, не раскрывающими его предполагаемое использование, например, вне помещения в крупном розничном предприятии. С этой точки зрения звуковые карты и веб-камеры могут быть лучшим источником случайности, чем оборудование, созданное для этой цели .
- Сохраняйте полный физический контроль над оборудованием после его покупки.
Проектирование безопасного генератора случайных чисел требует, по крайней мере, такого же высокого уровня внимания, как и проектирование других элементов криптографической системы.
Выдающиеся примеры
Прогнозируемое семя Netscape
Ранние версии Netscape «s Secure Sockets Layer (SSL) , протокол шифрования , используемые псевдослучайные величины , полученных из PRNG затравки трех значений переменных: время суток, идентификатор процесса, и идентификатор родительского процесса. Эти количества часто относительно предсказуемы, поэтому имеют небольшую энтропию и не являются случайными, и в результате эта версия SSL оказалась небезопасной. О проблеме сообщил Netscape в 1994 году Филипп Халлам-Бейкер , в то время исследователь в веб-команде CERN, но не был исправлен до выпуска. Проблема в работающем коде был обнаружен в 1995 году Ян Голдберг и Дэвид Вагнер , [4] , который должен был перепроектировать в объектный код , так как Netscape отказался раскрывать подробности своей генерации случайных чисел ( безопасности через неизвестность ). Этот ГСЧ был исправлен в более поздних выпусках (версия 2 и выше) с помощью более надежного (т.е. более случайного и, следовательно, более высокой энтропии с точки зрения злоумышленника) заполнения.
Генератор случайных чисел Microsoft Windows 2000 / XP
Microsoft использует неопубликованный алгоритм для генерации случайных значений для своей операционной системы Windows . Эти случайные величины предоставляются пользователям с помощью утилиты CryptGenRandom . В ноябре 2007 г. Leo Dorrendorf et al. из Еврейского университета Иерусалима и Университета Хайфы опубликовали статью под названием « Криптоанализ генератора случайных чисел в операционной системе Windows» . [5] В документе были представлены серьезные недостатки подхода Microsoft того времени. Выводы статьи были основаны на дизассемблировании кода в Windows 2000, но, согласно Microsoft, применимы и к Windows XP. [6] Microsoft заявила, что проблемы, описанные в документе, были решены в последующих выпусках Windows, в которых используется другая реализация ГСЧ. [6]
Возможный бэкдор в Elliptical Curve DRBG
США Национальный институт стандартов и технологий опубликовал сборник «детерминированных случайных битовых генераторов» он рекомендует в качестве NIST Special Publication 800-90. [7] Один из генераторов, Dual_EC_DRBG , был одобрен Агентством национальной безопасности . [8] Dual_EC_DRBG использует технологию эллиптических кривых и включает набор рекомендуемых констант. В августе 2007 года Дэн Шумов и Нильс Фергюсон из Microsoft показали, что константы могут быть сконструированы таким образом, чтобы создать клептографический бэкдор в алгоритме. [9] В сентябре 2013 года The New York Times написала, что «АНБ вставило лазейку в стандарт 2006 года, принятый NIST ... названный стандартом Dual EC DRBG» [10], тем самым раскрывая, что АНБ осуществило вредоносную атаку. против американского народа. В декабре 2013 года агентство Reuters сообщило, что документы, опубликованные Эдвардом Сноуденом, указали, что АНБ заплатило RSA Security 10 миллионов долларов, чтобы сделать Dual_EC_DRBG по умолчанию в их программном обеспечении для шифрования, и выразило дополнительные опасения, что алгоритм может содержать бэкдор для АНБ. [11] Из-за этих опасений в 2014 году NIST исключил Dual EC DRBG из своего проекта руководства по генераторам случайных чисел, порекомендовав «текущим пользователям Dual_EC_DRBG как можно быстрее перейти на один из трех оставшихся утвержденных алгоритмов». [12]
MIFARE Крипто-1
Crypto-1 - это криптосистема, разработанная NXP для использования на чипах MIFARE . Система проприетарная и изначально алгоритм не был опубликован. После обратного проектирования чипа исследователи из Университета Вирджинии и компьютерного клуба Chaos обнаружили атаку на Crypto-1 с использованием плохо инициализированного генератора случайных чисел. [13]
Debian OpenSSL
В мае 2008 года исследователь безопасности Лучано Белло сообщил о своем открытии, что изменения, внесенные в 2006 году в генератор случайных чисел в версии пакета OpenSSL , распространяемой с Debian GNU / Linux и другими дистрибутивами на основе Debian, такими как Ubuntu , резко снизили энтропию генерировал значения и делал различные ключи безопасности уязвимыми для атак. [14] [15] Слабость безопасности была вызвана изменениями, внесенными в код openssl разработчиком Debian в ответ на предупреждения компилятора о явно избыточном коде. [16] Это вызвало массовую регенерацию ключей по всему миру, и, несмотря на все внимание к проблеме, можно было предположить, что многие из этих старых ключей все еще используются. Затрагиваемые типы ключей включают ключи SSH, ключи OpenVPN, ключи DNSSEC , ключевой материал для использования в сертификатах X.509 и ключи сеанса, используемые в соединениях SSL / TLS . Ключи, созданные с помощью GnuPG или GNUTLS, не затрагиваются, поскольку эти программы использовали разные методы для генерации случайных чисел. Ключи, сгенерированные дистрибутивами Linux, не основанными на Debian, также не изменяются. Уязвимость, связанная с генерацией слабого ключа, была незамедлительно устранена после того, как о ней было сообщено, но любые службы, все еще использующие ключи, созданные старым кодом, остаются уязвимыми. Ряд программных пакетов теперь содержат проверки по черному списку слабых ключей, чтобы попытаться предотвратить использование любого из этих оставшихся слабых ключей, но исследователи продолжают находить реализации слабых ключей. [17]
PlayStation 3
В декабре 2010 года группа, называющая себя fail0verflow, объявила о восстановлении закрытого ключа алгоритма цифровой подписи на основе эллиптической кривой (ECDSA), используемого Sony для подписи программного обеспечения для игровой консоли PlayStation 3 . Атака стала возможной, потому что Sony не удалось сгенерировать новый случайный одноразовый номер для каждой подписи. [18]
Факторинг открытого ключа RSA
В 2012 году Ленстра, Хьюз, Ожье, Бос, Кляйнджунг и Вахтер объявили об анализе, сравнивающем миллионы открытых ключей RSA, собранных из Интернета. Они смогли разложить 0,2% ключей, используя только алгоритм Евклида . [19] [20] Они использовали уникальную уязвимость криптосистем, основанную на целочисленной факторизации . Если n = pq - один открытый ключ, а n ′ = p ′ q ′ - другой, то если случайно p = p ′ , то простое вычисление gcd ( n , n ′) = p множит как n, так и n ′, полностью компрометация обоих ключей. Надя Хенингер , часть группы, проводившей аналогичный эксперимент, сказала, что плохие ключи почти полностью возникли во встроенных приложениях , и пояснила, что проблема с одним общим простым числом, обнаруженная двумя группами, является результатом ситуаций, когда генератор псевдослучайных чисел плохо работает. сначала засевают, а затем повторно засевают между поколениями первого и второго простых чисел. [21]
Конфликт Java nonce
В августе 2013 года было обнаружено, что ошибки в Java- классе SecureRandom могут вызывать конфликты в значениях k nonce, используемых для ECDSA в реализациях Биткойн на Android . Когда это произошло, закрытый ключ можно было восстановить, что, в свою очередь, позволило украсть биткойны из содержащего его кошелька . [22]
Смотрите также
- Генератор псевдослучайных чисел
- Криптографически безопасный генератор псевдослучайных чисел
- Генерация ключей
- Одноразовый блокнот
- Соль
- Nonce
Рекомендации
- ^ Майкл Дженкинс; Лидия Зиглар (28 сентября 2018). «Профиль пакета коммерческих алгоритмов национальной безопасности (CNSA) для управления сертификатами через CMS» . Проект IETF draft-jenkins-cnsa-cmc-profile-00 . Агентство национальной безопасности США.
Использование неадекватных генераторов псевдослучайных чисел (ГПСЧ) может привести к незначительной или нулевой безопасности. Генерация качественных случайных чисел затруднена.
- ^ Халприн, Ран; Наор, Мони. «Игры для извлечения случайности» (PDF) .
- ^ Келси, Дж .; Б. Шнайер; Д. Вагнер; К. Холл (1998). «Криптоаналитические атаки на генераторы псевдослучайных чисел» . Быстрое шифрование программного обеспечения, Труды пятого международного семинара . Springer-Verlag. С. 168–188 . Проверено 15 августа 2013 года .
- ^ Гольдберг, Ян; Вагнер, Дэвид (январь 1996). «Случайность и браузер Netscape» . Журнал доктора Добба .
- ^ Доррендорф, Лео; Гуттерман, Цви; Пинкас, Бенни (1 октября 2009 г.). «Криптоанализ генератора случайных чисел операционной системы Windows» (PDF) . ACM-транзакции по информационной и системной безопасности . 13 (1): 1–32. DOI : 10.1145 / 1609956.1609966 . S2CID 14108026 .
- ^ а б Кейзер, Грегг (21 ноября 2007 г.). «Microsoft подтверждает, что XP содержит ошибку генератора случайных чисел» . Компьютерный мир .
- ^ Баркер, Элейн; Келси, Джон (январь 2012 г.). «Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . NIST .
- ^ Шнайер, Брюс (15 ноября 2007 г.). «Разве АНБ заложило секретный бэкдор в новый стандарт шифрования?» . Проводной . Архивировано из оригинала на 11 мая 2008 года. Альтернативный URL
- ^ Шумов, Дэн; Фергюсон, Нильс (21 августа 2007 г.). "О возможности лазейки в NIST SP800-90 Dual Ec Prng" (PDF) . cr.yp.to/ .
- ^ Перлрот, Николь (10 сентября 2013 г.). «Правительство объявляет о шагах по восстановлению доверия к стандартам шифрования» . Нью-Йорк Таймс .
- ^ Менн, Джозеф (20 декабря 2013 г.). «Эксклюзив: секретный контракт, связанный с АНБ и пионером индустрии безопасности» . Рейтер . Сан-Франциско . Проверено 20 декабря 2013 года .
- ^ «NIST удаляет алгоритм криптографии из рекомендаций по генератору случайных чисел» . Национальный институт стандартов и технологий . 21 апреля 2014 г.
- ^ Нол, Карстен; Дэвид Эванс; Starbug Starbug; Хенрик Плётц (31 июля 2008 г.). «Обратный инжиниринг криптографической метки RFID» . SS'08 Материалы 17-й конференции по безопасности симпозиума . СС'08. USENIX . С. 185–193.
- ^ «DSA-1571-1 openssl - предсказуемый генератор случайных чисел» . Рекомендации по безопасности Debian . 13 мая 2008 г.
- ^ «CVE-2008-0166» . CVE . 9 января 2008 г.
OpenSSL 0.9.8c-1 до версий до 0.9.8g-9 в операционных системах на базе Debian использует генератор случайных чисел, который генерирует предсказуемые числа, что упрощает удаленным злоумышленникам проведение атак методом подбора методом грубой силы. криптографические ключи.
- ^ Шнайер, Брюс (19 мая 2008 г.). «Ошибка случайного числа в Debian Linux» .
- ^ «Взломанные ключи SSH, используемые для доступа к репозиториям Spotify, Govt GitHub» .
- ^ Бендель, Майк (29 декабря 2010). «Хакеры описывают безопасность PS3 как эпический провал, получают неограниченный доступ» . Exophase.com . Проверено 5 января 2011 . Внешняя ссылка в
|publisher=
( помощь ) - ^ Марков, Джон (14 февраля 2012 г.). «Недостаток, обнаруженный в методе сетевого шифрования» . Нью-Йорк Таймс .
- ^ Ленстра, Арьен; Хьюз, Джеймс П .; Ожье, Максим; Бос, Йоппе Виллем; Кляйнджунг, Торстен; Вахтер, Кристоф (2012). «Рон был неправ, Уит прав» (PDF) . Санта-Барбара: IACR: 17. Цитировать журнал требует
|journal=
( помощь ) - ^ Хенингер, Надя. «Новое исследование: не нужно паниковать из-за факторизуемых ключей - просто помните о своих P и Q» . Свобода возиться . Архивировано из оригинала на 2016-12-24 . Проверено 27 ноября 2020 года .
- ^ Чиргвин, Ричард (12 августа 2013 г.). «Ошибка Android бьет биткойн-кошельки» . Регистр .
дальнейшее чтение
- Гуттерман, Цви; Бенни Пинкас; Цахи Рейнман (2006). «Анализ генератора случайных чисел Linux» (PDF) . Симпозиум IEEE по безопасности и конфиденциальности 2006 г. (S & P'06) . п. 385. DOI : 10,1109 / SP.2006.5 . ISBN 978-0-7695-2574-7. S2CID 6385808 .
- Eastlake, D .; Дж. Шиллер; С. Крокер (июнь 2005 г.). «Требования случайности для безопасности» . RFC . IETF .