Контакты
Подписка
МЕНЮ
Контакты
Подписка

Dual EC – криптографический стандарт с лазейкой

Dual EC – криптографический стандарт с лазейкой

В рубрику "Криптография" | К списку рубрик  |  К списку авторов  |  К списку публикаций

Dual EC – криптографический стандарт с лазейкой

Мы рассмотрим историю генератора псевдослучайных чисел Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator), ставшего в свое время федеральным криптографическим стандартом в США и продвинутого в международные криптографические стандарты. Несмотря на огромное количество работ, содержащих его серьезнейшую критику, данный стандарт просуществовал как часть стандартов ANSI и ISO/IEC с 2006 по 2015 г. По всеобщему мнению криптографических экспертов (не подтвержденному, однако, на официальном государственном уровне), этот алгоритм содержит лазейку, позволяющую владельцу ключа к лазейке вычислять по выходу генератора его внутреннее состояние, а затем предсказывать вырабатываемые им числа.
Алексей
Жуков
Председатель совета Ассоциации “РусКрипто”
Александра
Маркелова
Технический директор ООО НТЦ “Альфа-Проект”, к.ф.-м.н.

Обстоятельства, сопровождавшие процесс утверждения этого алгоритма в качестве криптографического стандарта на национальном и международном уровне, а также роль АНБ в этом процессе лишь укрепляют убеждение, что в данном случае мы имеем дело с успешной реализацией давней идеи государственных структур США о внедрении лазеек в криптоалгоритмы, являющиеся государственными (а еще лучше – международными) криптографическими стандартами [1].

История Dual EC: появление, стандартизация, модификация, отмена

Следует сразу сказать, что мы приводим историю Dual_EC_DRBG (Dual EC – для краткости) в той степени, в которой она известна общественности, т.е. пользуясь материалами, опубликованными в открытой печати. Сам алгоритм был впервые представлен на семинаре NIST по генерации случайных чисел в 2004 г. у как "теоретико-числовой генератор", использующий вычисления в группе точек эллиптической кривой [2].

АНБ – Агентство национальной безопасности США (National Security Agency – NSA) – специализированный орган в системе министерства обороны США, осуществляет разведывательные функции в электронных коммуникационных сетях, а также защиту американских правительственных и ведомственных закрытых линий связи. АНБ располагает широко разветвленной сетью пунктов подслушивания, радиоперехвата и радиопеленгации, расположенных во многих районах земного шара.

Надо сказать, что генераторы случайных и псевдослучайных чисел (далее – ГСЧ и ГПСЧ) являются важнейшими криптографическими примитивами, от свойств которых во многом зависит стойкость всей криптографической системы. Обычным требованием к таким генераторам является статистическая неотличимость порожденных ими последовательностей от случайных равновероятных последовательностей. Для проверки этих свойств разработаны многочисленные статистические тесты. Для криптографических приложений от ГПСЧ требуется еще и "непредсказуемость" – невозможность для нарушителя предсказывать очередной знак выходной последовательности, порождаемой генератором с вероятностью, существенно отличной от равновероятной, даже если ему известны все предыдущие знаки этой последовательности. Это подразумевает, что нельзя определить внутреннее состояние ГПСЧ на основе его выхода.

С самого начала было ясно, что скорость работы нашего генератора является достаточно низкой за счет вычислений на эллиптических кривых, но зато его стойкость, по утверждению докладчика, Дона Джонсона, существенно выше альтернатив, поскольку базируется на задаче дискретного логарифмирования в группе точек эллиптической кривой. Тогда же алгоритм Dual EC появился и в проекте стандарта ANSI X9.82 [3].

Однако вскоре были опубликованы исследования, доказывающие, что генератор Dual EC подвержен различительной атаке (distinguishing attack) [4], [5], т.е. вырабатываемые им последовательности чисел статистически отличимы от истинно случайных. Обычно такого рода уязвимости считаются критичными для ГПСЧ и являются причиной его исключения из криптографических стандартов, но не в этот раз…

