Пластиковый сейф: исследование уязвимости в системах цифровой сертификации
Многие смарт-карты обладают низкой криптографической защитой либо не имеют её вовсе. Это утверждение справедливо даже для тех карт, которые признаны соответствующими жёстким критериям FIPS 140-2 Level 2 и надёжность которых подтверждена двумя международными сертификатами. К такому выводу
Полный отчёт об исследовании, компрометирующем существующую систему сертификации, будет представлен на конференции Asiacrypt 2013. Часть любопытных деталей стала
Серьёзная уязвимость была выявлена в тайваньской программе цифровой сертификации с использованием персональных смарт-карт. С учётом её характера можно предположить, что она затрагивает другие страны и области применения. Основная проблема заключается в генераторе псевдослучайных чисел (ГПСЧ), применяемом в широко распространённом варианте криптосистемы RSA.
Приставка «псевдо» используется потому, что получение истинно случайных значений трудно реализовать на уровне математических алгоритмов. Создаваемые генераторами цифровые последовательности всегда немного отклоняются от закона равномерного распределения. Однако эти отличия от идеальной схемы обычно не слишком принципиальны и нивелируются по мере увеличения множества сгенерированных чисел, а каждый генератор проходит ряд проверок, прежде чем стать основой серьёзного программного продукта.
В рассматриваемом случае генератор для системы цифровой сертификации оказался настолько посредственным, что среди собранных ключей RSA длиной 1 024 бита группе аналитиков под руководством Кеннета Дж. Патерсона удалось взломать 184 штуки в течение нескольких часов на рядовом персональном компьютере.
При использовании корректного ГПСЧ стойкость криптографической системы RSA (как и всех алгоритмов асимметричного шифрования) базируется на том, что при наличии открытого ключа сложно вычислить парный ему секретный.
Ключи создаются на основе произведения пар больших простых чисел (натуральных чисел, которые делятся без остатка только на единицу и сами на себя). Эти числа генерируются псевдослучайным образом. В теории ключу длиной 1 024 бита соответствует множество из 2502 простых чисел. Для атакующей стороны они все равновероятны.
На практике это означает неприемлемо долгое время атаки (годы, века) даже с использованием суперкомпьютера или сети распределённых вычислений, так как она в конечном счёте сводится к решению задачи факторизации — представления (больших) целых чисел в виде произведения простых.
Эксперт по вопросам криптографии Марк Бернетт
Случайна ли ошибка в генераторе случайных чисел?
На первый взгляд, такая грубая ошибка, как дефектный генератор псевдослучайных чисел, в международной платёжной системе просто не могла пройти мимо десятков специалистов сертификационных центров и остаться незамеченной. Складывается впечатление, что их попросту заставили проигнорировать её, а сложившаяся ситуация возникла по причине закрытости деталей конкретной криптографической системы.
Распространено мнение, что открытый исходный код криптографических программ гарантирует их надёжность. Однако на практике получается, что открытость — необходимое, но не достаточное условие.
К примеру, подобная ошибка в генераторе случайных чисел криптографического пакета OpenSSL (применяемого в том числе и для создания ключей RSA) в ОС Debian
Оценка надёжности
Критерии надёжности криптографических систем пересматриваются каждый год. Происходит это даже не столько в связи с увеличением мощности компьютеров, сколько из-за развития математики. Продолжается поиск всё больших простых чисел, открываются их новые свойства, создаются более эффективные алгоритмы и реализующие их ценой минимальных затрат узкоспециализированные чипы.
В этом году перуанским математиком Харальдом Хельфготтом (Harald Andres Helfgott Seier) была
Определить общее количество простых чисел в заданном диапазоне гораздо проще, чем вычислить их ряд до этого предела. Существуют (и разрабатываются новые) также способы эффективного поиска простых чисел отдельных типов и алгоритмы проверки произвольного числа на соответствие критериям простоты.
При помощи проекта добровольных распределённых вычислений было найдено самое большое (среди известных на сегодня) простое число. Им оказалось число Мерсенна:
2 57885161 — 1. Его запись в десятичном виде в формате текстового файла выглядит так: [Осторожно! Браузер может зависнуть при попытке загрузить эту
Гладко было на бумаге…
Помимо очевидного упрощения задачи взлома систем шифрования с течением времени (в силу развития математики и закона Мура), существует гораздо более серьёзная проблема — снижение стойкости применяемых на практике криптографических средств из-за ошибок в их реализации или намеренного ослабления.
Именно в последнем заключается политика правительства США, Канады, Великобритании и, возможно, других стран в отношении как экспортируемых, так и свободно доступных криптографических продуктов. К примеру, эффективная длина ключа намеренно уменьшалась в системах с блочным алгоритмом
До недавнего времени считалось, что наиболее популярные варианты реализации RSA сегодня лишены такого явного огрубления, но их стойкость оказалась снижена на другом уровне.
После двух с половиной лет распределённых вычислений группе криптографов под руководством Торстена Клейнюнга (Thorsten Kleinjung) в декабре 2009 года
Последующие работы этого же коллектива выявили другие проблемы с практической реализацией криптосистем на базе RSA. Как и в рассмотренных выше случаях, её корнем стал ненадёжный ГПСЧ. Совпадающие произведения простых чисел были обнаружены у одного процента всех проанализированных ключей с длиной 1 024 бита. Это кажется не столь большим, пока не осознаёшь, что в таком огромном массиве идентичных пар не должно встречаться вовсе. Разложив модуль на произведение двух простых чисел, атакующий может вычислить недостающий секретный компонент и взломать RSA.
Главный специалист подразделения безопасности корпорации EMC и директор лаборатории RSA Ари Джулс (Ari Juels) ознакомился с исследованиями группы Торстена и опубликовал официальный комментарий. На страницах блога он в очередной раз
Что получается в сухом остатке? На протяжении как минимум последних пяти лет разные группы криптографов указывали на однотипные проблемы в самых распространённых системах, использующих алгоритм RSA. Проанализировав эти отчёты и фактические темпы вскрытия ключей разной длины в конкурсе RSA Challenge, Национальный институт стандартов и технологий США (NIST) рекомендовал устранить выявленные ошибки, а также прекратить использование ключей длиной 1 024 бита и менее не позже начала 2010 года. Однако проблема остаётся актуальной и для ключей длиной 2 048 бит, поскольку ненадёжные генераторы псевдослучайных чисел продолжают применяться до сих пор в самых ответственных областях.