1.0 Введение
В 2006 году АНБ скрыла в криптографическом стандарте Dual EC DRBG математический бэкдор. Агентство отрицало его наличие восемь лет. Затем утечки Сноудена подтвердили его существование.
Двойные эллиптические кривые (Dual Elliptic Curve) используются как безопасные генераторы случайных чисел (RNG). Математический бэкдор позволял правительству США расшифровывать SSL-трафик Интернета (Green 2013)1.
Эта статья будет технически глубоким исследованием для программистов. Мы реализуем и исходную правительственную научную статью (SP 800-90 2006)2, и бэкдор, обнаруженный исследователями Microsoft (Shumow & Ferguson 2007)3.
На моём домашнем компьютере для взлома 28 байт (не бит) при помощи этого бэкдора требуется 2 минуты. Представьте, какой объём Интернет-трафика правительство США могло расшифровывать при помощи суперкомпьютеров Министерства обороны.
1.1 Почему важны атаки на RNG
Математический бэкдор Dual EC позволил правительству США прослушивать Интернет-трафик. Вот ещё несколько примеров интересных атак, использующих небезопасные генераторы случайных чисел (RNG):
В 2009 году благодаря генерации куки неслучайным RNG были похищены аккаунты пользователей Hacker News. (Dfranke 2009)4
В 2013 году изъяны RNG в Android были популярным вектором атак на биткойн-кошельки. (Goodin 2013)5
2.0 Кодирование RNG
Авторы NIST SP 800-90 представили множество алгоритмов генераторов псевдослучайных чисел (PRNG), но посвятили Section 10.3 статьи алгоритму Dual EC.
*в статье Dual EC DRBG обозначает Dual Elliptic Curve Deterministic Random Bit Generator.
Dual EC генерирует случайные биты при помощи эллиптических кривых. Согласно статье, мы должны использовать одну из проверенных NIST эллиптических кривых. Я буду использовать P256 из библиотеки Python fastecdsa.
2.1 Импорты и установки PIP
Установим fastecdsa при помощи команды pip:
pip install 'fastecdsa>=1.4.1'Затем импортируем библиотеку следующим образом:
2.2 Собираем класс Dual EC
Нам нужно определить две точки эллиптической кривой P и Q. Также нужно задать исходное состояние нашего RNG. Всё это можно поместить в класс:
class DualEC():
def __init__(self, seed, P, Q):
self.seed = seed # Исходное целочисленное состояние RNG
self.P = P # Первая точка эллиптической кривой (публичный параметр)
self.Q = Q # Вторая точка эллиптической кривой (может быть выбрана со злоумышленными целями)Логика RNG довольно проста:
Умножаем наше порождающее значение (seed) на P.
Берём координату X результата и принимаем её в качестве нового seed.
Умножаем новое внутреннее состояние на Q и берём координату результата X.
Возвращаем усечённый результат r.
Для реализации этой логики можно написать функцию GenerateBits:
def GenerateBits(self):
t = self.seed
s = (t * self.P).x # Умножаем seed на P и берём координату X, чтобы получить новое состояние
self.seed = s # Обновляем внутреннее состояние
r = (s * self.Q).x # Умножаем новое состояние на Q и берём координату X, чтобы получить результат
return r & (2**(8 * 30) - 1) # Усекаем до 30 байтов (240 бит)К концу этого раздела ваш класс DualEC должен напоминать следующее:
3.0 Кодируем бэкдор
Согласно данным исследователей, обнаруживших бэкдор, проблема алгоритма Dual EC заключается в значении Q. Точка Q — это константа, представленная в приложении NIST SP 800-90 (2006), но на самом деле никто не знает, откуда она взялась (Schneier 2007)6.
Мы знаем, что P — это генератор кривой. НО... что насчёт Q?
Shumow & Ferguson (2007) выяснили, что можно легко подобрать число e, удовлетворяющее свойству кривой: Qe = P.
Таким образом, математический бэкдор заключается в том, что правительство США знает значение e.
На практике нам сложно узнать точное значение e, удовлетворяющее константе Q, указанной в качестве константы в NIST SP 800-90 (2006). Поэтому для нашего proof of concept нужно использовать малое значение Q, которое легко атаковать.
3.1 Генерация констант бэкдора
В нашей реализации мы сгенерируем собственные константы кривой P, Q. Это можно сделать, найдя обратное по модулю число и степенное выражение кривой при помощи этой функции:
def ModularInverse(a, m):
# работает, только если m простое (по теореме Эйлера)
return pow(a, m-2, m)
def GenerateBackdoorConstants():
P = P256.G # присваиваем P значение основания кривой
d = randint(2, P256.q) # выбираем случайное число в поле
e = ModularInverse(d, P256.q) # находим значение, обратное числу в поле
Q = e * P # Это возведение в степень P256
return P, Q, dВнутри нашей основной функции мы можем выполнить этот код для генерации случайных чисел на основе наших констант:
seed = 0x1fc95c3714652fe2
P,Q,d = GenerateBackdoorConstants()
print("Generated these constants ", P, Q, d)
dualec = DualEC(seed, P, Q)
rngBits0 = dualec.GenerateBits()
rngBits1 = dualec.GenerateBits()
observed = (rngBits0 << (2 * 8)) | (rngBits1 >> (28 * 8))
print('Observed 32 bytes:\n{:x}'.format(observed))3.2 Применение бэкдора
В предыдущем разделе мы сгенерировали достаточно случайную последовательность. Наш математический бэкдор позволяет нам спрогнозировать следующее число, которое сгенерирует Dual EC RNG. Для этого нам нужно написать вспомогательные функции:
-
p256_mod_sqrt: функцию для нахождения квадратного корня по модулю точки в P256.def p256_mod_sqrt(c): # работает только для поля P256 p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff t1 = pow(c, 2, p) t1 = (t1 * c) % p t2 = pow(t1, 2**2, p) t2 = (t2 * t1) % p t3 = pow(t2, 2**4, p) t3 = (t3 * t2) % p t4 = pow(t3, 2**8, p) t4 = (t4 * t3) % p r = pow(t4, 2**16, p) r = (r * t4) % p r = pow(r, 2**32, p) r = (r * c) % p r = pow(r, 2**96, p) r = (r * c) % p return pow(r, 2**94, p) -
FindPointOnCurve: функцию для нахождения точки на эллиптической кривой.def FindPointOnCurve(x): # Это уравнение: y^2 = x^3-ax+b y2 = (x * x * x) - (3 * x) + P256.b y2 = y2 % P256.p y = p256_mod_sqrt(y2) return y2 == (y * y) % P256.p, y -
GeneratePrediction: функцию, использующую бэкдор для прогнозирования следующего множества битов, которые будут сгенерированы нашим RNG.def GeneratePrediction(observed, Q, d): checkbits = observed & 0xffff for high_bits in range(2**16): guess = (high_bits << (8 * 30)) | (observed >> (8 * 2)) on_curve, y = FindPointOnCurve(guess) if on_curve: # используем бэкдор для угадывания следующих 30 байт # point = Point(p256.curve, guess, y) point = Point(guess, y, curve=P256) s = (d * point).x r = (s * Q).x & (2**(8 * 30) - 1) # сверяем первые 2 байта с наблюдаемыми байтами if checkbits == (r >> (8 * 28)): # если есть совпадение, то мы знаем следующие 28 бит return r & (2**(8 * 28) - 1) return 0
Изменим нашу основную функцию и запустим бэкдор:
На моём компьютере код выполняется 2 минуты. В конце мы видим, что можем спрогнозировать за эти 2 минуты 28 байт данных RNG.
Полный код приведён в gist.
Ссылки
Green, Matthew. (2009). The Many Flaws of Dual_EC_DRBG. Ссылка.
Barker, E., & Kelsey, J. (2006). Recommendation for Random Number Generation Using Deterministic Random Bit Generators. NIST. DOI.
Shumow, D., & Ferguson, N. (2007). On the Possibility of a Back Door in the NIST SP800-90 Dual EC PRNG. Ссылка.
Dfranke. (2009). How I Hacked Hacker News. Ссылка.
Goodin, Dan. (2013). Google confirms critical Android crypto flaw used in $5,700 Bitcoin heist. ArsTechnica. Ссылка.
Schneier, Bruce. (2007). The Strange Story of Dual_EC_DRBG. Ссылка.
Комментарии (26)
adante
20.06.2025 09:10Я что-то не очень понял, это самое Q должно было удовлетворять каким-то внешним условиям?
Если нет, то кто мешает задать новое Q = Q*2+1 и продолжать использовать алгоритм?
eimrine
20.06.2025 09:10Значение Q представляет собой тип данных - массив случайных бит, точнее как доказала статья "случайных" бит. Такие значения в современной криптографии обязаны удовлетворять условиям природности происхождения для того чтобы было понятно что массив не скомпрометирован. Разработчик криптоалгоритма может в процессе обычного рабочего дня отыскать такие значения Q при которых эффективная энтропия (противодействующая брутфорсингам) сильно уменьшается - но только для того нападающего кто заведомо готов именно к этому Q.
Часто в криптографических алгоритмах нужно столько-то бит энтропии. Пример - константа k в алгоритме sha256, там были взяты первые биты от квадратных корней от первых 64-х простых числа. Я не знаю насколько эти значения соответствуют параметру случайности, но я точно уверен что константа k не подобрана с целью уменьшить эффективную энтропию, последовательные простые числа и квадратные корни это в криптографии по-своему модно.
Если нет, то кто мешает задать новое Q = Q*2+1 и продолжать использовать алгоритм?
Это будет или Васян- реализация, или в лучшем случае другой стандарт то есть другой алгоритм с другими характеристиками вывода, ответсвенность за который понесут другие криптографы.
d2d8
20.06.2025 09:10Как знать. Возможно, выбирая это самое k перебрали "красивые" варианты источника битов и взяли наиболее или достаточно уязвимый.
eimrine
20.06.2025 09:10Вы издеваетесь? Пользователю криптоалгоритма нужно доказательство, что магические числа в коде не были полученны путём долгого и тщательного подбора. Красивых вариантов вы и 200 не назовёте, а что такое 200 хэшей/секунду для подбора чего-нибудь что позволит затроянить весь Интернет?
Вдумайтесь какие сущности использованны для получения этих битов: простые числа, натуральные числа начиная аж с первого, корень самой популярной степени, и снова натуральные числа начиная аж с первого.
Мне и 2 варианта предложить сложно: например если заменить корень на квадрат то сильно пострадает случайность, но допустим ещё можно использовать битовые операции, например XOR тоже популярный. Пусть будет: для первых M чисел Фибоначчи (не видел их использования в криптографии но ОК) возводим каждое из них в квадрат и ксорим N первых бит результата с N последних. Ещё варианты красивых последовательностей?
BugM
20.06.2025 09:10Хорошие криптоалгоритмы публикуют документы о каждом числе. Как и почему оно такое. Любая магическая константа должна приводить к тому что этот криптоаглоритм бракуется и не используется.
Увы, к этому пришли не так давно и легаси еще много. Тут тот случай когда надо пинать свои системы и мигрировать на более правильные и верно доказанные алгоритмы. Это делает мир лучше.
Я лично включил tls1.3 на всем доступном мне продакшене. Карма улучшилась, волосы стали более шелковистоми.
VADemon
20.06.2025 09:10Зачем использовать предложенный алгоритм, если уже в одном его месте нашли нестыковку?
Хотя взвешенный ответ наверняка находится в работах криптографов по этому алгоритму. Тем не менее, это был действительно один из кандидатов на конкурсе.
dartraiden
20.06.2025 09:10Например, в случае с российской криптографией, если вы хотите, чтобы у вас всё было сертифицировано и получены нужные бумажки, вы обязаны использовать одобренные значения, а не какие вам захотелось. При этом, эти одобренные значения заявлены, как сгенерированные случайным образом, а на самом деле, таковыми не являются.
SerjV
20.06.2025 09:10Более того, если вы хотите в России/для России делать именно средство криптографической защиты информации - то вам понадобится лицензия (иначе будет незаконное предпринимательство).
Nurked
20.06.2025 09:10Господи, Хабр, ты ли это? Статья о программировании. Интересная. Жесть. Чего только не напишуть.
@PatientZero, спасибо.
vened
20.06.2025 09:10Двойные эллиптические кривые
Всё ж, не "двойные эллиптические кривые" - а "удвоенный/двойной генератор (RNG) на эллиптической кривой". Кривая там одна, точек-генераторов - используется две.
Поэтому для нашего proof of concept нужно использовать малое значение Q, которое легко атаковать
Тут, видимо, какая-то опечатка. Что такое "малое значение", применительно к точке кривой? Непонятно, как сравнивать точки (это большая проблема). В упомянутом бэкдоре, если задана точка P, то можно использовать всякую другую точку Q кривой, если вычислить подходящий под P скаляр. Что, собственно, и делается дальше. Другими словами: так как дальше параметры с бэкдором задаются прямо, то никакое требование "малости" тут не нужно.
Вообще, математический смысл данной атаки в том, что владельцу ключа от бэкдора известно соотношение между точками P и Q. То есть, известно такое δ, что δ*P = Q. Это, фактически, шаг протокола Диффи-Хеллмана на эллиптической кривой: P - генератор, δ - секретный ключ, Q - открытый. Зная Q и P вычислительно сложно найти δ (в чистом виде задача "дискретного логарифмирования"). В этом и смысл - для успешной атаки нужно знать секретный ключ, этим ключом "заперт" бэкдор, поэтому не каждая сторона может им воспользоваться. Зная связь между P и Q - можно по выдаче генератора определить его внутреннее состояние (s), перебрав совсем небольшое количество значений.
shanker
20.06.2025 09:10Жаль, что подобные статьи не пользуются по пулярностью в профильных каналах в сфере блокчейна. Там основные тезисы: если бы были уязвимости, блокчейн бы умер, а взломщики бы обогатились. Тем более есть всякие багбаунти программы с большой выплатой. Из этого (по их мнению) следует, что блокчейны безопасны. Тот простой нюанс, что внедрение таких бекдоров в криптографии нужно не для того, чтоб украсть деньги у пользователей и подорвать доверие в блокчейну, а чтобы контролировать финансовые потоки (США вряд ли отказались от этой идеи со времён утечки секретных международных торговых соглашений TISA) им в голову не приходит. Игнорируют они и чудное везение у биткоина (сильно увеличившее его капитализацию) там, где у других были бы очень большие проблемы - надовящее на мысли о помощи сильных мира сего.
Miaskovskij
20.06.2025 09:10Кстати о биткойне- там есть несколько вариантов раскрытия приватного ключа
Если 2 раза использовать одно и тоже случайное число k
Если найдутся 2 пары транзакций с разными приватными ключами,но повторяющимися числами k
Если известна разница между числами k
Если известно отношение между числами k
Во всех этих случаях раскрытие приватного ключа кошелька довольно простая задача
dersoverflow
Если в шифре нет дупла,
он никогда не станет Государственным Стандартом.
Daddy_Cool
Хм. Одно дело математика, другое - конкретная реализация.
Вот статья про отечественные стандарты.
https://habr.com/ru/articles/530816/
Я думаю найти в них математическую дырку если она есть - вопрос технический. Но её может и не быть, а бэкдор для тех кому нужно делается в каждом конкретном программном продукте.
BugM
Дырка в математике на порядки ценнее. Реализаций много, пишутся они в опенсорсе. Иногда как часть других больших библиотек или проектов. Какая реализация станет популярной заранее неизвестно.
randomsimplenumber
Конечно. В мире много специалистов по криптографии. А если этот американский бекдор существует, и его обнаружат китайцы?
dartraiden
В отечественном алгоритме потенциальную дырку уже нашли, показав, что создатели алгоритма по какой-то причине лгут, утверждая, что в важнейшем элементе алгоритма используются случайно сгенерированные данные.
Про ГОСТовский шифр Кузнечик, его SBox и потерянные сиды
Очередные странности в алгоритмах ГОСТ Кузнечик и Стрибог
Напрашивается прямая аналогия с Dual EC DRBG, где тоже использовалась, вроде бы, случайная константа, а оказалось, что она специально подобрана.