Комитет по стандартизации проигнорировал работы, критикующие Dual EC, сославшись на формальное превышение сроков их подачи. При этом некоторые другие, менее существенные, замечания, поданные позже срока, все-таки были учтены. В результате в июне 2006 г. в пакете с другими генераторами псевдослучайных чисел Dual EC был принят NIST в качестве криптографического стандарта [6].

Джон Келси – Дону Джонсону: "Знаете ли вы, откуда взялось Q в Dual_EC_DRBG?"
Дон Джонсон – Джону Келси: "P = G.Q, по сути, открытый ключ для некоторого случайного закрытого ключа. Кроме того, Q может быть получена как еще одна каноническая точка G, но АНБ отвергло эту идею и запретило мне это публично обсуждать…"

Одновременно с этим алгоритм Dual EC стал частью международного стандарта – стандарта ISO 18031:2005. И здесь не обошлось без давления со стороны властей США. К лету 2003 г. подкомитет 27 объединенного технического комитета 1 ISO/IEC (Joint Technical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 27, IT Security techniques) занялся процессом стандартизации генераторов случайных чисел. При этом изначальная версия стандарта ISO, за которую проголосовало 19 стран из 24, не содержала генератора Dual EC. Было получено более 150 комментариев, но большинство из них были незначительными исправлениями и пояснениями. Участники голосования высказывали те или иные замечания и уточнения к проекту стандарта, комментируя его отдельные пункты и формулировки. Со стороны США не было конкретных замечаний, был только общий комментарий "ко всему документу", в котором говорилось, что текущая версия стандарта "не обладает достаточной глубиной"1. В качестве альтернативы ISO был предложен американский стандарт ANSI X9.82, как "более тщательно прорабо-танный"2. В результате США, по сути, навязали ISO свою версию стандарта, включающую Dual EC, которая в итоге и была принята [7].

Параллельно с процессом продвижения Dual EC шел процесс его критики со стороны независимых экспертов. В августе 2007 г. на конференции CRYPTO-2007 сотрудники Microsoft Дэн Шумов и Нильс Фергюсон продемонстрировали возможность существования лазейки в Dual EC [8]. В этом алгоритме при генерации случайных чисел используются две точки эллиптической кривой: P и Q. С помощью точки P задается внутреннее состояние генератора, а точка Q используется для вычисления выхода генератора. Если известна связь между точками P и Q (т.е. такое число d, что Q = d • P), то по нескольким известным значениям выхода можно вычислить текущее внутреннее состояние генератора, а значит, можно предсказать все последующие генерируемые им числа3.

В стандарте точки P и Q заданы. Поскольку задача дискретного логарифмирования является вычислительно трудной, то найти такое d, что Q = dP, на данный момент невозможно. Но дело в том, что эти точки заданы авторами стандарта, а они могли изначально выбрать число d, а затем вычислить точку Q как dP. Подобное предположение подтверждается и следующей перепиской между Дж. Келси и Д. Джонсоном, которую приводят авторы статьи [18], посвященной истории Dual EC (рис. 1). По сути, в ней говорится, что мы имеем дело с асимметричным SETUP-механизмом в структуре Dual EC, при этом Q играет роль открытого ключа SETUP-механизма, а d – роль секретного ключа [1].


Таким образом, наличие указанной скрытой лазейки в алгоритме Dual EC в принципе возможно, хотя ни доказать, ни опровергнуть ничего нельзя.

Из приведенной выше переписки видно еще одно немаловажное обстоятельство – роль АНБ в разработке и принятии стандарта Dual EC. Ни в одном из первоначальных материалов, посвященных нашему стандарту, не указан его автор или разработчик. Официальная публикация NIST, содержащая, наряду с другими генераторами псевдослучайных чисел, и алгоритм Dual EC, имеет официальных авторов – Элейн Баркер (Elaine Barker) и Джон Келси (John Kelsey), оба сотрудники NIST. В то же время существуют многочисленные подтверждения того, что ни Келси, ни Баркер не были разработчиками Dual EC, более того, они даже не чувствовали себя компетентными давать комментарии по поводу Dual EC, отсылая по этому поводу к сотрудникам АНБ, например, переписка между Э. Баркер и М. Кампанья (рис. 2), приведенная в [18].


