Ключевые слабости

(Февраль 2012)

Циники от криптографии всегда говорили: если в столь широко и повсеместно распространенной криптосистеме, как RSA, до сих пор не нашли дефектов, ослабляющих схему, – значит, просто плохо искали. Теперь вот поискали как следует – и действительно нашли…

В августе нынешнего (2012) года, как обычно, в калифорнийском городке Санта-Барбара пройдет международная криптографическая конференция CRYPTO 2012, дающая своего рода срез текущего состояния дел в этой области прикладной математики. И хотя до начала мероприятия остаются еще чистых полгода, уже сегодня можно с уверенностью сказать, какая из тем обсуждения будет среди самых горячих.

Прогнозировать это несложно, потому что одна из исследовательских работ (eprint.iacr.org/2012/064.pdf), намеченных для доклада на  CRYPTO, опубликована уже сейчас и сразу же вызвала заметный резонанс. Ибо то, что там исследователям – команде криптографов из Европы и США – удалось нарыть, для большинства специалистов от академической науки оказалось, выражаясь поделикатнее, сильной неожиданностью.

Как отреагировали на новость криптографы из секретных спецслужб, в СМИ, конечно же, не сообщают. Однако крайне маловероятно, что и там реакция была аналогичной.

Впрочем, прежде, чем гадать о реакциях криптоаналитических разведслужб типа АНБ, для начала имеет смысл подоходчивее объяснить, что же за интересные результаты удалось получить команде исследователей, которую возглавляли известный голландский математик-криптограф Арьен Ленстра (Arjen K. Lenstra) и независимый калифорнийский криптоэксперт Джеймс Хьюз (James P. Hughes). В настоящее время Ленстра является профессором Лозаннского федерального политехникума (École Polytechnique Fédérale de Lausanne), так что все остальные  криптографы-соавторы этой большой работы также представляют данный швейцарский ВУЗ.

Целью исследования, занявшего у команды в общей сложности около трех лет, являлся тщательный аналитический обзор той необъятной массы криптоключей, что повсеместно применяются ныне в реальной жизни. То есть ученые кропотливо собрали из интернет-баз все те ключи и сертификаты, что по определению предполагаются общедоступными и составляют основу криптографии с открытым ключом.

Криптосхемы такого рода, обеспечивающие засекреченную связь для совершенно незнакомых и никогда прежде не общавшихся сторон,  ныне повсеместно используются по всему миру для онлайновых покупок, в банковских операциях, для защиты электронной почты и всех прочих интернет-сервисов, подразумевающих защиту информации и приватности пользователей.

И именно здесь при тщательном анализе ключей удалось обнаружить неожиданную и весьма серьезную слабость, присущую практически всем криптосистемам такого рода, но в первую очередь RSA – как в силу конструктивных особенностей этого алгоритма, так и по причине наиболее широкого его распространения.

RSA, в частности, является базовым криптоалгоритмом с открытым ключом, используемым для генерации сертификатов протокола SSL, повсеместно применяемого для шифрования визитов на конкретные веб-сайты. Для того, чтобы вся эта система работала, лежащий в основе стойкости RSA ключевой элемент под названием «модуль» должен быть произведением двух очень больших простых чисел, причем для каждого конкретного ключа эти числа должны быть строго уникальными.

Если же выражать суть результата, обнаруженного исследователями, с помощью голых цифр, то на первый взгляд опасность может показаться не слишком серьезной. После анализа 7,1 миллиона ключей аналитиками было установлено, что сравнительно небольшая их доля – 27 тысяч или  примерно 0,4% – имеют с другими ключами-числами общий простой «фактор» или делитель.

По существу это означает, что с криптографической точки зрения числа оказываются очень слабыми. Иначе говоря, выявившие такого рода ключи аналитики могут их быстро взломать, а значит то же самое способен сделать и кто угодно еще, повторив траекторию данного исследования.

Отсюда можно, в принципе, заявлять, что согласно новейшим результатам анализа стойкость криптографии с открытым ключом составила 99,6 %. Казалось бы, не такой уж плохой результат для реальной защиты информации. Но аналитики оценивают этот итог существенно иначе. Потому что согласно теоретическим расчетам, выявленных ими 0,4% никудышных ключей и близко появляться никак не должно.

Цитируя одно из интервью Джеймса Хьюза:

«Факт заключается в том, что если бы эти числа-ключи имели ту энтропию, которая для них предполагается в теории, то вероятность даже одного-единственного из такого рода событий (совпадение факторов) для 7 миллионов ключей должна быть ничтожно малой… Мы считаем, что все это довольно необычно»…

Если опять-таки пояснять необычность открытия с помощью цифр, то с этой стороны они выглядят так. По свидетельству Хьюза, в тех случаях, когда генерация ключей делается правильно, то для случайного числа-ключа длиной 1024 бита теоретически понадобилось бы сгенерировать еще 2²⁰⁰ других ключей, прежде чем будут исчерпаны прочие множители-факторы и появится повторение. Гигантское количество 2²⁰⁰, для сравнения и примерного представления о его размерах, можно иначе записать как 10⁶⁰. Если же для каждого из 7 миллиардов жителей планеты ежесекундно вырабатывать по 1 такому ключу, то даже за сто лет общее число сгенерированных ключей будет измеряться числом с 16 нулями. А здесь этих нулей 60…

Причем для математически явно странной ситуации с криптографией в реальной жизни ситуация на самом деле обстоит, похоже, даже еще круче. Хотя основная масса всех аналитических усилий команды была сосредоточена на (общераспространенных ныне) ключах длиной 1024 бита, в поле их зрения попадались и более длинные  2048-битовые ключи. И хотя в теории столь огромные числа должны предоставлять просто-таки невообразимо гигантское пространство энтропии, напрочь исключающее возможности повторения множителей, неоднократные случаи ключей с общими факторами выявлены и здесь.

Но и это еще не все. Аналогичные нынешним исследования проводились и ранее, правда, на меньшем количестве доступных для анализа ключей. Исследованный ныне массив из 7 миллионов – это тоже далеко не все из применяемых в мире ключей. Очень важным новым открытием стал такой факт: процентная доля ключей, для которых установлено, что они сгенерированы с помощью неуникальных множителей, скорее всего, будет возрастать и далее по мере того, как будут становиться доступными для анализа еще большие количества ключей.

Доля 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-модуля стала бы историческим событием. Однако факторизация 12720 таких модулей скопом – это уже статистика.

Первое событие из этого ряда – пока что все еще недостижимая цель для академического сообщества. А вот второе событие – это своего рода малоприятное предупреждение, еще раз подчеркивающее, сколь непростой является задача правильной генерации криптоключей в реальном мире…

#  #  #

[Несколько конкретных историй о том, до какой степени это непросто – правильно применять теоретически стойкую криптографию – можно найти в тектах «Хитрости крипторемесла» и «Неслучайные случайности».]