Журнал "Information Security/ Информационная безопасность" #4, 2019

Элейн Баркер – Мэттью Кампанья, копия Джону Келси: "Мэтт, Джон – не тот человек, которому можно задавать вопросы касатель- но Dual_EC_DRBG. Я пере- адресовала ваше письмо Дебби Уоллнеру и Бобу Кар- коска из АНБ. Элейн". SIGINT – радиоэлектрон- ная разведка (англ. Signals Intelligence), включает пере- хват каналов связи. BULL- RUN – секретная программа по дешифрованию онлайн- коммуникаций и данных, которая осуществляется Агентством национальной безопасности США. В сентябре 2013 г. NIST выпустил рекомендации по отказу от использования Dual EC [13], но при этом алгоритм все еще оставался частью стандарта и некото- рые криптопродукты исполь- зовали его. В декабре 2013 г. в документах, обнародо- ванных Сноуденом, была обнаружена информация, что компания RSA Security получила от АНБ $10 млн за использование алгоритма Dual EC в криптобиблиотеке BSAFE в качестве основного генератора псевдослучай- ных чисел [14]. RSA не под- твердило и не опровергло эту информацию, сообщив, что они "всегда действуют в интересах своих клиен- тов". АНБ от комментариев, разумеется, воздержалось. использование альтернативных (сгенерированных пользовате- лем) P и Q, но на практике ока- залось, что это существенно усложняет разработчикам сер- тификацию соответствующего продукта на соответствие FIPS- 140-2 [11]. После разоблачений Эдварда Сноудена у криптографического сообщества не осталось сомне- ний, что история 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 Secu- rity выпустила рекомендации для пользователей библиотеки BSAFE: не использовать гене- ратор Dual EC. В июне 2015 г. вышла новая версия рекомендаций NIST [17], в которой алгоритм Dual EC уже отсутствовал. Конец исто- рии… Точка. Описание алгоритма Пусть задана эллиптическая кривая в форме Вейерштрасса: y 2 = x 3 +ax = b mod p, где p > 3 – простое число, точка P = (P x , P y ) – порождаю- щий элемент циклической под- группы группы точек эллипти- ческой кривой, r – порядок этой подгруппы, Q = (Q x , Q y ) – неко- торая ненулевая точка той же подгруппы, отличная от P. 5 В приложении А.1 стандарта NIST версии 2006 г. [6] были определены фиксированные значения параметров p, r, a, b, P x , P y , Q x , Q y для кривых P-256, P-384, P-521. Стойкость генератора бази- руется на сложности решения задачи дискретного логариф- мирования в группе точек эллиптической кривой, т.е. на нахождении такого числа d, что Q = dP. 6 Основная идея Общая схема работы генера- тора Dual EC показана на рис. 3. Значения s и r задают, соот- ветственно, внутреннее состоя- ние генератора и вырабатывае- мые псевдослучайные биты. В упрощенном варианте, если дополнительная строка additio- nal_input не задана, то s i = φ (x(s i - 1 P)), (1) r i = φ (x(s i Q)), (2) где x(•) – выбор x-координаты точки эллиптической кривой, а φ (•) – представление элемента поля в виде битовой строки (в формате Big Endian старшие биты записываются первыми). В силу сложности задачи дис- кретного логарифмирования обновление внутреннего состоя- ния по формуле (1) должно обеспечить стойкость генера- тора к обратному перебору (Backtracking Resistance). Последнее означает, что даже если в какой-то момент ском- прометировано внутреннее состояние генератора, то все равно невозможно восстано- вить предыдущие внутренние состояния и получить ранее выработанные случайные числа. Блок ExtractBits извлекает из пришедшей на вход битовой строки правые outlen бит. При этом значение outlen должно делиться на 8 и быть не больше, чем 240 для кривой P-256, 368 для P-384 и 504 для P-521. То есть от x-координаты точки s i Q берутся младшие outlen бит ("отбрасываются" как минимум два старших байта). Презентация генератора [2] обосновывала необходимость использования операции ExtractBits тем, что иначе гене- ратор становится предсказуе- мым в некоторых ситуациях. Дело в том, что количество точек эллиптической кривой приблизительно равно размер- ности поля: по теореме Хассе [20], порядок m абелевой группы точек эллиптической кривой удовлетворяет неравенству Из уравнения Вейерштрасса легко понять, что если точка (x, y) лежит на эллиптической 38 • ТЕХНОЛОГИИ Рис. 2. Электронная переписка между Э. Баркер и М. Кампанья, от 02.03.2006 [18] 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.