Вскоре после конференции, в ноябре 2007 г., вышла разгромная статья Брюса Шнайера [9], в которой он советовал ни при каких обстоятельствах не использовать генератор Dual EC, тем более что и в стандартах NIST, и в ISO есть альтернативы.

Другой способ избежать возможной закладки в Dual EC – это выработать собственные точки P и Q и запускать генератор с этими новыми значениями. Формально NIST разрешил использование альтернативных (сгенерированных пользователем) P и Q, но на практике оказалось, что это существенно усложняет разработчикам сертификацию соответствующего продукта на соответствие FIPS-140-2 [11].

Национальный институт стандартов и технологий США – (англ. The National Institute of Standards and Technology, NIST). Официальная задача института – "продвигать инновационную и индустриальную конкурентоспособность США путем развития наук об измерениях, стандартизации и технологий с целью повышения экономической безопасности и улучшения качества жизни". Вместе с Американским национальным институтом стандартов (ANSI) участвует в разработке стандартов и спецификаций к программным решениям, используемым как в государственном секторе США, так и имеющим коммерческое применение. https://ru.wikipedia.org

После разоблачений Эдварда Сноудена у криптографического сообщества не осталось сомнений, что история Dual EC была частью масштабных программ BULLRUN и SIGINT АНБ по ослаблению криптографических стандартов и встраиванию лазеек в коммерческие продукты [12]. Годовой бюджет АНБ на подобные мероприятия составлял порядка $250 млн.

Некоторые аффилированные с АНБ математики продолжали отрицать возможность практического использования лазейки в Dual EC. "Их глаза широко открываются, когда я говорю о том, как трудно на самом деле получить информацию, которую они предполагают получить такими атаками... Я бросил им вызов: предложил сгенерировать свои собственные параметры и показать мне, что они в действительности смогут восстановить таким способом. Никто пока этого не сделал"4,– заявил Ричард Джордж (Richard George) в мае 2014 г. [18]. Заметим, что сам Ричард Джордж работал в АНБ с 1970 по 2011 г., а затем перешел в RSA Security, где курировал финансируемые правительством проекты [15].

Вызов Ричарда Джорджа был принят группой математиков, и уже в августе 2014 г. они продемонстрировали реальную (а не только теоретическую) эксплуатацию уязвимости Dual EC [16]. Их статья показала, как вычислять ключи протокола TLS, используя знание связи между точками P и Q (число d, "ключ лазейки").

Вскоре после этого RSA Security выпустила рекомендации для пользователей библиотеки BSAFE: не использовать генератор Dual EC.

В июне 2015 г. вышла новая версия рекомендаций NIST [17], в которой алгоритм Dual EC уже отсутствовал. Конец истории… Точка.

Описание алгоритма

Пусть задана эллиптическая кривая в форме Вейерштрасса:

где p > 3 – простое число, точка P = (Px, Py) – порождающий элемент циклической подгруппы группы точек эллиптической кривой, r – порядок этой подгруппы, Q = (Qx, Qy) – некоторая ненулевая точка той же подгруппы, отличная от P.5

В приложении А.1 стандарта NIST версии 2006 г. [6] были определены фиксированные значения параметров p, r, a, b, Px, Py, Qx, Qy для кривых P-256, P-384, P-521.

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

Q = dP.6

Основная идея

Общая схема работы генератора Dual EC показана на рис. 3.


Значения s и r задают, соответственно, внутреннее состояние генератора и вырабатываемые псевдослучайные биты. В упрощенном варианте, если дополнительная строка additional_input не задана, то

где x(•) – выбор x-координаты точки эллиптической кривой, а φ(•) – представление элемента поля в виде битовой строки (в формате Big Endian старшие биты записываются первыми).

Элейн Баркер – Мэттью Кампанья, копия Джону Келси: "Мэтт, Джон – не тот человек, которому можно задавать вопросы касательно Dual_EC_DRBG. Я переадресовала ваше письмо Дебби Уоллнеру и Бобу Каркоска из АНБ. Элейн".

