1.0 Введение

В 2006 году АНБ скрыла в криптографическом стандарте Dual EC DRBG математический бэкдор. Агентство отрицало его наличие восемь лет. Затем утечки Сноудена подтвердили его существование.

Двойные эллиптические кривые (Dual Elliptic Curve) используются как безопасные генераторы случайных чисел (RNG). Математический бэкдор позволял правительству США расшифровывать SSL-трафик Интернета (Green 2013)¹.

Эта статья будет технически глубоким исследованием для программистов. Мы реализуем и исходную правительственную научную статью (SP 800-90 2006)², и бэкдор, обнаруженный исследователями Microsoft (Shumow & Ferguson 2007)³.

На моём домашнем компьютере для взлома 28 байт (не бит) при помощи этого бэкдора требуется 2 минуты. Представьте, какой объём Интернет-трафика правительство США могло расшифровывать при помощи суперкомпьютеров Министерства обороны.

1.1 Почему важны атаки на RNG

Математический бэкдор Dual EC позволил правительству США прослушивать Интернет-трафик. Вот ещё несколько примеров интересных атак, использующих небезопасные генераторы случайных чисел (RNG):

1. В 2009 году благодаря генерации куки неслучайным RNG были похищены аккаунты пользователей Hacker News. (Dfranke 2009)⁴

2. В 2013 году изъяны RNG в Android были популярным вектором атак на биткойн-кошельки. (Goodin 2013)⁵

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 довольно проста:

1. Умножаем наше порождающее значение (seed) на P.

2. Берём координату X результата и принимаем её в качестве нового seed.

3. Умножаем новое внутреннее состояние на Q и берём координату результата X.

4. Возвращаем усечённый результат 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)⁶.

Мы знаем, что P — это генератор кривой. НО... что насчёт Q?

Shumow & Ferguson (2007) выяснили, что можно легко подобрать число e, удовлетворяющее свойству кривой: Q^e = 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. Для этого нам нужно написать вспомогательные функции:

1. 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)

2. 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

3. 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.

Ссылки

1. Green, Matthew. (2009). The Many Flaws of Dual_EC_DRBG. Ссылка.

2. Barker, E., & Kelsey, J. (2006). Recommendation for Random Number Generation Using Deterministic Random Bit Generators. NIST. DOI.

3. Shumow, D., & Ferguson, N. (2007). On the Possibility of a Back Door in the NIST SP800-90 Dual EC PRNG. Ссылка.

4. Dfranke. (2009). How I Hacked Hacker News. Ссылка.

5. Goodin, Dan. (2013). Google confirms critical Android crypto flaw used in $5,700 Bitcoin heist. ArsTechnica. Ссылка.

6. Schneier, Bruce. (2007). The Strange Story of Dual_EC_DRBG. Ссылка.