Кивино гнездо: Ключевые слабости
АрхивКивино гнездоЦиники от криптографии всегда говорили: если в столь распространённой криптосистеме, как RSA, до сих пор не нашли дефектов, значит, просто плохо искали. Теперь вот поискали как следует – и действительно нашли.
В августе нынешнего года в калифорнийском городке Санта-Барбара пройдёт международная криптографическая конференция CRYPTO 2012, дающая своего рода срез текущего состояния дел в этой области прикладной математики. И хотя до начала мероприятия остаётся ещё полгода, уже сегодня можно с уверенностью сказать, какая из тем обсуждения будет среди самых горячих.
Прогнозировать это несложно, потому что одна из исследовательских работ, намеченных для доклада на CRYPTO, опубликована уже сейчас и сразу же вызвала заметный резонанс. Ибо то, что исследователям – команде криптографов из Европы и США – удалось обнаружить, для большинства специалистов от академической науки оказалось, выражаясь поделикатнее, сильной неожиданностью.
Для начала имеет смысл подоходчивее объяснить, что же за результаты удалось получить команде исследователей, которую возглавляли известный голландский математик-криптограф Арьен Ленстра (Arjen K. Lenstra) и независимый калифорнийский криптоэксперт Джеймс Хьюз (James P. Hughes). В настоящее время Ленстра является профессором Лозаннского федерального политехникума (École Polytechnique Fédérale de Lausanne), так что все остальные криптографы - соавторы этой большой работы также представляют данный швейцарский вуз.
Целью исследования, занявшего в общей сложности около трёх лет, являлся тщательный аналитический обзор той необъятной массы криптоключей, что повсеместно применяются ныне в реальной жизни. То есть учёные кропотливо собрали из интернет-баз все те ключи и сертификаты, что по определению предполагаются общедоступными и составляют основу криптографии с открытым ключом.
Криптосхемы такого рода, обеспечивающие засекреченную связь для совершенно незнакомых и никогда прежде не общавшихся сторон, ныне повсеместно используются по всему миру для онлайновых покупок, в банковских операциях, для защиты электронной почты и всех прочих интернет-сервисов, подразумевающих защиту информации и приватности пользователей. И именно здесь при тщательном анализе ключей удалось обнаружить неожиданную и весьма серьёзную слабость, присущую практически всем криптосистемам такого рода, но в первую очередь RSA – как в силу конструктивных особенностей этого алгоритма, так и по причине его популярности.
Именно RSA используется для генерации сертификатов протокола SSL, повсеместно применяемого для шифрования соединений в интернете. Для того чтобы вся эта система работала, лежащий в основе стойкости RSA ключевой элемент под названием "модуль" должен быть произведением двух очень больших простых чисел, причём для каждого конкретного ключа эти числа должны быть строго уникальными.
После анализа 7,1 миллиона ключей аналитиками было установлено, что сравнительно небольшая их доля – 27 тысяч, или примерно 0,4 процента, – имеют общий простой "фактор" или делитель с другими ключами-числами. Это означает, что с криптографической точки зрения числа оказываются очень слабыми. Иначе говоря, выявившие такого рода ключи аналитики могут их быстро взломать, а значит, то же самое способен сделать и кто угодно ещё.Выходит, что стойкость криптографии с открытым ключом составляет не 100процентов, а лишь 99,6. Казалось бы, не такой уж плохой результат для реальной защиты информации. Но аналитики оценивают этот итог существенно иначе. Потому что, согласно теоретическим расчётам, 0,4 процента никудышных ключей не должны были появиться.
Цитируем одно из интервью Джеймса Хьюза: "Факт заключается в том, что если бы эти числа-ключи имели ту энтропию, которая для них предполагается в теории, то вероятность даже одного-единственного из такого рода событий (совпадение факторов) для семи миллионов ключей должна быть ничтожно малой... Мы считаем, что всё это довольно необычно"...По свидетельству Хьюза, в тех случаях, когда генерация ключей делается правильно, для случайного числа-ключа длиной 1024 бита теоретически понадобилось бы сгенерировать ещё 2200 других ключей, прежде чем будут исчерпаны прочие множители-факторы и появится повторение. Гигантское количество 2200, для сравнения и примерного представления о его размерах, можно иначе (приближённо) записать как 1060. Если же для каждого из семи миллиардов жителей планеты ежесекундно вырабатывать по одному такому ключу, то даже за сто лет общее число сгенерированных ключей будет измеряться числом с шестнадцатью нулями. А здесь этих нулей шестьдесят.
Это странно с математической точки зрения, но в действительности дело обстоит, похоже, даже круче. Хотя основная масса всех аналитических усилий команды была сосредоточена на (общераспространённых ныне) ключах длиной 1024 бита, в поле их зрения попадали и более длинные 2048-разрядные ключи. И хотя в теории столь огромные числа должны предоставлять просто-таки невообразимо гигантское пространство энтропии, напрочь исключающее возможности повторения множителей, многочисленные ключи с общими факторами выявлены и здесь.
Но и это ещё не всё. Аналогичные нынешним исследования проводились и ранее, правда, на меньшем количестве ключей. Исследованный ныне массив из семи миллионов – это тоже далеко не все применяемые в мире ключи. Очень важным новым открытием стал такой факт: процентная доля ключей, для которых установлено, что они сгенерированы с помощью неуникальных множителей, скорее всего, будет возрастать и далее по мере того, как будут становиться доступными для анализа ещё большие количества ключей.
Доля 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 таких модулей скопом – это уже статистика. Первое событие из этого ряда – всё ещё недостижимая цель для академического сообщества. А вот второе событие – это своего рода малоприятное предупреждение, ещё раз подчеркивающее, сколь непростой является задача правильной генерации криптоключей в реальном мире... "