В силу сложности задачи дискретного логарифмирования обновление внутреннего состояния по формуле (1) должно обеспечить стойкость генератора к обратному перебору (Backtracking Resistance). Последнее означает, что даже если в какой-то момент скомпрометировано внутреннее состояние генератора, то все равно невозможно восстановить предыдущие внутренние состояния и получить ранее выработанные случайные числа.

Блок ExtractBits извлекает из пришедшей на вход битовой строки правые outlen бит. При этом значение outlen должно делиться на 8 и быть не больше, чем 240 для кривой P-256, 368 для P-384 и 504 для P-521. То есть от x-координаты точки siQ берутся младшие outlen бит ("отбрасываются" как минимум два старших байта).

Презентация генератора [2] обосновывала необходимость использования операции ExtractBits тем, что иначе генератор становится предсказуемым в некоторых ситуациях. Дело в том, что количество точек эллиптической кривой приблизительно равно размерности поля: по теореме Хассе [20], порядок m абелевой группы точек эллиптической кривой удовлетворяет неравенству

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

откуда следует, что количество значений, не являющихся x-координатами, оценивается как

SIGINT – радиоэлектронная разведка (англ. Signals Intelligence), включает перехват каналов связи. BULL-RUN – секретная программа по дешифрованию онлайн-коммуникаций и данных, которая осуществляется Агентством национальной безопасности США.

Мы видим, что почти половина значений не являются координатами точек эллиптической кривой, т.е. никогда не будут выработаны генератором без усечения, а следовательно такой генератор вырабатывает не всевозможные битовые строки, а только какое-то подмножество. По утверждению авторов алгоритма [2], отсечение 13 старших (левых) бит позволяет избавиться от этого недостатка, поскольку "валидные" и "невалидные" значения x распределены достаточно хаотично (к сожалению, точного объяснения, откуда взялось число 13, нигде не приводилось, как и многие другие пояснения к предложенной конструкции).

Итак, пусть необходимо выработать requested_number_of_bits бит, генератор ранее инициализирован (s – внутреннее состояние), на вход подана строка additional_input (если не задана, то считаем additional_input = 0).

Обозначим за TRUNC_R(a, len) – правые (младшие) len бит строки a, а за TRUNC_L(a, len) – левые (старшие) len бит строки a. Тогда алгоритм работает следующим образом:

1. temp = Null;
2. s = s ⊕ additional_input;
3. s = φ (x(sP));
4. r = φ (x(sQ));
5. temp = temp||TRUNC_R(r, outlen);
6. Если len(temp) < requested_number_of_bits, то перейти к 3;
7. returned_bits = TRUNC_L(temp, requested_number_of_bits).

В данном описании мы опустили некоторые шаги, связанные с переинициализацией генератора, проверкой корректности всех длин данных, дополнительной обработкой additional_input.

Заметим, кстати, что при выработке достаточно длинной битовой строки additional_input используется только в первом блоке данных. К этому аспекту мы еще вернемся, когда будем рассматривать структуру лазейки в данном алгоритме.

Модификация алгоритма

В обновленной версии стандарта NIST 2012 г. алгоритм Dual EC был немного модифицирован [21]. В конце алгоритма был добавлен еще один шаг:

т.е. было сделано дополнительное обновление внутреннего состояния. В комментариях к изменениям необходимость данного изменения объяснена "обеспечением стойкости к стойкости к раскрутке генератора в обратную сторону"7. Однако более вероятна версия, что данное исправление делает лазейку в алгоритме более универсальной, об этом мы расскажем чуть позже.

Лазейка с защитой

Сама математическая структура алгоритма Dual EC позволяет легко спроектировать лазейку. Действительно, так как P – порождающий элемент подгруппы группы точек эллиптической кривой, а Q – нетривиальный элемент этой же подгруппы, то существует число d:

Далее будем называть d ключом лазейки. Мы покажем, что знание d помогает вычислять внутреннее состояние генератора на основе полученной битовой строки. Напомним, что r – порядок подгруппы, порожденной точкой P. Пусть e задается формулой:

Тогда

