Но и это ещё не всё. Аналогичные нынешним исследования проводились и ранее, правда, на меньшем количестве ключей. Исследованный ныне массив из семи миллионов – это тоже далеко не все применяемые в мире ключи. Очень важным новым открытием стал такой факт: процентная доля ключей, для которых установлено, что они сгенерированы с помощью неуникальных множителей, скорее всего, будет возрастать и далее по мере того, как будут становиться доступными для анализа ещё большие количества ключей.
Доля 0,4 (точнее - 0,38) процента дефективных ключей была обнаружена в условиях, когда исследователи просмотрели в общей сложности 7,1 миллиона ключей, в то время как выявленная в более раннем исследовании доля дефективных ключей в размере 0,26 процента соответствовала проанализированному числу из 4,7 миллиона модулей RSA. Иначе говоря, как результат такой зависимости, подлинное количество ключей, которые на самом деле можно было бы вскрыть, используя данный подход, может оказаться даже выше, чем показывает нынешнее исследование.
Пытаясь логически осмыслить полученные результаты, учёные пришли к выводу, что кто-то наверняка уже знает об этом. Непосредственно в их статье данная мысль сформулирована следующим образом: "Учитывая отсутствие в наших методах анализа каких-то хитрых и сложных приёмов, а также последовавшие за этим открытия, очень трудно поверить, будто представленная нами работа является чем-то совершенно новым. Особенно принимая во внимание, что существуют организации, известные обострённым любопытством к подобного рода делам".
Комментируя эти выводы в своем блоге, известный криптоэксперт Брюс Шнайер особо отмечает, что главной причиной выявленной слабости практически наверняка является некачественный генератор случайных чисел, применявшийся для создания этих открытых ключей. И это не должно никого удивлять.
Одна из самых трудных частей криптографии, напоминает эксперт, - это качественная генерация случайных чисел. При этом низкое качество генератора случайных чисел может быть совершенно неочевидным на первый взгляд. Так что нельзя исключать, что слабые ключи появляются как результат слабого понимания криптографии и случайных неблагоприятных обстоятельств.
Один из репортёров, сообщивших Шнайеру об этой истории, попутно поделился с ним сплетней: будто сами исследователи ему рассказали о совершенно реальном генераторе случайных чисел из применяемого в жизни криптоприложения, на выходе которого выдавалось всего семь разных случайных чисел.
Но с другой стороны, отмечает Шнайер, нельзя исключать и другой вариант: некоторые генераторы случайных чисел могли быть ослаблены умышленно. Очевидным подозреваемым тут будут государственные разведслужбы вроде АНБ США. На всякий случай эксперт тут же оговаривается, что у него нет никаких свидетельств тому, что подобное действительно случалось. Однако, продолжает Шнайер, если бы он сам отвечал за ослабление криптосистем в реальном мире (чем спецслужбы вроде АНБ заведомо известны), то первая вещь, на которую он бы нацелился, стали бы именно генераторы случайных чисел.
Их легко ослабить, а заметить слабость - довольно трудно. Это намного безопаснее, чем шаманить с алгоритмами, которые можно протестировать с помощью уже известных контрольных примеров и альтернативных реализаций. Но, ещё раз оговаривается Шнайер, всё это лишь фантазии информированного человека...
Возвращаясь к тексту исследовательской работы Ленстры и его коллег, нельзя не отметить и такой факт: хотя сами учёные назвали свои методы анализа простыми и незамысловатыми, непосредственно оценить это невозможно. Потому что конкретный способ, применявшийся ими для выявления ключей, сгенерированных неуникальными множителями, в самой статье не описывается. Как не указаны и списки скомпрометированных сертификатов или держателей слабых ключей.
Со слов одного из участников, Джеймса Хьюза, известно лишь то, что их команда нашла вычислительно эффективный способ для "помечивания" ключей – без необходимости индивидуального сравнения каждого нового со всеми предыдущими.
Другой главный участник работы, Арьен Ленстра, счёл необходимым прокомментировать в интервью для прессы, почему они решили опубликовать свои открытия уже сейчас – существенно раньше начала августовской конференции. Таким образом, по свидетельству Ленстры, исследователи хотели бы как можно раньше предупредить всех пользователей криптографии с открытым ключом о выявлении столь большого количества слабых модулей.
Хотя их команде на проведение этого исследования потребовалось три года, они полагают, что грамотным коллегам хватит нескольких недель на воспроизведение тех же результатов по уже известному в общих чертах рецепту. Попутно, правда, это важное открытие подняло и весьма непростой вопрос о том, каким образом раскрыть подобного рода информацию, не облегчая при этом для злоумышленников взлом десятков тысяч скомпрометированных ключей.
Цитируем работу: "То гигантское количество уязвимых ключей, с которым мы столкнулись, делает непосильным правильное информирование всех и каждого, кто непосредственно с этим связан, хотя мы и предприняли всё для нас возможное для информирования наиболее крупных сторон, разослав также письма по всем тем email-адресам, которые были указаны в валидных сертификатах. Наше решение сделать результаты открытия публичными, несмотря на нашу неспособность непосредственно известить всех пострадавших, было своего рода призывом к судному дню".
Своё нынешнее открытие исследователи сравнивают с памятным многим открытием 2008 года, когда вдруг выяснилось, что сотни тысяч, а быть может, и миллионы криптографических ключей, сгенерированных в системах, работающих под Debian Linux, оказались столь предсказуемы, что атакующая сторона могла их вычислять максимум за несколько часов.
Отбирая ключи для последнего исследования, учёные для чистоты эксперимента заранее исключали те, что подпадали под уже скомпрометированную ранее "категорию Debian". Но и при таком подходе пока что осталось совершенно неясным, что именно является причиной для появления больших кластеров ключей, имеющих в себе одинаковые множители.
Исследователи пытались выявить какие-либо схожести среди уязвимых ключей в надежде понять причину дефектной работы алгоритмов в генераторах случайных чисел, вырабатывающих криптоключи, но не преуспели. "Единственное наше заключение здесь сводится к тому, что для всех этих проблем, похоже, имеется не единственная причина, - говорит Хьюз. - А это соответственно привело нас к заключению, что до тех пор, пока у вас нет абсолютного доверия к работе вашего генератора случайных чисел, RSA не есть хороший выбор для криптоалгоритма".
По мнению криптографов, другие алгоритмы криптографии с открытым ключом, такие, как схема Диффи-Хеллмана и DSA, оказываются не столь фатально уязвимы для компрометации, как RSA. Дело в том, что в альтернативных схемах появление дублей у множителей модуля делает владельца ключа уязвимым только для того человека, с которым непосредственно устанавливается шифрованная связь: "Если с вашим ключом случается коллизия, то вы влияете только лишь на одного другого человека. Вы можете навредить ему, а он может навредить вам, однако вы не можете сделать этот ущерб публичным, как в RSA, где пострадавшим оказывается каждый с таким же фактором-множителем в модуле".
Именно по этой причине, собственно, авторы работы и решили дать своей статье несколько необычное название - "Ron was wrong, Whit is right" ("Рон был неправ, а прав оказывается Уит"), имея в виду первооткрывателей самых первых криптосхем с открытым ключом, Рональда Райвеста (RSA) и Уитфилда Диффи (Diffie-Hellmann).
В качестве эпилога к этой занятной, но невесёлой истории можно привести такие слова из заключительной части исследовательской работы:
"Факторизация всего лишь одного (правильно сгенерированного) 1024-битного RSA-модуля стала бы историческим событием. Однако факторизация 12 720 таких модулей скопом – это уже статистика. Первое событие из этого ряда – всё ещё недостижимая цель для академического сообщества. А вот второе событие – это своего рода малоприятное предупреждение, ещё раз подчеркивающее, сколь непростой является задача правильной генерации криптоключей в реальном мире... "
Дмитрий Вибе: Я б в астрономы пошёл
Автор: Дмитрий Вибе
Опубликовано 02 марта 2012 года
У астрономии очень красивый фасад. На безупречно чёрном фоне сверкающими брильянтиками выложены фигуры созвездий. Пёстрой мозаикой развешаны по фронтону фотографии, и на каждой — разноцветное космическое чудо. От названий веет тайной и вековой мудростью: планетарная туманность, звёздное скопление, сталкивающиеся галактики, Конская Голова, Никс Олимпика, квазар Лист Клевера… Гигантским усилием воли пытаешься (безуспешно) втиснуть в голову мысль о том, что каждое пятнышко на снимке (а от них рябит в глазах!) — звезда, может быть, подобная Солнцу, а может быть, в тысячи раз более яркая. Что тёмное пятно на фотографии — облако пыли размером в десяток раз больше, чем расстояние от Солнца до Альфы Центавра. Что мы любуемся звёздами, многих из которых уже нет.