Для начала рассмотрим схему без additional_input. Из формул (1) и (2) следует:

где Si+1 = siP и Ri = siQ – соответствующие точки эллиптической кривой.

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

Правда, в алгоритме Dual EC известна только часть x-координаты точки Ri. Тем не менее всю точку Ri можно восстановить перебором.

Шумов и Фергюсон [8] предложили следующий алгоритм для подбора "кандидатов" на внутренние состояния.

Дано: oj – блок выходной битовой строки ключевого генератора.

Найти: множество возможных внутренних состояний

Если y = Vz mod p существует, то A = (x, y) - точка кривой, тогда

Мощность множества Σ приблизительно равна 215, поскольку всего есть 216 вариантов выбора, а квадратичными вычетами будет примерно половина из значений x = u|oj. Напомним, что нахождение числа y выполняется за полиномиальное время [22].

Общий алгоритм использования лазейки следующий:

  • запросить outlen + δ псевдослучайных бит;
  • на основе первых outlen бит сформировать множество Σ возможных внутренних состояний генератора;
  • для каждого s Є Σ вычислить следующие δ бит и сравнить с теми, которые выдал генератор.

Шумов и Фергюсон провели эксперимент для кривой P-256, заменив точку Q на вычисленную ими точку Q2 = d2P. При генерации 32 байт (т.е. 5= 16) внутреннее состояние генератора определялось всегда однозначно.

Возможности модификации Dual EC для защиты от лазеек

Самое радикальное и простейшее противодействие - не использовать "напрямую" в качестве выхода генератора координаты точки Ri, а каким-то образом преобразовывать их так, чтобы по выходу было затруднительно восстановить Ri, например "обрезать" x-координату точки Ri на большее число бит, переставлять выходные биты и др.

Шумов и Фергюсон предложили две возможные модификации алгоритма Dual EC, которые не давали бы возможности использовать подобного рода лазейку.

В сентябре 2013 г. NIST выпустил рекомендации по отказу от использования Dual EC [13], но при этом алгоритм все еще оставался частью стандарта и некоторые криптопродукты использовали его. В декабре 2013 г. в документах, обнародованных Сноуденом, была обнаружена информация, что компания RSA Security получила от АНБ $10 млн за использование алгоритма Dual EC в криптобиблиотеке BSAFE в качестве основного генератора псевдослучайных чисел [14]. RSA не подтвердило и не опровергло эту информацию, сообщив, что они "всегда действуют в интересах своих клиентов". АНБ от комментариев, разумеется, воздержалось.

Первая - уже упомянутое выше усечение x-координаты более чем на 16 бит. Имеет смысл брать половину бит x-координаты. В этом случае составление множества Σ и перебор всех его кандидатов становится вычислительно сложной задачей. Отметим, что стандарт NIST с первой же редакции [6] (п. 10.3.1.4) запрещает подобную модификацию "из соображений производительности".

Вторая рекомендация Шумова и Фергюсона - вырабатывать новую случайную точку Q’, собственную для каждого экземпляра генератора. Такой метод надежен, только если пользователь сам получает точку Q’ каким-либо доверенным способом, не связанным с генератором, где эта точка будет использоваться. В противном случае разработчик может заложить в алгоритм выработку каким-то специализированным образом ключа лазейки, а затем уже вычислять Q’ как Q’ = d’P.

Приложение А.2 описывает возможность генерации собственных P и Q на тех же эллиптических кривых, но, как указывалось выше, при такой реализации генератора становится невозможной сертификация криптографического модуля.

Дополнительно отметим, что в первоначальной версии Dual EC защитой от лазейки было использование additional_input (см. рис. 3), поскольку внутреннее состояние Si +1 вычислялось из соотношения Si+1 = siP. Однако, если подано ненулевое значение additional_input, то

т.е. формула (3) перестает быть верной. Сложность взлома базируется на том, что побитовое сложение происходит с неизвестной пока еще величиной si.

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

Практическая атака на Dual EC

В августе 2014 г. была продемонстрирована практическая эксплуатация лазейки и оценена стоимость такой атаки [16], [18]. Авторы исследовали четыре варианта реализации Dual EC: OpenSSL-FIPS, SChannel (Windows), а также версии C/C++ и Java библиотеки BSAFE RSA.

Атака базируется на предположении, что атакующий (владеющий к тому же ключом лазейки) знает случайные биты, выработанные генератором, и после этого может вычислить внутреннее состояние генератора и предсказывать все его дальнейшие вычисления. Атака была продемонстрирована на широко используемом протоколе TLS. Данный протокол состоит из нескольких частей, одной из которых является так называемый протокол рукопожатия (TLS handshake), упрощенная схема которого представлена на рис. 4.


Как видно из рис. 4, клиент и сервер обмениваются случайными числами – именно этой информации может быть достаточно для восстановления внутреннего состояния генератора. Авторы исследования показали, что в TLS передается достаточное для атаки количество случайных чисел. На первый взгляд, вырабатывается всего лишь 28 байт, но идентификатор сеанса – это тоже случайная битовая последовательность, генерируемая в большинстве случаев (но не всегда) тем же алгоритмом Dual EC.

Американский национальный институт стандартов (англ. American National Standards Institute, ANSI) осуществляет надзор за разработкой и использованием стандартов путем аккредитации процедур организаций, разрабатывающих стандарты. ANSI также определяет конкретные стандарты как американские национальные стандарты, или ANS. – https://ru.wikipedia.org

Поскольку для заданной в стандарте Dual EC точки Q значение дискретного логарифма (т.е. ключа лазейки) неизвестно, то при моделировании атаки было сгенерировано случайное число d’ и вычислена точка Q’ = d’P. Далее было необходимо заменить Q на Q’ во всех исследуемых библиотеках. Поскольку OpenSSL имеет открытый исходный код, то подмена точки в OpenSSL-FIPS была простой задачей. Для библиотек SChannel, BSAFE-Java и BSAFE-C потребовался реверс-инжиниринг.

В процессе исследования выяснилось, что библиотека OpenSSL-FIPS постоянно выдавала ошибку при самодиагностике, если была сконфигурирована для использования Dual EC, из чего можно предположить, что никто никогда не использовал данный функционал. Авторы исследования исправили эту ошибку и в дальнейших экспериментах использовали модифицированную версию библиотеки OpenSSL-fixed.

На табл. 1 показано время атаки на протокол TLS при использовании различных криптобиблиотек. Для атаки брали 4-узловой вычислительный кластер на базе 4-ядерных AMD Opteron 6276 (Bulldozer). Каждый из узлов имел 256 Гбайт оперативной памяти, а связь между ними обеспечивалась Infiniband. Авторы исследования отмечают, что реально для атаки достаточно всего 1 Гбайт оперативной памяти на узел и не требуется такой быстрой связи между узлами. Время атаки зависело от того, насколько длинную случайную последовательность может сразу получить злоумышленник, прослушивающий канал, в частности, от того, используется ли Dual EC для генерации идентификатора сеанса.


Атака на BSAFE-C оказалась самой легкой, поскольку идентификатор сеанса вырабатывается с помощью Dual EC, т.е. атакующий сразу имеет достаточное количество информации для взлома лазейки.

Помимо деятельности в области стандартизации в США, ANSI отстаивает политическую и техническую позицию США в международных организациях по стандартизации. ANSI является официальным представителем США в двух основных международных организациях по стандартизации – Международной организации по стандартизации (the International Organization for Standardization – ISO) и Международной электротехнической комиссии (the International Electrotechnical Commission – IEC). ANSI участвует почти во всей технической программе ISO и IEC и управляет многими ключевыми комитетами и подгруппами. Во многих случаях стандарты США передаются в ISO и IEC через ANSI, где они полностью или частично принимаются в качестве международных стандартов. https://ru.wikipedia.org

В BSAFE-Java идентификатор вырабатывается другим способом, поэтому первый вызов Dual EC – это 28 байт случайного числа в протоколе рукопожатия, после которых вырабатываются 32 байта для эфемерального ключа Диффи-Хэллмана. На основе переданных 28 байт требуется сделать 232 попыток, проверяя результат по открытому эфемеральному ключу.8

Библиотека SChannel при генерации идентификатора сеанса использует Dual EC, но преобразует результат некоторым образом, скрывающим от наблюдателя результат работы Dual EC. Это усложняет восстановление внутреннего состояния, но не делает его невозможным. Авторы исследования рассмотрели два случая: SChannel-I, если злоумышленнику известны данные предыдущих протоколов рукопожатия (Handshake), или же SChannel-II, когда атака проводится в пределах одного сеанса.

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

OpenSSL-fixed-I предполагает, что злоумышленник знает additional_input.

В случае OpenSSL-fixed-II злоумышленник знает значение счетчика (например, он атакует первое же соединение, когда счетчик равен 0) и идентификатор процесса (зная особенности нумерации и порядок запуска процессов в системе). Злоумышленнику остается пересчитать текущее время, заданное в секундах, в микросекунды, на это требуется 1 млн попыток.

В последнем случае, когда ни счетчик, ни идентификатор процесса не известны, требуется время в 2k раз большее времени атаки OpenSSL-fixed-II, поскольку требуется угадать k-бит.

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

Заключение

Как было отмечено ранее, работа [16] поставила точку в истории Dual EC, поскольку продемонстрировала не только теоретическую, но и практическую возможность использования встроенной в алгоритм лазейки.

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

В то же время эта история наглядно демонстрирует упорство, с которым спецслужбы готовы продвигать необходимые им стандарты и реализации ослабленных алгоритмов, невзирая на прямые обвинения со стороны экспертного сообщества. Эта история демонстрирует также серьезную зависимость международных институтов стандартизации (а уж тем более – национальных институтов стандартизации США) от спецслужб США: необходимые последним стандарты принимаются, невзирая на то, что ведущие математики, криптоаналитики, специалисты по информационной безопасности в один голос заявляют о ненадежности таких стандартов. История алгоритма Dual EC и его бесславный конец – грязное пятно на репутации солидных (во всяком случае, до сей поры) организаций – NIST, ISO.

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

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

Не исключено, что вскоре точка в истории Dual EC превратится в многоточие...

___________________________________________
1 We feel that this document is lacking sufficient depth in many areas and simply is not developed enough to be an ISO standard… [10].
2 We do feel that ANSI X9.82 Random Bit Generation standardization work is much further developed and should be used as the basis for this ISO standard [10].
3 Детально принцип работы генератора DUAL_EC_DRBG и механизм лазейки будет разобран в разделе 2.
4 “Their eyes open wide when I talk about how how hard it is to really get the information they assume they just get to attack this thing... I’ve challenged any of them to actually generate their own parameters and show me that in real life they can recover that. No one has done it yet" [18].
5 Слово Dual в названии алгоритма объясняют использованием в его работе двух точек.
6 В работе алгоритма Dual EC задействованы вычисления в группе точек эллиптической кривой [20], где в силу аддитивной записи групповой операции степень элемента P-группы превращается в его кратное n • P или короче – nP, а задача дискретного логарифмирования по основанию P принимает вид: для данного Q найти такое n, что nP = Q.
7 Provide Backtracking Resistance [16].
8 Эфемеральными (или разовыми) ключами протокола Диффи-Хеллмана называют случайные числа, участвующие в вычислениях, производимых в рамках этого протокола. Открытыми эфемеральными ключами называют информацию, которой обмениваются участники протокола по открытому каналу.

Литература

Опубликовано: Журнал "Information Security/ Информационная безопасность" #4, 2019
Посещений: 884

Приобрести этот номер или подписаться
  Автор

Алексей Жуков

Алексей Жуков

Председатель совета директоров ассоциации “РусКрипто", к.ф.-м.н., доцент, МГТУ им. Н.Э. Баумана

Всего статей:  6

  Автор

Александра Маркелова

Александра Маркелова

Технический директор ООО “НТЦ Альфа-Проект”, к. ф.-м. н.

Всего статей:  2

В рубрику "Криптография" | К списку рубрик  |  К списку авторов  |  К списку публикаций